《编译原理》总复习-07级

资源描述

《《编译原理》总复习-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)分析表的构造与分析方法。语法分析是在词法分析的基础上判定程序的语法结构是否符合语法规则的过程。词法分析器的构造技术

12、的原理，包括一些基本概念、简单优先分析法、算符优先分析法。（二）本章重点自下而上分析的思想，算符优先文法及其分析。（三）本章难点句柄的定义，优先关系的定义，求 FIRSTVT 集和 LASTVT 集，优先分析表的构造（四）本章考点基本概念的定义（短语、直接短语、句柄、最左素短语、规范归约等）。算符优先分析法。（五）学习指导理解最左素短语的基本概念；掌握算符优先分析方法。自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号，从输入串的语法树上直观地看就是沿着语法树的底部向上分析归约，最终能到达根结点的就认为当前的输入串能被接受。算符优先分析（OPG）

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

展开阅读全文

《编译原理》总复习-07级

最新文档