当前位置：文档库 › 编译原理期末复习

编译原理期末复习

编译原理期末复习鉴于编译原理马上就要期末考试，我将手中集中的一些资料上的题目进行了整理归类，每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最后由于时间很紧，整理的有些仓促，整理中难免有遗漏或错误，请大家见谅。

注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字母为非终结符，希腊字母为终结符与非终结符的任意组合。

1、简答题（或者名词解释）

下面涉及到的概念中，加下划线的都是在以往一些试卷中出现的原题，务必掌握。

注：这类题目老师说答案不会超过一百个字，否则写的再多也不给分，有些点到即可，不要重复啰嗦。

（1）简述编译程序的概念及其构成

答：1）编译程序：它特指把某种高级程序设计语言翻译成等价的低级程序设计语言的翻译程序。

2)构成：

（2）简述词法分析阶段的主要任务（也有可能问语法分析阶段主要任务）

答：词法分析的任务是输入源程序，对源程序进行扫描，识别其中的单词符号，把字符串形式的源程序转换成单词符号形式的源程序。

语法分析的主要任务是对输入的单词符号进行语法分析（根据语法规则进行推导或者归约），识别各类语法单位，判断输入是不是语法上正确的程序

(3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合）答：1）构造词法分析器：用于输入源程序进行词法分析，输出单词符号；

2）构造语法分析器：对输入的单词符号进行语法分析，识别各类语法单位，判断输入是不是语法上正确的程序

3）构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行语义分析并把它们翻译成中间代码。

4）构造优化器：对中间代码进行优化。

5) 构造目标代码生成器：把中间的代码翻译成目标程序。

6) 构造表格管理程序：登记源程序的各类信息和编译各阶段的进展情况。

7)构造错误处理程序：对出错进行处理。

(4) 说明编译和解释的区别：

1)编译要程序产生目标程序，解释程序是边解释边执行，不产生目标程序；

2)编译程序运行效率高而解释程序便于人机对话。

（5）文法：描述语言语法结构的形式规则，一般用一个四元式表示： G=(V

，

N ，S，P)，其中V

：终结符集合(非空) V

：非终结符集合(非空)，且V

= S：

文法的开始符号，SV

P：产生式集合(有限)。

（6）二义性文法：一个文法中存某个句子，它有两个不同的最左（或者最右推导），则称该文法是二义性的。

例子如文法G ：S →if expr then S |other

S →if expr then S else S 句子if e1 then if e2 then s1

else s2是二义性的。

（7）文法的形式（注：文法的形式一定要牢记，特别是2型和3型文法一定要牢记，不仅在概念题中有用，在下面的根据语言写文法题中也有重要作用，如果所写的文法形式不对，一切都是无用功……）

1）0型文法(短语文法，图灵机)：产生式形式为：，其中： (V T V N )*

且至少含有一个非终结符； (V T V N )*

2）1型(上下文有关文法，线性界限自动机)：产生式形式为: 其中：|| ||，仅 S 例外但是S 不得出现在任何产生式右部。

3）2型文法（上下文无关文法，非确定下推自动机)：产生式形式为：P ， PV N ， (V T V N )* 。

4）3型文法(正规文法，有限自动机)：右线性文法：产生式形如：A B 或 A 其中： V T *；A ，BV N 左线性文法：产生式形如：A B 或 A 其中： V T *；A ，BV N 例题：设G=(V T ，V N ，S ，P)是一个上下文无关文法，产生集合P 中的任一个产生式应具有什么样的形式若G 是1型文法呢若G 是正则文法呢上下文无关文法，产生式形式为：P ， PV N ， (V T V N )* 。 1型文法：产生式形式为: 其中：|| ||，仅 S 例外。

正则文法：右线性文法：产生式形如：A B 或 A 其中： V T *；A ，BV N

左线性文法：产生式形如：A B 或 A 其中： V T *；A ，BV N (8)什么是PDA(下推自动机)

答：PDA 是下推自动机，PDA M 用一个七元组表示(K,Σ,f,H,h0,S,Z)

K: 有穷状态集：输入字母表(有穷) H:下推栈符号的有穷字母表

h0 :H中的初始符号 f: K （Σ{}) H –> K H* S：属于K是初始状态。Z:包含于K，是终结状态集合。

(9) 什么是DFA（有穷状态自动机）

, F),其中：

自动机M是一个五元式M=(S, , f, S

1）S: 有穷状态集， 2）：输入字母表(有穷)，

3） f: 状态转换函数，为SS的单值部分映射，f(s，a)=s’表示：当现行状态为s，输入字符为a时，将状态转换到下一状态s’。我们把s’称为s

的一个后继状态。

S是唯一的一个初态； 5） FS ：终态集(可空)。