《编译原理课程教案》第3章：词法分析.ppt

例: L(M)如右图： 求正规式R，使L(R)=L(M). 解： 因此： L(R)= (a|b)(a|b)* － ＋ a b a,b - + a b a,b x y ? ? y a|b ? ? a|b x y (a|b)(a|b)* x 练 习 求下述有穷自动机对应的正规式 L(R) =(a|b)*abb ? y a b a b b x y ? (a|b)*a bb b x ? y ? a a b b ? x y ? (a|b)* abb 方法如下： x y x y ? x y a 正规式R?有穷自动机NFA M(P54) ? s,t是正规式，相应NFA为N(s),N(t)，则正规式R=s|t，构造NFA(R) 为： ? 对应正规式a，构造NFA为： ? ? 对应正规式?，构造NFA为： ? ? 正规式?，构造NFA为：? ? s,t是正规式，相应NFA为N(s),N(t)，则正规式R=st，构造NFA(R) 为： ? s是正规式，相应NFA为N(s) ，则正规式R=s*，构造NFA(R) 为： 书上例3.5 P56 R = 1的有穷自动机: R = 1*的有穷自动机: R = 01*的有穷自动机: q0 q1 1 q0 q1 1 q2 q3 ? ? ? ? q0 q1 1 ? q2 q3 ? ? ? q4 q5 0 ? R = 01* | 1的有穷自动机: q0 q1 1 ? q2 q3 ? ? ? q4 q5 0 ? q6 q7 1 Y X ? ? ? ? 练习 a a ? ? ? ? b ? ? q0 ? ? b b ? ? ? 正规式L(R) =(a|b)*abb，构造NFA使L(N)=L(R) 本章小结 本章要求 1．词法分析器的作用和接口，用高级语言编写词法分析器等内容，它们与词法分析器的实现有关。 2．掌握下面涉及的一些概念，它们之间转换的技巧、方法或算法。 ? NFA ? DFA ? DFA ? 最简DFA ? 非形式描述的语言 ? 正规式 ? 正规式 ? NFA ? 正规文法 ? NFA 课堂练习(1~3章) 1. 有文法G[S]： 问：符号串aidtcBcAb、ab、abidt是否是该文法的句型？为什么？ 2. 编译原理各个阶段各应遵循哪些原则？ 3. 写出不能被5整除的偶整数的正规文法和正规式 4. 有一台自动售货机，接受1元和5角的硬币，出售每瓶1元5角的饮料，顾客每次向机器中投放?1元5角的硬币，就可得到一瓶饮料( 注：每次只给一瓶饮料，且不找钱)，构造该售货机的有穷自动机。 5. 设计一个状态数最少的DFA, 其输入字母表是{0，1}，它能接受以00或01结尾的所有序列,并给出相应的正规文法。 S ? aAb A ? BcA | B B ? idt | ? 3.4词法分析程序的自动构造 对有穷自动机和正规表达式进行了上述讨论之后,我们介绍词法分析程序的自动构造方法,这个方法基于有穷自动机和正规式的等价性,即： 1.对于∑上的一个NFA M，可以构造一个∑上的正规式R,使得L(R)=L(M)。 2.对于∑上的一个正规式R，可以构造一个∑上的NFA M，使的L(M)=L(R)。 3.4.1 Lex的概述 * 为什么要做这样的变换：因为NFA中每条弧用?* 上的一个字来表示，而DFA每条弧用? 上的一个符号来表示；DFA有1个开始状态，而NFA可以有多个初始状态。 * 转换后是一个不确定的有穷自动机 * 从书上的证明过程来看，从正规文法到有穷自动机，只有一个终结状态F，因此不能得到B是终结状态 * 识别所有偶数个1和偶数个0的语言 NFA的确定化 第一步：对NFA的状态图进行改造 (1)增加状态X,Y,使之成为新的唯一的初态和终态。从X引ε弧到原初态结点, 从原终态结点引ε弧到Y结点。 (2) 对状态图进一步进行如下形式的改变 i j AB i k A j B i j A|B i A j B i j A* i k ε j ε A 例5：有NFA如下： 2 1 (a|b)*(aa|bb)(a|b)* Y 1 (a|b)*(aa|bb)(a|b)* X 2 ? ? a 8 Y 7 4 6 3 5 1 ? ? ? ? a a a b b b b X 2 ? ? Y 4 3 1 (aa|bb) (a|b)* (a|b)* X 2 ? ? a a Y 4 6 3 5 1 ? ? ? ? aa b bb b X 2 ? ? 练 习 求下述NFA对应的DFA（完成第一步） 0 1 (0|1)*00 2 Y X 4 ? 0 ? 1 3 ? 0 0 ? 0 1 上述NFA带有?弧，称为具有?转移的不确定的有穷自动机 对任何一个具有?转移的不确定的