0
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Are you trying to write a bottom-up parser? You seem to be saying that you already wrote a recursive descent parser, or am I mistaken about what you mean by "Parsing is done with recursive query."? $\endgroup$
    – rici
    Dec 31, 2022 at 17:30
  • $\begingroup$ @rici bottom up of course, hence I am talking about a finite state automaton, table. And it's not that I am "trying", it is I have the parser. The problem is to maintain the state transition table as I add to the grammar. $\endgroup$ Jan 1 at 4:13
  • 1
    $\begingroup$ I'm not sure if I can really offer to explain LR(0) table construction more simply than the standard textbooks, and I'm a bit daunted by figuring out where to start the explanation. If I assume you know absolutely nothing about automata theory and start at the beginning, the result will be pretty long and quite possibly boring, but if I don't start at the beginning I risk not explaining some essential piece of background. But I can offer a reasonable procedure for extracting the state table from Bison's XML output using an example short Python script. $\endgroup$
    – rici
    Jan 2 at 18:24
  • $\begingroup$ I have spent all day yesterday to dig into it. There were YouTube videos and a bunch of texts of course. I found this here cs.ecu.edu/karl/5220/spr16/Notes/Bottom-up/lr0machine.html most helpful. I am building this now and hopefully by tonight it's done. I come back to answer my own question in a new way, trying to explain to my naive self of 2 days ago what's really going on in a nutshell. $\endgroup$ Jan 3 at 5:34

1 Answer 1

0
$\begingroup$

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:

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.