习题课讲义

编译原理习题课Chap1~Chap6第一章引论重点：编译过程编译程序的结构编译过程词法分析语法分析中间代码产生优化目标代码产生词法分析器语法分析器中间代码生成器优化段源程序单词符号语法单位四元式表格管理出错处理目标代码生成器四元式目标代码第二章高级语言及其语法描述重点：上下文无关文法上下文无关文法根据给定的文法确定相应的语言根据给定的语言写出相应的文法判断文法的二义性是这样一种文法，它所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境的。根据给定的语言写出相应的文法P36.11.给出下面语言的相应文法L1={anbnci|n1,i0}L2={aibncn|n1,i0}L3={anbnambm|n,m0}L4={1n0m1m0n|n,m0}解题思路1.首先应当仔细研究语言的结构特点，通常这些语言具有形式上的对称性和字符数目上的相关性等特点，这些特性可以用文法的递归定义来实现对于L1，文法G1(S)：||cCCabaAbAACSbcbBcBaAAABS||对于L2，文法G2(S)：对于L3，文法G3(S)：||aBbBaAbAABS对于L4，文法G4(S)：ABBAABAS|01|10|2.适当时分解语言的结构•L5={aibj|ji1}bBbBabaAbAABS||判断文法的二义性解题思路：1.对于文法G(S)的某个句子有两棵不同的语法树与之对应2.对于文法G(S)的某个句子存在两个不同的规范推导P36.9.证明下面的文法G是二义的:SiSeS|iS|i解:句子iiiei有两个不同的语法树SiiSSiSeiSiSeSiSeiiiSeiiiieiSiiSSiSeiSiSiiSeSiiSeiiiieiP36-7解：G(S)：ONODNSOAOAADN1357924680|||||||||||第三章词法分析重点:1.根据正规式求确定有限自动机2.非确定有限自动机的确定化3.确定有限自动机的最小化习题P64--7构造下列正规式相应的DFA1(0|1)*101解:Step1.由正规式得到相应的NFAM’XY1(0|1)*101XY11423501011Step2.把上述NFA确定化——采用子集法.-closure(I)=I{s’|从某个sI出发经过任意条弧能到达s’}XY11423501011-closure({X})={X}=IJ={1},K=I1=-closure(J)={1,2,3}I0=-closure(K)=确定化01{X}φ{1,2,3}φφφ{1,2,3}{2,3}{2,3,4}{2,3}{2,3}{2,3,4}{2,3,4}{2,3,5}{2,3,4}{2,3,5}{2,3}{2,3,4,Y}{2,3,4,Y}{2,3,5}{2,3,4,}006151423110110100010Step3.把上述DFA最少化基本思想:-划分状态集不相交-可区别的等价的-每个子集选出一个代表006151423110110100010{,,,,,},{}{,,,,,}{,,}{,,,,,}{,,,}{,,,,},{},{}{,,,,}{,,}{,,,},{},{},{}{,,,}{,0123456012345135012345124601234560123413501234560123101003012312401234560110112233234012345610101}{,,,}{,,}{,},{,}{},{},{}{,}{}{,}{,}{,}{}{,}{}{},{},{,},{},{},{}{0}，{1}，{2,3}，{4}，{5}，{6}005141321110100010化简后的DFA例:对下图NFAM构造其DFA，并化简。aabbbXY•P64–8•(1)•(2)•(3)01)0|1(*)5|0(|)5|0()9|8|7|6|5|4|3|2|1|0)(9|8|7|6|5|4|3|2|1(*******01(0|101)|10(1|010)第四章语法分析重点：LL(1)分析法预测分析表的构造预测分析程序的构造LL(1)分析法构造不带回溯的自上而下分析算法–要消除文法的左递归性–克服回溯一般而言，假定P关于的全部产生式是P→P1|P2|…|Pm|1|2|…|n其中，每个都不等于，而每个都不以P开头那么，消除P的直接左递归性就是把这些规则改写成：P→1P|2P|…|nPP→1P|2P|…|为了消除回溯就必须保证：文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。我们可以找出满足构造不带回溯的自上而下分析的文法条件：1.文法不含左递归，2.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A→1|2|…|n则FIRST(i)∩FIRST(j)＝(ij)3.对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST(i)∩FOLLOW(A)=i=1,2,...,n对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为A→1|2|…|n1.若aFIRST(i)，则指派i执行匹配任务；2.若a不属于任何一个候选首符集，则：(1)若属于某个FIRST(i)且aFOLLOW(A)，则让A与自动匹配。(2)否则，a的出现是一种语法错误。递归下降分析程序的构造分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文法的定义通常是递归的)预测分析表的构造结合习题讲解SaTTTSS|^|(),|P81.1文法G:(1)消除左递归(1)消除左递归)(SG|,TSTTST)(||^TaSprocedureS;beginifsym='a'orsym='^'thenadvanceelseifsym='('thenbeginadvance;T;ifsym=')'thenadvance;elseerror;endelseerrorend;)(||^TaS递归子程序：对于procedureT;beginS;end;TSTprocedure;beginifsym=','thenbeginadvance;S;endend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序|,TST对于对于FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST(T’)={,,ε}|,TSTTST)(||^TaS)(SG(2)改写后的文法是否是LL(1)文法?给出预测分析表FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW(T’)={)}预测分析表a^(),#SSaS^ST()TTSTTSTTSTTTTST,是LL(1)文法P81.2文法:ETEEETFTTTFPFFFPEab+||*|()|||^(1)非终结符的FIRST和FOLLOWFIRST(E)={(,a,b,^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε}FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#}FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#}(2)考虑产生式:+EETTFFPEab||*|()|^||FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,该文法是LL(1)文法.(3)预测分析表+*()ab^#EETE'ETE'ETE'ETE'E'+EEEETTFTTFTTFTTFTT'TTTTTTTTTTTFFPFFPFFPFFPFF'FFF*FFFFFFPPE()PaPbP^(4)递归下降分析程序procedureE;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginT;E'endelseerrorendETE对于对于procedureE';beginifsym='+'thenbeginadvance;Eendelseifsym')'andsym'#'thenerrorendETE+|procedureT;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginF;T'endelseerrorendTFTTFT*|对于对于procedureT';beginifsym='('orsym='a'orsym='b'orsym='^'thenTelseifsym='*'thenerrorendprocedureF;beginifsym='('orsym='a'orsym='b'orsym='^'thenbeginP;F'endelseerrorendFPFFF*|procedureF';beginifsym='*'thenbeginadvance;F'endend对于对于procedureP;beginifsym='a'orsym='b'orsym='^'thenadvanceelseifsym='('thenbeginadvance;E;ifsym=')'thenadvanceelseerrorendelseerrorend;PEab()|||^对于第五章语法分析•重点：基本概念算符优先文法LR(0),SLR分析法比较两种语法分析方法•自下而上分析从语法树的末端开始，根据文法规则，对输入串步步向上归约，直到根结点。归约的对象是句柄，若归约成功，则证明输入串是该文法的一个句子，否则输入串有语法错误•自上而下分析从文法的开始符号（根结点）出发，对任何输入串，试图用一切可能的办法，自上而下地建立一棵语法树。一般的，当某一候选式与输入符号不匹配时，就要回溯，一直退回到可以使用另一个候选式的地方基本概念短语直接短语句柄素短语最左素短语定义：令G是一个文法，S是文法的开始符号，假定是文法G的一个句型，如果有AS*+A则称是句型相对于非终结符A的短语。特别是，如果有A,则称是句型相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。一个文法G的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。最左素短语是指处于句型最左边的那个素短语。短语直接短语句柄寻找方法：1.画出句型对应的语法树2.在该语法树按下列方法寻找：以某非终结符为根的两代以上的子树的所有末端结点从左