0

我目前正在为 ECMAScript 5 编写解析器（作为玩具）。该标准规定了如何解析逻辑或表达式：

<LogicalORExpression> :
    <LogicalANDExpression>
    <LogicalORExpression> || <LogicalANDExpression>

基本上这相当于

<logicalOrExpression> = [<logicalOrExpression> ||] <LogicalAndExpression>

但是我应该如何在不陷入无限循环的情况下解析它？我当前的解析器显然可以：

logicalOrExpression :: Parser LogicalOrExpression
logicalOrExpression = do
    orExpr <- optional $ do
        e <- logicalOrExpression
        _ <- symbol "||"
        return e
    andExpr <- logicalAndExpression
    case orExpr of
        Just e -> return $ LogicalOrExpression (e, andExpr)
        Nothing -> return $ AndExpression andExpr

谢谢

4

4 回答 4

3

如果您需要解析具有优先级和关联性的运算符语法，则使用megaparsec's 的内置工具是最简单的。

expr = makeExprParser term table
    where
        term = literal <|> parenthesised expr
        table = [[InfixL (string "&&" $> And)], [InfixL (string "||" $> Or)]]

对于 and 的合适定义literal，parenthesised这将解析由左结合中缀&&和||运算符组成的文字表达式语法，&&其优先级高于||. Megaparsec 负责生成 LL(k) 解析器的繁琐工作，并生成正确的（在本例中为左关联）解析树。

当然，JavaScript 的表达式语法远大于两个运算符。此示例可以直接扩展为包括（例如）一元前缀运算符!，如后缀函数调用等。请参阅模块的文档。

于 2017-11-17T02:23:20.380 回答
1

该语法看起来等同于

<LogicalORExpression> :
    <LogicalANDExpression>
    <LogicalANDExpression> || <LogicalORExpression>

变成

<LogicalORExpression> :
    <LogicalANDExpression> [|| <LogicalORExpression>]

一般来说，如果可能，您需要以（大致）LL(1) 形式重写语法。

于 2017-11-16T21:43:32.503 回答
0

空字符串匹配这个解析器，我相信这会导致 Magaparsec 中的无限递归。我认为您在函数的某处缺少“术语”或“布尔值”。如果我写True || False什么会捕捉到第一个“真”

于 2017-11-16T21:24:05.977 回答
-1

由于我想在生成的 AST 方面保持真实的规范，因此我决定切换到基于 Earley 的解析器而不是解析器组合器，因为 Earley 的算法可以处理左递归。

如果我可以扁平化语法，我会使用本杰明霍奇森的答案

于 2017-11-17T14:47:29.487 回答