parsing - 该语法需要什么类型的解析器？

Question

我有一个语法，除了我不相信该语法是 LL(1) 之外，我不知道需要什么类型的解析器来解析它。我想我需要一个带有回溯或 LL(*) 之类的解析器。我想出的语法(可能需要一些重写)是:

S: Rules
Rules: Rule | Rule Rules
Rule: id '=' Ids
Ids: id | Ids id

我尝试生成的语言看起来像这样:

abc = def g hi jk lm
xy = aaa bbb ccc ddd eee fff jjj kkk
foo = bar ha ha 

零个或多个规则，其中包含左标识符，后跟等号，后跟一个或多个标识符。我认为编写解析器时会遇到问题的部分是，语法允许规则中存在任意数量的 id，并且判断新规则何时开始的唯一方法是它何时找到 id =，这将需要回溯。

有谁知道这个语法的分类以及手写解析器的最佳解析方法吗？

Answer 1

生成标识符后跟等号后跟有限标识符序列的语法是常规。这意味着可以使用 DFA 或正则表达式来解析该语言中的字符串。不需要花哨的非确定性或 LL(*) 解析器。

要查看该语言是否是正则语言，令 Id = U {a : a ∈ Γ}，其中 Γ ⊂ Σ 是标识符中可能出现的符号集。您尝试生成的语言由正则表达式表示

• Id⁺ =( Id⁺)^* Id ⁺

设置 Γ = {a, b, ..., z}，正则表达式语言中的字符串示例为:

• 看 = 我说的是常规语言
• 嘿 = 这意味着我可以被 dfa 识别
• cool = 甚至是正则表达式

无需使用强大的解析技术来解析您的语言。这是使用正则表达式或 DFA 进行解析既合适又最佳的一种情况。

编辑:

将上面的正则表达式称为R。要解析R^*，请生成识别R^*语言的DFA。为此，请使用从 Kleene 定理获得的算法生成一个识别 R^* 语言的 NFA。然后使用子集构造将 NFA 转换为 DFA。生成的 DFA 将识别 R^* 中的所有字符串。给定用您的实现语言构建的 DFA 的表示，所需的操作 - 例如，

• 将最后一个解析的标识符添加到当前正在解析的声明语句的右侧
• 将最后一个解析的声明语句添加到已解析的声明列表中，并使用最后一个解析的标识符开始解析新的声明语句

可以被编码成DFA的状态。实际上，对于如此简单的语言来说，使用克莱恩定理和子集构造可能是不必要的。也就是说，您可能只需编写一个具有上述两个操作的解析器，而无需实现自动机。给定更复杂的常规语言(例如，编程语言的词法结构)，转换将是最佳选择。