第三章 词法分析

简而言之，词法分析的任务就是从左到右逐个字符的对源程序进行扫描，产生一个个的单词符号

1. 对于词法分析器的要求

功能：输入源程序，输出单词符号

单词符号的种类：

  • 基本字：begin、repeat

  • 标识符：变量名、数组名、过程名

  • 常数

  • 运算符：+、-、*、/、...

  • 界符：逗号、分号、括号、空格

输出单词的形式：（单词种别，单词自身的值）

  • 单词种别通常用整数编码表示

    • 一码一符：基本字、运算符、界符。如：（while，-）

    • 多码一符：标识符、常数。如：（id，100）

注：词法分析器作为一个独立子程序，但是其处理不作为一遍。并非词法分析器一遍扫描源程序，然后将结果交给语法分析器。

2. 词法分析器的设计

2.1 词法分析器的结构

词法分析器的结构

2.2 输入、预处理

问题：可能某一个单词长度超过了扫描缓冲区，多出缓冲区的部分只能重新加载到缓冲区中，会导致之前加入的内容丢失

解决方法：两个半区互补使用，单词的长度限制 = 半区的长度

2.3 单词符号的识别：超前搜索

导致超前搜索的原因：由于语言规则不够严格，程序员可以把基本字当做标识符使用等，导致词法分析器需要去扫描到该代词的前面，才可以确定单词的种类。

对于第一行需要扫描到逗号才可以确定 DO 是基本字；对于第二行需要扫描到点才可以确定DO99K是标识符

几点限制就可以不必使用超前搜索

  • 所有基本字都是保留字；用户不能用它们作为标识符

  • 基本字作为特殊的标识符来处理，使用保留字表

  • 基本字、标识符和常数（或标号）之间没有确定的运算符或界符作为间隔，则必须使用一个空格作为间隔

2.4 状态转换图

状态转换图是一张有限方向图

  • 结点代表状态，用圆圈表示

  • 状态之间用箭弧连接，箭弧上的标记（字符）代表射出该状态下可能出现的输入字符或者字符类

  • 一张转换图只包含有限个状态，其中有一个为初态，至少要有一个终态

状态转换图可用于识别（接收）一定的字符串

  • 若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记付连接成的字（串）等于 α\alpha ，则称 α\alpha 为该状态转换图所识别（接收）

  • 识别标识符的状态转换图：

  • 识别整数的状态转换图：

  • 注：终态上一个 * 代表到达终态时回退一个字符

2.5 词法分析器的示例

助记符：直接用编码表示不便于记忆，因此用助记符来表示编码

状态转换图的实现

思想：每个状态结点对应一小段程序

具体方法：

  1. 对不含回路的分叉结点，可用一组IF-THEN-ELSE语句实现

    GetChar( );
if (IsLetter( ))
    {… 状态 j 的对应程序段… ;}
else if (IsDigit( ))
    {… 状态 k 的对应程序段… ;}
else if (ch=‘/’)
    {… 状态 l 的对应程序段… ;}
else
    {… 错误处理… ;}

  2. 对含回路的状态结点，可对应一段由 WHILE 结构和 IF 语句构成的程序

    GetChar( );
while (IsLetter( )or IsDigit( ))
    GetChar( );
… 状态 j 的对应程序段…

  3. 终态结点表示识别出某种单词符号 RETURN(C, VAL)

缺点：利用WHILE结构和IF语句列出所有情况，进行处理，这种方法一点都不灵活

状态转换图的代码一般化

  • 变量 curState 用于保存现有的状态

  • 用二维数组表示：stateTrans[state][char] 

curState = 初态GetChar();
GetChar();
while( stateTrans[curState][ch] 有定义){
    //存在后继状态，读入、拼接
    Concat();
    //转换入下一状态，读入下一字符
    curState= stateTrans[curState][ch];
    if cur_state是终态 then 返回 strToken中的单词
    GetChar( );
}

3. 正规表达式与有限自动机

通过介绍词法分析器的设计和代码实现，发现不难，但是很繁琐，很多步骤都是有规律的，所以是否有方法可以自动产生词法分析程序！

3.1 正规式和正规集

  • 正规集可以用正规表达式（简称正规式）表示

  • 正规式是表示正规集的一种方法

  • 一个字集合是正规集，当且仅当它可以用正规式表示

一句话总结：正规式是抽象出的规则，正规集是根据正规式具体实现的集合

