编译原理 第三章 词法分析

编译原理 第三章 词法分析

3.1 词法分析器概述

3.1.1 词法分析器的功能

输入源程序字符串,每识别出一个单词,就产生其种别编码。

词法分析的基本功能

  • 预处理——过滤掉源程序中的无用成分
    • 注释、空格、换行等
  • 从左至右逐个字符地对源程序进行扫描
    • 按照语言的定义规则,将字符拼接成单词
    • 建立符号表记录用户自定义单词符号的信息
  • 词法错误检查

两种实现模式

  • 完全独立模式
    • 词法分析器作为编译的子系统
    • 增强编译程序的可移植性
  • 相对独立模式
    • 词法分析程序作为语法分析程序的子程序
    • 提高编译程序的效率

3.1.2 单词的类型和内部表示

单词的类型

  • 关键字
    • 基本字 / 保留字
    • if、while、bool、main 等
    • 一般不被用户重新定义
  • 标识符
    • 用户在设计源程序时自定义的名字
    • 变量名、数组名、过程名等
  • 常数
    • 整型、布尔型、字符型等
    • 12、3.14、true、'ABC' 等
  • 运算符
    • 算符
    • 算术运算符、逻辑运算符、关系运算符等
    • +、-、AND、OR 等
  • 分界符
    • 界符
    • 标点符号及一些特殊符号
    • ";"、"."、"/*" 等

单词的内部表示

词法分析器输出单词的内部表示,一般是二元式:(单词种别编码,单词的属性值)。

单词种别表示单词的种类,通常用整数表示。单词如何分类,如何编码,主要取决于处理上的方便。基本原则是,不同的单词能彼此区别且有唯一的表示。

如果一个种别只含有一个单词(如上表所示的关键字、算符和界符),则单词 的属性值没有必要给出,单词的种别码唯一的表示了这个单词。若一个种别含有多 个单词,则需要给出单词的属性值。

3.2 词法分析器的设计

3.2.1 总体设计

Figure 1 词法分析器
Figure 1 词法分析器
  • 将源程序字符串输入到缓冲区
  • 经预处理子程序处理一定长度的字符串后送入扫描缓冲区
  • 扫描器的工作从扫描缓冲区识别出一个个单词
  • 通过读入的首字符进行分类
  • 然后继续读入字符,识别关键字、标识符、常数以及算符和界符
  • 当扫描缓冲区中的字符串使用完后,再调用预处理子程序,将新的字符串送入扫描缓冲区

3.2.2 详细设计

输入和预处理

词法分析器工作的第一步是输入源程序字符串,一般存放在输入缓冲区中。

预处理子程序,处理长度为 N 的输入字符:

  • 滤掉源程序中的注释;
  • 去掉源程序中的无用字符;
  • 进行宏替换;
  • 实现文件包含的嵌入和条件编译的嵌入等。

扫描器对缓冲区进行扫描时一般使用两个指针:

  • 一个指向当前正在识别的单词的起始位置(起点指示器)
  • 一个用于向前搜索以寻找该单词的终点(搜索指示器)
  • 两个指针之间的符号串就是要识别的单词符号
  • 扫描缓冲区一般一分为二的两个区域
  • 如果单词搜索指针从单词起点出发搜索到半区的边界仍未达到单词的结尾,就应该调用预处理程序,将后续 N 个输入字符装进另外的半区

单词符号的识别

  • 标识符和关键字的识别
    • 首字符是字母
    • 遇到非字母数字时,标识符识别完成
    • 回退最后一个字符
    • 查找是否为关键字,是则返回关键字种别编码,否则标识符种别编码
  • 数值型常数的识别
    • 首字符是数字
    • 遇到 ".",继续读入(实数),遇到 "E" / "e",继续读入(指数),遇到其他非数字字符识别完毕
    • 回退最后一个字符
    • 返回整型常数或实型常数的种别编码
  • 字符型常数的识别
    • 首字符是单引号
    • 忽略单引号,开始识别字符常数
    • 读到下一个引号,识别结束
    • 返回字符常数及字符常数的种别编码
  • 算符和界符的识别
    • 首字符是 /
    • 下一字符是数字,则回退一个字符,返回 / 的种别编码
    • 下一字符是 *,开始识别注释,直到 */,无返回值
    • 对于 <、>、: 等符号,还需再读入一个符号,判别是否是双界符
    • 若是,返回种别编码,否返回单词的种别编码
  • 超前搜索和最长匹配
    • 为了识别一个更有意义的单词符号,在找到了可能是单词符号的起点或者构成了部分单词时,扫还要继续读入输入串,看是否能找到由更多符号所组成的单词(即长匹配)
    • 有时可能要扫描到 一个可以“断句”的符号(超前搜索),才能决定后一个扫描的符号不属于之前的符号串所构成的单词
    • 超前搜索符号通常是长匹配单词的结束标志,可以是空格符、回车符、制表 符等一些可以被预处理的符号,也可能是下一个单词符号的起始符

