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

...wd......wd......wd...目录\l"_Toc359442713#_Toc359442713"第一章2\l"_Toc359442714#_Toc359442714"词法分析：2\l"_Toc359442715#_Toc359442715"语义法分析2\l"_Toc359442716#_Toc359442716"中间代码2\l"_Toc359442717#_Toc359442717"第二章2\l"_Toc359442718#_Toc359442718"1.根据语言写出文法2\l"_Toc359442719#_Toc359442719"2.根据文法写语，描述其特点(必考大题2-3类型)3\l"_Toc359442720#_Toc359442720"3.文法的标准推导、语法树、短语、句柄〔必考大题，2-7，2-11〕3\l"_Toc359442721#_Toc359442721"第三章3\l"_Toc359442722#_Toc359442722"1.给出一个正规文法(左线性、右线性方法〕，写出其状态转换图(必考)3\l"_Toc359442723#_Toc359442723"1.1右线性文法写出状态转换图(必考)3\l"_Toc359442724#_Toc359442724"1.2状态转换图写出右线性文法G3\l"_Toc359442725#_Toc359442725"1.3左线性文法写出状态转换图(必考)3\l"_Toc359442726#_Toc359442726"2.非确定自动机确实定化3\l"_Toc359442727#_Toc359442727"第四章3\l"_Toc359442728#_Toc359442728"第五章3\l"_Toc359442729#_Toc359442729"属性文法与属性翻译文法3\l"_Toc359442730#_Toc359442730"逆波兰式〔大题〕3\l"_Toc359442731#_Toc359442731"四元式〔大题〕3第一章词法分析：分析源程序的构造，判断它是否是相应程序设计语言的合法程序语义法分析的任务是根据语言的语义规则对语法分析得到的语法构造进展静态的语义检查〔确定类型、类型与运算合法性检查、识别含义等〕，并且转换成另一种内部形式〔语义树〕表示出来或者直接用目标语言表示出来。中间代码是一种构造简单、含义明确的记号系统，这种记号系统可以设计为多种多样的形式，重要的设计原则为两点：一是容易生成；二是便于优化、移值；三是容易将它翻译成目标代码第二章文法G定义为四元组(VN，V→，P，S)其中VN为非终结符号(或语法实体，或变量)集；V→为终结符号集；P为产生式(也称规则)的集合；VN，V→和P是非空有穷集。S称作识别符号或开场符号，它是一个非终结符，至少要在一条产生式中作为左部出现。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|aAb|εS→aAb1.根据语言写出文法2.构造产生以下语言的文法〔1〕{anbn|n≥0}解：对应文法为G(S)=({S},{a,b},{S→ε|aSb},S)〔2〕{anbmcp|n,m,p≥0}解：对应文法为G(S)=({S,X,Y},{a,b,c},{S→aS|X,X→bX|Y,Y→cY|ε},S)〔3〕{an#bn,|n≥0}∪{cn#dn|n≥0}解：对应文法为G(S)=({S,X,Y},{a,b,c,d,#},{S→X,S→Y,X→aXb|#,Y→cYd|#},S)或者G[S]：S→X|YX→aXb|#Y→cYd|#〔4〕{w#wr#|w?{0,1}*,wr是w的逆序排列}解：G(S)=({S,W,R},{0,1,#},{S→W#,W→0W0|1W1|#},S)〔5〕任何不是以0打头的所有奇整数所组成的集合解：G(S)=({S,A,B,I,J},{-,0,1,2,3,4,5,6,7,8,9},{S→J|IBJ,B→0B|IB|e,I→J|2|4|6|8,Jà1|3|5|7|9},S)〔6〕所有偶数个0和偶数个1所组成的符号串集合解：对应文法为S→0A|1B|e，A→0S|1CB→0C|1SC→1A|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=>aSBE=>aaSBEBE=>aaaBEBEBE=>aaaBBEEBE=>aaaBBEBEE

aaaBBBEEE=>aaabBBEEE=>aaabbBEEE=>aaabbbEEE=>aaabbbeEE

aaabbbeeE=>aaabbbeee，即a3b3e32-3.描述语言特点〔1〕S→10S0S→aAA→bAA→a解：本文法构成的语言集为：L(G)={(10)nabma0n|n,m≥0}。〔2〕S→SSS→1A0A→1A解：L(G)={1n10n11n20n2…1nm0nm|n1,n2,…,nm≥0；且n1,n2,…nm不全为零}该语言特点是：产生的句子中，0、1个数一样，并且假设干相接的1后必然紧接数量一样连续的0。〔3〕S→1AS→B0A→1AA→CB→B0B→CC→1C0C解：本文法构成的语言集为：L(G)={1p1n0n|p≥1,n≥0}∪{1n0n0q|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)|n≥1}可知：奇数个a3.文法的标准推导、语法树、短语、句柄〔必考大题，2-7，2-11〕最右推导常被称为标准推导。由标准推导所得的句型称为标准句型。语法树是对句型的推导给出的一个图形表示其语法树为：2-7.解：aacb是文法G[S]中的句子，相应语法树是：最右推导：S=>aAcB=>aAcb=>aacb最左推导：S=>aAcB=>aacB=>aacb〔2〕aabacbadcd不是文法G[S]中的句子因为文法中的句子不可能以非终结符d结尾〔3〕aacbccb不是文法G[S]中的句子可知，aacbccb仅是文法G[S]的一个句型的一局部，而不是一个句子。〔4〕aacabcbcccaacdca不是文法G[S]中的句子因为终结符d后必然要跟终结符a，所以不可能出现…dc…这样的句子。〔5〕aacabcbcccaacbca不是文法G[S]中的句子由〔1〕可知：aacb可归约为S，由文法的产生式规则可知，终结符c后不可能跟非终结符S，所以不可能出现…caacb…这样的句子。2-11.解：(1)S→ABS→cA→bAA→aB→aSbB→cbbaacb上面推导中，下划线局部为当前句型的句柄。对应的语法树为：全部的短语：第一个a(a1)是句子bbaacb相对于非终结符A(A1)(产生式A?a〕的短语〔直接短语〕；b1a1是句子bbaacb相对于非终结符A2的短语；b2b1a1是句子bbaacb相对于非终结符A3的短语；c是句子bbaacb相对于非终结符S1〔产生式S?c〕的短语〔直接短语〕；a2cb3是句子bbaacb相对于非终结符B的短语；b2b1a1a注：符号的下标是为了描述方便加上去的。〔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+↑→F→P*i+↑→F→i*i+↑→FFi*i+↑→FPi*i+↑→Fii*i+↑→Pii*i+↑→iii*i+↑四类文法在描述语法的能力上是依次减弱的.因而有:第三章1.给出一个正规文法(左线性、右线性方法〕，写出其状态转换图(必考)1.1右线性文法写出状态转换图(必考)1.2状态转换图写出右线性文法G对应的右线性文法为：S→aB

B→bC

C→bC|aF

F→cF|ε对应的右线性文法为：S→Ab|bC

B→bC|a

C→bC|a1.3左线性文法写出状态转换图(必考)例1：文法G〔E〕为：

E→Ea|Ba

B→a|Bb

画出该文法对应的状态转换图。例2：(课堂练习)文法G〔Z〕为：

Z→U0|V1

U→Z1|1

V→Z0|0

画出该文法对应的状态转换图。2.非确定自动机确实定化NFAN第四章第五章属性文法与属性翻译文法文法符号的语义性质称为该文法符号的语义属性〔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:写出条件语句IFa>0THENx:=x+1ELSEx:=4*(x-1)的逆波兰表示解:假设BZ表示假(0)转,BR表示无条件转;再假设该条件语句的逆波兰形式的首地址为21,则得该语句的逆波兰表示为:例2:写出当型语句子[课堂练习]WHILEx+y>3DOBEGINa:=a+3*b;b:=a+e-f*eEND;的逆波兰表示.解:假设BZ,表示假(0)转,BR表示无条件转,再假设该语句的逆波兰形式的首地址为1,该语句的逆波兰表示为:四元式〔大题〕当op为一元运算符时，对应的四元式为： (op,arg1,-,result)当op为跳转语句时，对应的四元式为：(jrop,arg1,arg2,地址)如：当a>b时跳转到100，表示为：(j>,a,b,地址)无条