lambda演算语法LLR

Question

我正在尝试编写一个lambda演算解析器，我定义的语法似乎不在LLR:中

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

我减少左递归：

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

似乎不对，有人能帮忙吗？

Answer 1

什么是"LLR"？你的意思是"LL"、"LR"、"LALR"吗？

语言不在其中，因为它是模棱两可的；在lambda演算中，这种模糊性通常通过假设lambda表达式x.E尽可能向右扩展来解决。例如，x.xx解析为x.(xx)而不是(x.x)x。

通过消除左递归，您似乎在寻找LL语法。然而，你的语法仍然模糊不清（就像你原来的语法一样，见上文）。你需要先解决这个问题。没有更多提示。。。

Answer 2

在parsec:中实现lambda表达式解析器

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"

注意左递归是如何消除的