编译原理基础_0

1、编译原理基础 第一章 引论 主要内容：编译原理的基本概念、定义、编译原理的应用发展和现状。 重 点：编译程序工作的基本构成及各阶段的基本任务， 具体要求：理解什么是编译程序，了解各编译程序的基本构成及各阶段的基本任务，编译程序总框，了解编译程序生成过程和构造工具。 一、名词解释 1、编译程序：能够把用各种高级语言书写的源程序翻译成某种等价的目标程序的翻译程序。 2、遍：指编译程序对源程序或中间代码程序从头到尾扫描一次。 3、静态分配：在编译时就能够安排好目标程序运行时的全部数据空间。 二、问答题 1、简述编译程序的结构？ 答：编译程序包括词法分析、语法分析、中间代码生成、优化，目标代码产生五个

2、阶段，上述各阶段中还要进行表格处理和出错处理的工作。 2、编译程序可分成哪几个阶段 ？它们之间的关系如何？ 答：编译程序可分为五个阶段：词法分析、语法分析、中间代码生成、优化、目标代码生成。 上述五个阶段之间每个阶段输出为作下一阶段的输入，第一阶段的输入是源程序，最后阶段的输出是目标代码程序。 注意：编译过程中，阶段的划分和遍的划分不一定相同 第二章 高级程序语言概述 主要内容：程序语言定义、初等数据类型、数据结构、表达式、语句、高级语言的一般特征及程序语言的语法描述。 重 点：程序语言定义 具体要求：理解程序语言的词法、语法和语义等概念；熟悉高级程序语言的一般结构和主要共同特征。 一、填空题

3、 1、程序语言是由l 3、数组元素的地址计算与数组的存储方式没有关系（错） 4、语法是指程序的含义（错） 5、因名字都是用标识符表示的，故名字与标识符没有区别（错） 第三章 词法分析 主要内容：词法分析器的任务、词法分析器的设计、正规表达式与有限自动机、词法分析器的自动生成。 重 点：词法分析器的任务，词法分析器设计，正规表达式与有限自动机，词法分析器自动生成，状态转换图 具体要求：理解词法分析器的功能及输出形式；熟练掌握词法词法分析器的设计的原理，掌握运用状态转换图进行词法分析器设计。 一、是非题 1、一个状态转换图可以用于识别一定的字符串。（对） 二、填空题 1、词法分析器的任务是从（源程

4、序）中识别出一个个（单词符号）。 2、词法分析器的任务是（输入）源程序、（输出）单词符号。 3、执行词法分析的程序称为（词法分析器）或（扫描器）。 4、词法分析器所输出的单词符号常常表示成如下二元关系：（单词种别，单词自身值）。 5、一张转换图只包含有限个状态，其中有一个被认为是（初态），而且实际上至少要有一个（终态）。 6、程序语言的单词符号包括：（标识符）、（运算符）、（常数）、（基本字）、界符等。 7、一张转换图只包含有限个状态，其中有一个被认为是（初）态，而且是实际上至少要有一个（终）态。 三.名词解释 1、词法分析器：是一种程序，它能将字符串形式的源程序改造成单词符号串形式的中间程序

5、。 2、超前搜索：在词法分析过程中，有时为了确定词性，需要超前扫描若干个字符，这个动作为超前搜索。 四、简答题 1、何谓状态转换图？作用是什么？ 答：状态转换图是一张有限方向图，其中结点代表状态，状态之间用箭弧连接，箭弧上的标记代表在射出结点状态下可能出现的输入字符或字符类，状态中有一个初态，至少有一个终态。 第四章 语法分析-自上而下分析 主要内容：上下文无关文法，语法分析器的功能、自上而下分析所面临的问题、ll（1）分析法、递归下降分析的构造过程、预测分析程序等内容。 重 点：上下文无关文法，递归下降子程序预测分析表构造，ll（1）方法。 具体要求：正确理解上下文无关方法基本概念，包括：文

6、法的定义、缩写、句型、句子、语言、语法树、二义性等；正确理解自上而下分析的基本思想；熟练掌握递归下降分析基本方法；消除左递归、消除回溯，构造递归下降子程序；掌握预测分析程序的基本原理的预测分析构造；理解ll（1）方法的定义，ll（1）文法的条件及其判别，计算first集和follow集。 一、是非题： 1、使用自上而下分析法，首先必须消去文法的左递归。（对） 2、文法是描述语言语义的形式规则。（错） 3、一个文法是二义的，则这个文法的每个句子都对应两棵不同的语法树。（错） 4、一个上下文无关文法的产生式的左部符号可以是非终结符也可以是终结符。（错） 5、递归下降分析法是一种自下而上的分析法。（

7、错） 6、一个上下文无关文法的开始符号是一个特殊的非终结符。（对） 7、一个句型的推导可表示在一棵语法树。（对） 8、一个文法g，若它的分析表m不含多重定义入口，则g是ll（1）文法。（对） 9、文法的二义性与语言的二义性是两个相同的概念。（错） 10、对于任何一个含有左递归的文法必存在一个等价的不含左递归的文法。（对） 11、一个文法的句子也一定是该文法的句型。（对） 12、如果一个文法存在某个句子对应两棵不同的语法树，则该文法是二义的。（对） 13、一个上下文无关文法的开始符号可以是终结符和非终结符。（错） 14、已经证明文法的二义性是可判定的。（错） 二、填空题 *1、假定g是一个文法，

