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

1、;.目录第一章2词法分析：2语义法分析2中间代码2第二章21.根据语言写出文法22.根据文法写语，描述其特点(必考大题 2-3 类型 )33.文法的规范推导、语法树、短语、句柄（必考大题，2-7，2-11）4第三章101.给出一个正规文法(左线性、右线性方法），写出其状态转换图(必考 )101.1 右线性文法写出状态转换图(必考 )101.2 状态转换图写出右线性文法g111.3 左线性文法写出状态转换图(必考 )122.非确定自动机的确定化13第四章14第五章14属性文法与属性翻译文法14逆波兰式（大题）14四元式（大题）15;.;.第一章词法分析： 分析源程序的结构，判断它是否是相应程序设

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

3、别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。v n 和 v 不含公共的元素，即 v n v = ,通常用 v 表示 v n v ， v 称为文法 g 的字母表或字汇表。一个文法的有如下几种写法 g=(s,a ，a,b ，p，s)其中 p：saaba aba aaba g：s aabaabaaaba gs ： a ab a aab a s aab gs ： a ab |aab |saab1.根据语言写出文法2.构造产生下列语言的文法（1） a n bn |n 0;.;.解：对应文法为 g(s) = (s,a,b, s| asb ,s)（2）anbmcp|n,m,p 0解

4、：对应文法为 g(s) = (s,x,y,a,b,c,sas|x,x bx|y,y cy| ,s)（3）a n#bn,|n 0 c n #dn |n 0 解：对应文法为 g(s) = (s,x,y,a,b,c,d,#, sx, s y,xaxb|#,y cyd|# ,s) 或者gs ：sx|yxaxb|#ycyd|#（4）w#wr# | w?0,1*,wr是 w的逆序排列 解： g(s) = (s,w,r,0,1,#, s w#, w0w0|1w1|# ,s)（5）任何不是以 0 打头的所有奇整数所组成的集合解： g(s) = (s,a,b,i,j,-,0,1,2,3,4,5,6,7,8,9,

5、sj|ibj,b 0b|ib|e, ij|2|4|6|8, j1|3|5|7|9,s)（6）所有偶数个 0 和偶数个 1 所组成的符号串集合解：对应文法为s 0a|1b|e ， a 0s|1c b 0c|1s c1a|0b2.根据文法写语，描述其特点(必考大题2-3 类型 )例 3 写出文法 g：(1) s asbe（2) s abe(3) eb be (4) ab ab(5) bb bb (6) bebe(7) ee ee 所产生的语言。s =asbe =aasbebe = aaabebebe=aaabbeebe=aaabbebee aaabbbeee =aaabbbeee =aaabbbe

6、ee =aaabbbeee =aaabbbeee aaabbbeee=aaabbbeee ，即 a 3b3e3;.;.2-3.描述语言特点（1）s10s0 saa aba aa解：本文法构成的 言集 ：l(g)=(10)nabma0n|n, m 0 。（2）sss s1a0a 1a0a解： l(g)=1n10n11n20n2 1nm0nm |n1,n2, ,nm 0；且 n1,n2, nm不全 零 言特点是： 生的句子中， 0、1 个数相同，并且若干相接的 1 后必然 接数量相同 的 0。（3）s1asb0a1aa cbb0b cc1c0c解：本文法构成的 言集 ： l(g)=1p1n0n|p

7、 1,n 0 1n0n0q|q 1,n 0 ，特点是具有 1p1n0n 或 1n0n0q 形式， 一步，可知其具有形式 1n0mn,m 0, 且 n+m0。（4）sbadcaagsg a a解：可知， s= =basndc n 0 言特点是： 生的句子中， 是以 ba 开 dc 尾的串 , 且 ba、dc 个数相同。（5）sass sa解： l(g)=a(2n-1)|n 1 可知：奇数个 a3.文法的规范推导、 语法树、短语、句柄（必考大题， 2-7 ，2-11 ）最右推 常被称 范推 。由 范推 所得的句型称 范句型。 法 是 句型的推 出的一个 形表示;.;.其语法树为：;.;.2-7.解

