Compilers - Am I writing one?

Levi Pearson levi at
Sun Jun 29 19:30:03 MDT 2008

"Daniel C." <dcrookston at> writes:
> Someone said that I'm writing a compiler and therefore need to learn
> all about context-free grammars, LALR(1) parsers, deterministic finite
> state automata, and all sorts of other sexy-sounding but ultimately
> painful stuff.  Are they right or did they just want to give me
> headaches?

Yes, you're writing a compiler. :) No, you don't really have to learn
the 'painful' stuff, but I'd recommend it, as it's not *that* painful
and it's very useful to boot.

> I am aware that things like YACC exist but I'm wary of using such
> magic without understanding it first.

There are probably easier tools to use now than YACC, but if you're
writing in C, it may be a good choice.  You *really* don't want to
write something to do what YACC does, though you might want to write a
recursive descent parser.  I'm not a big fan of recursive descent
parsers because it means you've got to eliminate all the
left-recursion in your grammar, and that leads to a bit of obfuscation
in both the grammar and the code.

YACC doesn't really do anything you need to be wary of, though there
are some things you need to understand about how it works in order to
avoid nasty things like shift/reduce conflicts.  If you're comfortable
using regular expression engines, something like YACC is just another
step along the same path.  Both are based on the theory of automata,
which can get rather mind-bending but is really simple at its core.

Using lex and yacc will give you a syntax-directed parser, and you can
use your yacc semantic actions to either build your parse tree or to
output the intermediate data that you're sending to the other.  There
are programs or libraries like lex and yacc for just about every
language, so this is really the best route to go about writing simple

If you have any specific questions about any of it, or want to know of
resources for learning more about any of it, let me know.

> Thanks, and (since no-one else is going to say it) welcome back to me.

Um, welcome back? :)


More information about the PLUG mailing list