编译原理期末考试复习整理详细列出考试重点重点例题

1、真诚为您提供优质参考资料，若有不当之处，请指正。目录第一章2词法分析：2语义法分析2中间代码2第二章21.根据语言写出文法22.根据文法写语，描述其特点(必考大题2-3类型)33.文法的规范推导、语法树、短语、句柄（必考大题，2-7，2-11）3第三章31.给出一个正规文法 (左线性、右线性方法），写出其状态转换图(必考)31.1右线性文法写出状态转换图 (必考)31.2状态转换图写出右线性文法g31.3左线性文法写出状态转换图 (必考)32.非确定自动机的确定化3第四章3第五章3属性文法与属性翻译文法3逆波兰式（大题）3四元式（大题）3第一章词法分析：分析源程序的结构，判断它是否是相应程序设

2、计语言的合法程序语义法分析 的任务是根据语言的语义规则对语法分析得到的语法结构进行静态的语义检查（确定类型、类型与运算合法性检查、识别含义等），并且转换成另一种内部形式（语义树）表示出来或者直接用目标语言表示出来。中间代码是一种结构简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是便于优化、移值；三是容易将它翻译成目标代码第二章 文法g定义为四元组(vn，v，p，s )其中vn为非终结符号(或语法实体，或变量)集；v为终结符号集；p为产生式(也称规则)的集合； vn，v和p是非空有穷集。 s称作识别符号或开始符号，它是一个非终结符，至少要在

3、一条产生式中作为左部出现。 vn和v不含公共的元素，即vn v = ,通常用v表示vn v ，v称为文法g的字母表或字汇表。 一个文法的有如下几种写法 g=(s,a，a,b，p，s) 其中p：saab aab aaab a g：saab aab aaab a gs： aab aaab a s aab gs： aab |aab | saab1.根据语言写出文法2.构造产生下列语言的文法 （1） an bn |n0  解：对应文法为g(s) = (s,a,b, s| asb ,s)  （2）anbmcp|n,m,p0  解：对应文法为g(

4、s) = (s,x,y,a,b,c,sas|x,xbx|y,ycy|,s) （3）an#bn,|n0cn#dn |n0   解：对应文法为g(s) = (s,x,y,a,b,c,d,#, sx, sy,xaxb|#,ycyd|# ,s)或者gs： sx|y xaxb|# ycyd|# （4）w#wr# | w?0,1*,wr是w的逆序排列  解：g(s) = (s,w,r,0,1,#, sw#, w0w0|1w1|# ,s) （5）任何不是以0打头的所有奇整数所组成的集合  解：g(s) = (s,a,b

5、,i,j,-,0,1,2,3,4,5,6,7,8,9,sj|ibj,b0b|ib|e, ij|2|4|6|8, jà1|3|5|7|9,s) （6）所有偶数个0和偶数个1所组成的符号串集合  解：对应文法为 s0a|1b|e，a0s|1c b0c|1s c1a|0b2.根据文法写语，描述其特点(必考大题2-3类型)例3 写出文法g：(1) sasbe（2) sabe(3) ebbe (4) abab(5) bbbb (6) bebe(7) eeee 所产生的语言。 s =>asbe =>aasbebe => aaabebebe=>

6、aaabbeebe=>aaabbebee aaabbbeee =>aaabbbeee =>aaabbbeee =>aaabbbeee =>aaabbbeeeaaabbbeee=>aaabbbeee ，即 a3b3e3 2-3.描述语言特点 （1）s10s0 saa aba aa  解：本文法构成的语言集为：l(g)=(10)nabma0n|n, m0。 （2）sss s1a0a1a0a  解：l(g)=1n10n11n20n2 1nm0nm |n1,n2,nm0；且n1,n2,nm不全为零该语言特点

7、是：产生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同连续的0。 （3）s1asb0a1aacbb0bcc1c0c  解：本文法构成的语言集为：l(g)=1p1n0n|p1,n01n0n0q|q1,n0，特点是具有1p1n0n 或1n0n0q形式，进一步，可知其具有形式1n0mn,m0,且n+m>0。 （4）sbadcaagsgaa  解：可知，s=>=>basndc n0  该语言特点是：产生的句子中，是以ba开头dc结尾的串,且ba、dc个数相同。 （5）sass sa

