编译原理期末复习.pdf

编译原理期末复习

鉴于编译原理马上就要期末考试,我将手中集中的一些资料上的题目进行了

整理归类,每种类型题目给出了所涉及到的基本知识,然后对每类题目中的第一道

例题进行了做法进行了讲解,剩下的例题请给大家作为练习,答案也都给出,希望

对大家复习有所帮助,最后由于时间很紧,整理的有些仓促,整理中难免有遗漏或

错误,请大家见谅;
注：下面出现的字母中,若无特别说明,小写英文字母为终结符,大写英文字母为非终结符,
希腊字母为终结符与非终结符的任意组合;
1、简答题或者名词解释
下面涉及到的概念中,加下划线的都是在以往一些试卷中出现的原题,务必掌

握;

注：这类题目老师说答案不会超过一百个字,否则写的再多也不给分,有些点到

即可,不要重复啰嗦;

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

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

计语言的翻译程序;

2构成：

2简述词法分析阶段的主要任务也有可能问语法分析阶段主要任务
答：词法分析的任务是输入源程序,对源程序进行扫描,识别其中的单词符号,

把字符串形式的源程序转换成单词符号形式的源程序;

语法分析的主要任务是对输入的单词符号进行语法分析根据语法规则进

行推导或者归约,识别各类语法单位,判断输入是不是语法上正确的程序

3简述编译程序的构造过程这个大家看看,是对1和2的综合

答：1构造词法分析器：用于输入源程序进行词法分析,输出单词符号；

2构造语法分析器：对输入的单词符号进行语法分析,识别各类语法单位,判断

输入是不是语法上正确的程序

3构造语义分析和中间代码产生器：按照语义规则对已归约出的语法单位进行

语义分析并把它们翻译成中间代码;

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

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

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

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

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

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

程序运行效率高而解释程序便于人机对话;

5文法：描述语言语法结构的形式规则,一般用一个四元式表示：G=V,V,S,P,
TN
其中V：终结符集合非空V：非终结符集合非空,且VV=S：文法的开始符
TNTN
号,SVP：产生式集合有限;
N
6二义性文法：一个文法中存某个句子,它有两个不同的最左或者最右推导,则称该

文法是二义性的;
例子如文法G：S→ifexprthenS|other

S→ifexprthenSelseS句子ife1thenife2thens1

elses2是二义性的;

7文法的形式注：文法的形式一定要牢记,特别是2型和3型文法一定要牢记,不

仅在概念题中有用,在下面的根据语言写文法题中也有重要作用,如果所写的文法

形式不对,一切都是无用功……

10型文法短语文法,图灵机：产生式形式为：,其中：VV且至少含有一个非
TN

终结符；VV
TN
21型上下文有关文法,线性界限自动机：产生式形式为:其中：||||,仅S

例外但是S不得出现在任何产生式右部;

32型文法上下文无关文法,非确定下推自动机：产生式形式为：P,PV,VV;
NTN
43型文法正规文法,有限自动机：右线性文法：产生式形如：AB或A其中：V；
T
A,BV左线性文法：产生式形如：AB或A其中：V；A,BV
NTN
例题：设G=V,V,S,P是一个上下文无关文法,产生集合P中的任一个产生式应具
TN
有什么样的形式若G是1型文法呢若G是正则文法呢

上下文无关文法,产生式形式为：P,PV,VV;
NTN
1型文法：产生式形式为:其中：||||,仅S例外;

正则文法：右线性文法：产生式形如：AB或A其中：V；A,BV
TN

左线性文法：产生式形如：AB或A其中：V；A,BV
TN
8什么是PDA下推自动机

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

K:有穷状态集：输入字母表有穷H:下推栈符号的有穷字母表
h0:H中的初始符号f:KΣ{}H–>KHS：属于K是初始状态;

Z:包含于K,是终结状态集合;

9什么是DFA有穷状态自动机

自动机M是一个五元式M=S,,f,S,F,其中：
0
1S:有穷状态集,2：输入字母表有穷,

3f:状态转换函数,为SS的单值部分映射,fs,a=s’表示：当现行状态为s,

输入字符为a时,将状态转换到下一状态s’;我们把s’称为s的一个后

继状态;

4SS是唯一的一个初态；5FS：终态集可空;
0
10推导：所谓推导就是对于一个含非终结符A的符号串,利用规则A→α,把A替

换成α得到新符号串的过程;

最左