6

作为真实语言解析器的简化子问题，我正在尝试为虚构语言的表达式实现解析器，该语言看起来类似于标准命令式语言（如 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()()）。同样，语法是左递归的expr -> fun-call | ...; fun-call -> expr ( parameter-list )。有什么想法可以优雅地解决这个问题uu-parsinglib吗？（我猜这个问题应该直接适用于parsec,attoparsec和其他解析器组合器）。

请参阅下面我当前版本的程序。它运行良好，但功能应用程序仅在标识符上工作以删除左递归：

 {-# 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 ++ ")"
4

2 回答 2

4

我不知道这个库，但可以向您展示如何删除左递归。标准的右递归表达式语法是

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。

于 2014-10-05T00:05:44.083 回答
4

简要看一下（我更熟悉）的类似列表的组合器，我认为您可以通过折叠组合器的结果来解决这个问题：uu-parsinglibparsecpSome

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

这也相当于Alternative some组合器，它确实应该适用于您提到的其他解析库。

于 2014-10-05T19:47:54.743 回答