8、  解：l(g)=a(2n-1)|n1可知：奇数个a3.文法的规范推导、语法树、短语、句柄（必考大题，2-7，2-11）最右推导常被称为规范推导。由规范推导所得的句型称为规范句型。语法树是对句型的推导给出的一个图形表示其语法树为：2-7.解：aacb是文法gs中的句子，相应语法树是：最右推导：s=>aacb=>aacb=>aacb最左推导：s=>aacb=>aacb=>aacb（2）aabacbadcd不是文法gs中的句子因为文法中的句子不可能以非终结符d结尾（3）aacbccb不是文法gs中的句子可知，aacbccb仅是文法gs的一个句

9、型的一部分，而不是一个句子。（4）aacabcbcccaacdca不是文法gs中的句子因为终结符d后必然要跟终结符a，所以不可能出现dc这样的句子。（5）aacabcbcccaacbca不是文法gs中的句子由（1）可知：aacb可归约为s，由文法的产生式规则可知，终结符c后不可能跟非终结符s，所以不可能出现caacb这样的句子。2-11.解：(1) sab sc aba aa basb bc bbaacb上面推导中，下划线部分为当前句型的句柄。对应的语法树为：全部的短语：第一个a (a1)是句子bbaacb相对于非终结符a (a1) (产生式a?a）的短语（直接短语）；b1a1是句子bbaac

10、b相对于非终结符a2的短语；b2b1a1是句子bbaacb相对于非终结符a3的短语；c是句子bbaacb相对于非终结符s1（产生式s?c）的短语（直接短语）；a2cb3是句子bbaacb相对于非终结符b的短语；b2b1a1a2cb3是句子bbaacb相对于非终结符s2的短语；注：符号的下标是为了描述方便加上去的。（2）句子（b）a（a）（b）的最右推导：s（as）（a（b）（saa）（b）（sa（a）（b）（b）a（a）（b）相应的语法树是：（3）解：iii*i+对应的语法树略。最右推导：e =>f=>fp fe fe+ fef+ fep+ fei+fi+ ff*i+fp*i+ f

11、i*i+ffi*i+ fpi*i+fii*i+ pii*i+iii*i+四类文法在描述语法的能力上是依次减弱的.因而有:第三章1.给出一个正规文法 (左线性、右线性方法），写出其状态转换图(必考)1.1右线性文法写出状态转换图 (必考) 1.2状态转换图写出右线性文法g对应的右线性文法为： sab bbc cbc|af fcf|对应的右线性文法为： sab|bc bbc|a cbc|a1.3左线性文法写出状态转换图 (必考)例1：文法g（e）为： eea|ba ba|bb 画出该文法对应的状态转换图。例2：(课堂练习)文法g（z）为： zu0|v1 uz1|1 vz0|0画出该文法对应的状态转

12、换图。2.非确定自动机的确定化nfa n第四章第五章属性文法与属性翻译文法文法符号的语义性质称为该文法符号的语义属性（attributes），简称为属性。属性文法ag是一个四元组：ag=(g,a,r,b), 其中,g是已简化的cfg; a=xva(x)是属性的有限集合; r= ppr(p)是属性定义规则的有限集; b=ppb(p)是条件的有限集合，b(p)用于描述使规则r(p)有效的条件属性文法实际上就是对前后文无关文法的一种拓广逆波兰式（大题）例1:写出条件语句if a>0 then x:=x+1 else x :=4*(x-1)的逆波兰表示解:假设bz表示假(0)转,br表示无条件转

13、;再假设该条件语句的逆波兰形式的首地址为21,则得该语句的逆波兰表示为:例2:写出当型语句子 课堂练习 while x+y>3 do begin a:=a+3*b; b:=a+e-f*e end; 的逆波兰表示.解: 假设bz,表示假(0)转,br表示无条件转,再假设该语句的逆波兰形式的首地址为1,该语句的逆波兰表示为:四元式（大题）当op为一元运算符时，对应的四元式为： (op,arg1,-,result)当op为跳转语句时，对应的四元式为： (jrop,arg1, arg2 ,地址) 如：当a>b时跳转到100，表示为： (j>,a, b ,地址)无条件转移语句， 对应的四元式为： (j,-,-,地址) 。例：写出a:=b*c