兰州理工大学-2021年秋季-编绎原理－期末复习.docx

第一章

在计算机上执行一个高级程序一般要分为两步：（简答题）

①用一个编译程序把高级语言翻译成机器语言程序

②运行所得的机器语言求得计算结果

编译程序和解释程序的区别、联系：（简答题）

①翻译程序能够把某一种语言程序转换成另一种语言程序，而后者与前者在逻辑上是等价的。如果源语言是“高级语言”，而目标语言是诸如汇编语言或机器语言之类的“低级语言”，这样一个翻译程序就称为编译程序。

②解释程序：它以该语言写的源程序作为输入，但不产生目标程序而是边解释边执行源程序本身。

③高级语言除了先编译后执行外，有时也可“解释”执行

④实际上，许多编译程序的构造与实现技术同样适用于解释程序

编译过程概述（简答？选择？）

第一阶段：词法分析——（词法分析器）对构成源程序的字符串进行扫描和分解，识别出一个个单词

第二阶段：语法分析——（语法分析器）根据语言语法规则，把单词符号串分解成各类语法单元

第三阶段：语义分析和中间代码生成―（语义分析和中间代码生成器）对各类语法单位，分析其含义并对其初步翻译（产生中间代码）

第四阶段：优化——（优化器）产生更高效代码

第五阶段：目标代码生成——（目标代码生成器）把中间代码变换成特定机器上的低级语言指令形式。

词法分析识别的单词：关键字、标识符、常数、算符和界符

编译前端与后端（简答）

①概念上、把编译程序划分为编译前端和编译后端。

②前端主要由与源语言有关但与目标机无关的那些部分组成。这些部分通常包括词法分析、语法分析、语义分析与中间代码生成，有的代码优化工作也可包括在前端

③后端包括编译程序中与目标机有关的那些部分（如与目标机有关的代码和目标代码的生成）通常、后端不依赖于源语言而仅依赖于中间语言。

如何学习构造编译程序（简答题）

要在某一台机器上为某种语言构造一个编译程序，必须掌握下述三方面内容

①源语言，对被编译的源语言，要深刻理解其结构（语法）和含义（语义）

②目标语言，假定目标语言是机器语言那么就必须搞清楚硬件的系统结构和操作系统的功能

③编译方法，把一种语言程序翻译为另种语言程序方法很多，但必准确掌握一二

第二章

文法基本概念：

文法是描述语言语法结构的形式规则（即语法规则）

①这些规则必须是准确的、易于理解的，有相当强的描述能力，足以描述各种不同的结构

②要有利于句子分析和翻译

③最好能通过这些规则自动产生有效的语法分析程序

上下文无关文法：

上下文无关文法所定义的语法范畴（或语法单位）是完全独立于这种范畴可能出现的环境。

对于现今的程序语言来说，上下文无关文法基本够用

一个上下文无关文法包括四个组成部分：一组终结符号、一组非终结符号、一个开始符号、以及一组产生式。

形式语言鸟瞰：

乔姆斯基把文法分成四种类型、即0型、1型、2型和3型。0型强于1型、1型强于2型，2型强于3型，这几类文法的差别在于对产生式施加不同的限制。

程序语言常用2、3型文法

2型文也称上下文无关文法，3型文法也称右线性文法（用来描述单词）

何谓“标识符”，何谓＂名字＂，两者区别是什么

在程序设计语言中，标识符是一个最基本的概念，其定义为：凡以字母开头的字母数字序列（有限个字符）都是标识符。当给某标识符以确切的含义时，这个标识符就叫做名字。

程序语言中各种名字都是用标识符来表示的，只是标识符是一个没意义的字符序列，而名字却有着确切的意义和属性

第三章

词法分析的任务？

从左到右逐个字符地对源程序进行扫描，产生一个个的单词符号，把作为字符串的源程序改造成为单词符号串的中间程序。因此词法分析是编译的基础。

确定有限自动机DFA与非确定有限自动机NFA区别：

DFA是单值映射NFA是多值映射

第四章

满足构造不带回溯的自上而下分析的文法条件：

①文法不含左递归

②对于文法中每一个非终结符A的各个产生式的各候选首符集两两不相交

③对文法中的每个非终结符A?若它存在某个候选首符集包含空集，则该非终结符的终结首符集与其终结随符集的交集为空

第五章

算符优先分析特点

①一种简单直观、广为使用的自下而上分析法

②有利于表达式分析

③宜于手工实现

④算符优先分析法不是一种规范归约法。

算符优先分析过程

①算符优先分析过程是自下而上的归约过程

②借助算符之间的某种优先关系寻

算符文法的概念

一个文法，如果它的任一产生式的右部都不含两个相继（并列）的非终结符，即含如下形式的产生式右部：…AB…存对换到外存上则我们称该文法为算符文法

.

于一个文法，如果能够构造一张分析表，使得它的每个入口都是唯一确定的，则我们把这个文法称为LR文法。

②并非所有上下文无关文法都是LR文法，但对于大多数程序语言来说、一般都可用LR文法描述。

③LR文法肯定是无二义的一个前缀。这种前缀不含句柄之后的任何符号。之所称为活前缀，是因为在右边增添一些终结符号后，就可以