4
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.