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 = stringdatatype ast =  VAR of string| APP of ast * astfun 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?
How does this left-associative recursive descent parser work?
lambda calculus;parsers;left recursion