编译原理与技术 词法分析 (2) 2018/12/30 《编译原理与技术》讲义

有限自动机 有限自动机（Finite Automata－FA）是种更一般化的状态转换图。分为NFA和DFA。 词法分析器自动生成： 非确定有限自动机 确定的有限自动机 2018/12/30 《编译原理与技术》讲义

非确定有限自动机－NFA NFA Mn 是一个五元组 Mn =(, S, S0,F,)， 其中： －有限字母表（输入符号集） S0－非空初态集合，S0S F－终态集合，F S －状态转换函数，S x *  2S 2018/12/30 《编译原理与技术》讲义

确定的有限自动机－DFA DFA Md 是一个五元组 Md =(, S, S0,F,)， 其中: , S, S0,F 同NFA中的定义，而定义如下：  ：S x   S ， 为一单值映射函数。 2018/12/30 《编译原理与技术》讲义

有限自动机的表示 1）状态转换图 开始状态 一般状态 终态  a (s,a)=t (s,)=t s t s t 2018/12/30 《编译原理与技术》讲义

有限自动机的表示 2）状态转换矩阵（表） * 状态(集) a b … Si {Sj} Sj (Si,a) = {Sj} 2018/12/30 《编译原理与技术》讲义

有限自动机的表示 e.g.7 NFA Mn =(, S, S0,F,)，其中： (S1,0)= ∅ (S1,1)= {S2}  = { 0,1 } , S = {S0, S1 , S2 , S3 , S4 }，F={S2 , S4} (S0,0)= {S0, S3 } (S0,1)= {S0, S1 } (S1,0)= ∅ (S1,1)= {S2} (S2,0)= {S2} (S2,1)= {S2} (S3,0)= {S4} (S3,1)= ∅ (S4,0)= {S4} (S4,1)= {S4} 2018/12/30 《编译原理与技术》讲义

有限自动机的表示 e.g.7 中NFA的状态转换图如下： 0,1 0,1 S0 S3 S4 1 S1 1 S2 0,1 2018/12/30 S0 S3 S4 1 S1 1 S2 0,1 2018/12/30 《编译原理与技术》讲义

有限自动机的表示 e.g.7 中NFA的状态转换矩阵（表）如下： * 状态(集) 1 S0 {S0, S3 } {S0, S1 } S1 1 S0 {S0, S3 } {S0, S1 } S1 ∅ {S2} S2 S3 {S4} S4 2018/12/30 《编译原理与技术》讲义

有限自动机识别的语言 e.g.8 下面FA识别（接受）的串是什么？ 1 S0 S1 S2 FA识别（接受）串∈* , 如果存在一个从FA的初态到某个终态的（状态）转换路径，该路径上所有标记的字符依次连接为。 FA M 所识别的语言 L(M) L(M) = { | M 识别 ∈* } 2018/12/30 《编译原理与技术》讲义

有限自动机识别的语言 e.g.9 下面DFA M识别的语言L(M)是什么？ S2 S1 1 S0 S3 S 2018/12/30 1 S0 S3 S 2018/12/30 《编译原理与技术》讲义

有限自动机识别的语言 e.g.9 L(M) = {含偶数个0和偶数个1的0,1串} S0 偶数个“0”与偶数个“1”的0,1串 S2 S1 1 S0 S3 S1 偶数个“0”与奇数个“1”的0,1串 S2 奇数个“0”与偶数个“1”的0,1串 S3 奇数个“0”与奇数个“1”的0,1串 2018/12/30 《编译原理与技术》讲义

有限自动机识别的语言 e.g.10 下面DFA M识别的语言L(M)是什么？ 1 1 S0 S1 S2 1 2018/12/30 1 1 S0 S1 S2 1 2018/12/30 《编译原理与技术》讲义

有限自动机识别的语言 e.g.10 L(M) = { 能被“3”整除的二进制数(串) } S0 能被3整除 S2 S1 S0 1 S1 1 S1 被3整除…余1 S2 被3整除…余2 2018/12/30 《编译原理与技术》讲义

有限自动机识别的语言 e.g.10 L(M) = { 能被“3”整除的二进制数(串) } 二进制串 10010 , 即十进制18的识别过程： 1 S0 S1 S2 1 输入串 1 1 2018/12/30 《编译原理与技术》讲义

