haskell - ラムダ計算文法LLR

Question

ラムダ計算パーサーを作成しようとしていますが、定義した文法は LLR にないようです:

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

左の再帰を減らします:

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

正しくないようです。誰か助けてもらえますか?

Answer 1

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"

左再帰がどのように削除されるかに注意してください