8、s是它的开始符号，如果s?， 则称是一个（句型），仅包含终结符号的句型是一个（句子）。 2、常用的语法分析方法有（自下而上分析法）或（算符优先分析法），（自上而下分析法）或（递归下降法）等。 3、一个上下文无关文法包括四个组成部分是（一组终结符号，一组非终结符号，一个开始符号，一组产生式）。 4、一个文法g，若它的分析表m不含多重定义入口则（g是ll（1）文法）。 5、每个文法g的程序语言都包含（语法）和（语义）两方面定义的。 6、一个文法，如果存在非终结符p，ppa，则称这个文法含有（左递归）。 7、一般程序语言的语法单位有：（表达式）、（语句）、（过程）、（程序）等等。 8、所谓最右推导是

9、指：（任何一步=都是对中最右非终结符号进行替换的）。 9、语法分析的任务是（分析一个文法的句子结构）。 10、假定s是文法g的开始符号，对于g的任何非终结符a，定义集合 *follow（a）=（a|s?.aa.,aut）。 11、预测分析程序是使用一张（分析表）和一个（符号栈）进行联合控制的。 12、如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是（二义的）。 13、文法g所产生的句子的全体是（语言），将它记为l（g）。 14、文法是描述语言的（语法结构）的形式规则。 15、产生式的用于定义（语法范畴）的一种书写规则。 16、所谓最左推导是指（任何一步=都是对中的最左非终结符进行替

10、换的）。 17、语法分析的方法大致可分为两类，一类是（自上而下）分析法，另一类是（自下而上的）分析法。 18、如果a1=a2=an ,则我们称这个序列是（从a1到an的一个推导）。 19、语法规则是（语法单位）形成规则，词法规则的（单词符号）形成规则。 20、最右推导亦为（规范推导），由此推得的句型称为（规范）句型。 三、名词解释： 1、文法：描述语言的的语法结构的形式规则。 *2、句型：设g是一个文法，s是它的开始符号，若s?，则称为一个句型。 3、二义性文法：若文法存在某个句子对应两棵不同的语法树（或两种不同的推导）。 4、最左推导：推导的任何一步=都是对中最左非终结符进行替换。 5、语法

11、分析：按文法的产生式识别输入的符号串是否为一个句子的分析过程。 6、规范推导：最右推导称为规范推导。 7、语法：是一组规则，用它可以形成和产生一个合式的程式。 8、产生式：是定义语法范畴一种书写规则，其形式是a，其中：a是非终结符，是终结符或非终结符组成的串。 9、规范句型：由规范推导所得的句型。 10、语法树：用一张图表示一个句型的推导的表示方法。 第五章 语法分析自下而上分析 主要内容：上下文无关文法，自下而上分析的基本问题、算符优先分析、lr分析法。 重 点：上下文无关文法，算符优先分析基本方法、算符优先表和归约。 具体要求：正确理解上下文无关方法基本概念，正确理解自下而上分析的基本思想

12、；以及归约、短语、句柄、分析树等概念；掌握自下而上语法分析（算符优先分析法），算符优先分析基本方法、算符优先表和算符优先函数构造技术，lr分析器，lr(0)项目集族和lr(0)分析表的构造，slr分析表的构造，规范lr分析表的构造，出错处理概述，词法分析阶段的错误诊察，语法分析（自下而上）阶段的错误诊察。 一、判断题 1、最左归约是最右推导的逆过程。（ture） 2、一个优先表一定存在相应的优先函数。（false） 3、算符优先分析法是一种自上而下的分析法。（false） 4、优先关系表所对应的优先函数，如果存在，则一定唯一。（false） 5、一个句型的直接短语是唯一的。（false） 二、

13、填空题 1、如果一个文法的任何产生式的右部都不含有两个相继（并列）的非终结符，则这种文法称为（算符）文法。 2、一个句型的最左直接短语称为该句型的（句柄）。 三、名词解释 1、句柄：一个句型的最左直接短语称为句型的句柄。 2、对于文法g和每个非终结符p，定义集合 firstvt（p）=（a|p=a或p=qa,avt 而 qvn） 3、短语：令g是一个文法，s是文法的开始符号，假定是文法g的一个句型。如果 *有：s?a?，且a?,则称是句型相对非终结符a的短语。 4、素短语：素短语是指这样一个短语，它至少含有一个终结符，并且除它自身之外不再含任何更小的素短语。 5、算符优先文法：如果一个算符文法

14、g中任何终结符对，（a,b）至多只满足下述三关系之一：ab ,ab则称g是一个算符优先文法。 6、语法树：用一张图表示一个句型的推导之表示方法。 ?第七章 语法制导翻译和中间代码生成 主要内容：语法制导翻译概述，各种常见的中间语言形式，中间语言，说明语句，赋值语句的翻译，布尔表达式的翻译，控制语句到四元式的翻译，自上而下分析制导翻译概述。 重 点：语法制导翻译基本思想，三种中间语言，四元式，逆波兰表示，算术表达式，算术表达式的翻译，布尔表达式的翻译，控制语句的翻译。 具体要求：正确理解语法制导翻译基本原理；熟悉常见的几种中间语言。四元式、三元式，逆波兰表示；掌握各种语句到四元式的翻译方法，包括：简单算术表达式，布尔表达式，控制语句，数组引用，过程调用等。 一、是非题 1、数组元素的地址计算和数组的存贮方式无关。 （错） 2、逆波兰式表示的表达式亦称后缀式。