比较 DFA 和 NFA（1） DFA NFA  ：S x   S  ：S x   2S 没有 转换 有 转换 对∈*的“识别”路径可能存在多条不同的路径 对于正规式R，均有DFA Md和NFA Mn，使得L(Md) = L(Mn)=L(R)，即两者识别正规语言能力相同（等价） 2018/12/30 《编译原理与技术》讲义

比较 DFA 和 NFA（2） DFA NFA 容易实现－当输入串结束时（或不存在相应状态转换）时，若当前状态为终态即为接受“已读入”的串，否则拒绝。 由于面临同样输入符号存在多重状态转换或存在转换的选择，实现较为复杂。一般地，NFA接受串如果它在读完串后“能够”到达某终态。 识别相同正规集的DFA和NFA： DFA的规模（在状态数和状态转换上）一般比相应的NFA复杂（可以达到指数级） 2018/12/30 《编译原理与技术》讲义

比较 DFA 和 NFA（3） e.g.11 识别正规式（0|1）*01的DFA和NFA NFA : DFA : S2 S1 S0 1 S2 1 NFA : S2 S1 S0 1 DFA : 2018/12/30 《编译原理与技术》讲义

只引入初态S0和终态S1，他们之间无状态转换 正规式与有限自动机 对于上正规式R，存在一个NFA M，使得 L(M) = L(R) ，反之亦然。 Thopmson 方法： R= R=∅ R=a∈ 只引入初态S0和终态S1，他们之间无状态转换 S0 S0 S1 a S0 S1 2018/12/30 《编译原理与技术》讲义

正规式与有限自动机 R= R1 | R2 （1） R1对应的NFA,Si为初态，fi为终态 Si fi Sj fj R2对应的NFA,Sj为初态，fj为终态 2018/12/30 《编译原理与技术》讲义

引入新的初态S0和(S0,)=Si和(S0,)=Sj 正规式与有限自动机 R= R1 | R2 （2） Si fi  S0  Sj fj 引入新的初态S0和(S0,)=Si和(S0,)=Sj 2018/12/30 《编译原理与技术》讲义

引入新的终态f0和(fi,)=f0和(fj,)=f0 正规式与有限自动机 R= R1 | R2 （3） Si fi   S0 f0   Sj fj 引入新的终态f0和(fi,)=f0和(fj,)=f0 2018/12/30 《编译原理与技术》讲义

正规式与有限自动机 R= R1 · R2 （1） Si fi Sj fj R1对应的NFA,Si为初态，fi为终态 R2对应的NFA,Sj为初态，fj为终态 2018/12/30 《编译原理与技术》讲义

正规式与有限自动机 R= R1 · R2 （2）  Si fi Sj fj S0 引入新的初态S0和(S0,)=Si 2018/12/30 《编译原理与技术》讲义

正规式与有限自动机 R= R1 · R2 （3）   Si fi Sj fj S0 引入新的状态转换(fi,)=Sj 2018/12/30 《编译原理与技术》讲义

引入新的终态f0和状态转换(fj,)=f0 正规式与有限自动机 R= R1 · R2 （4）    Si fi S0 Sj fj f0 引入新的终态f0和状态转换(fj,)=f0 2018/12/30 《编译原理与技术》讲义

正规式与有限自动机 R= R1* （1） Si fi R1对应的NFA,Si为初态，fi为终态 2018/12/30 《编译原理与技术》讲义

正规式与有限自动机 R= R1* （2）  Si fi S0 引入新的初态S0和(S0,)=Si 2018/12/30 《编译原理与技术》讲义

引入新的终态f0和状态转换(fi,)=f0 正规式与有限自动机 R= R1* （3）   f0 S0 Si fi 引入新的终态f0和状态转换(fi,)=f0 2018/12/30 《编译原理与技术》讲义

正规式与有限自动机 R= R1* （4） 引入新的状态转换(fi,)=Si    f0 S0 Si fi 2018/12/30 《编译原理与技术》讲义

正规式与有限自动机 R= R1* （5）    f0 S0 Si fi  引入新的状态转换(S0,)=f0 2018/12/30 《编译原理与技术》讲义

