Simple description of the LR(0) table generator algorithm?

Question

I have just implemented a parser on the relational database. Parsing is done with recursive query. Note: one commenter was misled by the word "recursive" before "query" to think "recusive descent". But no. I am not talking about recursive descent top-down, I am talking about bottom up, LR, simple, no look-ahead, driven by a state-transition table.

I built the tokenizer, manually cobbled together the state event transition and action table, and I have an action function which updates the stack for each thread of parallel parsing.

All is working nicely. The only problem is for me to create the state transition table. My grammar isn't so hard. I don't even have a lot of complex repeated groups.

name        :             famname foobar
name        :             famname suffixes foobar
name        : PREFIX_WORD famname suffixes foobar
famname     : WORD_R
famname     : WORD
suffixes    : WORD
suffixes    : suffixes WORD
foobar      : bar FOO
foobar      : FOO bar
bar         : NUMBER UNIT denominator
bar         : NUMBER UNIT 
denominator :         SL_UNIT
denominator : SL_NUMBER  UNIT
denominator : PER NUMBER UNIT

I am not showing the semantic actions above, but I know how that's done.

For this simple structure I could still do it manually, but if I expand this grammar to about 2 - 10 times as many symbols it would become a nightmare to get right and I would waste a lot of time debugging my manually created state transition table.

I don't even care much about shift/reduce and reduce/reduce conflicts. So I don't even care about look-ahead to disambiguate. All I want is take a BNF structure as the above and transform it into a table of (old_state, token_type, new_state, action).

I am having a hard time to find a description that is intuitive for me. It's not that I couldn't drill through the literature with some extra effort, but I have very little time. I know there is something with item set and closure, but most descriptions I find are for more complicated considerations.

One idea I had was to just expand the structure by resolving all higher symbols to atomic token type sequences. And do it breadth first with detection of cycles. Then I have all the paths through the state transition graph and I could already produce a huge table from that, or I could try to squeeze out common sub-paths from the different paths. I know in a grammar for something like a programming language, trying to expand all possible token type sequences would be crazy. But in my case I could probably do it.

Perhaps there is only a couple of ah ha! moments from my naive idea to something serious?

Answer 1

I think the commenters are gracious for not having down-voted my question. It seemed I was lazy. But I was lazy no more. The last two days I have put my head into this matter and I just finished the implementation and verified it against the textbook example.

Of all the texts and presentations I could find I found these lecture notes the best:

• LR(0) items
• The LR(0) Finite State Machine

What had confused me in the past was all that theoretical talk about "item" and "item set". Also this dot notation seemed weird.

But what helped me was actually doing it all (in SQL) where it is clear that one production on the RHS has a sequence, and so we have a production id and a sequence number to get to exactly one RHS symbol (non-terminal or terminal). So what an "item" really is is one RHS symbol of one production, at least if we terminate the RHS symbols with one (implicit) termination, i.e., even though the rule: E : E "+" T has only 3 RHS symbols, a position 4 is valid and indicates the end of the production.

Then thanks to these lecture notes above for going directly from "item" to "state" and even including the transitions immediately in the picture (and for having a picture in the first place).

So, the approach in a nutshell is this:

To Prepare

1. Add a single trivial start symbol to the grammar if needed, so that if the real start symbol has multiple productions, there will be only one production for the top-level start symbol.
2. Think of the productions as a relation: PROD(P#, LHS, SEQ#, RHS), these tuples are all "items" (for lack of a better word), example
3. For ease of use complete the Production by adding a terminal item to each, this is so that if you ask for the next step by increasing to the next RHS symbol, you can find the final one which just has nil RHS symbol.
4. Now magically the State Transition network emerges simply from the following actions.

Why that initial trivial start symbol is required can be seen with the standard example:

E : T
E : E "+" T
T : F
T : T "*" F
F : n
F : "(" E ")"

If you don't add E' = E then there is not one top level symbol. You could start at E but you can also start at T or at F. You just don't know where to start!

To Begin

1. Create your first state (S0) with that trivial single start symbol production's first RHS (also trivially the original start symbol)
2. Now for that one RHS symbol of the start symbol, add more member items into the state by taking the first RHS symbol (item) of all productions with LHS being that initial RHS symbol of S0
3. Now do the same for all items you have added, and recursively until nothing new is added (this is the transitive closure of LHS -> RHS tuples).

I found it helpful to think of these items as individual PROD(P#,LHS,SEQ#,RHS) tuples. It's not that you need to write out the full LHS : RHS1 RHS2 RHS3 ... line and put a dot somewhere.

To Iterate

1. For each item in your completed state, make a list of unique RHS symbols
2. For each such unique RHS symbols, find all member items in your state that have that unique RHS symbol. (Remember an item is just one position on the RHS of a production, it's not a line of text with a dot somewhere. So there is only one RHS symbol (or nil) in any item, therefore there is no question about the RHS symbols have a dot before them or not.)
3. Now each of these (groups of) member items from your current state for the same unique RHS form a new state.
4. Each new state is defined by the next step in the production PROD(P#,LHS, ++SEQ#, RHS').
5. Regardless if RHS' is something or nil, each group of such production steps coming from one unique RHS identify one state.
6. You might have already seen that state before, check if you find one with the same definition items, if so, use that existing state, if not, make a new state.
7. For all new states, generate the closure by again going to the start RHS symbol of each production for the item that defines the state, and from there recursively for each item you just included (closure)
8. Continue for all such unique RHS symbols, for all previously generated states.
9. Note: the transitions come right out of this procedure, whether the state already existed, or you just created a new one, the transition from the current member item of your current state becomes a next state.
10. There is at most one transition from each member item of a state
11. Multiple member items of a state may have the same new state
12. The RHS of each member items of the state are the event which triggers the transition (at least the terminal symbols are.)

To Conclude:

So at the end of this process of unique RHS, state member for that RHS, next SEQ# of the RHS sequence of the production, merging states that already exist, and then complete the closure again, and recording the new state for each state member item, magically the entire finite state automaton has been defined.

Is this explanation shorter and more concise or intelligible as all he outstanding CS lectures and text books and lecture notes? Probably not. But it is concise enough to promise that the state transition network comes out of this one procedure right from the productions of the grammar.