0
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ I noticed your comment that you were not satisfied with the existing answer. I encourage you to edit your post to state more precisely what exactly your question is. I do not see a precise question. Normally a question ends with a "?". "Anyone ever done that or heard of such a thing?" is rather vague as it is not clear what exactly are the requirements to count as "doing that". "I like to know if this is something that has been discussed" is also vague because "this" is not precisely defined. $\endgroup$
    – D.W.
    Apr 4, 2023 at 0:06
  • $\begingroup$ I don't need to edit my post if the people don't read it. $\endgroup$ Apr 4, 2023 at 13:26
  • $\begingroup$ I don't know what you're getting at. I read your post. It seems a bit much to assume that others haven't read your post. We are a volunteer site, where people volunteer their time to help, and we have strict quality standards and high expectations for the quality of questions, so I encourage you to take the opportunity to improve your question. $\endgroup$
    – D.W.
    Apr 4, 2023 at 16:21
  • $\begingroup$ It is obvious. I was the one bringing up GLR and therein I also say that it isn't about that. The commentator that the non-responsive answer refers to has conceded that same point, hence the initial comment has been deleted. There is really not much to debate around that. $\endgroup$ Apr 4, 2023 at 20:13
  • $\begingroup$ It may be obvious to you, but it's not obvious to me. No one can force you to edit the question, but I think you're more likely to get useful answers if you do. I recommend that you spend some time thinking about what your requirements are, then articulate them clearly in the question. What are the criteria for evaluating proposed answers? We need clear requirements and criteria to vote on answers, and answerers need them to be sure that they won't be wasting their time or yours in writing a proposed answer. $\endgroup$
    – D.W.
    Apr 5, 2023 at 4:05

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ It's not the comment that had the idea, it's my question. But GLR isn`t really the issue, I do that anyway. My issue is that the standard algorithm to create an SLR parse table will not create a straight left-to-right FSA, and that is what I need in order to make the parser faster. $\endgroup$ Mar 31, 2023 at 11:34
  • $\begingroup$ ... So my question is if anyone has described an algorithm to take a grammar and produce a straight FSA from it (conflicts and all)? $\endgroup$ Mar 31, 2023 at 11:43
  • $\begingroup$ When you say FSA, does a PDA count? Because of course you can't represent most CFGs as a DFA/NFA. It's possible, if a little subtle, to mechanically transform an $LR(0)$ automaton into a PDA which is deterministic if the original grammar is $LR(k)$ for some finite $k$. The construction is quite a bit simpler if the PDA is allowed to examine its stack with a DFA instead of just consulting the top symbol. Unfortunately you can't annotate the PDA with reduction actions because PDAs don't have lookahead. $\endgroup$
    – Pseudonym
    Mar 31, 2023 at 15:44
  • $\begingroup$ A push-down-automaton is the usual way to implement LR parsers. What I mean is an FSA, like they are used in regular expression processing, where we always read terminal symbols as the next token, we don't first finish synthesizing a non-terminal symbol on the right to then take the transition on that non-terminal symbol. I want to turn it into an FSA which will generate one or more next states based on only the terminal symbol. $\endgroup$ Mar 31, 2023 at 21:55
  • $\begingroup$ An LR automaton is not the same as a PDA. An LR automaton has two stacks: a semantic stack, which is used to construct the parse three (and reduce actions to perform the actual building on that stack), and an action stack where every visited is pushed onto that stack, and popped during a reduce action. LR automata also have goto transitions which say what to do after a reduction. $\endgroup$
    – Pseudonym
    Apr 1, 2023 at 0:00

Your Answer

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

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