編譯原理筆記2：詞法分析基礎與模式的形式化描述

詞法分析，是詞法分析器将源程式轉化為線性記号流的過程。該過程中會對各種符号進行分類，比如将變量名換為辨別符。

詞法分析的含義：

1. 規定詞形成的規則，定義什麼詞是合法的；
2. 根據規則識别輸入的序列（詞法分析），識别合法單詞、指出非法的輸入序列。

詞法分析

模式、記号、單詞

• 模式（Pattern）： 産生和識别元素的規則。也就是定義的詞法規則；
• 記号（Token）： 按照某個模式（即，規則）識别出的（一組）元素。進行詞法分析時，詞法分析器将程式代碼中的各個部分轉為一個個記号的過程，就是根據規則得到一個記号流的過程；
• 單詞（lexeme）： 被識别出的元素自身的值（一個），也稱為詞值。可以了解為源程式中一個個的字元串。

上面三個詞放一起了解：源程式裡面是一個個單詞，我們使用“模式”這個規則，對單詞進行識别、分類，把它們放到相應的記号裡面去。記号是一堆單詞，Pascal 語言的記号舉例如下：

記号的類别	單詞舉例	模式的非形式化描述
const（01）	const
if（03）	if
relation（81）	<, <=, =, <>, >, >=	<, <=, =, ...
id（82）	pi, count, D2	字母打頭的字母數字串
num（83）	3.1416, 0, 6.02E23	任何數值常數
literal（84）	"core dumped"	雙引号間的任意字元串
comment	{ x is an integer }	花括号間的任意字元串

• id: 辨別符記号。這裡“字母”需要進行嚴格的形式化描述；
• literal：字面量；
• comment：注釋

單詞的基本分類

• 關鍵字 kw（keyword， reserved word）
• 辨別符 id （identifier）
• 字面量 literal
• 特殊符号 ks （key symbol， special symbol）

例：

記号

記号 = 記号的類别 + 記号的屬性

例如，mycount > 25，由三個記号組成。類别就是上表中對應的類别編号

詞法分析器的作用與工作方式

編譯器中隻有該部分直接接觸源代碼，其他的部分都是通過使用之前的工作成果來間接接觸源代碼。詞法分析器要進行的工作包括：

1. 去掉注釋、空格一類的無用部分；
2. 處理和平台有關的輸入，比如檔案結束符的不同表示；
3. 根據模式識别記号，交給文法分析器；（主要功能）
4. 調用符号表管理器/出錯處理器，進行相關處理。

工作方式：

1. 詞法分析器單獨進行掃描，生成記号流。再将整個記号流交給文法分析器；
2. 詞法分析器作為文法分析器的子程式進行工作，文法分析器調用詞法分析器去讀源程式，得到詞法分析器傳回的記号就拿來構造文法樹。然後用掉了這個記号就再去調用詞法分析器讀新的記号，如此重複；
3. 詞法、文法分析器并行工作。兩者有一個共享的記号流，前者不停讀程式、把記号放入記号流，後者不停取記号流來構造文法樹。

模式的形式化描述

字元串與語言

從詞法分析角度來看，語言是記号的集合。

語言 L 是有限字母表 Σ 上有限長度字元串的集合，字母表是字元的集合。

字母表中的字元能夠組成字元串。

例：字母表 Σ={ a, b, c }，則其上的語言 L = { ε, a, b, c, aa, ab, ac, ba, bb, bc, ... } （ε為空串，長度為0）

字元串的基本概念

術語	示例
|S|	|abc| = 3
ε	|ε| = 0
S1S2	abc def = abcdef
Sn	(abc)3 = abcabcabc
S 的字首 X	abc 的字首有：ε, a, ab, abc
S 的字尾 X	abc 的字尾有：ε, c, bc, abc
S 的子串 X	abc 的子串有：ε, a, b, c, ...
S 的真字首	abc 的真字首有：a, ab（去掉空和全）
S 的真字尾	（去掉空和全）
S 的真子串
S 的子序列 X	abdf 是 abcdef 的一個子序列（和原序列順序相同，可去掉一些字母）

	意義
Φ	空集合
{ ε }	空串是唯一進制素
X = L ∪ M	并： X = { s| s∈L or S ∈M }
X = L ∩ M	交：X = { s | s∈L and S ∈M }
X = LM	連接配接： X = { st|s∈L and t ∈ M }
X = L*	(星)閉包：X= L0∪L1∪L2∪...
X = L+	正閉包：X= L1∪L2∪L3∪...

若 L = {a, b}, M = {c, d}, 則 LM = {ac, bc, ad, bd}, L∪M = Φ

L* = { ε, a, b, aa, bb, ab, ba, aaa, ... }

L+ = { a, b, aa, bb, ab, ba, aaa, ... }

正規式與正規集

正規式是用來描述詞法規則的，也就是描述：記号該長成什麼樣子、數字該長成什麼樣子之類。

正規式（Regular Expression，也叫正規表達式）是在字母表之上的集合——正規式表示集合。

正規式表示的集合叫做正規集，而正規集是語言，是以正規式表示語言。

比如有個正規式是字母 a，那麼正規式 a 表示集合 {a}，集合 {a} 就是語言 L(a)。

正規式表示正規集，正規集是與正規式對應的語言。

這兩個概念是詞法分析的基礎。

正規式和正規集的遞歸定義

Σ 是有限字母表，則其上的正規式及其表示的集合（即正規集）遞歸定義如下：