R1对应的NFA，它也是(R1)对应的NFA 正规式与有限自动机 R= (R1) Si fi R1对应的NFA，它也是(R1)对应的NFA 2018/12/30 《编译原理与技术》讲义

e.g.12 构造（0|1）*01的对应的FA。（1） 1 1 0 | 1    1  2018/12/30 《编译原理与技术》讲义

e.g.12 构造（0|1）*01的对应的FA。（2） (0 | 1) 同 0 | 1 (0 | 1)*         1 (0 | 1) 同 0 | 1 (0 | 1)*       1   2018/12/30 《编译原理与技术》讲义

e.g.12 构造（0|1）*01的对应的FA。（3） (0 | 1)* 0          1 2018/12/30       1   2018/12/30 《编译原理与技术》讲义

e.g.12 构造（0|1）*01的对应的FA。（4） (0 | 1)* 0 1  1 2018/12/30 《编译原理与技术》讲义

e.g.12 构造（0|1）*01的对应的FA。（5） · · * （ ） R9 R7 R8 R5 R6 1 R4 R3 R1 | R2 1 （ ） R3 R1 | R2 1 2018/12/30 《编译原理与技术》讲义

Thompson方法所构造的NFA的状态数和转换较多。可以采用下面方法减少之： R R R1 R = R1 | R2 R2 R1 R2 R = R1 R2 R1 R1   R = R1* 2018/12/30 《编译原理与技术》讲义

e.g.13 构造（0|1）*01的对应的FA－简化版 1） 2） 3）   4） （0|1）* 0 1 0 | 1 (0|1)* 0 1 3）   1 4） 0 | 1 2018/12/30 《编译原理与技术》讲义

e.g.13 构造（0|1）*01的对应的FA－简化版   4）   5） 0 | 1 1 1 1 2018/12/30 1 4） 0 | 1 1   1 5） 2018/12/30 《编译原理与技术》讲义

正规式与有限自动机 对于一个FA M，皆有 上正规式R，使得 L(M) = L(R) ，反之亦然。 方法如下（1）首先添加新的开始和接收状态。 FA M   X S0 F Y 2018/12/30 《编译原理与技术》讲义

正规式与有限自动机 方法如下（2）逐个删除FA中的状态q。 q q1 p1 q1 p1 qn qn pm pm . . α1 . . β1 α1(γ1|…|γk)*β1 q1 p1 q1 p1 . . α1 . αn(γ1|…|γk)*β1 . β1 q αn βm α1(γ1|…|γk)*βm γ1 qn qn . pm pm αn(γ1|…|γk)*βm γk 2018/12/30 《编译原理与技术》讲义

正规式与有限自动机 方法如下（3）最终形成： R = R1 | R2 … | Rt X Y X Y R1 R R2 Rt 2018/12/30 《编译原理与技术》讲义

正规式与有限自动机 针对如下FA M，给出一个正规式R，使得L(R) = L(M)。 1 1 S0 S1 S2 1 2018/12/30 1 1 S0 S1 S2 1 2018/12/30 《编译原理与技术》讲义

正规式与有限自动机 引入新的开始状态x和新的接收状态y； 消除状态s2； 消除状态s1； 消除状态s0； 最终得到一个R： (0|1(01*0)*1)* 2018/12/30 《编译原理与技术》讲义

NFA的确定化（转换到DFA） 子集构造法 对NFA进行模拟。NFA的转换表中每个条目是状态子集，而在DFA中则为单一的状态。NFA到DFA的转换的一般想法是，让DFA中的每个状态代表NFA中的状态子集。DFA用它的状态去记住NFA在读入每个输入符号后能到达的所有状态的集合，即在DFA在读了符号a1a2…an后到达代表NFA状态子集T的状态，而这个子集T是从NFA开始状态沿着标记有a1a2…an的路径所能到达的所有状态的集合。 2018/12/30 《编译原理与技术》讲义

NFA的确定化（转换到DFA） 子集构造法 DFA的“状态”Sd是NFA的非空状态子集，Sd2S Sd0 = { S0，u | S0 * u }＝ -closure({S0}) -closure(T) = { 从状态集合T的每一个状态t出发，经过若干空转换（ 转换）所能到达的所有状态} 2018/12/30 《编译原理与技术》讲义

