無冗餘括號的算術表達式的明確語法

Question

我正在尋找無冗餘括號的算術表達式的明確語法。例如，括號在id+(id*id)中是多餘的，但不在(id+id)*id中。

Answer 1

它完全取決於'用於沒有多餘括號的算術表達式'的含義。這將接受沒有多餘的括號表達式，但也將接受任意嵌套的括號：

expr ::= factor 
expr ::= factor mul_div factor 

mul_div ::= '*' | '/' 

factor ::= term 
factor ::= term add_sub term 

add_sub ::= '+' | '-' 

term ::= NUMBER 
term ::= '(' expr ')' 

我假設這個數字管理，以識別符號數，所以沒有一元加或減在那裏。如果你需要他們，你可以研究如何處理他們。如果你需要它們，你也可以添加變量等。

如果您的意思是拒絕帶有不必要括號的表達式的語法，那麼我認爲您正在尋找不是上下文無關語法的東西。

Answer 2

您可以輕鬆地做到這一點。當括號成爲必要時，唯一的一次是作爲乘法表達式的片段之一存在和表達式，或者某個表達式作爲除法表達式之一的第二部分。在這兩種情況下，都可以通過強制括號內的內容至少有一個空操作符（不包括其他括號）來確保括號不重複。

我想我可能會幫助你回答一個我不太喜歡的入學考試或家庭作業的問題，但所有人都稱這不可能或暗示這可能是不可能的，這是錯誤的，我想直接設置它們。

要分析表達這樣：

expr  ::= expr addsub term 
expr  ::= prodterm 
expr  ::= value 

sum  ::= expr addsub term 

addsub ::= '+' | '-' 

term  ::= prodterm 
term  ::= unit 

prodterm ::= term '*' unit 
prodterm ::= term '/' produnit 

unit  ::= '(' sum ')' 
unit  ::= value 

produnit ::= unit 
produnit ::= '(' prodterm ')' 

value  ::= '0-9'* 

一個孤獨的價值永遠不能擁有它周圍括號。單位是乘法表達式的子表達式; produnits允許您的分割表達式的括號尾巴。 （5）將是（值），這是不可能的，因爲只有produnits和unit有括號，並且如果他們存在，他們需要一些算術運算符出現在括號內。 （值）不能從任何表達式派生，並且（（任何））是不可能的，因爲只有produnit和單位派生括號。仔細觀察，produnit需要一個*或一個/如果一個括號派生，或爲它解析爲一個單位，或一個值沒有括號。單位要求出現+或 - - ，否則不用括號。因爲（5 + 6）只能作爲一個單元進行解析，這可能會使它成爲一個produnit，但是沒有辦法在一個獨立的produnit上放置括號 - 沒有鏈一個單位或produnit圍繞單獨的produnit括號。你會認爲，5 *（6 * 7）不會解析 - 它是一個單位的時間，但是（6 * 7）不是單位，因爲單位必須是具有至少一個總和的表達式的值或括號。一旦出現至少一個總和，括號就不是微不足道的。另一方面，5 /（6 * 7）根本不同於5/6 * 7 - 第一個像5/6/7，第二個像5 * 7/6。然而，5 /（6）與5/6相同 - 在括號內不能出現單值。同樣，5 /（6/7）與5/6/7不同，因爲第一個與5 * 7/6相同，第二個與5 /（6 * 7）相同。換句話說，如果內部沒有運營商，分母周圍的括號絕不會是無關緊要的。 （5 + 6）+7也是不可能的，因爲總和的左手邊（和右手邊）要麼是嚴格的值，總和周圍沒有括號的總和，要麼是產品周圍沒有括號的產品。沒有辦法變身

你可以說服自己，這些舉行，並檢查自己，這是毫不含糊的。您可以向自己證明它通過擴展它來包含指數運算符，或者更好地將其推廣到更高優先級運算符或更低優先級運算符（如==或<）。

我希望這有助於！