《编译原理基础》由会员分享，可在线阅读，更多相关《编译原理基础（9页珍藏版）》请在金锄头文库上搜索。
1、第一章 引论主要内容：编译原理的基本概念、定义、编译原理的应用发展和现状。重 点：编译程序工作的基本构成及各阶段的基本任务， 具体要求：理解什么是编译程序，了解各编译程序的基本构成及各阶段的基本任务， 编译程序总框，了解编译程序生成过程和构造工具。一、名词解释1、编译程序：能够把用各种高级语言书写的源程序翻译成某种等价的目标程序的翻译程序。2、遍：指编译程序对源程序或中间代码程序从头到尾扫描一次。3、静态分配：在编译时就能够安排好目标程序运行时的全部数据空间。二、问答题1、简述编译程序的结构？答：编译程序包括词法分析、语法分析、中间代码生成、优化，目标代码产生五个阶段， 上述各阶段中还要进行表
2、格处理和出错处理的工作。2、编译程序可分成哪几个阶段 ？它们之间的关系如何？ 答：编译程序可分为五个阶段：词法分析、语法分析、中间代码生成、优化、目标代码 生成。上述五个阶段之间每个阶段输出为作下一阶段的输入，第一阶段的输入是源程序，最后 阶段的输出是目标代码程序。注意：编译过程中，阶段的划分和遍的划分不一定相同第二章 高级程序语言概述主要内容：程序语言定义、初等数据类型、数据结构、表达式、语句、高级语言的一 般特征及程序语言的语法描述。重 点：程序语言定义 具体要求：理解程序语言的词法、语法和语义等概念；熟悉高级程序语言的一般结构 和主要共同特征。一、填空题1、程序语言是由（语法）和（语义）
3、两方面定义的。2、一个名字的属性包括（类型）和（作用域）3、目标代码一般有三种形式：能够立即执行的机器语言代码，（待装配的机器语言模块）和 （汇编语言代码）4、语义：定义一个程序的意义的（一组规则）5、2 型文法又称为（上下文无关文法），3 型文法又为（正规文法）二、是非题1、虽然名字都是用标识符表示的，但名字和标识符有着本质的区别（对）2、各种名字都是用标识符表示的，所以名字和标识没有本质的区别（错）3、数组元素的地址计算与数组的存储方式没有关系（错）4、语法是指程序的含义（错）5、因名字都是用标识符表示的，故名字与标识符没有区别（错）第三章 词法分析主要内容：词法分析器的任务、词法分析器的
4、设计、正规表达式与有限自动机、词法 分析器的自动生成。重 点：词法分析器的任务，词法分析器设计，正规表达式与有限自动机，词法分 析器自动生成，状态转换图具体要求：理解词法分析器的功能及输出形式；熟练掌握词法词法分析器的设计的原 理，掌握运用状态转换图进行词法分析器设计。一、是非题1、一个状态转换图可以用于识别一定的字符串。（对）二、填空题1、词法分析器的任务是从（源程序）中识别出一个个（单词符号）。2、词法分析器的任务是（输入）源程序、（输出）单词符号。3、执行词法分析的程序称为（词法分析器）或（扫描器）。4、词法分析器所输出的单词符号常常表示成如下二元关系：（单词种别，单词自身值）。5、一张
5、转换图只包含有限个状态，其中有一个被认为是（初态），而且实际上至少要有一个 （终态）。6、程序语言的单词符号包括：（标识符）、（运算符）、（常数）、（基本字）、界符等。7、一张转换图只包含有限个状态，其中有一个被认为是（初）态，而且是实际上至少要有 一个（终）态。三. 名词解释1、词法分析器：是一种程序，它能将字符串形式的源程序改造成单词符号串形式的中间程 序。2、超前搜索：在词法分析过程中，有时为了确定词性，需要超前扫描若干个字符，这个动 作为超前搜索。四、简答题1、何谓状态转换图？作用是什么？ 答：状态转换图是一张有限方向图，其中结点代表状态，状态之间用箭弧连接，箭弧上 的标记代表在射出结
6、点状态下可能出现的输入字符或字符类，状态中有一个初态，至少有一 个终态。第四章 语法分析-自上而下分析主要内容：上下文无关文法，语法分析器的功能、自上而下分析所面临的问题、LL （1） 分析法、递归下降分析的构造过程、预测分析程序等内容。重点：上下文无关文法，递归下降子程序预测分析表构造，LL （1）方法。具体要求：正确理解上下文无关方法基本概念，包括：文法的定义、缩写、句型、句 子、语言、语法树、二义性等；正确理解自上而下分析的基本思想；熟练掌握递归下降分 析基本方法；消除左递归、消除回溯，构造递归下降子程序；掌握预测分析程序的基本原 理的预测分析构造；理解LL（1）方法的定义，LL（1）文
7、法的条件及其判别，计算first 集和 follow 集。一、是非题：1、使用自上而下分析法，首先必须消去文法的左递归。（对）2、文法是描述语言语义的形式规则。（错）3、一个文法是二义的，则这个文法的每个句子都对应两棵不同的语法树。（错）4、一个上下文无关文法的产生式的左部符号可以是非终结符也可以是终结符。（错）5、递归下降分析法是一种自下而上的分析法。（错）6、一个上下文无关文法的开始符号是一个特殊的非终结符。（对）7、一个句型的推导可表示在一棵语法树。（对）8、一个文法G,若它的分析表M不含多重定义入口，则G是LL（1）文法。（对）9、文法的二义性与语言的二义性是两个相同的概念。（错）10
8、、对于任何一个含有左递归的文法必存在一个等价的不含左递归的文法。（对）11、一个文法的句子也一定是该文法的句型。（对）12、如果一个文法存在某个句子对应两棵不同的语法树，则该文法是二义的。（对）13、一个上下文无关文法的开始符号可以是终结符和非终结符。（错）14、已经证明文法的二义性是可判定的。（错）二、填空题*1、 假定G是一个文法，S是它的开始符号，如果S n a，则称a是一个（句型），仅包含 终结符号的句型是一个（句子）。2、常用的语法分析方法有（自下而上分析法）或（算符优先分析法），（自上而下分析法） 或（递归下降法）等。3、一个上下文无关文法包括四个组成部分是（一组终结符号，一组非终
9、结符号，一个开始 符号，一组产生式）。4、一个文法G,若它的分析表M不含多重定义入口则（G是LL（1）文法）。5、每个文法 G 的程序语言都包含（语法）和（语义）两方面定义的。6、一个文法，如果存在非终结符P，PPa，则称这个文法含有（左递归）。7、一般程序语言的语法单位有：（表达式）、（语句）、（过程）、（程序）等等。8、所谓最右推导是指：（任何一步a =B都是对a中最右非终结符号进行替换的）。9、语法分析的任务是（分析一个文法的句子结构）。10、假定S是文法G的开始符号，对于G的任何非终结符A,定义集合*FOLLOW （A） = （a| S n . Aa ,8丘片）。11、预测分析程序是使
10、用一张（分析表）和一个（符号栈）进行联合控制的。12、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义的）。13、文法 G 所产生的句子的全体是（语言），将它记为 L（G）。14、文法是描述语言的（语法结构）的形式规则。15、产生式的用于定义（语法范畴）的一种书写规则。16、所谓最左推导是指（任何一步a =B都是对a中的最左非终结符进行替换的）。17、语法分析的方法大致可分为两类，一类是（自上而下）分析法，另一类是（自下而上的） 分析法。18、如果a =a二二a ,则我们称这个序列是（从a到a的一个推导）。1 2 n 1 n19、语法规则是（语法单位）形成规则，词法规则的（单
11、词符号）形成规则。20、最右推导亦为（规范推导），由此推得的句型称为（规范）句型。三、名词解释：1、文法：描述语言的的语法结构的形式规则。2、句型：设G是一个文法，S是它的开始符号，若S = a，贝临称为一个句型。3、二义性文法：若文法存在某个句子对应两棵不同的语法树（或两种不同的推导）。4、最左推导：推导的任何一步a =B都是对a中最左非终结符进行替换。5、语法分析：按文法的产生式识别输入的符号串是否为一个句子的分析过程。6、规范推导：最右推导称为规范推导。7、语法：是一组规则，用它可以形成和产生一个合式的程式。8、产生式：是定义语法范畴一种书写规则，其形式是Aa，其中：A是非终结符，a是终
12、 结符或非终结符组成的串。9、规范句型：由规范推导所得的句型。10、语法树：用一张图表示一个句型的推导的表示方法。第五章 语法分析自下而上分析主要内容：上下文无关文法，自下而上分析的基本问题、算符优先分析、LR分析法。 重 点：上下文无关文法，算符优先分析基本方法、算符优先表和归约。具体要求：正确理解上下文无关方法基本概念，正确理解自下而上分析的基本思想； 以及归约、短语、句柄、分析树等概念；掌握自下而上语法分析（算符优先分析法），算符 优先分析基本方法、算符优先表和算符优先函数构造技术，LR分析器，LR（O）项目集族和 LR（O）分析表的构造，SLR分析表的构造，规范LR分析表的构造，出错处
13、理概述，词法分析 阶段的错误诊察，语法分析（自下而上）阶段的错误诊察。一、判断题1、最左归约是最右推导的逆过程。（TURE）2、一个优先表一定存在相应的优先函数。（FALSE）3、算符优先分析法是一种自上而下的分析法。（FALSE）4、优先关系表所对应的优先函数，如果存在，则一定唯一。（FALSE）5、一个句型的直接短语是唯一的。（FALSE）二、填空题1、如果一个文法的任何产生式的右部都不含有两个相继（并列）的非终结符，则这种文法 称为（算符）文法。2、一个句型的最左直接短语称为该句型的（句柄）。三、名词解释1、句柄：一个句型的最左直接短语称为句型的句柄。2、对于文法G和每个非终结符P,定义
14、集合FIRSTVT （P） = （a|P=a 或 P=Qa ，aV 而 QUV）TN3、短语：令G是一个文法，S是文法的开始符号，假定a p 6是文法G的一个句型。如果*有：SnaA8，且A =0 ,则称p是句型a p 6相对非终结符A的短语。4、素短语：素短语是指这样一个短语，它至少含有一个终结符，并且除它自身之外不再含 任何更小的素短语。5、算符优先文法：如果一个算符文法G中任何终结符对，（a,b）至多只满足下述三关系之 一：ab ,a b ,a号则称G是一个算符优先文法。6、语法树：用一张图表示一个句型的推导之表示方法。第七章 语法制导翻译和中间代码生成主要内容：语法制导翻译概述，各种常
15、见的中间语言形式，中间语言，说明语句，赋 值语句的翻译，布尔表达式的翻译，控制语句到四元式的翻译，自上而下分析制导翻译概 述。重 点：语法制导翻译基本思想，三种中间语言，四元式，逆波兰表示，算术表达 式，算术表达式的翻译，布尔表达式的翻译，控制语句的翻译。具体要求：正确理解语法制导翻译基本原理；熟悉常见的几种中间语言。四元式、三 元式，逆波兰表示；掌握各种语句到四元式的翻译方法，包括：简单算术表达式，布尔表 达式，控制语句，数组引用，过程调用等。一、是非题1、 数组元素的地址计算和数组的存贮方式无关。（错）2、 逆波兰式表示的表达式亦称后缀式。（对）二、填空1、表达式a+b* （d-c）的逆波兰表示为（abdc-*+）。2、语法分析是根据语言的（语法规则）进行的，中间代码产生是根据语言的（语义规则） 进行的。3、表达式 a-（b+c） /d 的逆波兰表示为 （abc+d/-）。4、逆波兰式 abc*d+/ 所表示的表达式为 （a/（b*c+d）。5、逆波兰式 a