NFA的确定化（转换到DFA） 子集构造法 DFA状态转换函数d : Sd1 a Sd2 ， Sd2 = { t，u | s a t , s∈Sd1 ， t * u } = -closure( { t | s a t , s∈Sd1 } ) DFA的终态F－{ 含有原NFA终态的Sd } 2018/12/30 《编译原理与技术》讲义

while ( Dstates中有未标记的状态 T ） do { 标记 T； for 每个输入符号 a do 初始时，DFA的状态集合Dstates中只有初态Sd0且未标记。 while ( Dstates中有未标记的状态 T ） do { 标记 T； for 每个输入符号 a do { U = -closure( { s | NFA状态转换函数(t,a)=s, tT} ) if U 不在 Dstates中 则将其加入Dstates且未加标记； 记下DFA状态转换函数d（T，a）＝ U ； } 2018/12/30 《编译原理与技术》讲义

NFA的确定化 e.g.14 确定化以下NFA M。 X  1 3 2 y 6 4 5 a b 2018/12/30 《编译原理与技术》讲义

e.g.14 确定化以下NFA M。（续1）  状态Sd a b d : Sd1 a Sd2 d : Sd1 b Sd2 Sd0={ x,3,1} {3,4,1} {3,5,1} {3,2,4,1,6,y} {3,2,5,1,6,y} {3,2,4,6,1,y} {3,5,6,1,y} {3,4,6,1,y} {3,2,5,6,1,y} 2018/12/30 《编译原理与技术》讲义

e.g.14 确定化以下NFA M。（续2）  状态Sd a b d : Sd1 a Sd2 d : Sd1 b Sd2 {3,5,6,1,y} {3,6,4,1,y} {3,2,6,5,1,y} {3,4,6,1,y} {3,2,6,4,1,y} {3,6,5,1,y} 2018/12/30 《编译原理与技术》讲义

e.g.14 确定化以下NFA M。（续3） { x,3,1} { 3,4,1} { 3,5,1} {3,2,4,1,6,y} b 2018/12/30 《编译原理与技术》讲义

e.g.14 确定化以下NFA M。（续4） 1 2 3 4 5 6 a b 2018/12/30 《编译原理与技术》讲义

DFA的简化－极小化 DFA M 极小化 DFA M’，其中L(M)=L(M’)，且DFA M’是和DFA M等价（识别语言相同）的DFA中状态数最少的。 状态s1和s2是等价的，如果 s1  f1 且 s2  f2，f1，f2∈F，∈* 。 状态t1和t2是可区分的，如果t1和t2不等价。 2018/12/30 《编译原理与技术》讲义

DFA的简化－极小化 状态极小化－将DFA的状态集合S划分成若干不相交状态子集，不同子集的状态间是可区别的，相同子集内的状态间等价。取各个状态子集中的某一个状态为该子集代表，消除该子集中其他状态。 初始划分：终态集合 与 非终态集合 划分过程：如果s1,s2∈划分子集I，a ∈，有 (s1,a) ∈ 划分J ，(s2,a) ∈ 划分K ，则 划分I应进一步再划分成I1,I2 ,s1∈ I1,s2∈ I2 2018/12/30 《编译原理与技术》讲义

DFA的简化－极小化 e.g.15 将下面的DFA M极小化 （1） 1 2 3 4 5 6 a b 2018/12/30 1 2 3 4 5 6 a b 2018/12/30 《编译原理与技术》讲义

e.g.15 将下面的DFA M极小化 （2） 初始划分 I0=终态集合= { 3，4，5，6 } 和I1=非终态集合={ 0, 1, 2 } 考查 I1={0,1,2}, 0a 1 , 1a 3 , 2a 1 ，I1需再划分成I2={0,2}和I3={1}，此时划分为: I0, I2 和 I3 即{3,4,5,6}, {0,2} 和{1} 考查 I2, 0b 2 , 2b 4，I2需再划分成I4={0}和I5={2}，此时划分为: I0, I4, I5 和 I3 即{3,4,5,6}, {0}, {2} 和 {1} 考查I0={3,4,5,6}, 3a 3 , 4a 6 , 5a 6 , 6a 3 3b 5 , 4b 4 , 5b 4 , 6b 5 ，不需要划分I0，此时划分过程结束！ 2018/12/30 《编译原理与技术》讲义

e.g.15 将下面的DFA M极小化 （3） 最终划分 { 0 } , { 1 } , { 2 } 和 { 3，4，5，6 } //取状态3为代表 极小化的DFA如下： 3 a 1 2 b a, b 2018/12/30 《编译原理与技术》讲义

词法分析器自动生成－Lex LEX C编译器 lex.yy.c yylex() Lex 源程序 lex.yy.c yylex() 可执行文件/a.out 输入串 可执行文件/a.out 单词记号 2018/12/30 《编译原理与技术》讲义

词法分析器自动生成－Lex Lex 源程序组成 定义段 ％％ 规则段 用户程序段 2018/12/30 《编译原理与技术》讲义

词法分析器自动生成－Lex Lex 源程序组成－定义段: #include <stdlib.h> %{ #include <stdlib.h> #include <stdio.h> int count = 0; /* 任何形式的C声明 */ %} 上述C声明、语句被拷贝到lex.yy.c文件中 2018/12/30 《编译原理与技术》讲义

词法分析器自动生成－Lex Lex 源程序组成 定义段: 正规定义 digit [0-9] number {digit}+ 2018/12/30 《编译原理与技术》讲义

词法分析器自动生成－Lex Lex 源程序组成－规则段 正规式 { 语义动作 } {number} { 正规式 { 语义动作 } {number} { int n = atoi(yytext); printf(“%x”, n); /* 语义动作－合法的C语句 */ } 语义动作(C 语句)被拷贝到yylex()中 当正规式匹配时其相应的语义动作即被执行 2018/12/30 《编译原理与技术》讲义

词法分析器自动生成－Lex Lex 源程序组成 用户程序段－包含用户自定义的C函数，此段可空。如： main() int yywrap() { yylex(); { return 0; return 1; } } 2018/12/30 《编译原理与技术》讲义

e.g.16 一个lex例子程序 %{ #include <stdlib.h> #include <stdio.h> int count = 0; /*任何形式的C声明 */ %} digit [0-9] number {digit}+ %% {number} { int n = atoi(yytext); printf(“%x”, n); /*语义动作－合法的C语句 */ } main() { yylex(); return 0; } int yywrap() { return 1; } e.g.16 一个lex例子程序 2018/12/30 《编译原理与技术》讲义

转义符\，用来表示回车，\,tab制表,退格，引号” Lex 中元字符约定（1） 名称 含义 a 字符a “a” 字符a,无论a是否为元字符 \n \\ \t \b \” 转义符\，用来表示回车，\,tab制表,退格，引号” a* a的零次或多次重复(零闭包) a+ a的一次或多次重复(正闭包) a? a的零次或一次（可选） [abc] 同正规式 a | b | c [a-d] 表示范围，a,b,c,d中的一个 2018/12/30 《编译原理与技术》讲义

Lex 中元字符约定 （2） . 名称 含义 [a-d] 同 [abcd] [^ab] 除了a或b外的任一字符 除了 \n 外的任一字符 { xxx } 名字xxx表示正规式（正规定义） | “或” 运算符 ( ) < > ^a a$ a出现在行首（行尾） a / b a后面跟着b 2018/12/30 《编译原理与技术》讲义

Lex 内部名字 yytext yyleng lex.yy.c Lex的输出文件名 yylex() Lex词法扫描函数 名称 含义 lex.yy.c Lex的输出文件名 yylex() Lex词法扫描函数 yytext yyleng 跟规则匹配的字符串、串长 yyin Lex输入文件变量(缺省stdin) yyout Lex输出文件变量(缺省stdout) input Lex缓冲的输入例程 yywrap() 遇到输入（文件）结束符EOF时Lex调用。通常由用户自定义为{return 1;}以表示正常返回 ECHO Lex缺省动作将yytext打印到yyout 2018/12/30 《编译原理与技术》讲义

词法分析器自动生成－Lex Lex中二义性规则的处理 选择最长规则进行匹配，如 > 和 >= 输入串与两个（或两个以上）规则匹配时，选择在规则段中位置靠前（首先出现）的规则进行匹配。如，关键字规则靠前而（普通）标识符规则在后。 2018/12/30 《编译原理与技术》讲义