1

I'm very interested in the topic of parsers, especially in the topic of parser combinators like Superpower. The problem with them is that the grammars that they can work with are a bit limited. For instance, they can't handle left-recursion nor ambiguities.

That's why I got into the tracks of GLL (Generalized LL). The problem is that the literature and documentation about this technique is really dense and hard to understand for anybody that doesn't have a solid formation in the topic.

So, can somebody explain how it works (for dummies like me)? My goal is to make Superpower able to use it in order to work with more complex grammars.

3
  • 2
    GLL doesn't handle more complex grammars, really. Just the same grammars, except more easily expressed. (Because LL grammars with left recursion can be easily transformed into LL grammars without left recursion, and you can choose to resolve the ambiguities yourself the same way, in the grammar. But both those transformations lose some of the simplicity of expression of the original grammar.)
    – davidbak
    Apr 20 at 0:23
  • Maybe ... "so why did somebody come up with bison, instead of simply using yacc? Turns out that "there was a reason." Apr 28 at 14:32
  • @MikeRobinson - I thought the reason for bison instead of yacc was to have a free version of yacc, free in the GNU sense (which later became the GPL sense) at a time when yacc was controlled by AT&T. GLR support for bison came much later.
    – davidbak
    May 12 at 15:51
7

The reason LL grammars can't handle left-recursion or ambiguity is because those are both situations where the grammar has to make a choice based on something that it won't discover until the future. So they get stuck - the parser generator bails out with an error - or, frequently, a fixed choice is made for the grammar by the parser generator at the time the grammar is compiled into a table.

A GLL parser doesn't make any such choices: It takes all alternatives of the choice, building (conceptually) multiple parse trees - keeping the proper state in the grammar for each - and continuing through with the parse on each parse tree every time it reads a token. If, at any new token, one (or more) of those parse trees are invalid (the token can't be accepted by the grammar at that point): they're dropped. All which make it to the end are valid parses!

The trick, of course, is to do it in such a way that it isn't too expensive. A thing called a "Graph-Structured Stack" was invented for this (actually, for the earlier algorithm GLR). So, "proper" implementation should be able to achieve worst-case O(n³) time (size of parsed string). But in actual use, unless you're deliberately trying to confound the algorithm by trying test cases emphasizing left-recursion and ambiguity, you'll do much better - not far off from standard LL, but with relaxed constraints on the grammar. (Because in practice most ambiguities or left-recursion on actual inputs are resolved quickly, thus not many alternative trees are built and those that are don't last long before they're determined to be a dead end.)

(For a similar, easier to understand, problem: See the relationship between NFAs and DFAs when processing a regular expression. And there are plenty of good tutorials/blog posts on the internet explaining that.)

(For NFA vs DFA see the great tutorials by Russ Cox).

(BTW, I just found this recent master's thesis: "Exploring and visualizing GLL parsing (Cappers, 2014)". He claims to show how you can move incrementally from LL to GLL. It might help you. (If it does: report back!))

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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