將解析樹轉換爲AST

讓我首先提出問題：我可以將實現此特定語法的解析樹簡單地轉換爲AST。將解析樹轉換爲AST

我被賦予此語法構建解析樹：

literal := INTEGER | FLOAT | TRUE | FALSE . 

designator := IDENTIFIER { "[" expression0 "]" } . 

op0 := ">=" | "<=" | "!=" | "==" | ">" | "<" . 
op1 := "+" | "-" | "or" . 
op2 := "*" | "/" | "and" . 

expression0 := expression1 [ op0 expression1 ] . 
expression1 := expression2 { op1 expression2 } . 
expression2 := expression3 { op2 expression3 } . 
expression3 := "not" expression3 
     | "(" expression0 ")" 
     | designator 
     | call-expression 
     | literal .

對於這個特定的例子：

func main() : void { 
    let a = 1 + 2 + 3 + 4; 
}

我的解析器將生成（部分）的解析樹來

  EXPRESSION1 
       EXPRESSION2 
        EXPRESSION3 
        LITERAL 
         INTEGER(1)(lineNum:2, charPos:10) 
       OP1 
        ADD(lineNum:2, charPos:12) 
       EXPRESSION2 
        EXPRESSION3 
        LITERAL 
         INTEGER(2)(lineNum:2, charPos:14) 
       OP1 
        ADD(lineNum:2, charPos:16) 
       EXPRESSION2 
        EXPRESSION3 
        LITERAL 
         INTEGER(3)(lineNum:2, charPos:18) 
       OP1 
        ADD(lineNum:2, charPos:20) 
       EXPRESSION2 
        EXPRESSION3 
        LITERAL 
         INTEGER(4)(lineNum:2, charPos:22)

只需注意EXPRESSION1下的這些樹分支如何去：

EXPRESSION2 + EXPRESSION2 + EXPRESSION2 + EXPRESSION2

其中operator +不對應於它的兩個操作數。因此，在我看來，在AST轉換中，我無法獲得一個AST，它通過簡單地拉起操作員來替換非終端EXPRESSION1來幫助生成3位地址IR代碼。

爲了實現這個目標，我會爲這種語言所編寫的語法會是這樣，而不是

expression1 := expression2 | expression1 + expression2 (1) 
expression2 := expression3 | expression2 * expression3 (2) 
expression3 := literal         (3)

該表達式下的分支是唯一

EXPRESSION1 + EXPRESSION2

然而，這個語法是不LL（1）自| FIRST（expression2）| = | {literal，+} | > 1.

它引發了一個問題：（1）轉換這個分析樹最優雅和最簡單的方法是什麼？（2）是我的語法分析樹的構造完全浪費了時間，我應該開始編寫AST代碼了？

來源

2017-02-23 Davis

您可能會考慮分析樹和抽象語法樹之間的真正區別。看到我的回答：http://stackoverflow.com/questions/1888854/what-is-the-difference-between-an-abstract-syntax-tree-and-a-concrete-syntax-tre/1916687#1916687 –

這似乎非常好。我聽說過關於GLR的一些不錯的屬性。現在，科學技術委員會得到了壓縮。感謝您的信息。 – Davis

嗯，這是我在截止日期之前無法弄清楚的一些學校作業。我必須遵循一些具體的指導原則。我太愚蠢了，沒有意識到目標AST不僅僅是CST的「簡化」版本，而是表達語法存在問題。樹結構是不同的。我只是有點生氣。 – Davis

我相信你希望生產的AST，如：

 ADD 
    /\ 
    1 ADD 
     /\ 
     2 ADD 
     /\ 
      3 4

，不過也許你注意到你的分析樹實際上是不是代表一個簡單的出發點，以集團經營者和他們的單程操作數的簡單列表。無論如何編碼更高級的解析器，識別樹結構和應用語法減少並不是一件容易的事。

因此在開始之前，您可能希望考慮一些現有的解析器生成器，如yacc或ANTLR。可能你需要重寫你的語法來創建以操作符爲中心的規則，而不是將它們視爲遞歸實用程序。語法不是典型的LL（1）可能不是一個大問題，因爲現代生成器（如ANTLR）可以處理更大的預測，謂詞等LL（k）語法，並且只是繞過該類型的問題。

如果您仍然堅持要手動編碼，請考慮使用堆棧來存儲符號，並在收集表達式後將它們轉換爲AST節點，但這又不是一項簡單的任務。

來源

2017-02-23 16:23:50 jszpilewski

這是否意味着堅持使用LL（1）語法本身就是一個糟糕的設計，因爲它處理操作符優先級，但在操作符關聯性上失敗？ – Davis

@Davis Targeting LL（1）很好，但當您可以使用像ANTLR這樣的高級LL（k）解析器生成器時，通常並不實際，也不是絕對必要的。 – jszpilewski

將解析樹轉換爲AST

回答

相關問題