6
$\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$
1
  • $\begingroup$ 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. $\endgroup$
    – clinux
    Jun 18 at 1:16

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.