资源描述：
《编译原理期末考试复习整理详细列出考试重点重点例题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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：S→aAb A→ab A→aAb A→ε ②G：S→aAb A→ab A→aAb A→ε ③G[S]：A→abA→aAbA→εS→aAb ④G[S]：A→ab
4、aAb
5、εS→aAb1.根据语言写出文法2.构造产生下列语言的文法 （1）{anbn
6、n≥0} 解：对应文法为G(S)=({S},{a,b},{S→
7、ε
8、aSb},S) （2）{anbmcp
9、n,m,p≥0} 解：对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS
10、X,X→bX
11、Y,Y→cY
12、ε},S) （3）{an#bn,
13、n≥0}∪{cn#dn
14、n≥0} 解：对应文法为G(S)=({S,X,Y},{a,b,c,d,#},{S→X,S→Y,X→aXb
15、#,Y→cYd
16、#},S)或者G[S]：S→X
17、Y X→aXb
18、#Y→cYd
19、# （4）{w#wr#
20、w?{0,1}*,wr是w的逆序排列} 解：G(S)=({S,W,R},{0,1,#},{S→W#,W→0W0
21、1W1
22、#},S) （5
23、）任何不是以0打头的所有奇整数所组成的集合 解：G(S)=({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J
24、IBJ,B→0B
25、IB
26、e,I→J
27、2
28、4
29、6
30、8,Jà1
31、3
32、5
33、7
34、9},S) （6）所有偶数个0和偶数个1所组成的符号串集合 解：对应文法为S→0A
35、1B
36、e，A→0S
37、1CB→0C
38、1SC→1A
39、0B2.根据文法写语，描述其特点(必考大题2-3类型)例3写出文法G：(1)S→aSBE（2)S→aBE (3)EB→BE(4)aB→ab (5)bB→bb(6)bE→be (7)eE→ee所产生的语言。S=>a
40、SBE=>aaSBEBE=>aaaBEBEBE=>aaaBBEEBE=>aaaBBEBEEaaaBBBEEE=>aaabBBEEE=>aaabbBEEE=>aaabbbEEE=>aaabbbeEEaaabbbeeE=>aaabbbeee，即a3b3e32-3.描述语言特点 （1）S→10S0S→aAA→bAA→a 解：本文法构成的语言集为：L(G)={(10)nabma0n
41、n,m≥0}。 （2）S→SSS→1A0A→1A0A→ε 解：L(G)={1n10n11n20n2…1nm0nm
42、n1,n2,…,nm≥0；且n1,n2,…nm不全为零}该语言特点是：产
43、生的句子中，0、1个数相同，并且若干相接的1后必然紧接数量相同连续的0。 （3）S→1AS→B0A→1AA→CB→B0B→CC→1C0C→ε 解：本文法构成的语言集为：L(G)={1p1n0n
44、p≥1,n≥0}∪{1n0n0q
45、q≥1,n≥0}，特点是具有1p1n0n或1n0n0q形式，进一步，可知其具有形式1n0mn,m≥0,且n+m>0。 （4）S→bAdcA→AGSG→εA→a 解：可知，S=>…=>baSndcn≥0 该语言特点是：产生的句子中，是以ba开头dc结尾的串,且ba、dc个数相同。 （5）S→aSSS→a 解：L(G)={a(2n-1
46、)
47、n≥1}可知：奇数个
