Articles

The compilers article gave you the pipeline: lexing turns text into tokens, parsing turns tokens into a tree, and tree walking turns the tree into behavior. It defined the middle stage in one sentence: “parsing is pattern matching on a token stream.” This article works through that sentence. Parsing decides what a program means before anything runs. The algorithm here - recursive descent - is mechanical: the parser’s code mirrors its grammar line for line. The site’s shunting yard exercise handles precedence with a table and two stacks; recursive descent handles the same problem with function calls, and the tree appears as those calls return. By the end you can read a grammar and write its parser, and you will see why a parser is a direct example of the pattern matching this site drills from the first day.

The grammar is the spec

The grammar determines the parser’s job before the first token arrives. A grammar is a set of rules. Each rule names a syntactic category and the shapes that category may take. For arithmetic, the classic grammar has three rules:

expr    := term  (('+' | '-') term)*
term    := factor (('*' | '/') factor)*
factor  := number | '(' expr ')'

Read expr as “an addition-or-subtraction expression is a term, optionally followed by more terms joined by + or -.” Read term the same way one level down. factor is a leaf: a number or a parenthesized expression that recurses back to the top. These three rules define what a valid expression is and how it groups.

Grouping is the point. Cooper and Torczon’s Engineering a Compiler puts the problem and the fix in two adjacent sentences: a grammar that “treats all the arithmetic operators in the same way, ignoring precedence” is ambiguous - the same string has two parse trees - but “we can use this effect to encode levels of precedence into the grammar.” The three-rule shape above does that: each precedence level gets its own nonterminal. In their words, “Expr forms a level for + and -, Term forms a level for * and /, and Factor forms a level for ( ).” A grammar is not just a description of syntax; it is the syntax, including precedence. The parser follows it.

One function per rule

Recursive descent follows a grammar directly: one function per rule, each function matching the next token against the shapes its rule allows. Grune, van Reeuwijk, Bal, and Jacobs name it in Modern Compiler Design: “recursive descent parsing, because a set of routines descend recursively to construct the parse tree.” In Elixir, the three rules become three functions. The token stream is pattern matched at each step:

defmodule Lexer do
  @ops %{"+" => :plus, "-" => :minus, "*" => :times, "/" => :div,
         "(" => :lparen, ")" => :rparen}

  def lex(string) do
    ~r/\d+|[+\-*\/()]/
    |> Regex.scan(string)
    |> List.flatten()
    |> Enum.map(fn token ->
      case Integer.parse(token) do
        {n, ""} -> {:number, n}
        _ -> {@ops[token], token}
      end
    end)
  end
end

defmodule Parser do
  # expr   := term (('+' | '-') term)*
  # term   := factor (('*' | '/') factor)*
  # factor := number | '(' expr ')'
  def parse(tokens) do
    {ast, []} = parse_expr(tokens)
    ast
  end

  defp parse_expr(tokens) do
    {left, rest} = parse_term(tokens)
    parse_add_sub(rest, left)
  end

  defp parse_add_sub([{op, _} | rest], left) when op in [:plus, :minus] do
    {right, rest} = parse_term(rest)
    parse_add_sub(rest, {op, left, right})
  end

  defp parse_add_sub(rest, left), do: {left, rest}

  defp parse_term(tokens) do
    {left, rest} = parse_factor(tokens)
    parse_mul_div(rest, left)
  end

  defp parse_mul_div([{op, _} | rest], left) when op in [:times, :div] do
    {right, rest} = parse_factor(rest)
    parse_mul_div(rest, {op, left, right})
  end

  defp parse_mul_div(rest, left), do: {left, rest}

  defp parse_factor([{:number, n} | rest]), do: {n, rest}

  defp parse_factor([{:lparen, _} | rest]) do
    {expr, [{:rparen, _} | rest]} = parse_expr(rest)
    {expr, rest}
  end
end

IO.inspect(Parser.parse(Lexer.lex("3 + 4 * 2")), label: "3 + 4 * 2")
IO.inspect(Parser.parse(Lexer.lex("(3 + 4) * 2")), label: "(3 + 4) * 2")
IO.inspect(Parser.parse(Lexer.lex("10 - 4 / 2")), label: "10 - 4 / 2")

The three grammar rules become the six parser clauses, in order: parse_expr calls parse_term, which calls parse_factor. The parenthesis clause of parse_factor calls parse_expr again. That recursion lets parentheses contain a full expression. Grune et al. call the resemblance “astonishingly direct,” and say “this similarity is one of the great attractions of recursive descent parsing.” You do not have to design a recursive descent parser; transcribe the grammar.

