grammar - LALR(1) 文法中的错误恢复

Question

我正在使用一些解析器和词法分析器生成工具(类似于 Lex 和 Bison，但用于 C#)来生成将字符串解析为抽象语法树的程序，这些语法树可以在以后进行评估。

我想进行错误恢复(即在生成的抽象句子树中报告缺少标记等)。我有两种方法来构建生成的语法，我想知道哪种方法更好/更灵活/不会有冲突(.y 和 .lex 文件是根据描述生成的计算器)。

计算器描述允许用户指定终端/正则表达式及其运算符的位置和关联性。所以像这样:

grammar.AddTerminal("Plus", "\\+").
    AddNonTerminal(new NonTerminal("Add", Associativity.LeftToRight).
        AddTerminal("Expression").
        AddTerminal("Plus").
        AddTerminal("Expression"));

(通过添加Terminal 和NonTerminal 的顺序指定优先级。“Add” 是一种通过反射发现的方法。基本上它告诉 NonTerminal 在抽象语法树中调用什么运算符。)

---

方法 1:(允许任何表达式的空规则)

S -> E
E -> E + T
E -> T
T -> T * P
T -> P
P -> (E)
P -> (E [error]
P -> a
P -> @ [error]

---

a 是一个终端。@ 为空。

---

方法二:(开始规则只允许空规则)

S -> E
S -> @ [error]
E -> + [error]
E -> T + [error]
E -> + T [error]
E -> E + T
E -> T
T -> * [error]
T -> * P [error]
T -> P * [error]
T -> T * P
T -> P
P -> (E)
P -> (E [error]
P -> a

这是一个示例，显示了使用每种方法对错误输入的最左侧推导。

---

输入: (a +

---

方法 1:

S
E
T
P
(E
(E + T
(T + T
(P + T
(a + T
(a + P
(a +

---

方法 2:

S
E
T
P
(E
(T +
(P +
(a +

---

方法 2 更难编写代码(考虑减法/一元否定运算符。你不能只看减法 A -> A - B，首先取出 A 并在 A -> - B 上报告错误，因为这对一元运算符有效。)我今天早上为方法 2 编码只是为了发现我认为它有语法问题并且方法 1 中的空规则使事情在代码方面变得更加简单，但我主要关心的是哪种方法会产生最少的语法问题，因为程序员如上所述创建计算器描述。

Answer 1

这个问题已经存在了一段时间，涵盖了该主题的初学者经常访问的主题。人们经常发现，那些在本科阶段学习过编译器类(class)的人都知道，这是没有简单或单一答案的问题之一。你可能已经注意到你有 two questions on the same topic ，这两个都没有得到回答。 Another question someone else posted答案是指向解释为什么这很难的文献。

这个问题已经存在了 50 多年。如果随着时间的推移检查文献，从早期的 session 论文、类(class)教科书、博士论文和(今天的)SO，我们可以看到经常提到这是错误的问题! (或者更确切地说，解决问题的方法是错误的)。

仅从多年来的类(class)文本中抽取样本(从我的书架上随机选择):

Gries, D. (1970) Error Recovery and Correction - An introduction to the Literature，在 Compiler Construction, An advanced Course 中，由 Bauer, F.L. 编辑& Eickel, J., Springer Verlag, pp.627-638.
Gries, D.(1971)数字计算机的编译器构造，Wiley，pp.320-326。
Aho, A.V., Ullman, J.D.(1977)编译器设计原理，Addison Wesley，第 397-405 页。
Bornat, R.(1979)理解和编写编译器，Macmillan，pp.251-252。
Hanson, D.(1995)可重定向的 C 编译器:设计和实现，Addison-Wesley，第 140-146 页。
Grune, D.、Bal, H.E.、Jacobs, C.J.H. & Langendoen, K.G. (2000) 现代编译器设计，Wiley，pp.175-184。
Aho, A.V.、Lam, M.S.、Sethi, R.、Ullman, J.D.(2007 年)编译器:原理、技术和工具，Pearson，Addison-Wesley，第 283-296 页。

所有这些都同意(超过 40 年)您的问题是关于错误地使用错误的工具或朝着错误的方向前进。我想我是想说“你不能从这里到那里”。你应该从别的地方开始。

如果你想要更深入的东西，有一篇完整的博士论文:

Charles, P. (1991) A Practical method for Constructing Efficient LALR(k) Parsers with Automatic Error Recovery, New York University

希望以后再次访问这个问题的人，有一个答案的占位符。

---

我从评论中注意到您正在使用从 CPPG 派生的 MPPG。不是每个人都会用过这些，所以我提供了这些工具的几个链接:

Managed Babel Systems Essentials
Garden Points Parser Generator
Irony .NET compiler Construction Kit
Writing your first Visual Studio Language Service