1. ε 是正規式，其表示集合（正規集） L(ε) = {ε}
2. 若 a 是 Σ 上的字元，則 a 是正規式，它表示集合 L(a)={a}
3. 若正規式 r 和 s 分别表示集合 L(r) 和 L(s)，則
   1. r|s 是正規式，表示集合 L(r) ∪ L(s)（“|”在正規式中表示“或”，也可以寫作 r + s ）
   2. rs 是正規式，表示集合 L(r)L(s)（直接将兩個語言拼接起來，也可以寫作 r·s）
   3. r （正規式是一個星閉包）也是正規式，表示集合(L(r))（L(r)這個語言進行星閉包）
   4. (r) 是正規式，表示的集合仍然是 L(r)（也就是說正規式 r 外面括上括号得到的 (r) 仍然是正規式，加括号可以用來改變運算次序）

語言是字母表上字元串的集合，而正規式是語言，是以正規式是字母表上字元串的集合。

可以用正規式描述的語言，就是正規語言或正規集

定義的擴充說明

1. 運算有優先級和結合性
   • 三種運算都有左結合的性質（左結合的意思是，當多個同優先級符号連寫時是從左往右算。如果從右往左算就叫右結合）
   • 優先級從高到低：閉包、連接配接、或

正規式中不必要的括号（去掉了也不影響運算順序）是可以省略的。

例：正規式： a|b*c 表示的語言有以下兩種情況：

1. 表示一個串：a
2. 表示另一個串：以 0 到多個 b 開頭，以 c 結尾

1. 正規式的等價

長得不同的正規式可以表示同一個正規集（就像加法中的1+3、2+2都可以表示4一樣），即，同一個正規集可以對應多個正規式。

正規式等價

定義：若正規式 P、Q 表示了同一個正規集，則稱 P、Q 是等價的，記為 P = Q。

【例】： 設字母表 Σ={a, b, c}， 則 Σ 上有：

正規式	正規集
a, b, c	{a}, {b}, {c}
a|b, b|a	{a}∪{b} = {a, b}
a(a|b)*	{a, aa, ab, aba, abb, aab, ...}，以 a 為首的 ab 串
Σ*	{ε, a, b, c, aa, ab, ac, ba, bb, bc, ...}

【例】：令 L(x) = {a, b}, L(y) = {c, d}

     則 L(x|y) = {a, b, c, d}

          L(y, x) = {a, b, c, d}

判斷等價性，可以根據定義，證明兩個正規式是否能表達同一個集合；也可以使用正規式的代數性質進行運算比較：

公理
r|s = s|r	( r s ) t = r( s t )
r|( s|t ) = ( r|s )|t	ε r = r ， r ε = r
r ( s|t ) = r s | r t	r* = ( r+ | ε )
( s|t ) r = s r | t r	r** = r*

簡言之，就是：

• |可交換、可結合；
• · 對 | 可配置設定；
• · 可結合；
• 幂等

記号的說明

先複讀一遍模式、記号的概念：

• 模式（Pattern）： 産生和識别元素的規則，就是定義的詞法規則；
• 記号（Token）： 按照某個模式（或規則）識别出的元素（一組）。進行詞法分析時，将程式轉為一個個的記号，就是根據規則得到一個記号流；

正規式可以用于嚴格地規定記号的模式。用正規式說明記号的公式：

記号=正規式 讀作“記号定義為正規式” / “記号是正規式”。不引起混淆的情況下，可以直接把說明記号的公式叫做正規式/規則

e.g. id = a ( a | b )* 讀作：“id定義為a(a|b)*”（這裡的 id 就是一個辨別符了。定義為a開頭的ab串）

【例】記号 relation、id、num 分别是 Pascal 的關系運算符、辨別符和無符号數，它們的正規式表示如下：

relation = < | <= | <> | > | >= | =
    
id = (a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z)
(a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z|0|1|2|3|4|5|6|7|8|9)*
    
num = (0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*
      (ε|.(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)
      (ε|E(+|-|ε)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)           

其中，一些東西可以進行簡化描述

簡化描述

1. 正閉包：r 表示 L(r) 的正規式，那麼 r+ 就表示 (L(r))+的正規式。

即：r+ = rr = r*r, r = r+|ε

比如：(0|1...|9)(0|1...|9)* 可以化簡為 (0|1...|9)+

1. 可預設：r? 表示 L(r)∪{ε} 的正規式。

即：r? = r|ε

比如： E(+|-|ε) 可改寫為：E(+|-)?

上面這些運算中的 +、? 、* 的結合性、優先級相同。

1. 字元組。字元組是正規式的一種形式：對于隻由 | 構成的正規表達式 r，可以改寫為[r']：
   • r' 可以枚舉：正規式 r = a|b|c 等價于 [abc]
   • r' 可以分段：[0123456789abcdefghijklmnopqrstuvwxyz]等價于[0-9a-z]
2. 非字元組。這裡的“非”指的是非運算。也就是去掉某部分：

若 [r] 是字元組形式的正規式，則 [^r] 表示 Σ -L(r) 的正規式，例如：

若 Σ={a, b, c, d, e, f, g}，則 L(^abc)={d, e, f, g}

1. 輔助定義。就是給已有的正規式起個名字，以後可以直接用這個名字指代。

   

（如果 digits 不加花括号，那 digits 就是“ digittttt.... ”）

optional_fraction：可選的小數位。小數點如果不加雙引号，在這裡表示任意一個字元。

optional_exponent：可選指數

上面的是 id，下面的是 num