编译原理03_2.

1、程序设计语言程序设计语言 编译原理编译原理 P35 第第4题（题（2） P36 第第6题题 第第8题题 (i / i +i) i * i 第第10题题 第第11题题 L2和和L4 输入缓冲区输入缓冲区 预处理预处理 子程序子程序 扫描器扫描器 输入输入 列表列表 单词符号单词符号 扫描缓冲区扫描缓冲区 3.2.3 3.2.3 状态转换图状态转换图 有限方向图，有限方向图，结点结点表示状态，状态间用表示状态，状态间用箭弧箭弧连接，箭连接，箭 弧上的弧上的标记标记（符号）代表射出结点状态下有可能出现（符号）代表射出结点状态下有可能出现 的输入字符或字符类。的输入字符或字符类。 一个状态转换图可用于

2、识别（或接受）一定字符串。一个状态转换图可用于识别（或接受）一定字符串。 上图为接受上图为接受X X和和Y Y的状态转换图的状态转换图 标识符：以字母开头的标识符：以字母开头的 字母数字串字母数字串 0(10)n | n| n00 D D是死状态是死状态 3.2 词法分析器的设计词法分析器的设计 在限制的基础上：在限制的基础上： 步骤步骤(1): 了解该语言的单词符号了解该语言的单词符号 步骤步骤(2): 为单词符号构造状态转换图为单词符号构造状态转换图 步骤步骤(3): 状态转图的计算机实现状态转图的计算机实现 3.2 词法分析器的设计词法分析器的设计 3.2.4 状态转换图的实现状态转换图

3、的实现 每个状态对应一小段程序每个状态对应一小段程序 例：例： 预备工作预备工作 (1) ch 字符变量，存放最新读入的字符字符变量，存放最新读入的字符 (2) strToken 字符数组，字符数组， 存放一个单词符号存放一个单词符号 (1) GetChar 读一个字符，存入读一个字符，存入ch，指针下移，指针下移 (2) GetBC 检查当前检查当前ch是否为空白，若是，调用是否为空白，若是，调用 GetChar一直至找到一个非空白字符为止一直至找到一个非空白字符为止 (3) Concat 将将ch中的字符接到中的字符接到strToken之后之后 全局全局 部变部变 函数函数 3.2 词法分

4、析器的设计词法分析器的设计 (4) IsLetter 判断判断ch是否为字母是否为字母 (5) IsDigit 判断判断ch是否为数字是否为数字 (6) Reserve 将将strToken中的字符串与保留字表对照中的字符串与保留字表对照 若是保留字，则返回编号，否则返回若是保留字，则返回编号，否则返回0 (7) Retract 指针回调一个字符位置指针回调一个字符位置 (8) InsertID 将将strToken中的标识符插入符号表，返中的标识符插入符号表，返 回指针回指针 (9) InsertConst 将将strToken中的常数插入常数表，返中的常数插入常数表，返 回指针回指针 函数

5、函数 3.2 词法分析器的设计词法分析器的设计 预备知识预备知识 每个状态对应一小段程序每个状态对应一小段程序 自环状态：自环状态： while, for, do 3.2 词法分析器的设计词法分析器的设计 字母字母 数字数字 / / 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3 正规表达式与有限自动机正规表达式与有限自动机 源程序源程序 字符流字符流 单词单词 符号符号 非形式非形式 化描述化描述 形式化形式化 描述描述 字母字母 串串语言语言 字母表字母表 自动化的自动化的 计算机实计算机实 现现 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3 正规表达式与有限

