《《编译原理》总复习-07级》由会员分享,可在线阅读,更多相关《《编译原理》总复习-07级(10页珍藏版)》请在金锄头文库上搜索。
1、编译原理编译原理总复习总复习-07-07 级级第一章编译程序的概述第一章编译程序的概述(一)内容 本章介绍编译程序在计算机科学中的地位和作用,介绍编译技术的发展历史,讲解编 译程序、解释程序的基本概念,概述编译过程,介绍编译程序的逻辑结构和编译程序的组 织形式等。 (二)本章重点 编译(程序) ,解释(程序) ,编译程序的逻辑结构。 (三)本章难点 编译程序的生成。 (四)本章考点 全部基本概念。 编译程序的逻辑结构。 (五)学习指导引论部分主要是解释什么是编译程序以及编译的总体过程。因此学习时要对以下几个 点进行重点学习:翻译、编译、目标语言和源语言这几个概念的理解;编译的总体过程: 词法分
2、析,语法分析、语义分析与中间代码的生成、代码优化、目标代码的生成,以及伴 随着整个过程的表格管理与出错处理。第三章文法和语言课外训练第三章文法和语言课外训练(一)内容 本章是编译原理课程的理论基础,主要介绍与课程相关的形式语言的基本概念,包括 符号串的基本概念和术语、文法和语言的形式定义、推导与归约、句子和句型、语法分析 树和二义性文法等定义、文法和语言的 Chomsky 分类。 (二)本章重点 上下文无关文法,推导,句子和句型,文法生成的语言,语法分析树和二义性文法。 (三)本章难点 上下文无关文法,语法分析树,文法的分类。 (四)本章考点 上下文无关文法的定义。 符号串的推导。 语法分析树
3、的构造。 (五)学习指导要构造编译程序,就要把源语言用某种方式进行定义和描述。学习高级语言的语法描 述是学习编译原理的基础。上下文无关文法及语法树是本章学习的重点。语法与语义的概 念;程序的在逻辑上的层次结构;文法的定义,文法是一个四元组:终结符号集,非终结 符号集,开始符号、产生式集;与文法相关的概念,字符,正则闭包,积(连接),或, 空集,产生式,推导,直接推导,句子,句型,语言,最左推导,最右推导(规范推导); 学会用文法来描述语言及通过文法能分析该文法所描述的语言;语法树及二义性的概念、 能通过画语法树来分析一个文法描述的语言是否具有二义性;上下文无关文法的定义和正 规文法的定义,能判
4、断一个语言的文法是哪一类文法。 附训练试题:1:试构造生成语言 L=anbnci|n1, i 0的文法解:2:已知语言 L=anbbn| n 1, 写出产生 L 的文法。3:已知文法 G=(A,B,C,a,b,c,A,P) 其中产生式 P 由以下组成:A abc A aBbcBbbB Bc CbccbC Cb aC aaBaC aa 问:此文法表式的语言是什么?4请给出描述语言=a2m+1 b m+1 | m=0a2m b m+2| m=0的文法5 已知文法 GS为:SdABAaA|aBBb | GS产生的语言是什么?GS能否改写为等价的正则文法?6:试写一文法,使其描述的语言 L(G) 是能
5、被 5 整除的整数集合。7: 已知语言 L=x | xa,b,c*,且 x 重复排列是对称的(aabcbaa,aabbaa,等) 写出 该语言的文法。第四章第四章 词法分析课外训练词法分析课外训练(一)内容 本章介绍编译程序的第一个阶段词法分析的设计原理和设计方法,包括源程序输入与 词法分析程序输出、正则文法及其状态转换图、确定的有限自动机(DFA) 、 不确定的有限 自动机(NFA) 、正则表达式与正规集。 (二)本章重点 词法分析器的逻辑结构与功能,状态转换图,正规表达式与正规集、DFA、NFA 及其等 价转换,NFA 的确定化,DFA 的最小化。 (三)本章难点 正则式与自动机的应用,N
6、FA 的确定化,DFA 的最小化。 (四)本章考点 正规式到 NFA 的转换。 NFA 的确定化。 DFA 的最小化。 (五)学习指导掌握正规文法、状态转换图、DFA、NFA、正规表达式和正规集的基本概念和词法分析 器的设计与程序编写。词法分析的任务是对源语言所编写的代码进行从左到右的扫描,产 生一个个的单词符号(token),由这些单词符号形成的中间程序是后续语法分析输入。在 理论上词法分析器的构造是根据一种语言的正规文法描述形成相应的状态转换图(DFA), 若输入字符串能够被该 DFA 接受,则认为当前输入是语言中的一个单词符号。因此,DFA 的构造是本章学习的重点。 附训练试题: 1 写
7、出能被 5 整除的十进制整数的文法及正规表达式。 2:已知有限自动机如图(1)以上状态转换图表示的语言有什么特征? (2)写出其正规式与正规文法. (3)构造识别该语言的确定有限自动机 DFA.3 请构造与正规式 R=(a*b)*ba(a|b)* 等价的状态最少的 DFA(确定有限自动机)4 设字符集= a, b ,请写出不以 a 开头的但以 aa 结尾的字符串集合的正规表达式, 并构造与之等价的状态最少的 DFA。第五章自顶而下语法分析方法课外训练第五章自顶而下语法分析方法课外训练(一)内容 本章介绍编译程序的第二个阶段语法分析的第一种设计方法和实现原理即自上而下分 析的原理及无回朔的递归下
8、降分析、 LL(1)分析法和相应程序构造。 (二)本章重点 自上而下分析的思想,LL(1)文法,LL(1)预测分析,递归下降分析程序的构造。 (三)本章难点 消除左递归,预测分析表的构造,求 First 集和 Follow 集,预测分析中的出错处理。 (四)本章考点 LL(1)文法的判定。 递归下降分析程序的构造。 预测分析程序的构造与分析方法。 (五)学习指导理解自上而下分析面临的问题,理解递归下降分析、LL(1)文法,掌握无回朔的递归下 降分析方法的设计和程序实现、LL(1)分析表的构造与分析方法。语法分析是在词法分析的 基础上判定程序的语法结构是否符合语法规则的过程。词法分析器的构造技术
9、是编译器的 主要技术。词法分析分为自上而下的分析(LL(K)和自下而上的分析(算符优先、 LR(K)。本章先学习在逻辑概念上易于接受的自上而下的分析,即从文法开始符号出发, 自上而下地为输入串建立一棵语法树,或者说为输入串寻找一个最左推导。LL(1)分析法是本章的学习重点。 附训练试题: 1 试构造与下列文法 GS等价的无左递归文法。GS: SSa|Nb|c (1)N Sd|Ne|f 2:文法 G 的规则集为;P begin d : X endX d : X | sYY: sY | e 做出该文法 LL(1)分析表。 3 设有以下文法:GS: SeEfGh | g EFSG | hFSEc |
10、 cG | GSh | (1) 求出该文法每一个非终结符的 FOLLOW 集。 (2) 它是 LL(1)文法吗?为什么?4:给出语言 L=1na0n1ma0m|n0, m=0 的 LL(1)文法 GS并说明其理由。 5 设有文法:GS: SaBc | bABAaAb | bBb | 构造其 LL(1)分析表,并分析符号串 baabbb 是否是该文发的句子。6 将 GV改造为 LL(1)文法GV : VN | NEEV | V+ENi 7 有文法 GS:S BAABS | dBaA | bS | c(1)证明文法为 LL(1)文法。(2)构造 LL(1)分析表。(3)写出句子 adccd 的分析
11、过程 8 考虑下面文法 G1:Sa| (T) TT, S | S (1) 消去 G1 的左递归。然后对每一个非终结符,写出不带回溯的递归子程序。 (2) 经改写后的文法是否是 LL(1)文法?给出它的预测分析表。 9 下面文法中那些是 LL(1)文法,说明理由。 (1) 1、 SAbc2、 Aa|3、 Bb|(2) SAbAa | B|Bb | (3)S ABBAAa | B b | (4) SaSe |BBbBe | CCc Ce | d第六章第六章 自底而上优先分析法课外训练自底而上优先分析法课外训练(一)内容 本章介绍编译程序的第二个阶段语法分析的第二种设计方法和实现原理即自下而上分 析
12、的原理,包括一些基本概念、简单优先分析法、算符优先分析法。 (二)本章重点 自下而上分析的思想,算符优先文法及其分析。 (三)本章难点 句柄的定义,优先关系的定义,求 FIRSTVT 集和 LASTVT 集,优先分析表的构造 (四)本章考点 基本概念的定义(短语、直接短语、句柄、最左素短语、规范归约等) 。 算符优先分析法。 (五)学习指导理解最左素短语的基本概念;掌握算符优先分析方法。自下而上分析法就是从输入串 开始,逐步进行“归约”,直至归约到文法的开始符号,从输入串的语法树上直观地看就 是沿着语法树的底部向上分析归约,最终能到达根结点的就认为当前的输入串能被接受。 算符优先分析(OPG)
13、是自下而上分析中针对运算表达式较为常用的易于理解的分析算法。 附训练试题: 1 已知文法 GS为算符优先文法,其规则为:SSaF|FF FbP|PP c|d 求优先关系表 2 对下列文法 G:S #S# P S|iS D(R) D i R R; P|P 求:出每个非终结符的 FIRSTVT 集和 LASTVT 集,并构造算符优先关系矩阵。 3 考虑下面文法 G2:S a| | (T)T T, S | S (1)给出(a,(a, a)) 和(a,a), ,(a),a)的最左和最右推导。 (2)给出串(a, (a, a))的算符优先分析过程。第七章第七章 LRLR 分析法课外训练分析法课外训练(一
14、)内容 本章介绍编译程序的第二个阶段语法分析的第二种设计方法和实现原理即自下而上分 析的原理,包括一些基本概念、LR 分析法。 (二)本章重点 自下而上分析的思想,LR 分析器逻辑结构和功能,LR(0)文法及其分析、SLR(1)文法及 其分析、LR(1)、LALR(1) 文法及其分析。 (三)本章难点 句柄的定义,LR 项目及活前缀识别自动机,四种 LR 文法的差别。 (四)本章考点 基本概念的定义(短语、直接短语、句柄、规范归约等) 。 LR(0) 、SLR(1)分析。 (五)学习指导理解有效项目的基本概念;掌握 LR(0)、SLR(1)文法的判断及 LR(0)、SLR(1)分析 表的构造与
15、分析方法。自下而上分析法就是从输入串开始,逐步进行“归约”,直至归约 到文法的开始符号,从输入串的语法树上直观地看就是沿着语法树的底部向上分析归约, 最终能到达根结点的就认为当前的输入串能被接受。大部分现代的编译器都采用 LR 分析作 为语法分析的方式。因此本章的学习重点是学习如何构造 LR 分析表。OPG 分析可以作为自 下而上分析算法的切入点要求重点掌握。 附训练试题: 1、对于文法 GSS ( L) | aS |aL L, S | S (1)画出句型( S ,(a)的语法树 (2)写出上述句型的所有短语, 直接短语, 句柄. 2、 设有文法 GS:SL=RS RL *RL iR L 为构造拓广文法,增加新的非终结符 S ,得到规则 S S,则:closure ( S .S, # )=_ 3、设文法 G(S)SA A aA | b 构造识别文法 G(S)的所有活前缀的 DFA. 4、求文法 (1) SA (2) A aA (3)A b LR(0)分析表: 5、设文法 G,试构造 G 的 LR(0)分析表G: 1) SCC 2) C cC 3) C