Clojure Data Structures and Algorithms Cookbook

Building a recursive descent parser using trampoline

A recursive descent parser, as the name implies, makes heavy use of recursion in order to process some input tokens and be able to tell if they comply with a particular grammar code. For each of the grammar rules, such a parser will have to fire a function that proceeds with the verification of the input according to this very rule.

Let's consider, for the purposes of this recipe, a very simple grammar code: one that allows describing the structure of a symbolic expression that is very broadly speaking a set of elements confined between parentheses:

S = sexp
sexp =  "(" element* ")"
element = term | sexp
term = [a-zA-Z0-9]*'

Our parser recognizes as valid structures those which are symbolic expressions, ...