左遞歸，關聯性和AST評估

所以我一直在閱讀詞法分析器，解析器，解釋器甚至編譯。左遞歸，關聯性和AST評估

對於我試圖實現的語言，我在Recrusive Descent Parser上解決了問題。由於語言的原始語法具有左遞歸，我不得不稍微重寫它。

這裏是語法我有一個簡化版本（注意，這不是任何標準格式的語法，但有點假，我想，這就是我發現它在文檔中）：

expr: 
----- 
expr + expr 
expr - expr 
expr * expr 
expr/expr 
(expr) 
integer 
identifier

爲了擺脫左遞歸的，我把它變成這樣（請注意添加NOT運算符的）：

expr: 
----- 
expr_term {+ expr} 
expr_term {- expr} 
expr_term {* expr} 
expr_term {/ expr} 

expr_term: 
---------- 
! expr_term 
(expr) 
integer 
identifier

然後通過我的令牌使用以下子例程去（簡化的僞代碼-ISH）：

public string Expression() 
{ 
    string term = ExpressionTerm(); 

    if (term != null) 
    { 
     while (PeekToken() == OperatorToken) 
     { 
      term += ReadToken() + Expression(); 
     } 
    } 

    return term; 
} 

public string ExpressionTerm() 
{ 
    //PeekToken and ReadToken accordingly, otherwise return null 
}

This Works！調用Expression後的結果總是等於它給出的輸入。

這使我想知道：如果我要在這些子程序中創建AST節點而不是字符串，並且使用中綴評估器（它也記住運算符的關聯性和優先級等）來評估AST，我不會得到相同的結果？

如果我這樣做，那麼爲什麼會有這麼多的話題涉及到「固定左遞歸，牢記關聯性和什麼不是」，當它實際上「簡單地」解決或者甚至是一個非問題時，它似乎就是這樣？或者，它真的是AST人們關心的結構（而不是它所評估的）？任何人都可以點亮一下，我可能會把它弄錯，哈哈！

來源

2013-10-19 Lennard Fonteijn

解析器的目的是產生解釋（動作）或翻譯（相同或另一種語言中的等效文檔，如優化，註釋或編譯中）。重現原始輸入是無趣的。 – Apalala

我認爲這表明我得到了我的遞歸循環，因爲如果我將字符串更改爲節點樹，我最終還會得到一個語法正確的「句子」。這個假設是不正確的？ –

重現輸入證明沒有關於識別結構。它可以通過回聲或運氣來完成。一個簡單而透明的翻譯將嘗試將輸入轉換爲前綴或後綴（波蘭語）符號。你甚至可以爲postfix建立一個評估器來知道你是否正確地解釋了輸入結構。就你而言，你會發現你不是，因爲所有的操作員都在同一個級別。您需要某種運算符優先權，請注意a + b * 3表示a +（b * 3）而不是（a + b）* 3。 – Apalala

的AST 的形狀重要的，因爲a+(b*3)通常不是一樣(a+b)*3和一個合理預期會解析器來指示那些a+b*3手段。

通常情況下，AST實際上會刪除括號。（A解析樹不會，而是AST預計抽象掉語法噪音。）因此，對於a+(b*3) AST的應該是這個樣子：

  Sum 
      | 
     +---+---+ 
     |  | 
     Var  Prod 
     |  | 
     a +---+---+ 
      |  | 
      Var Const 
      |  | 
      b  3

如果你的語言服從通常的數學符號約定，所以將AST爲a+b*3。

「中綴評估者」 - 或者我想象中的你所指的 - 只是另一個解析器。所以，是的，如果你以後很樂意解析，你現在不必解析。

順便說一句，表明您可以將令牌放回到您閱讀它們的順序中，但實際上並沒有多少關於解析器的功能。只需回顯標記器的輸出即可做到這一點。

來源

2013-10-19 01:16:05 rici

Ahhh，我現在開始明白了，所以AST幾乎是「評估準備好的」，因爲你只是經歷過它，實際上不必再解析（對於分析樹來說，情況仍然如此）？ –

評估準備就緒，像這樣的表達式存儲在AST（例如）中的後綴。雖然我可能會過度複雜的思考過程。 –

@LennardFonteijn：分析樹也準備好評估。你只需要忽略更多的東西。（例如，「（expr）」規則的評估包括「返回第二個孩子的值」）。樹通常作爲樹存儲，所以後綴和前綴不相關。（或者，如果你願意，他們是類方法，因爲樹可以遍歷預訂或後序。） – rici

標準和處理表達式，數學或其他最簡單的方法，是反映預期的協會和運算符優先級規則層次：

expre = sum 

sum = addend '+' sum | addend 

addend = term '*' addend | term 

term = '(' expre ')' | '-' integer | '+' integer | integer

這樣的語法讓分析或抽象的樹木直接可求。您可以擴展規則層次結構以包含電源和按位運算符，或者使其成爲邏輯表達式的層次結構的一部分，並與比較結果進行比較。

來源

2013-10-19 15:54:30 Apalala

我已經嘗試過這個，雖然這個工作，你必須在你之前通過一個'n'數量的優先級得到你的條件，不要提到可維護性是可怕的。我現在開發了一種算法來構建樹，我不知道它是否存在於一個衆所周知的名稱下，但我會在今天晚些時候發佈它。 –

顯然我想出了優先攀登的推導：http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm#climbing –

http://en.wikipedia.org/wiki/Operator-precedence_grammar – Apalala

左遞歸，關聯性和AST評估

回答

相關問題