解析器语法中的循环依赖

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

这样的循环依赖关系很好-这是一个递归定义，类似于在程序中使用递归。因此，要注意的重要事项是基本情况的实现方式，因为这是终止响应的方式。如果您没有基本情况（或者不触发其他递归就无法实现），那么您会遇到问题-永远无法匹配任何有限输入的无限循环。