时间戳

首页 > 解决方案 > 解析器/语法：嵌套规则中的 2x 括号

parsing - 解析器/语法：嵌套规则中的 2x 括号

问题描述

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

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

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)？据我所知，所有这些都被里面(的规则所消耗，即它们也必须在之后关闭才能不会导致错误并且永远不会被击中。我想我阅读这种语法的经验/直觉不足以理解它。ABNF 中的一条评论说：“注意 boolCommonExpr 也是一个 commonExpr”。也许这就是谜团的一部分？parenExprcommonExprcommonExprboolParenExpr

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

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

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

实际上，我从Wikipedia 上给出的递归下降解析器示例开始。然后我想更好地适应 OData 标准给出的官方语法更“符合”。但是根据 rici 的建议（以及“内部服务器错误”的评论）来重写语法，我倾向于回到 Wikipedia 上提供的更易于理解的结构。

适应 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：感谢您对类型检查的详细评论。新语法应该解决您对算术表达式优先级的担忧。

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

编辑 2：返回原始 OData 语法

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

我最终实现了原始的 OData 语法。在我运行解析器之前，我会向后检查所有标记以找出哪些(属于逻辑/算术表达式。URL 的潜在长度不是问题。

标签： parsinggrammarparenthesesrecursive-descentambiguous-grammar

解决方案

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

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

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

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

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

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

推荐阅读