# How does this left-associative recursive descent parser work?

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?

• I'd say shift-reduce parsing is the trick. It is not a recursive decent method. That is why you can hand roll a left associative solution. You are very lightly touching on the technique. Your using a loop rather than recursion. (Even though that loop is implemented recursively). That hinting it could be working bottom up rather than top down. Jun 18 at 1:16