野牛 - 語法中沒有用的非終結者

Question

我想用野牛創建一個簡單的語法，但是我得到一個警告說非終結者是無用的（additive_expr）。

我的代碼如下所示：

%% 
multiplicative_expr: 
CONSTANT_INTEGER 
| multiplicative_expr MULTIPLICATION CONSTANT_INTEGER 
; 
additive_expr: 
multiplicative_expr 
| additive_expr ADDITION multiplicative_expr 

我見過很多類似的問題，我曾經認爲這是因爲它不能在其他表達式中使用，但我創建了一個新的表達方式，包括這一個，警告繼續。

Answer 1

野牛的語法是由符號和規則連接起來的，可以用「那個符號是那些符號的合成形式」這個短語來理解。同樣，反過來說，你會說「這些符號是這個符號的擴展形式」。

符號可以合成一些基本的東西，如不可分割的單位，稱爲「終端符號」，或與其他符號一樣複雜，這些符號反過來是更多事物的綜合，在這種情況下，後者和前者被稱爲「非終結符號「。

所有關於合成和擴展的內容都可以被認爲是通過不同形式表達同一事物的一種方式。每次表單根據屬於語法的規則而變化時，它就被認爲是重寫，就像以不同方式表達同一事物的概念一樣。

這裏繼承常識（以及關於解析器，Bison等的文章），隨機重寫符號沒有多大意義。一系列重寫應朝着既定目標努力，成功或未能達到目標，但始終能夠檢測到任何一種情況，並停下手中的結果。 Bison的方法是用戶（程序員）突出顯示語法的一組符號中的一個，並且它被認爲完全刪除了任何有效的符號串，而無效的串沒有被找到被重寫的方式。這被稱爲開始符號。

類型的註釋旨在不讓人忽視，在一個典型的語法佈局中，並不是所有的符號都明確地在規則的左右兩側分別與啓動符號相關。與其餘的開始符號的連接是這樣構成的，即通過參與相同的規則將任何符號與另一個符號連接起來，並且這種構造被做成一次或多次，其中一個符號與起始符號進行連接。

繼上述之後，沒有連接開始符號的文法符號是沒有用的。由於重寫是由追求達到開始符號驅動的，一個斷開的符號永遠無法達成，所以永遠不會使用它。當然，在解析器生成階段，會宣佈「無用符號」的警告，因爲這裏的問題不是符號字符串實例，而是語法符號（符號類型）。

由於終端符號的控制不強制執行，因爲野牛讓終端在這裏出於其他目的（例如，建立優先順序，而不一定用於告訴符號組是如何製造的），而非終端代替，無用永遠是這樣，如果選項或指令沒有設置，則會發出警告。

該報告沒有錯誤的嚴重性，因爲接受您可能希望它出於任何原因存在，儘管Bison會以其他方式忽略它。儘管如此，警告還是要引起足夠的重視，因爲這可能意味着輸入錯誤導致語法不能反映，語法分析器也無法達到您想要的效果。

繼續之前的解決方案，一些注意事項：

• 你的語法定義additive_exp和multiplicative_exp集團，這聽起來像是對數學運算+和*。

• 您的語法遵循Bison關於遞歸性的建議，即面對證據表明您的Esense與multiplicative_expr MULTIPLICATION CONSTANT_INTEGER或CONSTANT_INTEGER MULTIPLICATION multiplicative_expr相同，您的方便是前者的構造。 （Bison手冊，§3.3.3遞歸規則）。

• 你的語法正確地避免了Bison的reduce/reduce和shift/reduce衝突，它根據* over +的更高優先級的數學意義做出相同的呼吸。

考慮到上述情況，我會針對「無用符號」的具體問題提出一些小竅門。

野牛不需要規則的任何特定順序。除了有特權的第一條規則是選擇起始符號的特權之外，Bison不介意規則中是否提到語法中未定義但後面的符號。如果您交換規則，以便additive_exp首先出現，它將成爲開始符號，並且因爲它擴展到另一個而不是相反，警告將消失。或者在文法頂部的%%之前放置一個%start additive_exp，具有完全相同的效果。

考慮到你的語法有一個規則additive_exp: multiplicative_exp其他的方法出現。繼參考書目之後，這種形式的規則通常被稱爲「單一生產」，並且引用它：「當語法用於描述操作員的優先級和關聯性時，出現單個生產的常見情況」。 「事實證明，在運算符優先級或關聯性表示中出現的單個生成總是可以被消除」（LR解析「，」A.V.Aho「和」S.C.Johnson「）。 什麼書目在這裏說，完全適合你的情況，因爲你的語法沒有更多的功能相比，你將使用裸露的exp而不是additive_exp和multiplicative_exp，這會留下一個開始符號，而該開始符號反過來是唯一的非終結符放置非終結點無用的可能性，更重要的是，保留語法的含義。

Bison可以通過它的指令％prec，％left和％right來幫助您進行簡化，特別是它們在指令部分出現的順序。非正式地，它關於運算符的優先級，但更準確地說，實際上被改變的是Bison的解析器決定立即進行分組，或者延遲後者作爲遇到的符號，從而給出兩種可能性。 Bison的手冊有詳細的信息，Yacc的手冊也是如此（通常捆綁在Bison發行版中的原因都是非常相關的），甚至可能更詳細地討論如何優先考慮語法規則。 （野牛手冊，第3.7.3節操作符優先權和Yacc手冊，第6節：優先權）。

在可以的地方使用優先順序的指令，可能會幫助野牛避免一些優化，它通常會在建立解析器時節省一些時間。 同樣，基於同一來源（「LR解析」，「A.V.Aho」和「S.C.Johnson」）： 「模糊語法立即生成簡化解析器，而不需要此優化算法」。