我有一个表示表达式的语法。为简单起见，我们可以这样说:
S -> E
E -> T + E | T
T -> P * T | P
P -> a | (E)
以 a、+、*、( 和 ) 为我的字母表中的字母。
上述规则可以使用正确的运算顺序和结合性生成包含括号、乘法和加法的有效算术表达式。
我的目标是接受包含 0 个或多个字母表中的字母的每个字符串。这是我的限制:
- 语法必须“接受”包含 0 个或多个字母表中字母的所有字符串。
- 可以通过算法引入新的终端并将其插入到输入中。 (我发现，出于某种原因，显式提供 EOF 终端有助于检测超出有效表达式的额外标记。)
- 可能会引入新的生产规则。新规则将是错误标志(即，如果使用错误标志解析字符串，则尽管该字符串被接受，但在语义上被认为是错误)。
- 可以修改生产规则，以便插入新引入的终端。
- 语法应该是 LALR(1) 至少可以被类似 Lex/Yacc 的工具处理(如果我记得悬空 else 问题需要非 LALR(1)，尽管与 Lex/Yacc 兼容)。
此外，我希望额外的规则能够对应不同类型的错误(二元运算缺少参数、缺少括号 - 左或右 - 超出可接受表达式的额外标记等)。我这么说是因为可能有一些简单的方法来回答我的问题以“接受”所有输入，否则这些输入对错误报告没有好处。
我发现这些规则很有用，尽管我不知道它们是否违反了我的限制:
P -> @ [error]
P -> (E [error]
S -> E $ [instead of S -> E]
S -> E X $ [error]
X -> X Y [error]
X -> Y [error]
Y -> a [error]
Y -> ( [error]
Y -> ) [error]
Y -> * [error]
Y -> + [error]
其中 $ 是显式 EOF 标记，@ 是空字符串。
如果我的问题不清楚:如何在限制范围内修改语法以实现接受所有输入的目标，最好是规则与错误类型的良好对应？我的规则符合我的目标吗？
最佳答案
这个问题已经存在了一段时间，涵盖了该主题的初学者经常访问的主题。人们经常发现，那些在本科阶段学过编译器类(class)的人都知道，这是没有简单或单一答案的问题之一。您可能已经注意到您有 two questions on the same topic ，这两个问题都没有得到解答。 Another question someone else posted答案是指向解释为什么这很难的文献。
这个问题已经存在了 50 多年。如果人们随着时间的推移检查文献，从早期的 session 论文、类(class)教科书、博士论文和(今天)SO ，我们可以看到经常提到这是一个错误的问题! (或者更确切地说，解决问题的方法是错误的)。
仅从多年来的类(class)文本中抽取样本(从我的书架中随机选择):
Gries, D. (1970) 错误恢复和纠正 - 文献简介，编译器构造，高级类(class)，由 Bauer, F.L. 编辑。 & Eickel, J.，施普林格出版社，第 627-638 页。
Gries, D. (1971) 数字计算机的编译器构建，Wiley，第 320-326 页。
Aho, A.V.、Ullman, J.D. (1977) 编译器设计原理，Addison Wesley，第 397-405 页。
Bornat, R. (1979) 理解和编写编译器，Macmillan，第 251-252 页。
Hanson, D. (1995) 可重定向 C 编译器:设计与实现，Addison-Wesley，第 140-146 页。
Grune, D.、Bal, H.E.、Jacobs, C.J.H. ＆兰根多恩，K.G. (2000) 现代编译器设计，Wiley，第 175-184 页。
Aho, A.V.、Lam, M.S.、Sethi, R.、Ullman, J.D. (2007) 编译器:原理、技术和工具，Pearson, Addison-Wesley，第 283-296 页。
所有这些(超过 40 年的时间跨度)都同意您的问题是错误地使用了错误的工具或走错了方向。我想我想说“你不能从这里到那里”。您应该从其他地方开始。
如果您想要更深入的内容，可以阅读完整的博士论文:
希望对于那些将来再次访问此问题的人来说，答案有一个占位符。
我从对您其他问题的评论中注意到您正在使用源自 CPPG 的 MPPG。并非每个人都会使用这些工具，因此我提供了一些这些工具的链接:
Managed Babel Systems Essentials
Garden Points Parser Generator
Irony .NET compiler Construction Kit
Writing your first Visual Studio Language Service
关于grammar - 通过产生式规则向 LALR(1) 语法添加错误检查以处理所有输入，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11940733/