解析+和*通過遞歸下降

Question

我寫布爾表達式的遞歸下降解析器的布爾表達式，例如：

(1 * 0) 
(0 + ~1) 
(0 * (1 + c) 

其中1爲「真」，0是「假」，+是'或'，*是'和'，〜是'不是'，'c'只是一些變量名（可以是任何單個字母）。我計劃使用括號而不是實施某種操作順序。

我現在的分析器可以識別表達

Expression ::= 1 
      | 0 
      | Character 
      | ~ Expression 

以下形式，但我不能確定爲我將如何實現+和*在此之上。我是從我讀了明顯的實施

Expression ::= 1 
      | 0 
      | Character 
      | (Expression + Expression) 
      | (Expression * Expression) 

，因爲它是「左遞歸」會導致一個無限循環相當肯定。我不確定如何改變這個去除這樣的無限遞歸。

Answer 1

有了括號，你有什麼不是左遞歸。左遞歸是當一個產品可以直接或間接地到達它自己，而沒有在它們之間消耗的令牌時。這樣的語法在遞歸下降解析器中確實會導致無限遞歸，但這不會與您的發生。

您確實存在語法不明確的問題：括號後，不知道+或*表單是否被解析，直到解析完整個左側表達式爲止。圍繞這個問題得到的

一種方式是通過在共享前綴/後綴生產拉起公用部分：

Expression ::= 1 
      | 0 
      | Character 
      | ParExpr 

ParExpr ::= (Expression ParOp Expression) 

ParOp ::= + 
     | * 

Answer 2

讓我尋找適合您...... https://en.wikipedia.org/wiki/Recursive_descent_parser

領先LPAREN保持它不被左遞歸。 如果您想概括表達式並獲得某些運算符優先級，請按照Wikipedia文章中BNF的表達式部分進行操作。

但是，您在選擇的語法中存在語法歧義。當您擁有相同優先級的運營商時，將它們組合成非終端，如

LogOp :: = + | *

標籤類似的操作數允許擴展：

UnaryOp :: =〜

現在你可以......沒關係，@ 500剛剛發佈，涵蓋我的最後一點一個很好的答案。