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

Question

尽管我在编译/解析方面的知识有限，但我还是敢于为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等式2）这样的简单表达式？从我所能看到的一切（被parenExpr内部的commonExpr规则所消耗，也就是说，它们必须在commonExpr之后关闭，以避免引起错误，并且boolParenExpr永远不会被击中。我想我阅读这种语法的经验/直觉不足以得到它。ABNF中的一条评论说：“注意boolCommonExpr也是一个commonExpr”。也许这就是谜团的一部分？

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

我宁愿在输入上有限制或一点黑客攻击，也不愿切换到一个通常更强大的解析器模型。对于像这样的简单表达式翻译，我还想避免使用编译器工具。

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

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

适用于OData$过滤器的布尔表达式，可能如下所示：

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：谢谢你对类型检查的详细评论。新的语法可以解决你对算术表达式中优先顺序的担忧。

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

编辑2：返回原始的OData语法

逻辑和算术之间的区别不是微不足道的。为了解决这个问题，甚至N. Wirth也使用了一个不可靠的变通方法来保持Pascal的语法简单。因此，在Pascal中，一对额外的（）在和和或表达式周围是强制性的。既不直观也不符合OData：-（.关于（）难度，我发现最好的阅读是在让我们建立一个编译器（第六部分）。其他语言似乎在语法上花了很长时间来解决这个问题。由于我没有语法构建的经验，我停止了自己的语法构建。

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

Answer 1

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

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

TGS是我从事的一个项目。

Answer 2

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

具体来说，如果目标是boolCommonExpr，则有两个产品可以匹配（lookahead令牌：

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

在大多数情况下，这是一种误导性的尝试，试图让语法检测类型冲突。（如果事实上是类型冲突。）这是错误的，因为如果存在布尔变量，它注定会失败，而在这个环境中显然存在布尔变量。由于没有关于变量类型的语法线索，解析器无法确定特定表达式的格式是否正确，因此完全不尝试是一个很好的理由，特别是如果它造成解析难题的话。更好的解决方案是首先将表达式解析为某种形式的AST，然后对AST进行另一次传递，以检查每个运算符是否具有正确类型的操作数（如果有必要，还可能插入显式强制转换运算符）。

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

将不同运算符（而不是括号）放入不同语法变量的一个可能原因是为了表示语法优先级。这种考虑可能会鼓励你以明确的优先顺序重写语法。（如前所述，语法假设所有算术运算符具有相同的优先级，这可能会导致23*a被解析为（23）*a，这可能会让人大吃一惊。）或者，您可以对表达式使用一些简单的优先级感知子parser。