解析與PEG.js

Question

完整的數學表達式

我試圖延長PEG.js例子語法解析所有的4個運營商的數學表達式爲我在線BASIC解釋實驗：

http://www.dantonag.it/basicjs/basicjs.html

但不是全部表達式被正確解析。

這是我的PEG語法：

expression = additive 

additive = left:multiplicative atag:("+"/"-") right:additive { return {tag: atag, left:left, right:right}; }/multiplicative 

multiplicative = left:primary atag:("*"/"/") right:multiplicative { return {tag: atag, left:left, right:right}; }/primary 

primary = number/"(" additive:additive ")" { return additive; } 

number = digits:[0-9]+ { return parseInt(digits.join(""), 10); } 

它解析正確表達式等2 * 3 + 1（給予7），但不象2-1-1的表達，給出2而不是0。

你能幫我改進和調試嗎？

在此先感謝。

編輯：我已將「數字」規則添加到語法中。是的，我的語法給出了一個類似於分析樹的遞歸結構。

Answer 1

第一：您的語法缺少number規則。另外，正如我相信你知道的，在你的例子中運行你的語法（在添加number之後）並不給出2，而是像分析樹一樣。你介意更新問題來解決這兩個問題嗎？

---

問題： 看起來你碰到的關聯性。當具有相同優先級的兩個運算符競爭操作數時，相關性起作用。在你的例子中，-與-競爭 - 如此清楚它將具有與其自身相同的優先級 - 但關聯性對於打破+和-之間以及*和/之間的關係也是重要的。

我認爲2*3+1被正確解析，因爲這兩家運營商有不同的優先級，這意味着關聯性不發揮作用，那你的語法正確實現優先級（雖然你應該注意到，2+3*1是表明一個更標準的例子乘法具有比加法更高的優先級，因爲簡單的從左到右的解析2*3+1給出了與解析器相同的結果）。

我假設你想-爲左關聯的，但它似乎是右結合在你的語法，在此基礎上例如：

• 輸入：

  1-2-3 
  

• 輸出（解析爲1-(2-3)）：

  { 
      "tag": "-", 
      "left": "1", 
      "right": { 
       "tag": "-", 
       "left": "2", 
       "right": "3" 
      } 
  } 
  

左聯樹看起來像這樣（從(1-2)-3）：

{ 
    "tag": "-", 
    "left": { 
     "tag": "-", 
     "left": "1", 
     "right": "2" 
    }, 
    "right": "3" 
} 

你應該注意到，您的其他運營商也似乎是右關聯，而不是左手。

解決方法：我並不真正瞭解peg.js是如何工作的，但有些快速的谷歌搜索出現了this。

對於運算符優先級和關聯性的基於語法的解決方案通常很難理解（請參閱grammar for Python以獲取證據），因此您可能希望檢查[自上而下]運算符優先級解析，以獲得更靈活和更具表達性的選擇。 Douglas Crockford，Vaughn Pratt和Annika Aasa在這個主題上有一些不錯的文章。

Answer 2

馬特的答案是正確的，但對如何pegjs內實現左結合：

expression = additive 

additive 
    = first:multiplicative rest:(("+"/"-") multiplicative)+ { 
    return rest.reduce(function(memo, curr) { 
     return {atag: curr[0], left: memo, right: curr[1]}; 
    }, first); 
    } 
/multiplicative 

multiplicative 
    = first:primary rest:(("*"/"/") primary)+ { 
    return rest.reduce(function(memo, curr) { 
     return {atag: curr[0], left: memo, right: curr[1]}; 
    }, first); 
    } 
/primary 

primary 
    = number 
/"(" additive:additive ")" { return additive; } 

number 
    = digits:[0-9]+ { return parseInt(digits.join(""), 10); } 

的javascript.pegjs例如馬特鏈接使用了類似的方法。關鍵是處理與列表相同優先級的操作字符串，這使您能夠以正確的關聯性構建樹。