使用解析器組合器解析具有函數應用程序的表達式語法（左遞歸）

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。