解析器语法中的循环依赖

Question

我正在尝试构建我的第一个解析器。不幸的是我不熟悉语法理论，现在我想知道它是否

明确禁止
只是个坏主意或者
还可以

在我的语法中有循环依赖。我的直觉升起了黄旗，但由于我不熟悉解析器的理论，所以我不确定。

如果我的词法分析器是定义明确的，并且是人们期望从他们的名字中得到的标记，那么我有以下语法：

list_content    : value
                | list_content COMMA list_content

list            : LBRACE list_content RBRACE

value           : INT
                | list

在那里，value依赖于list，list依赖于list_content，list_content依赖于value。

之前在文法中看到过递归定义，比如：

sum             | NUMBER + NUMBER
                | NUMBER + sum
                | LBRACE sum RBRACE

但是，我认为我的循环定义是不同的（在：更脏方面），因为它更难概括并且定义的循环跨越多个语法规则。我不确定我的循环定义是否会在我的语法中造成歧义。我也担心它可能会使我的代码难以调试。

所以，我有两个问题：

A) 我应该重新构造 我的语法（和我的词法分析器）还是可以接受这个循环定义？

B) 如果我应该重组，我最好怎么做？

Answer 1

像这样的循环依赖很好——它是一个递归定义，类似于在程序中使用递归。因此，重要的是要看基本案例是如何实现的，因为这就是回避终止的方式。如果你没有基本情况（或者如果不触发额外的递归就无法达到），你就会遇到问题——一个永远无法匹配任何有限输入的无限循环。

在你的情况下，基本情况是 primitive 规则——因为 value 可以减少到单个 primitive 和 list_content 到单个 value,一切都很好。

你的语法确实有一个问题，那就是规则

list_content: list_content COMMA list_content

是模棱两可的。这意味着对于任何具有三个或更多元素（两个或更多逗号）的列表，有多种解析它的方法——首先匹配左逗号（左递归）或右逗号（右递归）。这将导致大多数无法处理歧义的解析器工具出现问题，并且在您的情况下可能无关紧要（您并不真正关心它的解析方式，因为您可能只是连接列表）。

解决此问题的方法是将规则重写为简单的左或右递归规则（但不是两者）。您要使用哪种取决于您使用的解析器样式——对于 LL（自上而下或递归下降）解析器，您需要正确的递归规则。对于 LR（自下而上或 shift/reduce）解析器，您（通常）需要左递归规则。

左递归：list_content : value | list_content COMMA value ;
右递归：list_content : value | value COMMA list_content ;

解析器语法中的循环依赖

Circular Dependency in Parser Grammar

grammar

parsing

yacc