第3章编译原理答案(主编张晶).pptVIP

词法分析程序的设计与实现？ 3.1 有穷自动机 1.状态图 （补充） 2. 正规文法（左线性文法）转换状态图（重点）:教材3.3 ②以每个非终结符号做其它状态 ③对于形如Q→q的规则, 对于形如Q→Rq的规则, ④以文法开始符号为终止状态 例3-2： 文法G[Z]： Z→Za|Aa|Bb A→Ba|a B→Ab|b 例3-3 已知文法G[Z]: Z→U1|V1 U→Z0|1 V→Z0|0 （1）画出状态图（5分） （2）是NFA吗？为什么？（3分） 由此可见，在NFA中由于某些状态的转换需从 若干个可能的后继状态中进行选择，这种不确定 性给识别过程带来反复，影响了工作效率。 将NFA的初始状态集S出发，作为DFA的初态S=[ , ,…, ] 从S出发，把遇到输入符号a所转移到的后继状态集作为DFA的新状态 如此重复，直到不再有新的状态出现为止。 在DFA中，含有NFA终止状态的状态均为DFA的终止状态 。 练习1：有NFA A=({q0,q1,q2},{a,b},M,{q0},{q1}) M=(q0,a)={q1,q2} M=(q0,b)={q0} M=(q1,a)={q1,q0} M=(q1,b)=Φ 字母表?, 定义在? 上的正规式和正规集递归定义如下: 1. ?和?都是? 上的正规式, 它们所表示的正规集分别为:{?}和?; 2. 任何a? ? , a是? 上的正规式,它所表示的正规集为:{a}; 3. 假定U和V ? 上的正规式, 它们所表示的正规集分别记为L(e1) 和L(e2), 那么e1|e2, e1?e2和e1*也都是? 上的正规式, 它们所表示的正规集分别为L(e1) ?L(e2)、 L(e1) ? L(e2)和(L(e1))* 4. 任何? 上的正规式和正规集均由1、2和3产生。 练习： 1.设Σ={0,1}，写出描述下列语言的正规式。 （1）以01结尾的所有串 （2）只包含一个0的所有串 （3）包含偶数个1且不含0的所有串 2.设Σ={x,y}，描述正规式所定义的语言。 （1） x(x|y)*x （2） (x|y)* (xx|yy) (x|y)* （1）对NFA M构造一个广义的状态图，其中只有一个初态S和终态Z，连接S和Z的有向弧标记为正规式。 （2）对正规式依次进行分解，分解的过程是一个不断加入结点和弧的过程，直到转换图上的所有弧标记上都是字母表Σ上的元素或?为止。 练习题： 给出下列在字母表｛0，1｝上的DFA (A)所有以00结束的符号串集合 （B）所有具有三个0的符号串集合 ？正规集构造正规文法： ？正规文法构造正规式 重点:自动机的简化（是否含有等价状态） （1）将所有状态分成两个子集：终态集和非终态集 （2）把等价的状态构成一个子集，每个子集若存在不等价继续划分 （3）结束后，合并等价状态 { , , , }={ , , } { } 例2 (一)区分终态与非终 解：{ 1 , 2 , 3 , 4 } { 5,6,7 } { 1 , 2 , 3 , 4 } = { 1 , 2} { 3 , 4 } {5,6,7 } 总结： DFA的化简 1 每个集合内部状态互相之间是等价的 2 状态等价：所有输入字符到达集合步调一致 3 状态不等价：至少存在一个输入字符到达集合步调不一致 练习 2 将下列NFA转换为DFA，并转化为最小DFA ①token 用来存放构成单词符号的字符串； ②sum 用来整型单词； ③syn 用来存放单词符号的种别码。 main(){p=0; printf(\n please input a string(end with #):/n); do{ scanf(%c,ch); prog[p++]=ch; }while(ch!=#); p=0; do{ scaner(); switch(syn) {case 11:printf(( %-10d%5d )\n,sum,syn); break; case -1:printf(you have input a wrong string\n); getch(); exit(0); default: printf