噢！我的編譯器 - Lexical Analysis Overview

前一篇 Introduction II 中我們提到編譯器主要的工作就是進行 分析 與 生成，而又可以再把工作細分為以下，本篇要討論的就是分析的第一步驟： 詞彙分析器 lexical analyzer

分析 (analysis):

• 詞彙分析器 (lexical analyzer)，亦稱 scanner，建立 symbol table
• 語法分析器 (syntax analyzer)，亦稱 parser
• 語意分析器 (semantic analyzer)
• 中間碼產生器 (intermediate code generator)
• 程式碼最佳化 (code optimizer) (optional & machine-independent)

Lexical analyzer 做了什麼？

lexical analyzer 是第一個拿到原始碼的，那它要做什麼呢？

就是判斷詞性囉！除了斷詞還需要做分類，那怎麼樣叫做斷詞呢？

舉個簡單的例子，a = b + 2;，我們可以拆成以下，也就是進行斷詞：

• a
• =
• b
• +
• 2
• ;

除了會除去空白，還有 Tab 鍵、註解、換行符號等等。另外，也同時根據換行符號得知行號，以做錯誤訊息與程式碼的對應。那分類呢？請見以下：

• a : identifier
• = : assign
• b : identifier
• + : plus
• 2 : number
• ; : semicolon

而遇到 identifier 時，就會把相關資訊插入 symbol table，所以現在 symbol table 會有 a, b, c 的資訊。

以上就是 lexical analyzer 所做的事情，接下來便會把整理好的資訊與 symbol table 提供給下一個 syntax analyzer 使用。

token, pattern 和 lexeme

有了基本概念後，先介紹三個名詞：

• token : 類別及其屬性，以 <token name,  optional attribute> 表示，如 a 就是 <id，pointer to symbol-table entry for a>
• pattern : 每個類別的格式，如被歸類到 number 這個類別底下的都是數值格式，而 literal 就是被 "" 所環繞的字串
• lexeme : 類別底下的斷詞，如上述的 id 底下有 a, b, c 三個 lexeme

token 跟 lexeme 的解釋很相像，可以用 class 跟 instance 的關係更清楚的說明。token 就像是 class，token name 就是 class 的名稱。而 lexeme 就像是 instance，同 class 可以創造出許多不同的 instances ，同理，同一個 token 可以有很多 lexeme，而這些 lexeme 的不同之處就是 optional attribute，但他們都符合這個 token 的 pattern。當然這種種資訊都會被紀錄在 symbol table 中，以便後面的人接續使用。

看看下表更清楚了：

token	pattern	sample lexeme
comparison	< or > or <= or >= or == or !=	<=, ==
id	字母後面跟著字母或數字	pi, abc, tmp1
number	數值常數	3.14159, 123
semicolon	;	;

Lexical errors

在 lexical 階段除錯是困難的，因為只單純的讀進程式並進行分類。因此，這裡除的錯是 拼字的錯，也就是沒有任何一個 token 的 pattern 符合這筆輸入時就是錯誤。那 lexical analyzer 如何處理這個錯誤呢？

龍書裡頭提到幾種修正辦法：

1. 刪掉已讀進的字元，直到剩餘字符合某 token 的 pattern
2. 僅刪掉一個字元
3. 插入缺少的字元
4. 替代某個字元
5. 交換某組相鄰字元的順序

當然，最單純的方法就是以 一種 修正辦法改正目前讀入的字串，以得到符合規範的 lexeme。但最常見的方法其實是依據整份原始碼進行修正，使得全部都是合法的 lexemes，這個實作上也就複雜的多囉！