我想解析算术表达式。
这是我当前的解析器:
data AExpr
= ExprAsAExpr Expr
| IntConst Integer
| Neg AExpr
| ABinary ABinOp AExpr AExpr
deriving (Show, Eq)
aExpr :: Parser AExpr
aExpr = makeExprParser aTerm aOperators
aTerm :: Parser AExpr
aTerm
= parens aExpr
<|> IntConst <$> integerParser
aOperators :: [[Operator Parser AExpr]]
aOperators =
[ [Prefix (Neg <$ symbol "-") ]
, [ InfixL (ABinary Multiply <$ symbol "*")
, InfixL (ABinary Divide <$ symbol "/") ]
, [ InfixL (ABinary Add <$ symbol "+")
, InfixL (ABinary Subtract <$ symbol "-") ]
]
使用这个我可以正确解析这个:
1 + 2
像这样生成 AST。
(ABinary Add (IntConst 1) (IntConst 2))
我可以解析的另一件事是通用表达式。这些可以是变量、方法调用、三元组等。
例如
标识符:
varName
这会生成:
(Identifier (Name "varName"))
方法调用:
methodCall()
这会生成:
(MethodCall (Name "methodCall") (BlockExpr []))
这是一个解析通用表达式的示例。
expressionParser :: Parser Expr
expressionParser
= methodCallParser
<|> identifierParser
这工作正常,但我还想解析其中的算术表达式。
expressionParser :: Parser Expr
expressionParser
= newClassInstanceParser
<|> methodCallParser
<|> AExprAsExpr <$> aExpr
<|> identifierParser
这意味着使用表达式解析器
我现在可以解析所有不同的表达式,包括算术表达式。如果它恰好是一个算术表达式,它将被包装在 AExprAsExpr
中。
问题
我想解析包含其他表达式的算术表达式。
例如
x + y
为此,我最初的想法是更改算术解析器,以便它也解析表达式。
data AExpr
= ExprAsAExpr Expr
| IntConst Integer
| Neg AExpr
| ABinary ABinOp AExpr AExpr
deriving (Show, Eq)
aExpr :: Parser AExpr
aExpr = makeExprParser aTerm aOperators
aTerm :: Parser AExpr
aTerm
= parens aExpr
<|> IntConst <$> integerParser
<|> ExprAsAExpr <$> expressionParser
aOperators :: [[Operator Parser AExpr]]
aOperators =
[ [Prefix (Neg <$ symbol "-") ]
, [ InfixL (ABinary Multiply <$ symbol "*")
, InfixL (ABinary Divide <$ symbol "/") ]
, [ InfixL (ABinary Add <$ symbol "+")
, InfixL (ABinary Subtract <$ symbol "-") ]
]
问题在于,当aTerm
调用表达式解析器时,存在一个递归循环,表达式解析器调用aExpr
。这会导致无限循环。还有一个问题是,所有标识符
现在都将包装在AExprAsExpr
内。
解析算术表达式中的表达式的正确方法是什么?
最佳答案
编辑我刚刚意识到您正在使用makeExpressionParser
,而我的答案并不真正适用于此。无论如何,也许这个答案仍然有帮助?
Parsec 是一种递归下降解析器,这意味着它无法处理左递归,正如您所看到的。你需要将其分解出来,如果语法是上下文无关的,那么这总是可以完成的。完成分解的一种方法是为每个优先级进行产生式。以下是简单算术的语法示例:
expr ::= addExpr
addExpr ::= mulExpr '+' addExpr
| mulExpr '-' addExpr
| mulExpr
mulExpr ::= term '*' mulExpr
| term '/' mulExpr
| term
term ::= '(' expr ')'
| number
注意这个模式:每个产生式中的第一个符号向下调用下一个更具体的符号。然后显式括号允许我们重新输入顶级产生式。这通常是递归下降中表达运算符优先级的方式。
上述语法只能产生右嵌套表达式。虽然它会接受正确的字符串,但当解释为左关联时,它无法正确解析。特别是,
1 - 2 - 3 - 4
将被解析为
1 - (2 - (3 - 4))
根据我们的惯例,这是不正确的。在一般的递归下降解析器中,您必须执行一些技巧才能在此处正确关联。然而,在秒差距中,我们有许多
组合器,我们可以利用它们来发挥我们的优势。例如,要解析左关联减法,我们可以说
subExpr = foldl1 (-) <$> many1 mulExpr
这里的下一个级别显然是 chainl
组合器似乎就是为了这个目的而设计的(尽管我现在才了解到它——我想我应该更多地阅读文档)。使用这个的一个例子是
addExpr = chainl1 mulExpr oper
where
oper = choice [ (+) <$ symbol '+'
, (-) <$ symbol '-'
]
我喜欢用 Haskell 编写解析器。祝你好运!
关于解析算术表达式内的表达式,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/50261752/