编译原理期末复习知识点

编译原理

需积分: 46 139 浏览量更新于2023-05-18 7 收藏 2.89MB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

编译原理期末复习

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

每种类型题目给出了所涉及到的基本知识，然后对每类题目中的第一道例题进行了做法进

行了讲解，剩下的例题请给大家作为练习，答案也都给出，希望对大家复习有所帮助，最

后由于时间很紧，整理的有些仓促，整理中难免有遗漏或错误，请大家见谅。

注：下面出现的字母中，若无特别说明，小写英文字母为终结符，大写英文字

母为非终结符，希腊字母为终结符与非终结符的任意组合。

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

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

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

不要重复啰嗦。

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

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

的翻译程序。

2)构成：

（ 2 ）简述词法分析

阶段的主要任务（也有

可能问语法分析阶段主

要任务）

答：词法分析的任

务是输入源程序，对源

程序进行扫描，识别其

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

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

归约），识别各类语法单位，判断输入是不是语法上正确的程序

(3) 简述编译程序的构造过程（这个大家看看，是对（1）和（2）的综合）

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

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

是不是语法上正确的程序

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

分析并把它们翻译成中间代码。

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

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

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

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

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

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

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

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

G=(V

， V

， S ， P) ，其中

：终结符集合 ( 非空 ) V

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

= Æ S ：文法的开始符号， S Î V

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 型文法(短语文法，图灵机)：产生式形式为：a ® b ，其中：aÎ (V

)

且至少含

有一个非终结符；bÎ (V

)

2）1 型(上下文有关文法，线性界限自动机)：产生式形式为 : a ® b 其中： | a | £ | b | ，仅

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

3）2 型文法（上下文无关文法，非确定下推自动机)：产生式形式为： P ®a ， P Î V

， a

Î (V

)

。

4）3 型文法(正规文法，有限自动机)：右线性文法：产生式形如： A ® a B 或 A ® a

其中：

aÎ V

； A ， B Î V

左线性文法：产生式形如： A ® B a 或 A ® a 其中： aÎ V

；

A ， B Î V

例题：设 G=(V

，V

，S，P)是一个上下文无关文法，产生集合 P 中的任一个产生式应

具有什么样的形式？若 G 是 1 型文法呢？若 G 是正则文法呢？

上下文无关文法，产生式形式为： P ®a ， P Î V

， a Î (V

)

。

型文法：产生式形式为 : a ® b 其中： | a | £ | b | ，仅 S ®e 例外。

正则文法：右线性文法：产生式形如： A ® a B 或 A ® a

其中： aÎ V

； A ， B Î V

左线性文法：产生式形如： A ® B a 或 A ® a 其中： aÎ V

； A ， B Î V

(8)什么是 PDA(下推自动机)?

答： PDA

是下推自动机， P DA M

用一个七元组表示 (K,Σ,f,H,h0,S,Z)

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

h0 :H

中的初始符号 f: K ´ （ Σ È { e }) ´ H –> K ´ H* S ：属于

是初始状态。

包含于

，是终结状态集合

。

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

自动机

是一个五元式

M=(S, S , f, S

, F), 其中：

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

3 ） f: 状态转换函数，为

S ´S® S

的单值部分映射， f(s ， a)=s’ 表示：当现行状态为

s ，输入字符为

时，将状态转换到下一状态

s’ 。我们把

s’ 称为

的一个后继状态。

4 ） S

Î S

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

（10）推导：所谓推导就是对于一个含非终结符

的符号串，利用规则

A→α ，把

替换

成

得到新符号串的过程。

最左推导：在推导的每一步，选择符号串最左边的非终结符进行替换。

最右推导：在推导的每一步，选择符号串最右边的非终结符进行替换。

(11)归约：归约是推倒的逆过程，即用产生式的左部非终结符替换右部符号串。

(12)什么是句型？什么称为句子？什么是语言？

句型：从文法的起始符号出发，经过有限步的推导能够推导出来的符号称为句子。

句子：只由终结符构成的句型称为句子。

语言：所有句子的集合构成该文法描述的语言。

(13)什么是短语？什么是直接短语（也称为简单短语）？什么是句柄？什么是素短语？什

么是最左素短语？（以下几个概念一定要理解，考试中肯定会考哪些是短语，直接短语，

句柄等，具体方法请参见后面的）

短语：如果存在某个文法非终结符 P,满足 S βPγ,并且 Pα 则称 α 为句型 βαγ 相对

于非终结符 P 的短语。

直接短语：如果 PÞα,即从 P 出发一步推出 α，则 α 称为直接短语。

句柄：一个句型的最左直接短语称为该句型的句柄。

素短语：至少含有一个终结符的短语，并且除了自身外，不包含更小的素短语。

最左素短语：句型中最左边的素短语。

（14）自顶向下的语法分析方法中需要解决的主要问题什么？如何表示？

答： 1 ）主要需要解决回溯和左递归问题。

2 ）表示方式，回溯：文法中存在形如

A→α

|α

| … |α

, 即产生式右部存在多个候选，导

致推导时不能确定到底应该选择哪个候选式。

左递归：文法中存在形如

P→Pα

的形式，推导时会导致推导过程无休止的进行

下去。

注：解决方法，对回溯采取的是提取左公因子，对左递归使消除左递归（包括直接左递归

和间接左递归）。

(15)内情向量：一般编译程序对数组说明的处理是把数组的有关信息汇集在一个叫做“内情

向量”或“信息向量”的表格中，以便以后计算数组元素的地址时引用这些信息。每个数组有

一个内情向量。其中的信息包括，数组的类型，维数，各维的上、下界，以及数组的首地

址。

（16） C 语言的活动

记录：

2、最左最右推

导，画语法树，

找短语、直接短

语、句柄等。

这种题目很简单，

送分题，一定不

能丢分！

考题：1）文法 G[S]

为：S→SdT | T

T→T<G | G G→(S) |

a 试给出句型

(SdG)<a 的推导过

程及语法树，并找出(SdG)<a 的短语，直接（简单）短语、句柄和最左素短语。

Ol d SP

返回地址

参数个数

形式单元

局部变量

内情向量

临时单元

TOP

剩余22页未读，继续阅读

votal30

粉丝: 52
资源: 247

会员权益专享

编译原理期末复习知识点

《编译原理》——期末复习.docx

编译原理—姜守旭@哈工大.pdf

编译原理期末考试题

编译原理期末试卷csdn

编译原理期末考试 csdn

北邮编译原理期末csdn

编译原理期末考试csdn

编译原理期末试题 csdn

编译原理知识点pdf

编译原理题库csdn

编译原理 笔记 pdf

贵州大学编译原理csdn

liunx期末复习知识点

编译原理实验:语法分析程序编译原理语法解读及定义-c++文档类资源-csdn下载编译原

如何快速学习编译原理

type在c语言的用法和短语,编译原理复习题集

编译原理本科教学版pdf

编译原理陈火旺课后答案 csdn

csdn 编译原理 笔记

编译原理王生原pdf

会员权益专享

最新资源

编译原理笔记 pdf

csdn 编译原理笔记