The stack holds two types of objects: tokens and nonterminals. Notice the runs of reduce actions: the first time, it works its way up from 1 to value to elements later, from to array to value and from elements, value to elements finally, from to array to value.

Parsing the input, 3 ], using the shift-reduce approach described above, should look like this: Input It matches a subset of JSON-possibly-nested arrays of numbers. Here is a simple example grammar to try this out. This is not how it works! The stack grows with function calls on shift actions and shrinks with returns on reduce actions. I kept expecting the function calls of recursive ascent to “ascend” somehow. The recursion in “recursive descent” happens when the parser “descends” into a nested rule. That was one thing that confused me early on. A recursive implementation calls a function to shift a token and change states, and returns when it’s time to reduce. It also pushes states onto the stack alongside their corresponding tokens, so it can return to where it was before starting into that rule.Ī table-driven LR implementation is fairly direct-an actual stack, a lookup table from the current state and token to an action. How does the parser know when it’s seen the body of a rule? Intuitively, it defines a state for each position in a grammar rule, tracks a current state based on the tokens it shifts, and triggers a reduce action when it reaches a state for the end of a rule. Unlike recursive descent, which processes the grammar top-down, LR is bottom-up: it reads the complete body of a rule before it decides which rule to use. It works by shifting tokens from the input onto a stack until it recognizes a rule from the grammar, when it reduces those tokens into the thing they represent.

The LR algorithmĪn LR parser is a kind of shift-reduce parser. It should be easy to follow if you’re familiar with a language with sum types and pattern matching. The code in this article is written in Rust. This should build some intution for how LR parsers work and why you might use one. This means writing functions instead of filling out a state table, giving things meaningful names, and avoiding too much jargon. So I decided I would try an experiment: write an LR parser by hand, and see how readable I could make it. They involve an extra build step, their output is often an opaque state table, and it’s hard to tweak their behavior. While LR parser generators have several nice properties-using the grammar directly as the parser’s source code, automatic ambiguity checking and other algorithmic guarantees-they can be a pain.

There is another way-parser generators like Menhir, LALRPOP, or the venerable Bison use the bottom-up LR algorithm. For a long time, I’ve used hand-written recursive descent for its straightforwardness, flexibility, and performance. I’ve been exploring various ways to write parsers. Writing a recursive ascent parser by hand

Hands bottom sum compilation