郑州大学编译原理.ppt

第三章 词法分析 词法分析的任务： 从左到右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成单词符号串的中间程序。 §3.1 对于词法分析器的要求 单词符号 例如：C的代码段 词法分析器作为一个独立子程序 §3.2 词法分析器的设计 常常按词法分析的任务和作为一个独立子程序来考虑它的设计。 预处理子程序 预处理子程序就是完成上述任务的。每当词法分析器调用它时，它就处理一串确定长度的输入字符，并装入扫描缓冲区中。 扫描缓冲区 单词符号的识别---超前搜索 状态转换图 例如 大多数程序语言的单词符号都可以用转换图予以识别。 词法分析的状态转换图 3.2.4 状态转换图的实现 例如 思考题 解答 §3.3 正规表达式与有限自动机 词法分析器的自动生成可依据正规表达式和有限自动机的理论。实际上，状态转换图与正规表达式和有限自动机在描述语言能力方面是等价的。 正规式和正规集的递归定义（ 续） 例3.1 令∑= {a , b} ， 下面是∑上的正规式和相应的正规集： 例3.2 令∑= {a，b，0，1} ，则： 正规式的等价性 若两个正规式所表示的正规集相同，则称两者等价。 例如 b(ab)*=(ba)*b (a|b)*=(a*b*)* 思考题：写出下面正规式 确定的有限自动机 状态转换矩阵 状态转换矩阵 状态转换图 DFA M 接受的语言 例如：有DFA M 如下： 非确定的有限自动机 同样,一个 NFA M 也可表示成状态转换图。 NFA M 接受的语言L(M) 例如：下图就是一个NFA M NFA 与 DFA 等价 ② 对M的状态转换图进行如下替换： （2）将 NFA M’ 进一步变换成等价的 DFA M” ③ 假定∑={ a1, … , ak }。构造一张含有k+1列的表 （3）将所构造出的表视为状态转换矩阵 例如：正规式(a|b)*(aa|bb)(a|b)* 利用子集法求状态转换表： 继续求新的子集： I、Ia、Ib，得出下表： 对所有的状态子集重新命名，由此而得： 例题1 (3)用子集法求状态转换矩阵 (4) 重新命名得 DFA 作业（3）P64 例题2 正规文法与有限自动机的等价性 证明 (1)对每一个右线性文法G，都存在一个FA M，使得: L(M) = L(G) 显然 A?a ? A F  A?aB ? A B 例题3 已知正规文法 G 如下，构造其等价的FA M 。 证明 (2) 对于每一个DFA M，都存在一个右线性文法G，使得： L(M) = L(G) 例题4 设 DFA M 如下，构造其等价的正规文法。 例题5 证明(1)对每一个左线性文法G，都存在一个FA M，使得： L(M) = L(G) 显然 A?a ? q0 A  A?Ba ? B A 证明 (2) 对于每一个DFA M，都存在一个左线性文法G，使得： L(M) = L (G) 例3.4(1) p(53) 例3.4(2) p(53) 例3.4(3) p(53) 正规式与有限自动机的等价性 证明 对任何 FA M，都存在一个正规式r,使得： L(r) = L(M) 证明: 对任何正规式r ，都存在一个 FA M，使得 L(M) = L(r) （2）假设结论对少于k(k0)个运算符的 r 成立。 ② r=r1.r2 例题6 1.写出{a,b}上不以a开头，以aa结尾的正规式和 DFA 。 例题7 写出下面 NFA 对应的正规式 （1） 确定有限自动机的化简 例题8 ● DFA M 的状态最少化过程 将DFA最小化的方法 (4)在每个子集I中选取一个状态代表其它状态 例题9将DFA 最小化 例题3.6 设 DFA M 如下，将其最少化。 例题3.6 设 DFA M 如下，将其最少化。 最少化的 DFA ： §3.4 词法分析器 L 的自动产生 LEX语言：是专门描述词法分析器的语言。 作业 P64 证明：（采用归纳证明法） （1）若 r 具有0个运算符， 则 r=? 或 r=? 或 r=a 此时，对应的FA 分别为： q0 q0 q0 q a （3）当 r 具有k个运算符时，