什麼是語法樹？

其中每個葉子節點描述一個運算元，每個內部節點描述一個運算子。語法樹是語法分析樹的簡寫形式。

示例 1 - 為字串 a + b ∗ c − d 繪製語法樹。

構建語法樹的規則

語法樹中的每個節點都可以作為具有多個欄位的資料執行。在運算子的節點中，一個欄位識別運算子，其餘欄位包含指向運算元節點的指標。運算子稱為節點的標籤。以下函式用於為具有二元運算子的表示式建立語法樹的節點。每個函式都返回指向最近生成的節點的指標。

mknode (op, left, right) - 它生成一個帶有標籤 op 的運算子節點，以及兩個包含指向左節點和右節點的指標的欄位。
mkleaf (id, entry) - 它生成一個帶有標籤 id 的識別符號節點，以及包含 entry 的欄位，entry 是指向識別符號符號表條目的指標。
mkleaf (num, val) - 它生成一個帶有標籤 num 的數字節點，以及包含 val 的欄位，val 是數字的值。例如，為表示式 a − 4 + c 構建語法樹。在這個序列中，p₁、p₂、……p₅分別是指向識別符號 'a' 和 'c' 的符號表條目的指標。

p₁− mkleaf (id, entry a);
p₂− mkleaf (num, 4);
p₃− mknode ( ′−′, p₁, p₂)
p₄− mkleaf(id, entry c)
p₅− mknode(′+′, p₃, p₄);

樹以自底向上的方式生成。函式呼叫 mkleaf (id, entry a) 和 mkleaf (num 4) 為 a 和 4 構造葉子節點。指向這些節點的指標使用 p₁ 和 p₂ 儲存。然後，呼叫 mknodes (′−′, p₁, p₂ ) 建立內部節點，其中 a 和 4 的葉子作為子節點。語法樹將是

語法樹的語法制導翻譯

產生式	語義動作
E → E⁽¹⁾ + E⁽²⁾	{E. VAL = Node (+, E⁽¹⁾. VAL, E⁽²⁾. VAL)}
E → E⁽¹⁾ ∗ E⁽²⁾	{E. VAL = Node (∗, E⁽¹⁾. VAL, E⁽²⁾. VAL)})
E → (E⁽¹⁾)	{E. VAL = E⁽¹⁾. VAL}
E → E⁽¹⁾	{E. VAL = UNARY (−, E⁽¹⁾. VAL}
E → id	{E. VAL = Leaf (id)}