通過生產規則向LALR（1）語法添加錯誤檢查以處理所有輸入

Question

我有一個表示表達式的語法。比方說，爲了簡單起見，它是：

S -> E 
E -> T + E | T 
T -> P * T | P 
P -> a | (E) 

隨着a，+，*，(和)是在我的英語字母，這個。

上述規則可以生成包含圓括號，乘法和加法的有效算術表達式，並使用正確的操作順序和關聯性。

我的目標是接受每個字符串，包含0個或更多字母的字母。以下是我的約束：

• 語法必須「接受」包含0個或多個字母的所有字符串。
• 可以引入新的終端並通過算法插入輸入。 （由於某種原因，我發現明確提供了一個EOF終端幫助檢測超出其他有效表達式的額外令牌時）。
• 可能會引入新的生產規則。新的規則將是錯誤標誌（即，如果字符串是使用一個進行分析的，那麼雖然字符串被接受，但它被認爲是語義上的錯誤）。
• 可以修改生產規則，以便插入新引入的終端。
• 語法應該是LALR（1）至少可以通過Lex/Yacc-like工具處理（如果我記得其他問題需要非LALR（1），儘管與Lex/Yacc兼容）。

此外，我想額外的規則，以對應不同類型的錯誤（缺少參數二元運算，括號缺失 - 向左或向右 - 額外的令牌（S）以外的其他方式接受，能表達，等等。 ）。我說這是因爲可能有一些微不足道的方法來回答我的問題，以便「接受」所有不會對錯誤報告有益的輸入。

我發現這些規則是有用的，雖然我不知道他們是否違反我的制約，或不：

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令牌和@是空字符串。

---

如果我的問題不明確：如何修改我的約束來實現我接受所有輸入的目標之內我的語法，最好的規則，一個很好的對應關係類型的錯誤？我的規則是否符合我的目標？

Answer 1

這個問題已經存在了一段時間，涵蓋了主題中的初學者經常訪問的主題。人們經常發現，那些已經完成了本科學位的編譯器課程的人都知道，這是那些沒有簡單或單一答案的問題之一。你可能已經注意到你有two questions on the same topic，這兩者都沒有被回答。 Another question someone else posted被解釋爲什麼這很難解釋文獻的指針。

這是一個仍然存在超過50年的問題。如果從早期的會議論文，課程教科書，博士論文和（今日）SO中檢驗文獻，我們可以經常看到這樣的事實：錯誤的問題！ （或者說錯誤的解決問題的方法）。

只是把從多年來的歷程文本樣本（從我的書架隨機選擇）：

格里斯，D.（1970）錯誤恢復和糾正 - 介紹了文學，在編譯器建設，安高級課程由Bauer，FL編輯Eickel，J.，Springer Verlag，pp.627-638。
Gries，D.（1971）數字計算機的編譯器構造，Wiley，第320-326頁。 Aho，A.V.，Ullman，J.D。（1977）編譯器設計原理，Addison Wesley，pp.397-405。
Bornat，R.（1979）Understanding and Writing Compilers，Macmillan，pp.251-252。
Hanson，D。（1995）A retargetable C compiler：Design and Implementation，Addison-Wesley，pp.140-146。
Grune，D.，Bal，H.E.，Jacobs，C.J.H. Langendoen，K.G. （2000）Modern Compiler Design，Wiley，pp.175-184。 Aho，A.V.，Lam，M.S.，Sethi，R.，Ullman，J.D。（2007）Compilers：Principles，Techniques，& Tools，Pearson，Addison-Wesley，pp.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