iT邦幫忙

2024 iThome 鐵人賽

DAY 15
0

零・一版語法規則整理如下:

音界咒檔 = 音界咒・檔案結尾

音界咒     = 句
          | 句・音界咒

句        = 變數宣告式
          | 算式

變數宣告式 = "元"・"・"・變數・"="・算式

算式      = 乘除式・重複乘除式

重複乘除式 = +・重複乘除式
         | −・重複乘除式
         | e

乘除式    = 原子式・重複原子式

重複原子式 = *・重複乘除式
         | /・重複乘除式
         | e

原子式    = 數字
         | 變數
         | "("・算式・")"

抽象語法樹

依照回溯剖析算法(或是其他剖析算法),吾人能得到一棵紀錄了所有生成符展開點的語法樹。然而,語法樹中的許多細節並無實際意義。

變數宣告式為例,元・甲=(1),若嚴格按照展開規則,會得到如下繁複的語法樹:

變數宣告式具體語法樹

這種嚴格按照語法規則展開的語法樹,吾人稱其為「具體語法樹」,然而,具體語法樹中,某些節點含有的資訊對接下來的編譯器後端毫無用處,例如這些協助詞法分隔的符號,在任何變數宣告式裡都有,所以沒有紀錄的意義。另外,以如此深的樹來紀錄(1)這個算式也是極度冗餘的,原子式重複原子式...這些玩意兒完全是為了消除左遞迴跟歧義才製造出來的,語義上僅需知道它是數字1就夠了。

省略不重要的資訊後,可以得到:

變數宣告式抽象語法樹

這種精簡後,但在語義上沒有損失的語法樹,被稱為抽象語法樹。若語境明確,也可以直接叫語法樹。


上一篇
零.一版剖析器(三)回溯剖析與左遞迴問題
下一篇
零.一版剖析器(五)實作遞迴下降剖析器
系列文
離塵指引.卷之一.試結丹:程式語言自舉32
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言