《编译原理》词法分析.pptVIP

? 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) 第3章 作 业 教材P64 7(任选2题) 9(1) 12 学习指导书P65 3 4 9 13 本章小结 本章要求 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 | ? 1、S= aAb = aBcAb =aidtcAb = aidtcBcAb S= aAb = aBb = ab 2、词法分析阶段遵循单词的构词规则; 语法分析遵循语言的语法规则; 语义分析阶段遵循语言的语义规则; 代码优化遵循等价变换规则; 3、S → d4S S → d1A|d3 A → d2A|d3 d1 → 1|2|… |9 d2 → 0|2|… |9 d3 → 2|4|6|8 d4→+|-正规式: (+|-)(d1d2*| ?) d3或(d4)(d1d2*| ?) d3 5、 正规式:(0|1) *(00|01) 4、 3.4词法分析程序的自动构造 对有穷自动机和正规表达式进行了上述讨论之后,我们介绍词法分析程序的自动构造方法,这个方法基于有穷自动机和正规式的等价性,即： 1.对于∑上的一个NFA M，可以构造一个∑上的正规式R,使得L(R)=L(M)。 2.对于∑上的一个正规式R，可以构造一个∑上的NFA M，使的L(M)=L(R)。 * 为什么要做这样的变换：因为NFA中每条弧用?* 上的一个字来表示，而DFA每条弧用? 上的一个符号来表示；DFA有1个开始状态，而NFA可以有多个初始状态。 * 转换后是一个不确定的有穷自动机 * 从书上的证明过程来看，从正规文法到有穷自动机，只有一个终结状态F，因此不能得到B是终结状态 * 识别所有偶数个1和偶数个0的语言 正规式和正规集的递归定义：（设字母表为?） 1、 ?和?都是?上的正规式，表示{?}和{ }； 2 、任何a? ?，则a是正规式，表示{a}； 3 、假定r和s都是?上的正规式，分别表示语言 L(r)和L(s)： a） (r) | (s)是正规式，表示L (r) U L (s) ； b） (r)(s)是正规式，表示L (r)L (s)； c） (r)*是正规式，表示(L (r) )*； d） (r)是正规式，表示L (r)； 4、有限次使用上述三步骤而定义的表达式才是?上的正规式，仅由这些正规式所表示的集合才是?上的正规集。 思考题： ?={d，. }，则?上表示无符号数的正规式是什么？（不考虑含e的科学计数法，其中d为0~9的数字） 如：2 ，12.59 ，471.88等都是该集合中的元素。 dd*(.dd*| ?) 正规式的等价 若两个正规式e1和e2所表示的正规集相同,则e1和e2等价,写作e1=e2。 设r,s,t为正规式，正规式服从的代数规律有： 1. r?s=s?r “或”服从交换律 2. r?(s?t)