使用解析器组合器解析具有函数应用程序的表达式语法(左递归)
作为真实语言解析器的简化子问题,我正在尝试实现解析器以查看与标准命令式语言类似的虚构语言表达式(如Python,JavaScript等)。其语法的特点如下构建体:使用解析器组合器解析具有函数应用程序的表达式语法(左递归)
- 整数
- 标识符(
[a-zA-Z]+
) - 与
+
和*
和括号算术表达式 与
- 元组
- 结构的接入(例如
(1, foo, bar.buz)
)(为了消除歧义,一元组被写为(x,)
) - 功能的应用程序(例如
foo(1, bar, buz())
) - 功能是一流的,使他们也可以从其它功能直接返回和应用(如
foo()()
是合法的,因为foo()
可能会返回一个函数)
.
(例如
foo.bar.buz
)
所以一个相当复杂的程序在这种语言是
(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 ++ ")"
在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)
这也相当于Alternative
some
combinator,它确实应用于您提到的其他解析库。
我不知道这个库,但可以告诉你如何删除左递归。标准的右递归表达式文法是
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。
谢谢@Gene!我其实并没有在我的问题中提到这一点,但我试图解决左边的保理问题,因为它不是很优雅,是很多工作,并且使得AST更难。因此,我非常高兴能够解决运营商问题(而不是功能应用)的'pChainl'组合器。但是,也许实际上并没有一个简单而优雅的解决方案,我必须将整个语法的因素留下: - \。我可能也会切换到像yacc那样的'happy'解析器生成器。 – 2014-10-05 00:46:36
哦,是的,的确,这非常优雅,简单,并且工作正常! – 2014-10-05 20:49:26