符号表及其操作

  • 识别标识符和常数后的各种信息,保存在符号表中
  • 符号表的每一项包含两部分内容
    • 一部分是用于存放标识符名称的名字栏,
    • 一部分是用于存放标识符有关信息的信息栏,其中,信息栏包括类型、值、内存地址等
  • 符号表的内容只有一小部分可以在词法分析阶段填写,如单词的名字和长度等,许多内容需要在编译的后续阶段填写

错误处理

词法分析阶段的错误通常是

  • 非法字符,程序字符集之外的字符
  • 关键字拼写错误
  • 注释或字符常数不闭合
  • 变量说明有重复

3.2.3 状态转换图

状态转换图是一个有限图,结点用圆圈表示,称为状态。状态之间用带箭头的弧线连接,称为边。

一张状态转换图只包含有限个状态(即有限个结点)。其中,有一个初态(用“⇒”表示), 至少有一个终态(用双圈表示)。

指针回退一个字符,将其退回给扫描缓冲 区,并在终态结点上标上星号*

Figure 2 状态转换图
Figure 2 状态转换图

3.2.4 L 语言词法分析器的设计与实现

Figure 3 词法分析器的输入和输出
Figure 3 词法分析器的输入和输出

数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//token 文件结构
typedef struct WordToken {
int label; //单词序号
char name[30]; //单词本身,假设长度为 30
int code; //单词种别编码
int addr; //单词在符号表中登记项的指针,仅用于标识符或常数,其他情况下为 0
} WT;

//符号表文件结构
typedef struct WordSymble {
int number; //序号
char name[30]; //名字,假设长度为 30
int type; //类型
…… //根据需要可添加其他相关信息栏
} WS;

词法分析器流程图

Figure 4 词法分析器流程图
Figure 4 词法分析器流程图

词法分析器的实现

  1. 读入源文件到缓冲区;
  2. 从缓冲区读入一个非空字符,列计数+1,继续读入字符(每读入一个字符, 列计数+1),直到一个单词读完(单词结束的标志是单词分隔符,如空格符号、换行符和界符等,但单词的分隔符不属于该单词) ;
  3. 通过首字符判断该单词属于标识符(含关键字)、常数还是其他单词符号, 并通过各类单词分析程序完成识别工作;
  4. 将识别出的单词及其种别编码写入 token 表中,并且,若该单词符号是标识 符或常数,也要将其有关信息填入符号表
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int sort(char ch) { 
if (isalpha(ch)) return 标识符;
//若是字母,则是标识符或关键字
else if (isdight(ch)) return 数值常数;
//若是数字,则是整数或实数
else if (ch == ′ / ′)) return 注释或除号;
//若是/,则是注释或除号
else if (ch == ′ \′ ′)) return 字符常数;
//若是′,则是字符常数
else if (ch == 其他界符)) return 界符;
//若是其他界符,则返回界符
else return error;
//否则出错处理,意味着出现了无法识别的字符
}

3.3 正规表达式与有限自动机

3.3.1 正规式与正规集

正规式和正规集的递归定义:

  • ε 和 Φ 都是 ∑ 上的正规式,它们所表示的正规集分别为 {ε} 和 Φ ;
  • 对任何 a∈∑,a 是 ∑ 上的一个正规式,它所表示的正规集为 {a};
  • 假定 U 和 V 都是 ∑ 上的正规式,它们所表示的正规集分别记为 L(U) 和L(V), 那么,(U | V)、(U• V) 和 U* 也都是正规式,它们所表示的正规集分别为 L(U)∪L(V)、 L(U)L(V)(连接积)和 (L(U))*(闭包)。

仅由有限次使用上述三步骤而得到的表达式才是 ∑ 上的正规式,仅由这些正规 式所表示的集合(即 ∑ 上的语言)才是∑上的正规集。

3.3.2 确定有限自动机(DFA)

用五元组 \(M=(S,\Sigma,\delta,s_0,F)\) 来表示:

  • S 是一个有限集,每个元素称为一个状态
  • Σ 是一个有穷字母表,每个元素是一个输入字符
  • δ 是状态转换函数,实在 $S S $ 上的单值部分映射,如 \(\delta (s_1,a)=s_2\) 表示当前状态 \(s_1\) 输入字符 a 后,转换到下一状态 \(s_2\),称 \(s_2\)\(s_1\) 的一个后继状态
  • \(s_0\) 是唯一的初态,且 \(s_0 \in S\)
  • F 是一个终态集,可以为空,且 \(F \subsetneq S\)

