程序设计语言编译原理_考试重点.doc

程序设计语言编译原理_考试重点(终).doc第一章 引论 于宿主机的机器代码的程序。 到尾扫描一次,并作有关的加工处理,态集合、有穷字母表、转换函数、唯一1.编译程序分几个阶段,每个阶段的任14.可变目标编译程序,如果不需要重生成新的中间结果或目标程序。 的初始状态、终止状态集合。一个确定务是什么, 新编译程序中与机器无关的部分就能编译前段,由与源程序有关但与目标程有限自动机,DFA, M是一个五元式,五个阶段,词法分析、语法分析、语义改变目标机,则该编译程序就叫做可变序无关的那些部分组成。包括词法分M , (S,?,s0 ,F) ,其中S是一个有分析、中间代码生成、优化、目标代码目标编译程序。 析、语法分析、语义分析与中间代码和限集,它的每个元素称为一个状态,?生成 PS,世界上第一个编译程序一些优化工作。 是一个有穷字母表,它的每个元素称为词法分析任务,输入源程序,对构成源FORTRAN编译程序20世纪50年编译后端,编译程序中与目标机有关的一个输入字符,是一个从S?至S的程序的字符串进行扫描和分解,识别出代 那些部分,后端不依赖于源语言而仅仅单值部分映射。 (s,a)=s?意味着,当一个个的单词。,如基本字,标识符,15.编译过程 依赖于中间语言。 现行状态为、输入字符为a时,将转换常数,算符和界符,。 第一阶段,词法分析词法分析器 集成化的程序设计环境的特点,它将相到下一状态s?。我们称s?为s的一个后语法分析任务,在词法分析基础上,将1)任务,输入源程序,对构成源程序的互独立的程序设计工具集成起来,以使继状s0?S是唯一的初态F 是一个终态单词符号串转化为语法单位,语法范字符串进行扫描和分解,识别出一个个为程序员提供完整的、一体化的支持,集,可空,。一个非确定有限自动机畴,短语、子句、句子、程序段、程的单词,亦称单词符号或简称符号,从而进一步提高程序开放效率,改善程,NFA, M是一个五元式,M , (S,序,并确定整个输入串是否构成语法标示符,常熟,算符和界符。2,单词序质量。 ?,S0 ,F) ,其中S是一个有限集,它上正确的程序。 符号是语言的基本组成成分,是人们理17.T形图 的每个元素称为一个状态,?是一个有语义分析和中间代码生成任务,对语法解和编程的基本要素。3)描述词法规则第二章 高级语言及其语法描述 穷字母表,它的每个元素称为一个输入分析所识别出的各类语法范畴,分析其的有效工具是,正规式和有限自动机 1. 程序语言是由语法和语义两方面定字符,是一个从S?*至S的子集的含义,并进行初步翻译,产生中间代第二阶段,语法分析,词法,分析义的。 映射,即, S?* ? 2s,S0?S是唯码,。 器 2.上下文无关文法的定义,四个组成部一的初态,F是一个终态集,可空,。 代码优化任务,对于代码,主要是中间1)任务,在词法分析的基础上,根据语分,一组终结符号、一组非终结符号、3.设有确定的有限自动机DFA M = 代码,进行加工变换,以期能够产生更言的语法规则,把单词符号分解成各类一个开始符号、一组产生式。一个上下(0,1,2,3,a,b,0,3),其中为:为高效,省时间和空间,的目标代码 。 语法单位,如“短语”、“子句”、“句子”、“程序文无关文法G是一个四元式,VT,VN,S, (0,a)=1 (0,b)=2 (1,a)=3 目标代码生成任务,将中间代码变换成段”和“程序”等。通过语法分析,确定整P ,其中: VT,是非空有限集,它的(1,b)=2 (2,a)=1 (2,b)=3 (3,a)=3 特定机器上的低级语言代码 个输入串是否构成语法上正确的“程每个元素是终结符号,VN,是非空有(3,b)=3 2.表格管理和出错处理,编译各阶段均序”。2)语法分析所依据的是语言的语法限集,它的每个元素是非终结符号,请画出状态转换矩阵和状态转化图。相须维持表格并进行表格管理,建表的技规则。通常是上下文无关文法描述、3) VT?VN=,VT?VN=V;S,S?应的状态转换矩阵如下表, 术支持是数据结构,表格的分类、结构、词法分析是一种线性分析,而语法分析VN,称为开始符号,P ,产生式集合状态 a b 处理方法决定于语言及机器,还有优化是一种层次结构分析。 ,有限,每个产生式形式是 P-| P?0 1 2 措施。一个好的编译程序应该,全,最第三阶段,语义分析和中间代码产生VN, ?(VT?VN)*,S至少一次为P , 1 3 2 大限度发现错误,准,准确指出错误的语义分析器 3.推导、最左推导、最右推导,1、推2 1 3 性质和发生地点,局部化,将错误的影1)任务,对语法分析所识别出的各类语导,如两个串u0、un,存在一个串序3 3 3 响限制在尽可能小的范围内。源程序中法范畴,分析其含义,并进行初步翻译列u0=u1=un,则我们称这个序的错误通常分为 ,语法错误,不符合,产生中间代码,。2)对每种语法范畴列是从u0到un 的一个推导。 对应的状态转换图 语法,或词法,规则的错误,如单词拼进行静态语义检查进行中间代码的U1un,表示从u0出发,经一步写错误、括号不匹配 . 语义错误,不翻译。3)语义分析所依据的是语言的语或若干步,可推导出un. 符合语义规则的错误,如说明错误、作义规则,通常使用属性文法描述语义规U1un,表示从u0出发,经0步1 a 用域错误、类型不匹配 . 则。4)中间代码,一种含义明确、便于或若干步,可推导出un. a 3.前端、后端,编译前端主要由与源语处理的记号系统,它通常独立于具体的最左推导是指,任何一步=都是对言有关,但与目标机无关的那些部分组硬件。5)中间代码的四元式表示形式。中的最左非终结符进行替换的。最右推0 b 3 a a，成。编译后端包括编译程序中与目标机此外还有三元式、间接三元式、逆波兰导是指,任何一步=都是对中的最b 有关记号和树。 右非终结符进行替换的。 的那些部分。 b 2 b 4.语法树,在编译中产生语法树是为了4.遍,根据系统资源的状况、运行目标算符 左操右操结果 4.设计一个DFA,要求能够识别?=0,1语法分析。 的要求等,可以将一个编译程序设作数 作数 上能被5整除的二 5、什么是句型,什么是句子,什么是计成多遍扫描的形式,在每一遍扫描 进制数。 语言, 中,完成不同的任务。遍可以和阶段相第四阶段,优化优化器 假定G是一个文法,S是它的开始符对应,也可无关。单遍代码不太有效。1)任务,在于前段产生的中间代码进行5.词法分析的流号。如果S= ,则称是一个句型。遍 是对源程序或源程序的中间结果0 0 加工交换,以期在最后阶段能产生更1 从头到尾扫描一次,并作有关的加工处仅含终结符的句型是一个句子。文法G为高效,省时间和空间,的目标代码。理,生成新的中间结果或目标程序。 所产生的句子的全体是一个语言。 语2)优化的主要方面有,公共字表达式、0 0 1 5.“运算符与运算对象类型不符”属于语言是由句子组成的集合,是由一组记号0 优化循环、删除无用代码等等。3)优化1 义错误 所构成的集合。 所依据的原则,程序的等价变化原则。 程 6.算法逻辑上的错误属于语义错误 6.乔姆斯基把文法分成4种类型,即0开第五阶段,目标代码生成目标代码第四章 语7.编译程序,能够把某一种语言程序转型文法、1型文法、2型文法和3型文生成器 1 法分析自1 换成另一种语言程序,而后者与前者在法。0型文法也称为短语文法。1型文1)任务,吧中间代码,或经优化处理后,始上而下分析 0 法也称为上下文有关文法。2型文法也逻辑上是等价的一种程序。通常是从高变换成特定机器上的低级语言代码。2)1.语法分析器的功能,识别语法成分,称为上下文无关文法。3型文法也称为级语言转换成为低级语言。 形式,绝对指令代码或可重定位的指令并作语法检查. 正规文法。与程序语言语法有关的文法8.解释程序,它以该语言写的源程序作开代码或汇编指令代码。 2.自上而下语法分析方法遇到的主要是上下文无关文法。 为输入,但是不产生目标代码,而是边16.编译程序的结构 问题是回溯和左递归。 第三章 词法分析 解释边执行源程序本身。 语法错误,指源程序中不符合语法,或3.把一个文法改造成任何非终结符的始 1.状态转换图,使用状态转换图是设计9.诊断编译程序,专门用于帮助程序开词法,规则的错误,他们可在词法分析所有候选式首符集两两不相交的方法发和调试的编译程序。 词法分析程序的一种好途径,状态转换和语法分析时检测出来 是提取公共左因子。 10.优化编译程序,着重于提高目标代图是一张有限方向图。在状态转换图语法错误,指源程序中不符合语义规则4.LL,1,分析法中,第一个L表示从码效率的编译程序。 中,结点代表状态,用圆圈表示。一个的错误,一般在语义分析时检测出来,左到右扫描输入串,第二个L表示最左11.宿主机,运行编译程序的计算机。 状态转换图可用于识别,或接受,一定有的要在运行时才能检测出来。通常推导。1表示分析时每步只需向前看一12.目标机,运行编译程序所产生目标的字符串。 有,说明错误、作用域错误、类型不一个符号。 代码的计算机。 2.确定的有限自动机,DFA,、非确定致等 5.LL,1,文法的条件,1文法不含左13.交叉编译程序,一个程序产生不同有限自动机,NFA,。五元式,有限状遍,对源程序或源程序的中间结果从头递归2,FIRST()? FIRST() = 3,对文法中的每个非终结符A,若它存在2.写出产生式、语义规则和语义子程序的后缀表示。 能块。 某个候选首符集包含,则 FIRST,A,之间的关系。 3.已知A是一个1020的数组(每维下5. SDL系统中的功能块最终都需要定? FOLLOW,A,=。 ?产生式:一个产生式描述了一个语法界均为1),每个元素占1个单元,且按义为进程。 6. 对下文法,计算每个非终结符的单位,但它只说明了该语法单位能产生行存放,要求写出,赋值语句X=AI,J6.在SDL系统中的基本单位是进程实FIRST集合和FOLLOW集合。E?TE 的符号串,并未指明所产生的符号串有的四元式序列。 例 。 E?+E| T?FT T?T| F?PF 什么实际意义,即该符号串究竟要做什100 (*,I,20,T1) /*d2=2 7. SDL描述系统行为的基础是扩展的F?*F| P?(E)|a|b|? 么。?语义规则:一个产生式的语义规101 (+,J,T1,T1) /*得到 有限状态自动机。 First(E)= First(T)= First(F)=(,a,b, ?则描述了该产生式的具体的动作意义,102 (?,A,21,T2) /*得到A 8 SDL 的每个进程实例就是有限状态即该产生式产生的符号串要做什么。?103(= ,T2T1,_,T3)/*T2T1即为自动机。 First(E)=+, ,First(T)=(,a,b, ?, 语义子程序:按照产生式的语义规则生AI, J即T3=T21*/ 9. SDL中,进程规定了系统的动态结 成某种中间代码,实现相应的动作。 104 (=,T3,_,X) 构。 First(F)=*, ,Follow(E)= 3.对于文法的每个产生式都配备了一第十章 优化 Block代表了系统的静态结构 。 Follow(E)=#, ) 组属性的计算规则,称为属性。 1,为了获得更优化的程序,可以从哪一、单项选择题(共10小题,每小题2Follow(T)= Follow(T)=+,#, ) 4.文法符号的属性有两种,一种称为综些层次上对程序进行优化,为了获得分,共20分) Follow(F)= Follow(F)=(,a,b, ?,+,),# 合属性,一种称为继承属性。综合属性更优化的程序,可以从各个环节着手,1,语言是 传递信息的方向是自下而上。继承属性在源代码级,可以选择适当的算法和安A句子的集合 B,产生式的集合 C,符Follow(P)=*, (,a,b, ?,+,),# 传递信息的方向是自上而下。 排适当的实现语句来提高程序的效率。号串的集合 D,句型的集合 7.两种实现方法,递归下降分析法、预5. 在分析树中,一个结点的综合属性在语义动作的设计上,考虑产生更高效测分析程序。 值是从其子结点的属性值计算出来的。的中间代码,并为优化阶段做准备。在2,编译程序前三个阶段完成的工作是 第五章 语法分析自下而上分析 一个结点的继承属性由此结点的父结中间代码级,安排专门的优化阶段,进A,词法分析、语法分析和代码优化 1. 简述自下而上的语法分析方法:就是点或兄弟结点的某些属性确定。 行各种等价变换,以改进代码的效率。B,代码生成、代码优化和词法分析 从输入串开始,逐步进行“规约”,直至6.为文法S ?( L ) | a L ? L , S | S在目标代码级,考虑如何有效地利用寄C,词法分析、语法分析、语义分析和规约到文法的开始符号,或者说从语法写一个语法制导定义,它输出括号的对存器,如何选择指令,以及进行窥孔优树的树叶开始,逐步向上规约,直至规数。 化等。 中间代码生成 约到根节点。 S ?S print (S. num) 2.常用的优化方法 D,词法分析、语法分析和代码优化 2.一个句型的句柄是该句型的最左直S ?( L ) S. num := L.num 局部优化: 删除公共子表达式、复写传3,一个句型中称为句柄的是该句型的接短语。 S ? a S. num := 0 播、删除无用代码。循环优化,代码外3.规范规约是指最右推导的逆过程。 L ?L1 , S L. num :=max L1. 提、强度削弱、删除归纳变量 最左A,非终结符号 B,短语 C,句4.算符优先分析法1,特别适应于表达num , S. num 3.程序基本块是指程序中一顺序执行子 D,直接短语 式分析的方法2,算符优先分析法中,L ?S L. num := S.num 的语句序列,其中只有一个入口和一个4,下推自动机识别的语言是 优先表中存储的是优先关系3,算符优7.为文法S?( L ) | a L ? L , S | S出口。 先分析法的可规约串是句型的最左素写一个翻译方案,它输出每个a的嵌套4.基本块的入口、基本块的划分、流图,A,0型语言 B,1型语言 C,2型语短语。 深度。例如,对于( a , ( a , a) ),输出入口就是其中的第一个语句1.求出四言 D,3型语言 5.LR分析法:1,LR,K,文法是从左到的结果是1 2 2。 元式程序中的各个基本块中的入口地5,扫描器所完成的任务是从字符串形右分析,每次向貌似句柄的符号串后看S?S. depth := 0 S 1)程序的第一个语句2)能由条件转移式的源程序中识别出一个个具有独立K个输入符号的一种编译方法2,四种S?L. depth := S. depth + 1 ( L ) S ?语句或无条件转移语句转移到的语句分析表3,LR(0)项目的含义4,例给定a print (S. depth) 3)紧跟在条件转移语句后面的语句2. 含义的最小语法单位即 文法,S?AS|b A?SA|a要求列出这L ?L1. depth := L. depth L1 , S. 对以上求出的每一人口语句,构造其所A, 字符 B,单词 C,句子 D,句个文法的所有LR(0)项目。 depth := L. depth S 属的基本块。它是由该人口语句,开始,型 S?.AS S?A.S S?AS. S?.b L?S. depth := L. depth S 到一转移语句(包括该转移语句),或到S?b. A?.SA A?S.A A?8.S-属性文法,只含有综合属性。可借一停语句(包括该停语句)之间的语句序6,对应Chomsky四种文法的四种语言SA. A?.a A?a. 助于LR分析器实现。采用自底向上分列组成的。3. 删除无用代码。凡未被之间的关系是 5,写出LR(0)分析表的构造步骤:?确析,例如LR分析,首先给出S-属性定纳入某一基本块中的语句,都是程序中 A,L0 L1 L2 L3 定G的LR(0)项目?以LR(0)项目为状义,然后,把S-属性定义变成可执行的控制流程无法到达的语句,从而也是不态代码段,这就构成了翻译程序。L-属性会被执行到的语句,我们可把它们从程,构造一个能识别文法G的所有活前B,L3 L2 L1 L0 文法,如果对于每个产生式A序中删除。 缀的NFA?利用子集法,将NFA确定化, C,L3=L2 L1 L0 ,5.已知如下中间代码序列,1,read X 成为以项目集合为状态的DFA根据?X1X2Xn,其每个语义规则中的每D,L0 L1 L2=L3 利用上述DFA可直接构造出LR分析个属性或者是综合属性,或者是Xj2,read Y 7,词法分析的任务是 表。 ,1=j=n) 的一个继承属性且这个继 3,R := X mod Y 4,if R=0 goto(8) 6,比较LR(0)、SLR,1,、LR,1,、承属性仅依赖于, 5,X := Y A,识别单词 B,分析句子的含义 LALR,1,分析表的优缺点:这4种分a. 产生式Xj的左边符号X1,6,Y := R 7,goto (3) 8,write Y C,识别句子 D,生成目标代码 析表都能识别对应文法的全部句子,其X2,Xj-1的属性 9,halt 8,常用的中间代码形式不含 共同特征就是用规范规约的方法寻找 b. A的继承属性。S-属性文法是L-属要求,1,写出基本块的入口语句。2,句柄进行规约。在这4种方法中,LR性文法。 为其划分基本块。3,为其构造流图。A,三元式 B,四元式 C,逆,0,分析表对文法的要求较高,其构第七章 语义分析和中间代码产生 ?入口语句,1、3、5、8 ?基本块和波兰式 D,语法树 造方法是其它表构造方法的基础,SLR1.常用的中间代码的形式,后缀式,逆流图 (最后面的图) 代码优化的目的是 9,1,分析表对文法的要求有所降低,波兰式,、三地址码,三元式、四元式、1.目标代码的形式 容易实现,因而很有实用价值,LR,1,间接三元式,。 2.考虑问题1,指令选择2,寄存器分 A,节省时间 B,节省空间 C,节省分析表对文法的要求最低,适用于一大2.会用后缀式表示, 配3,计算顺序选择 时间和空间D,把编译程序进行等价交类文法,故其分析能力最强,但其实现表达式的后缀表示可以如下递归定义,SDL 换 代价过高,LALR,1,分析表的分析能1,如果E是变量或者常数,那么E的1. SDL把应用领域分为两部分SDL系10,代码生成阶段的主要任务是 力介于SLR,1,和LR,1,之间,实后缀表示就是E本身2,如果E是形式统和环境。 现代价比LR,1,低。 为E1 op E2的表达式,其中op是任意2. SDL中,系统与环境之间的通信可 A,把高级语言翻译成汇编语言 第六章 属性文法和语法制导定义 的二元算符,那么E的后缀表示是以通过什么来通信交换信号。 B,把高级语言翻译成机器语言 1.语法制导翻译法就是在语法分析的E1E2op,其中E1和E2分别是E1和3.SDL系统由系统、功能块和进程3个 C,把中间代码变换成依赖具体机器的过程中,随分析的过程,根据为每个产生E2的后缀表示3,如果E是形式为,E1)层次的实体组成。 式添加的语义动作进行翻译的方法。 的表达式,那么E1的后缀表示也是E4. SDL中每个系统可以划分为多个功目标代码 D,把汇编语言翻译成机器语言 址。通过DISPLAY表可以访问其外层的任何句型都能构造与之关联的 编译程序的工作情况有三种,汇编型、二、填空题,本大题共5小题,每小题过程的变量。 语法树。这棵树具有下列特征, 解释型和编译型。汇编型编译程序用来2分,共10分, 1. 简要说明语义分析的基本功能。 (1)根节点的标记是开始符号S。 将汇编语言编写的程序,按照一一对应1,编译程序首先要识别出源程序中每答,语义分析的基本功能包括: 确定类(2)每个节点的标记都是V中的一个符的关系,转换成用机器语言表示的程个(单词),然后再分析每个(句子)并翻型、类型检查、语义处理和某些静态语号。 序。解释型编译程序将高级语言程序的译其意义。 义检 查。 (3)若一棵子树的根节点为A,且其所有一个语句,先解释成为一组机器语言的2,编译器常用的语法分析方法有(自底2. 考虑文法 GS: S ? (T) | a+S | 直接子孙的标记从左向右的排列 指令,然后立即执行,执行完了,取下向上)和(自顶向下)两种。 a ;T ? T,S | S 次序为A1A2AR,那么A A1A2一组语句解释和执行,如此继续到完成3,通常把编译过程分为分析前端与综消除文法的左递归及提取公共左因子。 AR一定是P中的一条产生式。 一个程序止。用解释型编译程序,执行合后端两大阶段。词法、语法和语义分解,消除文法GS的左递归,S?(T) | (4)若一标记为A的节点至少有一个除速度很慢,但可以进行人和计算机的,析是对源程序的(分析),中间代码生成、a+S | a ;T?ST;T?,ST| 对话,随时可以修改高级语言的程序。它以外的子孙,则AVN。 代码优化与目标代码的生成则是对源提取公共左因子, S?(T) | aS;S?+S | (5)若树的所有叶节点上的标记从左到BASIC语言就是解释型高级语言。编译程序的(综合)。 ;T?ST ;T?,ST| 右排列为字符串w,则w是文法G 型编译程序将级语言编写的程序,一次4,程序设计语言的发展带来了日渐多3.试为表达式w+(a+b)*(c+d/(e-10)+8) 的句型,若w中仅含终结符号,则w就会部翻译成机器语言表示的程序,而变的运行时存储管理方案,主要分为两写出相应的逆波兰表示。解, w a b + c 为文法G所产生的句子。 且过程进行很快,在过程中,不能进行大类,即(静态存储分配)方案和(动态存d e 10 - / + 8 + * + 4,LR(0)分析器 人机对话修改。FORTRAN语言就是编储分配)方案。 5.已知文法 GS 为 S ? 所谓LR(0)分析,是指从左至右扫描译型高级语言。 5,对编译程序而言,输入数据是(源程aSb|Sb|b ,试证明文法 GS 为二义和自底向上的语法分析,且在分析的 2,编译程序的工作分为那几个阶段? 序),输出结果是(目标程序)。 文法。 每一步,只须根据分析栈当前已移进和 词法分析、语法分析和语义分析是对1,什么是S-属性文法,什么是L-属性证明,由文法GS,S?aSb|Sb|b,对归约出的全部文法符号,并至多再 源程序进行的分析(称为编译程序的前文法,它们之间有什么关系, 句子aabbbb对应的两棵语法树为, 向前查看0个输入符号,就能确定相对端),而中间代码生成、代码优化和代解答, 于某一产生式左部符号的句柄是否 码生成三个阶段合称为对源程序进行S-属性文法是只含有综合属性的属性已在分析栈的顶部形成,从而也就可以综合(称为编译程序的后端),它们从源文法。 ,2分, 确定当前所应采取的分析动作 (是 程序的中间表示建立起和源程序等价L-属性文法要求对于每个产生式移进还是按某一产生式进行归约等)。 的目标程序。 A X1X2Xn,其每个语义规则中的每5,语言和文法 3,简述自下而上的分析方法。 个属性或者是综合属性,或者是Xj的因此,文法GS为二义文法。 文法就是语言结构的定义和描述,是有 所谓自下而上分析法就是从输入串一个继承属性,且该属性仅依赖于, 1,词法分析 穷非空的产生式集合。 开始,逐步进行“归约”,直至归约到文产生式Xj的左边符号X1,X2Xj-1的词法分析的主要任务是从左向右扫描文法G定义为四元组的形式,G=(VN,法的开始符号,或者说从语法树的末端属性,A的继承属性。 每行源程序的符号,按照词法规则 VT,P,S)其中,VN 是非空有穷集合,开始,步步向上“归约”,直到根节点。 S-属性文法是L-属性文法的特例。 称为非终结符号集合,VT 是非空有穷从构成源程序的字符串中识别出一个4,简述代码优化的目的和意义。 2集合,称为终结符号集合,P是产生式,什么是句柄,什么是素短语, 个具有独立意义的最小语法单位, 代码优化是尽量生成“好”的代