例如：正规式：x + 1（x 为 整数）；正规集：所有整数加一的式子构成的集合

递归定义

  1. ϵ\epsilon 和 ϕ\phi 都是 ∑\sum 上的正规式，他们所表示的正规集为 {ϵ}\{ \epsilon \} 和 ϕ\phi

  2. 任何 a∈∑a \in \sum ， aa 是 ∑\sum 上的正规式，它所表示的正规集为 {a}\{ a \}

  3. 假定 e1e_1 和 e2e_2 都是 ∑\sum 上的正规式，他们所表示的正规集为 L(e1)L(e_1) 和 L(e2)L(e_2) ，则：

    • (e1∣e2)(e_1 \mid e_2) 为正规式，正规集为 L(e1)⋃L(e2)L(e_1)\bigcup L(e_2)

    • (e1⋅e2)(e_1 \cdot e_2) 为正规式，正规集为 L(e1)L(e2)L(e_1) L(e_2)

    • (e1)∗(e_1)^* 为正规式，正规集为 (L(e1))∗(L(e_1))^*

    仅由有限次使用上述三步骤而定义的表达式才是 ∑\sum 上的正规式，仅有这些正规式表示的字集才是 ∑\sum 上的正规集

等价变形

  • 交换律： e1∣e2=e2∣e1e_1 \mid e_2 = e_2 \mid e_1

  • 结合律： e1∣(e2∣e3)=(e1∣e2)∣e3e_1 \mid (e_2 \mid e_3) = (e_1 \mid e_2) \mid e_3

  • 结合律： e1(e2e3)=(e1e2)e3e_1 (e_2 e_3) = (e_1 e_2 ) e_3

  • 分配率： e1∣(e2∣e3)=e1e2∣e1e3e_1 \mid (e_2 \mid e_3) = e_1e_2 \mid e_1 e_3

  • 分配率： (e1∣e2)∣e3=e1e3∣e2e3(e_1 \mid e_2) \mid e_3 = e_1e_3 \mid e_2 e_3

  • eϵ=ϵe=ee\epsilon = \epsilon e = e

  • e1e2<>e2e1e_1e_2 <> e_2e_1

3.2 确定有限自动机（DFA）

确定有限自动机是对状态转化图进行形式化表达

(DFA)M=(S,∑,f,S0,F)(DFA)M = (S, \sum, f, S_0, F) 其中：

  1. SS ：有穷状态集

  2. ∑\sum ：输入字母表（有穷）

  3. ff ：状态转移函数，单值部分映射， f(S,a)=S′f(S, a) = S'，当前状态 SS ，输入字符 aa ，下一状态 S′S'

  4. S0∈SS_0 \in S 是唯一的一个初态

  5. F⊆SF \subseteq S ：终态集（可空）

3.3 非确定有限自动机（NFA）

(NFA)M=(S,∑,f,S0,F)(NFA)M = (S, \sum, f, S_0, F) 其中：

  1. SS ：有穷状态集

  2. ∑\sum ：输入字母表（有穷）

  3. ff ：状态转移函数，单值部分映射， f(S,a)=S′f(S, a) = S'，通过输入相同的字符 aa ，下一状态可能会有多个

  4. S0∈SS_0 \in S 非空初态集合

  5. F⊆SF \subseteq S ：终态集（可空）

3.4 DFA 和 NFA 的关系

区别：

  1. DFA 只有一个初态；NFA可以有多个初态

  2. DFA 的弧上只能是一个字符；NFA 弧上的标记可以是 ∑∗\sum ^* 中的一个字（甚至是一个正规式）

  3. DFA 的一个状态通过一个字符只能到达唯一的下个状态；NFA 中一个状态可以通过同一个字到达多个不同的下个状态

联系：

  1. DFA 是 NFA 的特例

  2. 对于任何两个有限自动机 MM 和 M′M' ，如果 L(M)=L(M′)L(M) = L(M') ，则称 MM 与 M′M'等价

  3. 重要结论：判定两个自动机等价性的算法存在

  4. 对于每个NFA M 存在一个DFA M'，使得 L(M)=L(M′)L(M) = L(M')

  5. DFA 与 NFA 描述能力相同！

  6. NFA：易于人工设计；DFA：易于计算机使用

