解析算术表达式中的表达式

Question

我想解析算术表达式。

这是我当前的解析器：

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

这意味着使用 expressionParser 我现在可以解析所有不同的表达式，包括算术表达式。如果它恰好是一个算术表达式，它会被包裹在 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。这会导致无限循环。还有一个问题是所有 identifiers 现在都将包含在 AExprAsExpr.

中

解析算术表达式内部表达式的正确方法是什么？

Answer 1

编辑我刚刚意识到您正在使用 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))

根据我们的惯例，这是不正确的。在一般的递归下降解析器中，你必须做一些技巧才能在此处正确关联。然而，在 Parsec 中，我们有 many 组合子，我们可以利用它来发挥我们的优势。例如，要解析左相关减法，我们可以说

subExpr = foldl1 (-) <$> many1 mulExpr

这里的下一层显然是 chainl 组合器，它们似乎就是为此目的而设计的（尽管我现在才知道它——我想我应该仔细阅读文档）。使用它的一个例子是

addExpr = chainl1 mulExpr oper
    where
    oper = choice [ (+) <$ symbol '+'
                  , (-) <$ symbol '-'
                  ]

我喜欢在 Haskell 中编写解析器。祝你好运！

解析算术表达式中的表达式

Parsing expressions inside arithmetic expressions

compiler-construction

parsing

haskell

parsec

megaparsec