You asked for a brief, step-by-step guide for creating LALR(1) context-free state machines (CFSMs). I have created a draft: Constructing the LALR(1) CFSM
I was shooting for 2 pages or maybe 3, but ended up with 7 ... and that's with no pictures and no worked examples. I am willing to work on this some more to make it better, but I could use some feedback on the current version. Is this clearer than the books you are using? Less clear? Is it too verbose, or too concise? Too formal or too hand-wavy? Can you see how the inductive rules for First and Nullable are the underlying logic for the pseudocode in the books?
There are small discrepancies in the construction from book to book. I think the Dragon Book mixes together the Nullable and First set algorithms, placing an epsilon in the first set to indicate that a terminal symbol is nullable, while Crafting a Compiler treats these as two different analyses (as I do in this guide). There may also be bugs in my description. If you find something confusing, or think you have spotted an error in my instructions, please let me know.
Subscribe to:
Post Comments (Atom)
Typos found so far:
ReplyDeletepage 3: computer terminal symbols =>
compute terminal symbols
As for Nullable => As in Nullable
(or maybe there is better wording)
page 4 (and probably other places):
it's => its
And I need to be more consistent in use of terms "string", "sequence", and "sentence". A "sentence" contains only terminal symbols, and is what a grammar describes. I use alpha, beta, etc to denote "sequences" of symbols that could be terminals or non-terminals. It's better not to use the term "string" at all, since it's not clear whether it would mean a string of characters or a string of symbols.