| HN Mirror

Gotcha. GLR is painful to learn, you have my sympathy there. I feel like a big chunk of that is due to overly complex formalism and nomenclature around it, but it's definitely still tough, especially if you're trying to implement it efficiently. If you're interested in doing so, I recommend making sure you understand each of the following parsing algorithms in order: regexes via NFA, regexes via DFA, unambiguous LR(0) without empty productions and while ignoring time complexity, LR(0) with time complexity optimizations and with empty productions, LR(1), and then finally GLR (to handle ambiguity). The hardest part will probably be the LR(0) stage.

If you get stuck on LR(0), here's the idea: you use a state machine with a stack, and (b) treat nonterminal symbols like any other input tokens. How? Like below. Say you had the rules:

  #1: Add: Add '+' NUMBER;
  #2: Add: NUMBER;

Initially, you could be in the beginning of any of these rules: either in rule #1 offset 0 (before the Add), or in rule #2 offset 0 (before the NUMBER). Push ({(#1, 0), (#2, 0)}, <null>) onto your stack, where the second list is the symbols you've seen so far (nothing so far). Now consume the first token in the input; let's say it was a NUMBER (say, "55"). Go through every possible new location in your stack, and update where it could be now, and push the new candidate locations along with the symbol you just saw, filtering out any locations where you went past the end of the rule. In this case, that means pushing ({(#1, 1), (#2, 1)}, NUMBER). Now, carefully examine your stack. You've seen [<null>, NUMBER] so far (i.e., just [NUMBER]), and you're either in the middle of rule #1, or at the end of rule #2. Well, it can't be #1, because the last symbol you saw was NUMBER, not Add. Therefore it's #2, and you've finished rule #2, which means you've recognized an Add. Therefore, pop all the symbols in the production of #2 from the stack (which leaves the stack empty), then push the output back (i.e. "reduce" it to the Add symbol). This leaves you with a stack that has just one item, ({(#1, 1)}, Add). Since you're no longer at the end of a production, consume the next input symbol, then go repeat this process, reducing as much as you can every time before consuming an input. [1]

Once you understand this intuitively (and if you stare at it long enough, you'll realize the process I just explained resembles that of a regex NFA), then learn how to optimize this by preprocessing the set of possible locations into simple integers instead of entire sets, so you don't have to do O(|rules|) work every iteration. Then move onto LR(1), which is merely about disambiguating the rules using a lookahead. After that, GLR is "just" keeping a DAG instead of a stack (and it reduces to a linked-list version of a stack if there is no ambiguity)... best of luck.

[1] I lied a little here, in that the process starts with reducing, not shifting. Because you might need to reduce (possibly multiple times) before you consume any inputs. But that's easier to explain here after the fact, than when you're initially learning it.