Clojure Data Structures and Algorithms Cookbook

Building a simple shift-reduce parser

A shift-reduce parser is a program that is generated from a grammar definition. It is a kind of state machine capable of doing two kinds of actions:

• Either it consumes a token from an input program, adding up a new state in a stack. This is called shifting.
• It recognizes that a rule of grammar has been fully matched, so it pops as many states from the stack as the rule contains and acknowledges that it recognized that particular rule, adding up an entry to the parse tree. This is known as reducing.

Given how these parsers operate, we'd say that they belong to the "bottom-up" parsing family. That is, they operate on input and deduce the parse outcome while traversing it, in contrast to the other way around, which ...