使用解析器组合器解析具有函数应用程序的表达式语法（左递归）

Question

作为真实语言解析器的简化子问题，我正在尝试实现解析器以查看与标准命令式语言类似的虚构语言表达式（如Python，JavaScript等）。其语法的特点如下构建体：

• 整数
• 标识符（[a-zA-Z]+）
• 与+和*和括号算术表达式
与 .（例如 foo.bar.buz）
• 元组
• 结构的接入（例如(1, foo, bar.buz)）（为了消除歧义，一元组被写为(x,)）
• 功能的应用程序（例如foo(1, bar, buz())）
• 功能是一流的，使他们也可以从其它功能直接返回和应用（如foo()()是合法的，因为foo()可能会返回一个函数）

所以一个相当复杂的程序在这种语言是

(1+2*3, f(4,5,6)(bar) + qux.quux()().quuux) 

关联性应该是

((1+(2*3)), (((f(4,5,6))(bar)) + ((((qux.quux)())()).quuux))) 

我目前使用非常好的uu-parsinglib一个应用解析器组合库。

的第一个问题是明显的是，直觉的表达式文法（expr -> identifier | number | expr * expr | expr + expr | (expr)是左递归的。但是，我可以使用的pChainl组合子（见parseExpr在下面的示例）解决这个问题。

剩下的问题（因此这个问题）是功能应用与从其他功能（f()()）返回的函数。 combinators以及我猜）

请参阅下面的我的当前版本的程序。它运作良好，但功能的应用程序仅在标识，努力消除左递归：

{-# LANGUAGE FlexibleContexts #-} 
{-# LANGUAGE RankNTypes #-} 

module TestExprGrammar 
    (
    ) where 

import Data.Foldable (asum) 
import Data.List (intercalate) 
import Text.ParserCombinators.UU 
import Text.ParserCombinators.UU.Utils 
import Text.ParserCombinators.UU.BasicInstances 

data Node = 
    NumberLiteral Integer 
    | Identifier String 
    | Tuple [Node] 
    | MemberAccess Node Node 
    | FunctionCall Node [Node] 
    | BinaryOperation String Node Node 

parseFunctionCall :: Parser Node 
parseFunctionCall = 
    FunctionCall <$> 
     parseIdentifier {- `parseExpr' would be correct but left-recursive -} 
     <*> parseParenthesisedNodeList 0 

operators :: [[(Char, Node -> Node -> Node)]] 
operators = [ [('+', BinaryOperation "+")] 
      , [('*' , BinaryOperation "*")] 
      , [('.', MemberAccess)] 
      ] 

samePrio :: [(Char, Node -> Node -> Node)] -> Parser (Node -> Node -> Node) 
samePrio ops = asum [op <$ pSym c <* pSpaces | (c, op) <- ops] 

parseExpr :: Parser Node 
parseExpr = 
    foldr pChainl 
      (parseIdentifier 
      <|> parseNumber 
      <|> parseTuple 
      <|> parseFunctionCall 
      <|> pParens parseExpr 
      ) 
      (map samePrio operators) 

parseNodeList :: Int -> Parser [Node] 
parseNodeList n = 
    case n of 
     _ | n < 0 -> parseNodeList 0 
     0 -> pListSep (pSymbol ",") parseExpr 
     n -> (:) <$> 
      parseExpr 
      <* pSymbol "," 
      <*> parseNodeList (n-1) 

parseParenthesisedNodeList :: Int -> Parser [Node] 
parseParenthesisedNodeList n = pParens (parseNodeList n) 

parseIdentifier :: Parser Node 
parseIdentifier = Identifier <$> pSome pLetter <* pSpaces 

parseNumber :: Parser Node 
parseNumber = NumberLiteral <$> pNatural 

parseTuple :: Parser Node 
parseTuple = 
    Tuple <$> parseParenthesisedNodeList 1 
    <|> Tuple [] <$ pSymbol "()" 

instance Show Node where 
    show n = 
     let showNodeList ns = intercalate ", " (map show ns) 
      showParenthesisedNodeList ns = "(" ++ showNodeList ns ++ ")" 
     in case n of 
       Identifier i -> i 
       Tuple ns -> showParenthesisedNodeList ns 
       NumberLiteral n -> show n 
       FunctionCall f args -> show f ++ showParenthesisedNodeList args 
       MemberAccess f g -> show f ++ "." ++ show g 
       BinaryOperation op l r -> "(" ++ show l ++ op ++ show r ++ ")" 

Answer 1

在the list-like combinators为uu-parsinglib寻找简单（我更熟悉parsec），我想你可以通过折叠pSome组合子的结果，解决这个问题：

parseFunctionCall :: Parser Node 
parseFunctionCall = 
    foldl' FunctionCall <$> 
     parseIdentifier {- `parseExpr' would be correct but left-recursive -} 
     <*> pSome (parseParenthesisedNodeList 0) 

这也相当于Alternativesome combinator，它确实应用于您提到的其他解析库。

Answer 2

我不知道这个库，但可以告诉你如何删除左递归。标准的右递归表达式文法是

E -> T E' 
E' -> + TE' | eps 
T -> F T' 
T' -> * FT' | eps 
F -> NUMBER | ID | (E) 

要添加函数应用程序，您必须确定其优先级。在大多数语言中，我看到它是最高的。所以你会为功能应用添加另一层作品。

E -> T E' 
E' -> + TE' | eps 
T -> AT' 
T' -> * A T' | eps 
A -> F A' 
A' -> (E) A' | eps 
F -> NUMBER | ID | (E) 

是的，这是比左递归一个毛茸茸的前瞻性语法和更大。这是自顶向下预测分析的价格。如果你想让简单的语法使用自下而上的解析器生成器la yacc。