Parsing algorithms

Question

I have experimented with a grammar that I could turn into a strict left-to-right finite state automaton driven algorithm (bottom up, table driven). The FSA could be complex, that's not a problem. It doesn't need to deal with infinite recursive structures.

I then moved the grammar into BNF, and built a standard SLR parse table. And I found that the SLR parser relies a lot on building non-terminal symbols on the right before it finishes the symbol that it has started on the left. This causes -- in my implementation at least -- a major disadvantage, because if I could just read token for token from left to right, everything would be much, much faster.

I like to know if this is something that has been discussed in the literature and where I would find that discussion. I.e., a certain restricted subset of grammars which can be parsed with a simple FSA token by token from left to right?

Trying to wrap my head around it, let's take the simple expression grammar example:

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

I think I can turn this into a simple FSA if I limited the depth of the recursion on F : ( E ).

S   -[n]-> Sn   : push(token)
Sn  -[+]-> Snp
Sn  -[*]-> Snt
Snt -[n]-> ST   : push(token * pop())
Snp -[n]-> Snpn : push(token)
Snpn-[*]-> Snt  : 
ST  -[*]-> Snt 
...

I can't finish this idea right now, I should, to think this all the way through, but my intuition (and experience with having crafted a grammar before only by creating an FSA table directly, is that it causes a lot of states to be created, that the state carries a memory of a lot of what came before, that there appears to be quite a bit of redundancy in those many states, and that the S-attributes, that compute the value of the expression (or parse tree) will be a lot more to deal with those several cases.

But despite this redundancy doesn't matter as it is just a quick table lookup at every state for every new token and goes strictly left to right, terminal token by terminal token.

You might say, that perhaps I can't deal with shift-reduce, shift-shift and reduce-reduce conflicts, and here I am telling you that I don't care about those, because in my application I want to just follow every possible path, creating multiple parse trees if necessary. I.e., there isn't just one stack, but each instance of a state in the state machine carries its own value stack, so that, when conflicts arise, two or more states are derived, and the FSA continues on both of them with the next token. If there is no transition given the next token for any state, that simply gets abandoned. I guess this is a GLR parser in a way.

But the point is that I want to run it strictly as a finite state automaton.

Anyone ever done that or heard of such a thing?

Answer 1

The comment basically has the right idea: What you want is some kind of LR parsing; GLR is fine.

You see, if a grammar is not $LR(k)$ but you try to build a $LR(k)$ automaton for it anyway, then the automaton is still correct and will still parse it just fine. The catch is that it is nondeterministic. Shift-reduce and reduce-reduce conflicts (there is no such thing as a shift-shift conflict in $LR$ parsing) are choice points that you need to handle somehow, such as by backtracking.

$GLR$ parsing embraces the nondeterminism. The automaton, and I can't stress this enough, is the same as the $LR$ automaton. The only difference is in how it's executed.