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?