3.5 NFA 转换为 DFA

  1. 添加新初态结点 XX 和终态结点 YY ， X,Y∉SX,Y \notin S ，从 XX 到 S0S_0 中任意状态结点连一条 ϵ\epsilon 箭弧，从 FF 中任意状态结点连一条 ϵ\epsilon 箭弧到 YY

    ⟶\longrightarrow

  2. 根据下面三条规则进行分裂，让箭弧上的标记变为单个字符

    ⟶\longrightarrow

  3. 确定化：消除 ϵ\epsilon 和下一状态唯一化（采用子集法）

    • 找出第一行第一列的 ϵ−closure({X})\epsilon - closure(\{X\}) ，并求出这一列的 IaI_a 和 IbI_b

    • 检查IaI_a 和 IbI_b 是否在表中的第一列出现，未曾出现的话，就加入第一列中进行计算

    • 重复上述过程，直至第二、三列的子集全部出现在第一列中为止

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

定理：

  • 对任何FA M，都存在一个正规式 rr ，使得 L(r)=L(M)L(r) = L(M)

  • 对任何正规式 rr ，都存在一个FA M ，使得 L(M)=L(r)L(M) = L(r)

3.7 NFA M 转化为 正规式 rr

  1. 同 NFA 转化为 DFA 的第一步骤

  2. NFA 转化为 DFA 的第二步骤的逆过程

  3. 通过第二步骤可以将 NFA 的所有箭弧化成一条，即可得出正规式 rr

3.8 正规式 rr 转化为 NFA M

  4. 还可以通过子集法将NFA 转化为 DFA

3.9 确定有限自动机的化简

两个状态等价：如果从状态 ss 出发能读出某个字 α\alpha 而停止于终态，那么同样，从 tt 出发也能读出 α\alpha 而停止于终态；反之亦然

化简基本思想：把 M 的状态集划分为一些不相交的子集，使得任何两个不同的子集的状态都是可区别的，而同一个子集的任何两个状态是等价的

第一步：首先划分为终态和非终态

第二步：对某个 I(i)I^{(i)} ，令 I(i)={S1,S2,⋯ ,Sk}I^{(i)} = \{ S_1, S_2, \cdots,S_k \} ，若存在一个输入字符 aa 使得 Ia(i)I_a^{(i)} 不会包含在现行 π\pi 的某个子集 I(j)I^{(j)} 中，则至少应把 I(i)I^{(i)} 分为两个部分。

3.10 正规文法

2型（上下文无关文法，非确定下推自动机）

  • A→βA \rightarrow \beta ，其中 A∈VN;β∈(VT⋃VN)∗A \in V_N ; \beta \in (V_T \bigcup V_N)^*

3型（正规文法，有限自动机）

  • 右线性文法

    • A→αB或者A→αA \rightarrow \alpha B 或者 A \rightarrow \alpha ，其中 α∈VT∗;A,B∈VN\alpha \in V_T^* ; A,B \in V_N

  • 左线性文法

    • A→Bα或者A→αA \rightarrow B\alpha 或者 A \rightarrow \alpha ，其中 α∈VT∗;A,B∈VN\alpha \in V_T^* ; A,B \in V_N

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

定理：

  • 对每一个右线性正规文法 GG 和左线性正规文法 GG ，都存在一个有限自动机 (FA) M，使得 L(M)=L(G)L(M) = L(G)

  • 对每一个FA M，都存在一个右线性正规文法 GRG_R 和左线性正规文法 GLG_L ，使得 L(M)=L(GR)=L(GL)L(M) = L(G_R) = L(G_L)

3.12 正规文法 转化为 有限自动机

右线性文法 →\rightarrow 有限自动机 （根据 A 经过 0 到达 B 的方法 连线）

→\rightarrow

左线性文法 →\rightarrow 有限自动机 （根据 C 经过 0 到达 F 的方法 连线）

→\rightarrow

3.13 总结

通过这一节所有的内容梳理了正规表达式、有限自动机之间的关系、联系和转换。

给出下面的图，一目了然

4. 词法分析器的自动产生 -- LEX

工作过程：

  • 首先，对每条识别规则 PiP_i 构造出一个相应的非确定有限自动机 MiM_i

  • 通过转化：NFA →\rightarrow DFA

  • 化简 DFA

可见 LEX 的工作过程就是我们上面总结的相互转化，它大大简化了词法分析过程，程序员只需要把正规式或者正规文法输入到 LEX 中，即可以自动生成出最简化的 DFA

Previous第二章 程序设计语言及其文法Next第四章 语法分析

Last updated

Was this helpful?