編譯器設計 - 詞法分析

---

---

詞法分析是編譯器的第一個階段。它接收來自語言預處理器的經過修改的原始碼，這些原始碼以句子的形式編寫。詞法分析器透過去除原始碼中的任何空格或註釋，將這些語法分解成一系列標記。

如果詞法分析器發現標記無效，它會生成錯誤。詞法分析器與語法分析器緊密協作。它從原始碼讀取字元流，檢查合法標記，並在語法分析器需要時將資料傳遞給它。

標記

詞素被稱為標記中的一系列字元（字母數字）。每個詞素要被識別為有效標記，都有一些預定義的規則。這些規則由語法規則定義，透過模式來表達。模式解釋了什麼可以是標記，這些模式透過正則表示式來定義。

在程式語言中，關鍵字、常量、識別符號、字串、數字、運算子和標點符號可以被視為標記。

例如，在 C 語言中，變數宣告行

int value = 100;

包含以下標記

int (keyword), value (identifier), = (operator), 100 (constant) and ; (symbol).

標記規範

讓我們瞭解語言理論如何處理以下術語

字母表

任何有限的符號集 {0,1} 都是一組二進位制字母表，{0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F} 是一組十六進位制字母表，{a-z, A-Z} 是一組英文字母表。

字串

任何有限的字母（字元）序列稱為字串。字串的長度是字母出現的總次數，例如，字串 tutorialspoint 的長度為 14，表示為 |tutorialspoint| = 14。沒有字母的字串，即長度為零的字串，稱為空字串，用 ε（epsilon）表示。

特殊符號

一個典型的高階語言包含以下符號：

語言

語言被認為是在某個有限字母集上的一組有限字串。計算機語言被認為是有限集，並且可以在它們上執行數學集合運算。有限語言可以透過正則表示式來描述。

正則表示式

詞法分析器只需要掃描和識別屬於手頭語言的有限集的有效字串/標記/詞素。它搜尋由語言規則定義的模式。

正則表示式能夠透過定義有限符號字串的模式來表達有限語言。由正則表示式定義的語法稱為正則語法。由正則語法定義的語言稱為正則語言。

正則表示式是指定模式的重要表示法。每個模式都匹配一組字串，因此正則表示式充當一組字串的名稱。程式語言標記可以透過正則語言來描述。正則表示式的規範是遞迴定義的一個例子。正則語言易於理解並且具有高效的實現。

正則表示式遵循許多代數定律，這些定律可用於將正則表示式操作為等價形式。

運算

語言上的各種運算為

• 兩個語言 L 和 M 的並集寫成

  L U M = {s | s 在 L 中或 s 在 M 中}

• 兩個語言 L 和 M 的連線寫成

  LM = {st | s 在 L 中且 t 在 M 中}

• 語言 L 的 Kleene 閉包寫成

  L* = 語言 L 的零次或多次出現。

表示法

如果 r 和 s 是分別表示語言 L(r) 和 L(s) 的正則表示式，則

• 並集：(r)|(s) 是表示 L(r) U L(s) 的正則表示式

• 連線：(r)(s) 是表示 L(r)L(s) 的正則表示式

• Kleene 閉包：(r)* 是表示 (L(r))* 的正則表示式

• (r) 是表示 L(r) 的正則表示式

優先順序和結合性

• *, 連線 (.) 和 |（管道符號）都是左結合的
• * 具有最高優先順序
• 連線 (.) 具有第二高優先順序。
• |（管道符號）具有最低優先順序。

用正則表示式表示語言的有效標記

如果 x 是一個正則表示式，則

x* 表示 x 的零次或多次出現。

即，它可以生成 { e, x, xx, xxx, xxxx, … }

x+ 表示 x 的一次或多次出現。

即，它可以生成 { x, xx, xxx, xxxx … } 或 x.x*

x? 表示 x 的最多一次出現

即，它可以生成 {x} 或 {e}。

[a-z] 是英文的所有小寫字母。

[A-Z] 是英文的所有大寫字母。

[0-9] 是數學中使用的所有自然數字。

使用正則表示式表示符號的出現

letter = [a – z] 或 [A – Z]

digit = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 或 [0-9]

sign = [ + | - ]

使用正則表示式表示語言標記

Decimal = (sign)^?(digit)⁺

Identifier = (letter)(letter | digit)*

詞法分析器剩下的唯一問題是如何驗證用於指定語言關鍵字模式的正則表示式的有效性。一個被廣泛接受的解決方案是使用有限自動機進行驗證。

有限自動機

有限自動機是一種狀態機，它以符號字串作為輸入並相應地更改其狀態。有限自動機是正則表示式的識別器。當正則表示式字串被饋送到有限自動機時，它會為每個字面量更改其狀態。如果輸入字串成功處理並且自動機達到其最終狀態，則它被接受，即，剛剛饋送的字串被稱為手頭語言的有效標記。

有限自動機的數學模型包括

• 有限狀態集 (Q)
• 有限輸入符號集 (Σ)
• 一個起始狀態 (q0)
• 一組最終狀態 (qf)
• 轉移函式 (δ)

轉移函式 (δ) 將有限狀態集 (Q) 對映到有限輸入符號集 (Σ)，Q × Σ ➔ Q

有限自動機構造

令 L(r) 為某個有限自動機 (FA) 識別的正則語言。

• 狀態：FA 的狀態用圓圈表示。狀態名稱寫在圓圈內。

• 起始狀態：自動機開始執行的狀態稱為起始狀態。起始狀態有一個指向它的箭頭。

• 中間狀態：所有中間狀態至少有兩個箭頭；一個指向它，另一個從它指向。

• 最終狀態：如果輸入字串成功解析，則期望自動機處於此狀態。最終狀態用雙圓圈表示。它可以有任何奇數個指向它的箭頭和偶數個從它指向的箭頭。奇數箭頭的數量比偶數箭頭多一個，即奇數 = 偶數 + 1。

• 轉移：當找到輸入中的所需符號時，就會發生從一個狀態到另一個狀態的轉移。在轉移時，自動機可以移動到下一個狀態或保持在同一狀態。從一個狀態到另一個狀態的移動顯示為一個有向箭頭，其中箭頭指向目標狀態。如果自動機保持在同一狀態，則繪製一個從狀態到自身的箭頭。

示例：我們假設 FA 接受以數字 1 結尾的任何三位二進位制值。FA = {Q(q₀, q_f), Σ(0,1), q₀, q_f, δ}

最長匹配規則

當詞法分析器讀取原始碼時，它逐個字元掃描程式碼；當遇到空格、運算子符號或特殊符號時，它會確定一個單詞已完成。

例如

int intvalue;

在掃描到“int”之前的兩個詞素時，詞法分析器無法確定它是一個關鍵字int還是識別符號 int 值的開頭字母。

最長匹配規則規定，應根據所有可用標記中最長的匹配來確定掃描的詞素。

詞法分析器還遵循規則優先順序，其中語言的保留字（例如，關鍵字）優先於使用者輸入。也就是說，如果詞法分析器找到與任何現有保留字匹配的詞素，它應該生成錯誤。