Parser/Grammar：嵌套规则中的 2x 括号

Question

尽管我对 compiling/parsing 的了解有限，但我敢于为 OData $filter 表达式构建一个小型递归下降解析器。解析器只需要检查表达式的正确性并在SQL中输出一个相应的条件。由于输入和输出具有几乎相同的标记和结构，这非常简单，我的实现完成了我想要的 90%。

但现在我被括号困住了，括号出现在逻辑和算术表达式的不同规则中。 ABNF 中的完整 OData 语法是 here，所涉及规则的压缩版本是这样的：

boolCommonExpr = ( boolMethodCallExpr 
                 / notExpr  
                 / commonExpr [ eqExpr / neExpr / ltExpr / ... ]
                 / boolParenExpr
                 ) [ andExpr / orExpr ] 
commonExpr = ( primitiveLiteral
             / firstMemberExpr  ; = identifier
             / methodCallExpr 
             / parenExpr 
             ) [ addExpr / subExpr / mulExpr / divExpr / modExpr ]  
boolParenExpr = "(" boolCommonExpr ")"
parenExpr     = "(" commonExpr ")"

这个语法如何匹配像 (1 eq 2) 这样的简单表达式？据我所知，所有 ( 都被 commonExpr 内的规则 parenExpr 消耗，即它们还必须在 commonExpr 之后关闭，以免导致错误和 boolParenExpr永远不会被击中。我想我阅读这种语法的经验/直觉不足以理解它。 ABNF 中的评论说：“注意 boolCommonExpr 也是一个 commonExpr”。也许这就是谜团的一部分？

显然，开盘 ( 本身并不能告诉我它将在哪里结束：在当前 commonExpr 表达式之后或在 boolCommonExpr 之后更远。我的词法分析器前面有一个 all 标记的列表（URL 是非常短的输入）。我想用它来找出我有什么类型的 (。好主意？

我宁愿在输入方面有限制或有一些技巧，也不愿切换到通常更强大的解析器模型。对于这样一个简单的表达式翻译，我也想避免使用编译器工具。

编辑 1：rici 回答后的扩展 - 语法重写是否正确？

实际上我是从 example for recursive-descent parsers given on Wikipedia 开始的。然后我想更好地适应OData标准给出的官方语法更“符合”。但是根据 rici 的建议（以及“内部服务器错误”的评论）重写语法，我倾向于回到维基百科上提供的更易于理解的结构。

适应 OData $filter 的布尔表达式，这可能看起来像这样：

boolSequence= boolExpr {("and"|"or") boolExpr} .
boolExpr    = ["not"] expression ("eq"|"ne"|"lt"|"gt"|"lt"|"le") expression .
expression  = term {("add"|"sum") term} .
term        = factor {("mul"|"div"|"mod") factor} .
factor      = IDENT | methodCall | LITERAL | "(" boolSequence")" .
methodCall  = METHODNAME "(" [ expression {"," expression} ] ")" .

以上对于布尔表达式是否有意义，它是否大部分等同于上面的原始结构并且可以被递归下降解析器消化？

@rici：感谢您对类型检查的详细评论。新语法应该可以解决您对算术表达式优先级的担忧。

对于所有三个终端（上面语法中的大写），我的词法分析器提供了一个类型（字符串、数字、日期时间或布尔值）。非终结符 return 它们产生的类型。有了这个，我在当前的实现中很好地进行了动态类型检查，包括不错的错误消息。希望这也适用于新语法。

编辑 2：Return 到原始 OData 语法

“逻辑”和“算术”之间的区别 ( 不是微不足道的。为了解决这个问题，甚至 N.Wirth 使用了一种狡猾的变通方法来保持 Pascal 语法的简单性。因此，在 Pascal 中，一对额外的 () 是 mandatory 围绕 and 和 or 表达式。既不直观也不符合 OData :-(。我发现的关于“() 困难”的最佳读物是 Let's Build a Compiler (Part VI)。其他语言似乎在语法上花了大量篇幅来解决这个问题。因为我没有有语法构造的经验我不再自己做。

我最终实现了原始的 OData 语法。在我运行解析器之前，我向后遍历所有标记以找出哪个 ( 属于 logical/arithmetic 表达式。 URL.

的潜在长度不是问题

Answer 1

就我个人而言，我只是修改语法，使其只有一种表达式，因此只有一种括号。我不相信 OData grammar 实际上是正确的；由于您提到的原因，它肯定不能用于 LL(1)（或递归下降）解析器。

具体来说，如果目标是boolCommonExpr，有两个产生式可以匹配(前瞻标记：

boolCommonExpr = ( … 
                 / commonExpr [ eqExpr / neExpr / … ]
                 / boolParenExpr
                 / …
                 ) …
commonExpr     = ( …
                 / parenExpr
                 / …
                 ) …

在大多数情况下，这是使语法检测类型违规的错误尝试。（如果实际上这是一种类型冲突。）它被误导了，因为如果有布尔变量，它注定会失败，而布尔变量显然存在于这个环境中。由于没有关于变量类型的语法线索，解析器无法确定特定表达式是否为 well-formed头痛。更好的解决方案是首先将表达式解析为某种形式的 AST，然后再次传递 AST 以检查每个运算符是否具有正确类型的操作数（并且可能在必要时插入显式转换运算符）。

除了任何其他优势之外，在单独的传递中进行类型检查可以让您产生更好的错误消息。如果你犯了（某些）类型违规语法错误，那么你可能会让用户感到困惑，为什么他们的表达式被拒绝了；相反，如果您注意到比较运算被用作乘法操作数（并且如果您的语言的语义不允许从 True/False 自动转换为 1/0），那么您可以生成 well-targetted 错误消息（例如，“比较不能用作算术运算符的操作数”）。

将不同的运算符（而不是括号）放入不同的语法变量中的一个可能原因是表达语法优先级。这种考虑可能会鼓励您以明确的优先级重写语法。（如所写，语法假定所有算术运算符具有相同的优先级，这可能会导致 2 + 3 * a 被解析为 (2 + 3) * a，这可能是一个巨大的惊喜。）或者，您可以使用一些简单的表达式的优先级感知子解析器。

Answer 2

如果您想测试 ABNF 语法的确定性（即 LL(1)），您可以使用 Tunnel Grammar Studio (TGS)。我已经测试了完整的语法，并且有很多冲突，不仅仅是这个范围。如果您能够提取相关规则，则可以使用桌面版 TGS 来可视化冲突（在线版检查器仅具有文本结果）。如果规则不是太多，演示可能会帮助您根据规则创建 LL(1) 语法。

如果您提取所有需要的规则，并将它们添加到您的问题中，我可以为您运行并告诉您是 LL(1)。请注意，语法不完全是 ABNF 元语法，因为区分大小写的字符串使用 ' 键入区分大小写。根据定义，ABNF (RFC 5234) 不区分大小写，因为 RFC 7405 在实际字符串之前使用 %s 和 %i（敏感和不敏感）前缀定义了敏感度。默认大小写（没有前缀）仍然意味着不敏感。这意味着在 TGS 中测试之前，您必须将此无效的 '...' 字符串替换为 %s"..."。

TGS 是我从事的项目。

Parser/Grammar：嵌套规则中的 2x 括号

Parser/Grammar: 2x parenthesis in nested rules

grammar

parsing

recursive-descent

parentheses

ambiguous-grammar