8、：aacb 是文法 gs 中的句子，相应语法树是：;.;.最右推 ： s=aacb=aacb=aacb最左推 ： s=aacb=aacb=aacb（ 2） aabacbadcd 不是文法 gs 中的句子因 文法中的句子不可能以非 符 d 尾（ 3） aacbccb 不是文法 gs 中的句子可知， aacbccb 是文法 gs 的一个句型的一部分，而不是一个句子。（ 4） aacabcbcccaacdca 不是文法 gs 中的句子因 符 d 后必然要跟 符a，所以不可能出 dc 的句子。（ 5） aacabcbcccaacbca 不是文法 gs 中的句子由（ 1）可知： aacb 可 s，由文法

9、的 生式 可知， 符 c 后不可能跟非 符 s，所以不可能出 caacb 的句子。2-11.解：(1) s ab sc a ba aa b asb bcbbaacb上面推 中，下划 部分 当前句型的句柄。 的 法 ：;.;.全部的短语：第一个 a (a1) 是句子 bbaacb 相对于非终结符 a (a1) ( 产生式 a?a）的短语（直接短语）；b1a1 是句子 bbaacb 相对于非终结符a2 的短语；b2b1a1 是句子 bbaacb 相对于非终结符a3的短语；c 是句子 bbaacb 相对于非终结符s1（产生式 s?c）的短语（直接短语）；a2cb3 是句子 bbaacb 相对于非终结

10、符 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+ f i+ f f*i+ fp*i+ f i*i+ ffi*i+ fpi*i+ fii*i+ pii*i+ iii*i+ ;.;.四类文法在描述语法的能力上是依次减弱的.因而有 :第三章1

11、.给出一个正规文法( 左线性、 右线性方法），写出其状态转换图 (必考 )1.1 右线性文法写出状态转换图(必考 );.;.1.2 状态转换图写出右线性文法g;.;.对应的右线性文法为：sabbbccbc|affcf| 对应的右线性文法为：sab|bcbbc|acbc|a1.3 左线性文法写出状态转换图(必考 )例 1：文法 g（e）为：eea|baba|bb画出该文法对应的状态转换图。;.;.例 2： (课堂练习 )文法 g（z）为：z u0|v1 uz1|1vz0|0画出该文法对应的状态转换图。2.非确定自动机的确定化nfa n;.;.第四章第五章属性文法与属性翻译文法文法符号的语义性质称

12、为该文法符号的语义属性（attributes），简称为属性。属性文法 ag 是一个四元组： ag=(g,a,r,b), 其中 ,g 是已简化的 cfg;a= x va(x) 是属性的有限集合 ;r= p pr(p)是属性定义规则的有限集;b=p pb(p)是条件的有限集合， b(p)用于描述使规则r(p)有效的条件属性文法实际上就是对前后文无关文法的一种拓广逆波兰式（大题）例 1:写出条件语句 if a0then x:=x+1 elsex :=4*(x-1) 的逆波兰表示;.;.解 :假设 bz 表示假 (0)转 ,br 表示无条件转 ;再假设该条件语句的逆波兰形式的首地址为 21,则得该语句的逆波兰表示为 :例 2:写出当型语句子课堂练习 whilex+y3dobegina:=a+3*b; b:=a+e-f*eend;的逆波兰表示 .解 : 假设 bz,表示假 (0)转,br 表示无条件转 ,再假设该语句的逆波兰形式的首地址为 1,该语句的逆波兰表示为 :四元式（大题）当 op 为一元运算符时，对应的四元式为：(op,arg1,-,result)当 op 为跳转语句时，对应的四元式为：(jrop,arg1, arg2 地,址 )如：当 ab 时跳转到 100，表示为：(j,a, b ,地址 )无条件转移语句，对应的四元式为：(j,-,-, 地址 ) 。例：写出 a:=b