DFA 可以用状态转换矩阵表示,行表示状态,列表示输入字符。

对于 \(∑^*\) 中的任何字 α,若存在一条从初态结点到某一终态结点的通路,则称 α可为 DFA M所识别或接受。若 M 的初态结点同时又是终态结点,则空字 ε 可为 M 所识别。DFA M 所能识别的 字的全体记为 L(M)。

3.3.3 不确定有限自动机(NFA)

当一个状态遇到同一个输入符号时,可能有多种不同的转换。

用五元组 \(M=(S,\Sigma,\delta,S_0,F)\) 来表示:

  • S 是一个有限状态集
  • Σ 是一个有穷输入字母表
  • δ 是状态转换函数,实在 $S ^* S $ 上的子集的一个映射,即 \(\delta: S\times \Sigma ^* \rightarrow 2^S\)
  • \(S_0\),非空初态集,且 \(S_0 \in S\)
  • F 是一个终态集,可以为空,且 \(F \subsetneq S\)

对于 \(∑^*\) 中的任何字 α,若存在一条从初态结点到某一终态结点的通路,且这条 通路上所有弧的标记字依序连接成的字(忽略标记为 ε 的弧)等于 α,则称 α 可为 NFA M 所识别(读出或接受)。若 M 的某些结点既是初态结点又是终态结点,或者存在一条从某个初态结点到某个终态结点的通路,其上所有弧的标记均为 ε,则空字 ε 可为 M 所接受。NFA M 所能识别的字的全体记为 L(M)。

DFA 是 NFA 的特例。对于每个 NFA M,都存在一个 DFA M',使得 L(M) = L(M'),与某一 NFA 等价的 DFA 不唯一。

状态集合 \(I\) 的 ε- 闭包,记为 \(ε\_Closure(I)\),定义为:

  • \(q∈I\),则 \(q∈ε\_Closure(I)\)
  • \(q∈I\),则从 q 出发经任意条 ε 边而能到达的状态 q′ 都属于 \(ε\_Closure(I)\)

状态集合 \(I\) 的 α 弧转换,记为 \(I_α\),定义为:

  • \(I_α = ε\_Closure(J)\)
  • 其中,J 是所有那些可从 \(I\) 中的某一状态结点出发经过一条 α 弧而到达的状态的全体

将 NFA 确定化的两个步骤:

  1. 首先改造 NFA 的状态图
    1. 增加状态 X 和 Y,使其成为新的唯一的初态和终态。从 X 引 ε 弧到原初态 结点,从原终态结点引 ε 弧到 Y 结点。

    2. 依据 Figure 5 中的规则对状态图进行替换,不断重复这一过程,直到图中每 条边上的标记转化为 ∑ 上的单个符号或者 ε 为止。

      Figure 5 替换规则
      Figure 5 替换规则
  2. 其次,使用子集法将改造后的 NFA 确定化

    1. \(∑=\{a_1, … , a_k \}\),构造一个 k+1 列的状态转换表,行为状态,列为输入字符。置该表的首行首列为 \(ε\_Closure(X)\),X 为第一步完成后的唯一的开始状态。
    2. 若某行的第一列的状态已确定为 \(I\),则计算第 i+1(i = 1, 2, … , k)列的值为 \(I_{ai+1}\),然后,检查该行上的所有状态子集,看其是否已在第一列出现。若未出现, 则将其添加到后面的空行上。重复这一过程,直到所有状态子集均在第一列中出现为止。
    3. 将每个状态子集视为一个新的状态,即可得到一个 DFA。初态就是首行首列的状态,终态就是含有原有终态的所有状态。

3.3.4 正规文法与有限自动机的等价性

对于正规文法 G 和有限自动机 M,如果 L(G) = L(M),则称 G 和 M 是等价的。

  • 对任一右线性或左线性正规文法 G,都存在一个有限自动机 M,使得 L(M) = L(G);
  • 对任一有限自动机 M,都存在一个右线性正规文法 GR 和左线性正规文法 GL,使得 \(L(M) = L(G_R) = L(G_L)\)

正规文法转换为有限自动机

