LR（1）直接解析爲抽象語法樹

所以我最近問了一個question關閉，並收到了非常好的答案。但是，所描述的步驟似乎更像是創建具體語法樹的步驟。LR（1）直接解析爲抽象語法樹

LR解析過程中的每個縮減對應於解析樹中的內部節點。減少的規則是內部節點AST ，並且彈出堆棧的項目對應於內部節點的子項。推送到goto的項目對應於內部節點，而通過移位操作推送的項目對應於AST的葉子（令牌）。

把所有一起，你可以很容易地通過每一個你做一個還原時間createing一個新的內部節點，並適當地一起佈線一切建立一個AST。〜克里斯多德

我知道，所採取的步驟隱含的分析樹，但我不想明確地建立分析樹。每減少一個節點就會產生整個解析樹。我曾考慮過，如果看到某個狀態，我只會建立一個節點。但是，這似乎不能正常工作。

來源

2015-05-26 Devin Wall

你並不需要建立一個節點上每減少，而你做構建節點不需要包括每符號正在減少。縮減的符號也不需要以與解析相同的順序出現。

在很多情況下，AST是對應於上面的完整分析樹的簡化。

簡單的例子，對於一個表達式語法，使用類yacc解析器生成器：

expr: term   { $$ = $1; /* see below */ } 
    | expr '+' term { $$ = new_sum_node($1, $3); } 
term: factor   { $$ = $1; /* see below */ } 
    | term '*' factor { $$ = new_product_node($1, $3); } 
factor: '(' expr ')' { $$ = $2; /* See below */ } 
     | ID   { $$ = new_variable_node($1); } 
     | NUMBER  { $$ = new_literal_node($1); }

的AST被構建爲所述非端子的語義值。預期功能new_*_node將返回指定類型的新分配的節點。（在這裏我們假設有一些機制可以從指針中推斷出它是什麼類型的節點，例如，可以使用子類型和虛函數。）

在Yacc（和類似的解析器生成器）中，每個符號（終端或非終端）具有相關的「價值」，每個生產都有一個相關的動作，當生產減少時執行。生產動作可以分配非終端的「價值」被降低。該動作可以利用右側組件的「值」，因爲每一個都是終端（其值由掃描儀設置）或非終端已經減少。實際上，這是一個S-attributed grammar。

上面的一些減少在AST中完全不出現。尤其是，單位減少量（expr:term和term:factor）只是簡單地通過AST的右側。同樣，括號減少term:'(' expr ')'只是通過AST的expr，其結果是括號有效地從AST消失。（這在所有語言中都不正確;在某些語言中，明顯冗餘的括號實際上會影響語義，您需要創建一個AST節點來記錄事實。）

在Yacc中，$$ = $1是未指定操作時的默認縮減操作，並且由於大多數單位縮減都從AST中刪除，所以通常會顯示它們而沒有縮減操作。爲了教學目的，我明確表示他們;在實踐中，你不應該那樣做。

來源

2015-05-27 02:57:09 rici

您介意我是否要求您詳細說明通過和默認操作。我也不熟悉$$符號。這只是代表一個變量？對不起，如果這是一個愚蠢的問題，出於某種原因，我的大腦只是在這個特殊問題上遇到困難。但是，謝謝你的回覆！ –

@devin：對不起，我假設一個yacc-like語法分析器生成器，我應該更加明確。在yacc中，設置$$設置縮減非終結符的「值」。右邊符號的「值」是$ 1，$ 2等。 – rici

@DevinWall：希望額外的解釋有所幫助。 – rici

LR（1）直接解析爲抽象語法樹

回答

相關問題