6

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.

Improve this question
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, 2021 at 0:23
  • Maybe ... "so why did somebody come up with bison, instead of simply using yacc? Turns out that "there was a reason."
    – Mike Robinson
    Apr 28, 2021 at 14:32
  • 2
    @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, 2021 at 15:51

2 Answers 2

Reset to default
15

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!))

Improve this answer
3
  • The Cappers 2014 thesis is a wonderful ressource, picture book didactics, thank you for linking it!
    – Susanne Oberhauser
    Feb 28, 2022 at 9:16
  • A year later, I printed the thesis you linked (thanks!) started to read it and got frustrated. It's still quite difficult to understand what's going on. Of course, I'm still not able to code anything. I wonder if somebody with enough knowledge can create a minimal project showing the basics.
    – SuperJMN
    Jun 1, 2022 at 14:50
  • 1
    @SuperJMN here is my attempt so far, which seems to work. I still have to implement the grammar compilation, and it is not a combinator as you require. Perhaps it may be of help to you as a starting point.
    – Rahul Gopinath
    Jul 1, 2022 at 13:16
5

Since I don't have enough reputation to comment I am dropping this as an answer.

Adrian Johnstone (the co-author of the GLL parsing paper) has an implementation of the GLL parser generator in his tool called ART that he uses to teach an undergraduate course. Here's a link to his departmental page that has source and jar of his tool. It has a lot more features than just parsing though. I haven't looked at the source but he did tell us that this uses GLL parsing.

I hope this helps :)

Improve this answer

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.