將文法結構表示為樹（tree）
實作程式語言的分析器時，輸入為扁平的標記列，而輸出為表示巢狀結構的樹式非常常見的作法。本書的構造也是如此。
C語言的if或while文法可以是巢狀的，也很適合用樹結構來表現此類架構。
算式中，有括號內必須先計算、先乘除後加減的結構。這樣的結構乍看之下可能不像樹結構，但是用樹來表示的話可以非常簡單地代表算式的結構。舉例來說 1*(2+3)可以想成用底下的樹來表示：
我們從最邊緣照順序開始計算的話，上述的樹，可以代表1乘上2+3的算式。也就是說，上述的樹是以樹的結構代表了 1*(2+3)的具體計算順序。
再用一個例子來說明。以下式表示7-3-3的樹：
上述的樹是以樹的結構表達「減法必須從左至右計算」規則的結果。也就是說，上述的樹是代表(7-3)-3 = 1而不是7-(3-3) = 7。如果是後者的話，其代表的樹應該是右邊會比較深，而不是左邊。
必須從左至右計算的運算子為「左結合」運算子，而必須從右邊開始計算的運算子叫作「右結合」運算子。在C裡，除了=（代入）之外，大部分的運算子都是左結合。
以樹來表達的話，加深樹的深度可以表達任意長度的算式。底下的樹為代表1*2+3*4*5的樹。
上述的樹叫作「語法樹」（syntax tree）。其中，去除分組用的括號等冗長的元素，儘可能精減的語法樹稱為「抽象語法樹」（abstract syntax tree, AST）。上述的語法樹都可以轉成抽象語法樹。
抽象語法樹是編譯器的內部結構，可以依據實作上的方便來定義。但像是加法或乘法等算術運算子都是定義為左邊和右邊兩邊計算，採用二分樹比較自然。但是，如函式引數等照順序執行、可以有任意長度的要素，則是用可以表示所有要素的扁平樹結構比較自然。
語法分析的目標就是建立抽象語法樹。編譯器首先會進行語法分析，把輸入的標記列轉換成抽象語法樹，再把抽象語法樹轉換成組合語言指令。
Last updated
