第二章 词法分析

词法分析器的任务是把构成源程序的字符流翻译成词法记号流。构造词法分析器的一种简单办法是用状态转换图来描述源语言记号的结构，然后手工把这种状态转换图翻译成为识别词法记号的程序。

2.1词法记号及属性

2.1.1 词法记号、模式、词法单元

记号名	词法单元例举	模式的非形式描述
if	if	字符i, f
for	for	字符f, o, r
relation	< , <= , = , …	< 或 <= 或 = 或 …
id	sum, count, D5	由字母开头的字母数字串
number	3.1, 10, 2.8 E12	任何数值常数
literal	“seg. error”	引号“和”之间的任意字符串，但引号本身除外

• 历史上词法定义中的一些问题
  • 忽略空格带来的困难
    DO 8 I = 3. 75
    DO 8 I = 3, 75
    DO8I = 3. 75
  • 关键字不保留
    IF THEN THEN THEN=ELSE；ELSE …
• 关键字、保留字和标准标识符的区别
  • 保留字是语言预先确定了含义的词法单元
  • 标准标识符也是预先确定了含义的标识符，但程序可以重新声明它的含义

2.1.2 词法记号的属性

position = initial + rate * 60的记号和属性值：
<id，指向符号表中position条目的指针>

<id，指向符号表中initial条目的指针>

<id，指向符号表中rate条目的指针>

<number，整数值60>

2.1.3 词法错误

• 词法分析器对源程序采取非常局部的观点
• 难以发现下面的错误
  fi (a == f (x) ) …
• 在实数是a.b格式下，可以发现下面的错误
  123.
• 紧急方式的错误恢复
• 错误修补

2.2 词法记号的描述与识别

2.2.1 串和语言

• 概念

  • 字母表：符号的有限集合， 例：Σ = {0, 1}
  • 串：符号的有穷序列，例：0110, ε
  • 语言：字母表上的一个串集
    {ε, 0, 00, 000, …}, {ε}, ∅
  • 句子：属于语言的串

• 串的运算

  • 连接 xy，sε = εs = s
  • 积（指数） s⁰为ε，sⁱ为s^{i -1}s（i > 0）

• 语言的运算

  • 和：L ∪ M = {s | s ∈L 或 s ∈ M }
  • 连接：LM = {st | s ∈ L 且 t ∈ M}
  • 指数：L⁰是{ε }，Lⁱ是L^{i -1}L
  • 闭包：L^* = L⁰ ∪ L¹ ∪ L² ∪ …
  • 正闭包： L⁺ = L¹ ∪ L² ∪ …

    2.2.2 正规式

• 正规式用来表示简单的语言，叫做正规集。

  正规式	定义的语言	备注
  ε	{ε}
  a	{a}	a ∈ Σ
  (r) | (s)	L(r)∪L(s)	r和s是正规式
  (r)(s)	L(r)L(s)	r和s是正规式
  (r)*	(L(r))*	r是正规式
  (r)	L(r)	r是正规式

• 正规式的例子 Σ = {a, b}

  • a | b {a, b}
  • (a | b) (a | b ) {aa, ab, ba, bb}
  • aa | ab | ba | bb {aa, ab, ba, bb}
  • a^* 由字母a构成的所有串集
  • (a | b)^* 由a和b构成的所有串集

• 复杂的例子

  • ( 00|11| ( (01|10) (00|11) (01|10))) 句子：01001101000010000010111001

2.2.3 正规定义

• 对正规式命名，使表示简洁
  d₁ → r₁
  d₂ → r₂
  . . .
  d_n → r_n

• 各个d_i的名字都不同

• 每个r_i都是Σ ∪{ d₁, d₂, …, d_i-1 }上的正规式

• 正规定义的例子

  • C语言的标识符是字母、数字和下划线组成的串
    letter_ → A | B | … | Z | a | b | … | z | _
    digit → 0 | 1 | … | 9
    id → letter_(letter_ |digit)^*
  • 无符号数集合，例1946,11.28,63E8,1.99E6
    digit → 0 | 1 | … | 9
    digits → digit digit^*
    optional_fraction → .digits|ε
    optional_exponent → ( E ( + | - | ε ) digits ) | ε
    number → digits optional_fraction optional_exponent
  • 简化表示
    number → digit⁺ (.digit⁺)? (E(+|-)? digit⁺)?

2.2.4

• 关系算符的转换图

图片3.1

• 标识符和保留字的转换图

图片3.2

• 无符号数的转换图

图片3.3

• 空白的转换图
  图片3.4

2.3 有限自动机

2.3.1不确定的有限自动机（简称NFA）

是一个数学模型，它包括：
1、状态集合S
2、输入符号集合Σ
3、转换函数move : S × ( Σ∪{ε} ) → P(S)
4、状态s⁰是开始状态
5、F ⊆ S是接受状态集合

2.3.2 确定的有限自动机（简称DFA)

一个数学模型，包括：
1、状态集合S
2、输入字母表Σ
3、转换函数move : S × Σ → S
4、唯一的初态 s∈ S
5、终态集合F ⊆ S

2.3.3 NFA到DFA的变换

子集构造法
1、DFA的一个状态是NFA的一个状态集合
2、读了输入a₁ a₂ … a_n后，NFA能到达的所有状态：s₁, s₂, …, s_k，则DFA到达状态{s₁, s₂, …, s_k}

2.3.4 DFA的化简

• 死状态
• 分割算法

2.4 从正规式到有限自动机

• 从正规式建立识别器
  • 从正规式构造NFA
    用语法制导的算法，它用正规式语法结构来指导构造过程
  • 把NFA变成DFA （子集构造法）
  • 将DFA化简 （合并不可区别状态）

2.5 词法分析器的生成器

• Lex的使用。