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?