6、自动机正规表达式与有限自动机 3.3 正规表达式与有限自动机正规表达式与有限自动机 正规式的正规式的例子例子 = = a a, , b b 正规式正规式正规集正规集 a|ba|bL(a)L(b)=L(a)L(b)=a,ba,b ababL(a)L(b)=L(a)L(b)=abab a a* *(L(a)(L(a)* * =a =a* *= =aan n|n 0|n 0 a a* *b b(L(a)(L(a)* * L(b)=L(b)=aan n b b |n 0 |n 0 (a|b)(a|b)* *(L(a|b)(L(a|b)* * =a,b =a,b* *或或a|ba|b* * a a* *

7、b b* *(L(a)(L(a)* *(L(b)(L(b)* *=a=an n |n 0b |n 0bm m |m |m 0=0=aan n b bm m |m,n 0 |m,n 0 3.3 正规表达式与有限自动机正规表达式与有限自动机 正规式的正规式的例子例子 = = a a, , b b 正规式正规式正规集正规集 aa|ab|ba|bbaa|ab|ba|bb aa, ab, ba, bbaa, ab, ba, bb ( (a|b)(a|b)a|b)(a|b) aa, ab, ba, bbaa, ab, ba, bb a(a|b)a(a|b)* * 上上a a为首的任意字符串的集合为首的任意

8、字符串的集合 (a|b)(a|b)* *a a 上上a a为尾的任意字符串的集合为尾的任意字符串的集合 b b* *(abb(abb* *) )* *每个每个a a至少有一个至少有一个b b紧跟其后的字符紧跟其后的字符 串的集合串的集合 (a|b)(a|b)* *(aa|bb)(a|b)(aa|bb)(a|b)* *含有两个相连的含有两个相连的a a或两个相连的或两个相连的b b的的 字符串的集合字符串的集合 3.3 正规表达式与有限自动机正规表达式与有限自动机 正规式的正规式的例子例子 = = A, B, 0, 1A, B, 0, 1 正规式等价：正规式等价：若两个正规式若两个正规式U U和

9、和V V表示的正规集相同，表示的正规集相同， 则称二者等价，记为则称二者等价，记为U=VU=V。 例：例： b(ab)b(ab)* * = (ba)= (ba)* *b b (a|b) (a|b)* * = (a= (a* *b b* *) )* * 正规式正规式正规集正规集 上所有上所有“标识符标识符”的集合的集合 上所有上所有“数数”的集合的集合 3.3 正规表达式与有限自动机正规表达式与有限自动机 性质性质: 若若U、V和和W都为正规式，则都为正规式，则 计算机实现计算机实现状态转换图状态转换图正规式正规式 不确定有不确定有 限自动机限自动机 确定有限确定有限 自动机自动机 3.3 正规

10、表达式与有限自动机正规表达式与有限自动机 有限自动机有限自动机 最简确定有最简确定有 限自动机限自动机 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3.2 如：如：DFA M=(S,s0，F) = ( 0, 1, 2, 3, a,b, , 0, 3) (0,a) = 1 (0,b) = 2 (1,a) = 3 (1,b) = 2 (2,a) = 1 (2,b) = 3 (3,a) = 3 (3,b) = 3 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3.2 4、特点：、特点： (1) 初态唯一初态唯一 (2) 输入字符不包括输入字符不包括 (3) 有向边上只有一个

11、字符有向边上只有一个字符 (4) 一个状态对于某个字符，最多只有一条出边一个状态对于某个字符，最多只有一条出边 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3.2 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3.2 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3.3 不不 1.1.不不 状态转换函数，状态转换函数，：S S* *SS的映射的映射 12 a 0 a b b a a 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3.3 不不 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3.3 不不 3.3 正规表达式与有限自动机正

12、规表达式与有限自动机 3.3.3 NFA确定化确定化(NFADFA)子集法子集法 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3.3 NFA确定化确定化(NFADFA)子集法子集法 2.子集法子集法 (1) -closure(q) 从状态从状态q出发，只经出发，只经转换能到达的所有状态的转换能到达的所有状态的 集合集合 (a) q-closure(q)； (b) 从从q出发经任意条出发经任意条弧而能到达的任何状态弧而能到达的任何状态q- closure(q) (2)-closure(I) q|q-closure(q) & qI (3) Ia=-closure(J) a，其中，其中

13、J为从为从I中任一状态出发经中任一状态出发经 输入符号输入符号a所能到达状态结点的全体所能到达状态结点的全体。 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3.3 NFA确定化确定化(NFADFA)子集法子集法 下图确定化：下图确定化： ： ： 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3.6 确定有限自动机的化简确定有限自动机的化简合并等价的状态合并等价的状态 BD 开始开始a A a b b a a, b C b a E b 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3.6 确定有限自动机的化简确定有限自动机的化简 3.3 正规表达式与有限自动

14、机正规表达式与有限自动机 3.3.6 确定有限自动机的化简确定有限自动机的化简 最小化的思路：最小化的思路： 将将M的状态集合分成一些不相交的子集，的状态集合分成一些不相交的子集， 使任何不同的两个子集的状态都是可区别的，使任何不同的两个子集的状态都是可区别的， 而同一子集中的任何两个状态都是等价的。而同一子集中的任何两个状态都是等价的。 最后，在每个子集选出一个代表，同时消去其他等价最后，在每个子集选出一个代表，同时消去其他等价 状态。状态。 3.3 正规表达式与有限自动机正规表达式与有限自动机 3.3.6 确定有限自动机的化简确定有限自动机的化简 1.1.把把DFADFA状态分割成两个状态

15、状态分割成两个状态S S1 1( (终止状态集终止状态集) )和和S S2 2( (非终止非终止 状态集状态集) )。 2.2.对每个状态集按下述方法进行分割：对每个状态集按下述方法进行分割： 设第设第i i次分割把集合分割成次分割把集合分割成S=SS=S1 1(i) (i)S S2 2(i) (i)S Sk k(i) (i)，检查 ，检查 状态集状态集S Sj j(i) (i)(j=1,2,k) (j=1,2,k)设设S Sj j 和 和S Sj j” ” S Sj j(i) (i)， ，(S(Sj j ,a)= ,a)= S Sm m ，(S (Sj j” ”,a)= S ,a)= Sn

16、n 若若S Sm m，S Sn n处于同一集合中，则放在同一集；处于同一集合中，则放在同一集； 若若S Sm m，S Sn n不处于同一集合中，则放在两个集。不处于同一集合中，则放在两个集。 3.3.重复重复2 2直至不产生新的分割为止直至不产生新的分割为止 4.4.合并等价状态：在状态集中选一代表其它删除。如合并等价状态：在状态集中选一代表其它删除。如I=qI=q1 1,q,q2 2, , , q, qk k 不可再分，则可选择不可再分，则可选择q q1 1代表这个子集，凡导入到代表这个子集，凡导入到q q2 2, , , q, qk k的弧都改成导入到的弧都改成导入到q q1 1，若，若I I中含有原来的初态，则中含有原来的初态，则q q1 1是是 新的初态，若新的初态，若I I中含有原来的终态，则中含有原来的终态，则q q1 1是新的终态。是新的终态。 例：书例：书P51 图图3.8 计算机实现计算机实现状态转换图状态转换图正规式正规式 不确定有不确定有 限自动机限自动机 确定有限确定有限 自动