已知正规文法(右线性)\(G_R = (V_T, V_N, S, P)\),令 NFA M = (Q, ∑, δ, S, F),根据正规文法的 4 个部分求 NFA 的 5 个部分的方法是:

  • 输入字母表 ∑,为文法终结符号集合 \(V_T\)
  • 初始状态 S,为开始符号 S;
  • 状态集合 Q:增加一个终态 T,将 \(Q = T∪V_N\) 作为状态集合;
  • 终态集合 F:若 P 中含有产生式 S→ε,则 F = {T, S},否则,F = {T};
  • 状态转换函数 δ 的构造方法:
    • 对 P 中的产生式 \(A→aB\),δ(A, a) = B,画从 A 到 B 的弧,弧上标记 a;
    • 对 P 中的产生式 A→a,δ(A, a) = T,画从 A 到 T 的弧,弧上标记 a;
    • 对于 \(V_T\) 中的每个 a,\(δ(T, a) =\emptyset\),表示在终态下没有动作。

有限自动机转换为正规文法

已知 \(NFA \ \ M = (Q, ∑, δ, S_0, F)\),求等价的右线性正规文法 \(G_R = (V_T, V_N, S, P)\),根据 NFA 的 5 个部分求正规文法的 4 个部分,其方法是:

  • 终结符号集合 \(V_T\),为字母表 ∑;
  • 开始符号 S,为初始状态 \(S_0\)
  • 非终结符集合 \(V_N\),为有限自动机的状态集合 Q;
  • 产生式 P 的构造方法:对任何 a∈∑,A, B∈Q,若有 δ(A, a) = B,则
  • 当 B∉F 时,令 A→aB;
  • 当 B∈F 时,令 A→a | aB;
  • \(S_0∈F\) 时,令 \(S_0→ε\)

3.3.5 正规式与有限自动机的等价性

  • 对任何有限自动机 M,都存在一个正规式 r,使得 L(r) = L(M);
  • 对任何正规式 r,都存在一个有限自动机 M,使得 L(M) = L(r)。

不确定有限自动机转换为正规式

首先,在 M 的状态转换图上加入两个结点,一个为 X,另一个为 Y。从 X 用 ε 弧连接到 M 的所有初态结点,从 M 的所有终态结点用 ε 弧连接到 Y。

其次,逐步消去 M′中的所有结点,直到仅剩下 X 和 Y 为止。在消除过程中, 逐步用正规式来标记箭弧。只反复使用 Figure 6 中的替换规则:

Figure 6 替换规则
Figure 6 替换规则

正规式转换为不确定有限自动机

首先分析正规式 r,将其分解成子表达式,然后使用下面的规则 1-3,为 r 中的每 个基本符号(ε 或字母表符号)构造 NFA。然后,据 r 的语法结构,使用规则 4 将这些 NFA 归纳组合起来,直至获得整个正规式的 NFA。

  1. 对正规式 Φ 构造 NFA,如 Figure 7(a) 所示。
  2. 对于 ε 构造 NFA,如 Figure 7(b) 所示。显然,它识别 {ε}。
  3. 对 ∑ 中的每个符号 a 构造 NFA,如 Figure 7(c) 所示,它识别 {a}。
Figure 7(a) (b) (c)
Figure 7(a) (b) (c)
  1. 如果 N(s) 和 N(t) 分别是正规式 s 和 t 的 NFA,则:

    Figure 8 我不想写了
    Figure 8 我不想写了

3.3.6 DFA 的化简

寻找一个状态数少的 DFA M′,使得 L(M) = L(M′)

  • 每个正规集都可以由一个状态数少的 DFA 所识别
  • 消去 DFA 中多余或无用状态、并合并等价状态
    • 多余状态
      • 从该状态 没有通路能够到达终态
    • 等价状态
      • 假定 s 和 t 是 M 的两个不同状态,二者等价是指:如果从状态 s 出发能读出某个字 w 而停于终态,则从 t 出发也能读出同样的字 w 而停于终态
      • 一致性条件:s 和 t 同时为可接受状态或不可接受状态
      • 蔓延性条件:对所有输入符号,s 和 t 都能转换到等价的状态中

基本思想

分割法:把 DFA M 的状态分成一些不相交的子集,使得任何不同子集中的状态都是可区别的,而同一子集中的状态都是等价的。然后,从每个子集中选出一个状态作为代表,同时消去其他等价状态。具体过程:

  1. 将 M 的所有状态分成两个子集:终态集和非终态集;
  2. 考察每个子集,若发现某子集中的状态不等价,则将其划分为两个集合;
  3. 重复第 2 步,继续考察已得到的每个子集,直到没有任何一个子集需要继 续划分为止。此时,DFA 的状态被分割成若干个互不相交的子集;
  4. 从每个子集中选出一个状态作为代表,即可得到简 DFA。

注意事项

状态合并时需要注意以下两点:

  • 由于子集中的状态都是等价的,因此,要将原来进入(离开)该子集中每 个状态的弧改为进入(离开)所选的代表状态;
  • 含有原来初态的子集仍为初态,含有原来各终态的子集仍为终态。

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×