CODEWITHSUNDEEP
haskellcompiler-constructioncontext-free-grammarlambda-calculusleft-recursion
user1408134
user1408134

Reputation: 17

lambda calculus grammar LLR

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?

Upvotes: 0

Views: 1411

Answers (2)

Boldizs&#225;r N&#233;meth
Boldizs&#225;r N&#233;meth

Reputation: 1847

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

Upvotes: 4

nickie
nickie

Reputation: 5818

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...

Upvotes: 5

Related Questions