How does this left-associative recursive descent parser work?

Question

For personal enlightenment, I'm trying to write a recursive descent parser for lambda calculus without abstraction, i.e., just identifiers and function application.

The BNF grammar that describes the language could be this, where <var> is a terminal standing for identifiers:

<exp> ::= <exp> <var>
        | <var>

But this grammar can't be parsed by a recursive descent parser because it is left-recursive. So we need to rewrite it to something like this:

<exp> ::= <var> <app>
<app> ::= <var> <app> | ""

We can now write a recursive descent parser, in Standard ML here, that parallels the grammar:

type token = string

datatype ast =
  VAR of string
| APP of ast * ast

fun exp tokens =
  case tokens of
    [] => raise Fail "missing expression"
  | var :: tokens =>
    case app tokens of
      NONE => SOME (VAR var, tokens)
    | SOME (absyn, tokens) => SOME (APP (VAR var, absyn), tokens)

and app tokens =
  case tokens of
    [] => NONE
  | var :: tokens =>
    case app tokens of
      NONE => SOME (VAR var, tokens)
    | SOME (absyn, tokens) => SOME (APP (VAR var, absyn), tokens)

However, while the new grammar doesn't exhibit left-recursion, the parser that implements it will produce right-associative function application nodes. This is a fairly known limitation of recursive descent parsers.

- exp ["a", "b", "c"];
val it = SOME (APP (VAR "a",APP (VAR "b",VAR "c")),[])

Here's what puzzles me, though. I can write a function that can parse a list of tokens into an AST with the correct left-associative function application nodes, but I'm not sure why I can do that. Is this parser still a recursive descent parser? What's the grammar that it implements? Does it work because it uses a 2-token lookahead? I'm unsure.

fun exp tokens =
  let
    fun loop tokens ast =
      case tokens of
        [] => SOME (ast, tokens)
      | name :: rest => loop rest (APP (ast, VAR name))
  in
    case tokens of
      [] => NONE
    | name :: rest => loop rest (VAR name)
  end

- exp ["a", "b", "c"];
val it = SOME (APP (APP (VAR "a",VAR "b"),VAR "c"),[])

Is this a known, formalized, trick for hand-writing recursive descent parsers?

Answer 1

ANTLR handles direct left recursive grammar via a technic they call an oracle. You can find their paper to learn all about it.

Basically the parser remembers if it had just parsed the current non-terminal being parsed. If it hasn't, then the left recursive choice gets ignored. Otherwise the left recursive branch is visited using the parse that was remember to jump over the left recursive part.

ANTLR however can only handle direct left recursion and not indirect left recursion. So an oracle is no silver bullet.

That said. Left recursive in recursive descent parsing is extremely rare. Most people rewrite their grammars to be right recursive, if they are going to write their own recursive descent parser.

Shift reduce parsers however have no problem with left recursive or right recursion, and no problems with direct or indirect recursion either. They work from bottom up rather than top down. However the learning curve is a lot steeper, but I think it is worth it imo.

Your hand rolled code down the bottom of your post is using a loop and parsing from bottom up. It is very lightly touching on the shift-reduce parsing technique. I'd google or watch YouTube videos on implementing an LR(1) parser (its shift-reduce based). It will be very enlightening.

Answer 2

You can’t use recursive descent for two reasons: You don’t know which rule to apply until you have parsed the first var. And a recursive call must not parse the last var, or the caller will fail. Fortunately you can handle this easily in this case:

var = parse_var()
exp = make_exp(rule2, var)
while input starts with var
    var = parse_var()
    exp = make_exp(rule1, exp, var)
end while
return exp