lambda calculus grammar LLR

Question

I am trying to write a lambda calculus parser, the grammar I defined seems not in LLR:

E ::= x | \x.E | EE | (E)

I reduce the left recursive:

E ::= xE' | \x.EE' | (E)E'
E'::= EE' | <empty>

seems not right, can anyone help with?

Answer 1

What's "LLR"? Do you mean "LL", "LR", "LALR"?

The language is not in any of those, as it is ambiguous; in the lambda calculus, this ambiguity is generally resolved by assuming that a lambda expression \x.E extends to the right as much as possible. For example, \x.xx parses as \x.(xx) and not as (\x.x)x.

By eliminating left recursion, you seem to be looking for an LL grammar. However, your grammar is still ambiguous (as your original grammar was, see above). You'll need to resolve this first. No more hints...

Answer 2

An implementation of a lambda expression parser in parsec:

import Text.Parsec
import Text.Parsec.String

data LambdaExpr = Variable Char
                | Abstraction Char LambdaExpr
                | Application LambdaExpr LambdaExpr
                deriving Show

lambdaExprParser :: Parser LambdaExpr
lambdaExprParser = do char '\\'
                      var <- letter
                      char '.'
                      expr <- lambdaExprParser
                      return $ Abstraction var expr
               <|> do apps <- many1 term
                      return $ foldl1 Application apps

term :: Parser LambdaExpr
term = do var <- letter 
          return $ Variable var 
   <|> do char '('
          expr <- lambdaExprParser      
          char ')'
          return expr

test = parseTest (do expr <- lambdaExprParser; eof; return expr) "\\y.y(\\x.x)y"

Notice how the left recursion is eliminated