CODEWITHSUNDEEP
parsingfunctional-programminglambda-calculus
joeA
joeA

Reputation: 281

Is There an LL(k) Grammar for PCF?

We're working on top-down parsing in a compiler design class. Examples are all java-like languages. I decided to try a simple functional language to make it interesting so I went with PCF (see e.g. here). I can't seem to get it into an LL(1) grammar, though. I think the issue is function application (i.e. juxtaposition of two expressions). I'm not getting clear answers on how to determine if it's just my lack of skill or if this is a language for which there is no LL(1) grammar, or LL(k) for that matter. Can someone clarify if I just need to be more clever or if there simply doesn't exist such a grammar?

Basically, my version of PCF is something like the below sketch (upper case are non-terminals, "//" starts comment). I say "something like" because I am not wedded to exactly this and I have written up many variants -- just want a reasonable variant of PCF.

Note that I have tried left-factoring and accounting for precedence with intermediate non-terminals.

Exp -> Const     // integer and boolean literals, normal ops e.g. +
    |  if Exp then Exp else Exp
    |  lambda identifier dot Exp    //lambda (function) abstraction
    |  Exp Exp                      // function application
    |  fix Exp                      // fixpoint operator (recursion)

Upvotes: 1

Views: 177

Answers (1)

comingstorm
comingstorm

Reputation: 26117

The problem is that your grammar is left-recursive, which does not play well with top-down parsers, as described by LL(k).

Specifically, trying to parse an Exp leads to trying to first parse the first part of a function application Exp Exp... which, for a top-down parser, makes an infinite loop.

The likely solution in your case would be to implement an arbitrary-length function application in a right-recursive style:

AppExp -> Exp | Exp AppExp

Exp -> Const | (AppExp) | ...

Note that this construction removes a grammar ambiguity. Unfortunately, it resolves it in the wrong direction for your problem -- and there is no nice way to fix it; a left-associative version:

AppExp  -> Exp | AppExp Exp

will be just as left-recursive as the original.

The (not-so-nice) way to fix this within the scope of a top-down parser is to accept the right-associative grammar, treat AppExp as a list, and reverse it after parsing so that your abstract syntax tree has the associativity you want:

 application expression:    f a b c d
   |
   |  LL(1) parse
   v
 right-associative   --->   left-associative
       @             list              @
      / \          reversal           / \
     f   @                           @   d
        / \                         / \
       a   @                       @   c
          / \                     / \
         b   @                   @   b
            / \                 / \
           c   .               .   a
               |               |
               d               f

Combinator parser libraries like Parsec typically have conveniently pre-packaged features that will do this for you.

In language-theoretic terms, this demonstrates the distinction between the language accepted by a grammar, and a parsing produced by a parser based on that grammar....

Upvotes: 1

Related Questions