Run it. The tree has the grammar’s structure:

3 + 4 * 2     -> {:plus, 3, {:times, 4, 2}}
(3 + 4) * 2   -> {:times, {:plus, 3, 4}, 2}
10 - 4 / 2    -> {:minus, 10, {:div, 4, 2}}

Precedence is call order

Look at 3 + 4 * 2. The result is {:plus, 3, {:times, 4, 2}}: multiplication is a child of addition, one level deeper in the tree. No precedence table was consulted. No stack was shuffled. The call order supplies the precedence. parse_expr must finish parse_term before it examines +, and parse_term consumes 4 * 2 before returning. Since * is handled one level deeper than +, it binds tighter. Expr above Term above Factor is the grammar’s precedence, and the call stack makes that layering concrete.

This is the same problem the shunting yard exercise solves with a precedence table and two stacks. Put the approaches side by side. Shunting yard is the table driven answer: one loop and one table of {"*" => 2, "+" => 1}, popping operators whose precedence beats the incoming one. Recursive descent is the grammar driven answer: no table, because the grammar already says which operators outrank which, and the parser follows it. Both produce the same answer. Recursive descent produces a tree, not a flat RPN string, and the next stage of the pipeline can walk that tree.

Pattern matching on a token stream

The connection from the compilers article is visible in the code. Each parser clause is a pattern: [{op, _} | rest] when op in [:plus, :minus] matches the head of the token list, [{:number, n} | rest] matches a number, and [{:lparen, _} | rest] matches a left parenthesis. The token stream is the list. The grammar rule is the pattern. The function clause is the match. This is not a metaphor. It is the pattern matching article’s subject, = matching structure, applied to a list that contains tokens. Recursion grows the tree: a rule that sees a sub-expression calls back into the parser, and each call returns a subtree for the caller to wrap in a larger one.

The resulting tree has the shape the encoding article teaches you to read: a tuple tree, {:op, left, right}, where each node is an operator with two operands. Grune et al. draw one distinction worth keeping. A parse tree follows the grammar, with one node per symbol. An abstract syntax tree (AST) keeps only what the compiler needs. Parentheses, for example, have shaped the tree and leave no node behind. The tuples above are the AST: the parentheses in (3 + 4) * 2 are invisible in {:times, {:plus, 3, 4}, 2}. Their only trace is that + became a child of * rather than the other way around.

The parser’s honest limits

Recursive descent is the simplest way to get a parser, not the strongest. Modern Compiler Design states the main limit directly: “Recursive descent parsers cannot handle left-recursive grammars, which is a serious disadvantage.” A left-recursive rule begins by calling itself, like expr := expr + term. The parser loops forever because parse_expr calls parse_expr before consuming any token. The three-rule grammar above is deliberately written right-recursive instead. It loops with the parse_add_sub helper rather than recursing on the left; that is the standard fix. The method does not backtrack either. Grune et al. warn that “the first alternative that can produce a possible tree is assumed to be the correct alternative; needless to say, this assumption gets us into trouble occasionally.” A rule with two alternatives commits to the first one that looks viable. If the grammar needs the parser to reconsider - the classic dangling-else in if-statements - reshape it into a form the parser can commit to. Grammar design and parser design are the same task.

Those limits are the price of the method’s main virtue: you can read it. A recursive descent parser is the grammar with its punctuation changed into Elixir. That legibility is worth more in practice than the parsing power of the table-driven methods that superseded it for production compilers. The compilers article made the case that compilers are tree-munching programs. This article is the first bite: the front end that grows the tree.

Where to go next

Shunting Yard - the table-driven sibling: the same precedence problem, solved with a precedence table and two stacks instead of recursive calls.
Evaluate RPN - the stage after this one: walk the tree (or its flattened RPN form) and compute the value. Parsing builds the tree; evaluation walks it.
Pattern matching - the reflex this article’s parser is made of; every parser clause is a pattern.
The encoding
- the AST as a tuple tree, and the encodings that store it compactly.
Compilers for the practicing programmer
- the series this article belongs to: the full pipeline, and why tree munching fits a functional language.
Introducing lambda calculus - the next stage’s purest form; beta-reduction is the evaluator that walks the tree, which is the subject of the next article in this series.