Compilers - Am I writing one?

Jacob Fugal lukfugl at
Sun Jun 29 22:39:47 MDT 2008

Ditto the stuff Levi said. In addition:

On Sun, Jun 29, 2008 at 8:51 PM, Daniel C. <dcrookston at> wrote:
>> You might want to write a recursive descent parser.
> My primary goal is to make Raskal as simple as possible, so using a
> tool that requires obfuscation in the language isn't really where I
> want to go.

To clarify on Levi's comment, eliminating left recursion and the other
optimizations you need to make recursive descent parsing work nicely
involves tweaking the *grammar*, not the *language*. The language is
the set of strings that are valid under the grammar. The tweaks
involved to make your grammar more RD-friendly should not change the
language at all, just the manner of defining the language. And in my
opinion, it's really not *that* bad. But it does require a more robust
understanding of CFGs (context-free grammars).

My suggestions on the principles to read up on:

Lexing -- regexes and DFAs. But when it comes to DFAs, most of what
you need to know is "it's a state machine, where the stream of
characters is the stream of events". Most simple ad-hoc lexers don't
end up being a straight DFA or regex implementation, but do build off
the fact that you make decisions based off one or two characters of
lookahead in the input stream.

Parsing -- context-free grammars. It's really hard to do good parsing,
in my opinion, without a solid grasp of CFGs. On the flip side, once
you have that foundation, that actual task of parsing isn't really
that hard. Pay particular attention to BNF, EBNF and recursive descent
techniques. As I mentioned above, I don't think the constraints on the
grammar to make it RD-friendly are really that bad, especially if
you've got your grammar specified as an EBNF.

It sounds like you've already got the gist of the syntax tree that
will be the result of parsing, and once you have that, code generation
is (mostly) as easy as walking the tree.

Jacob Fugal

More information about the PLUG mailing list