C編譯器入門~想懂低階系統從自幹編譯器開始~
  • 譯者序
  • 前言
    • 符號與規範
    • 本書的開發環境
    • 關於作者
    • 結束前言之前
  • 機械語言與組譯器
    • CPU 與記憶體
    • 什麼是組譯器
    • C程式和所對應的組合語言
      • 簡單的範例
      • 包含呼叫函式的範例
    • 本章小結
  • 創造計算機等級的語言
    • 第1步:創造能編譯1個整數的語言
    • 第2步:製作可以算加減法的編譯器
    • 第3步:加入標記解析器(tokenizer)
    • 第4步:改良錯誤訊息
    • 文法的記法與遞迴下降分析法
      • 將文法結構表示為樹(tree)
      • 以生成規則定義文法
      • 以 BNF 描述生成規則
      • 簡單的生成規則
      • 以生成規則描述運算子的優先順序
      • 包含遞迴的生成規則
      • 遞迴下降語法分析
    • 堆疊機
      • 堆疊機的概念
      • 編譯成堆疊機指令
      • 以x86-64實作堆疊機的方法
    • 第5步:製作可進行四則運算的編譯器
    • 第6步:單項加與單項減
    • 第7步:比較運算子
      • 修改標記解析器
      • 新的文法
      • 產生組合語言指令
  • 分離編譯與連結
    • 分離編譯
      • 分離編譯與其必要性
      • 標頭檔的必要性與其內容
      • 連結錯誤
      • 全域變數的宣告與定義
    • 第8步:分割檔案與修改 Makefile
      • 分割檔案
      • 修改 Makefile
  • 函式與區域變數
    • 第9步:1個字的區域變數
      • 堆疊上的變數空間
      • 修改標記解析器
      • 修改分析器
      • 左邊值與右邊值
      • 從任意的記憶體位址取得其值
      • 修改指令產生器
      • 修改主函式
    • 第10步:複數文字的區域變數
    • 第11步:return
    • 1973年的C編譯器
Powered by GitBook
On this page

Was this helpful?

  1. 創造計算機等級的語言
  2. 文法的記法與遞迴下降分析法

簡單的生成規則

Previous以 BNF 描述生成規則Next以生成規則描述運算子的優先順序

Last updated 5 years ago

Was this helpful?

作為使用 EBNF 描述文法的範例,考慮下面的生成規則:

expr = num ("+" num | "-" num)*

num可以想成已經在其他的規則中被定義,是代表數值的符號的意思。在這個文法中,expr首先有一個num,隨後跟著0個以上的「+和num或-和num」。這個規則其實就是表達加減法算式的文法。

從expr開始展開,可以組合出任意的加減法的字串,舉例來說像1或10+5或42-30+25。底下為展開式:

1
expr → num → "1"
10+5
expr → num "+" num

     → "10" "+" "5"
42-30+25
expr → num "-" num "+" num

     → "42" "-" "30" "+" "2"

這樣的展開順序不只可以用箭頭表達,也可以用樹來表示。上列算式的語法樹如以下所示:

用樹結構來表示,就可以很清楚看出哪個非終端符號會展開成什麼樣子。

向上圖這樣和文法一一對應的語法樹也被稱為「具體語法樹」(concrete syntax tree)。這個說法在和抽象語法樹作對比的時候較常用到。

此外,上述的具體語法樹中,並沒有把加減法從左到右的規則表現在樹上。這類規則在此處說明的文法中,並不是以 EBNF 描述,而是在語言的規格書裡有加註「加減法必須從左到右計算」。分析器必須同時考慮 EBNF 和這些說明,讀進代表算式的標記列,妥當地建立能符合算式順序的抽象語法樹。

因此,在以上的文法中,EBNF 表現的具體語法樹和分析器所輸出的抽象語法樹其實看起來差滿多的。要定義出具體語法樹和抽象語法樹儘可能一致的文法不是不可能,但是該類文法會變得非常地冗長,會導致實作分析器時不知道該從何下手。上述的文法是在形式文法的嚴謹性,和以自然語言描述的易於理解上取得平衡,是一個較好上手的描述方式。

1的語法樹
10+5的語法樹
42-20+2的語法樹