haskell - λ演算文法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"

注意左递归是如何被消除的