编译原理期末复习资料

《编译原理期末复习资料》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、编译原理期末复习资料一、简答题：1.什么是编译程序？答：编译程序是指一个把源语言（如C,Pascal，java等高级语言）转换为目标语言（汇编语言、机器语言等低级语言）的翻译程序。2.什么是解释程序？答：解释程序指以一个源语言（C，Pascal，java等高级语言）为输入，但不产生目标程序，而是边解释边执行源程序本身的程序。3.编译程序和解释程序的区别？答：一个产生目标代码（编译），一个不产生目标代码（解释）。4.编译程序的步骤和任务：1）词法分析：从左至右扫描字符流的源程序、分解构成源程序的字符串，识别出(拼

2、)一个个的单词（符号）2）语法分析：层次分析，依据源程序的语法规则把源程序的单词序列组成语法短语（表示成语法树）3）语义分析与中间代码产生：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译（产生中间代码）。4）优化：对前段产生的中间代码进行加工变换，以期在最后阶段能产生出更为高效（省时间和空间）的目标代码。（书本）应用一些技术对代码进行变换以使得编译产生的目标代码高效（PPT）。5）目标代码生成：把中间代码（或经优化处理之后）变换成特定机器上的低级语言代码。（书本）生成目标机汇编和机器指令。二、名词

3、解释5.文法：一个文法G是一个四元组（VT,VN,S,P），其中：1．VT是一个非空有穷终结符号集合；2．VN是一个非空有穷的非终结符号集合，且VT∩VN=Φ；3．S∈VN开始符号。4．P是一个产生式的非空有穷集合，每个产生式的形式是A→α，其中A∈VN，α∈（VT∪VN）*开始符号S至必须在某个产生式的左部出现一次6.直接推导和推导直接推导：令G=(VT,VN,S,P),若A→γ∈P,且α,β∈(VT∪VN)*称αAβ直接推出αγβ,表示成αAβ⇒αγβ同时也称αγβ是αAβ的直接推导，或称αγβ直接归约到α

4、Aβ。推导：如果存在一个直接推导序列：α0⇒α1⇒α2⇒…⇒αn（n＞0）表示成α0+⇒αn，称从α0到αn的长度为n的推导。α0*⇒αn,或者α0=αn或者α0+⇒αn.7.语言：设文法G＝（VT，VN，S,P）。如果S*⇒α,则称α是一个句型。仅含终结符号的句型是一个句子。语言L(G）是由文法G产生的所有句子所组成的集合：L(G)＝{α

5、S*⇒α且α∈VT*}三、问答题8.文法的分类：分为四种，逐渐对产生式施加限制形成一个层次0型：G=(VT,VN,S,P)规则形式：α→βα,β∈(VT∪VN)*,α≠ε推

6、导：γαδ⇒γβδ1型（上下文有关）：规则α→β有

7、α

8、≤

9、β

10、规则形式：ξAη→ξγηA∈VN,ξ,γ,.η∈(VT∪VN)*,γ≠ε2型（上下文无关）：规则形式：A→βA∈VN，β∈(VT∪VN)*3型（右线性）：A→aB或A→a（右线性）A→Ba或A→a（左线性）a∈VT∪{ε}9.给语言写文法：P36：6、7、8、9、1110.改二义性文法：P36：10基本步骤：把出现二义的部分优先级分块。然后每个优先级用一个新的VN表示。最底优先级的VN符号要能由VT符号定义如：A→…

11、a11.NFA、DFA：P64

12、：12基本步骤：正则表达式→NFA→确定化（确定化表）→DFA(未简化)→最小化→最小化DFA（12.写正则表达式：P64：813.练习理解文法的First和Follow集，证明文法是LL（1）的，预测分析表，构造递归下降分析程序。1）计算FIRST（x）集：·若x属于VT，则FIRST（x）={x}·若x属于VN，x→a…，则a加入FIRST（x）·若x属于VN，x→Y…，则FIRST（Y）除“空串”之外的加入FIRST（x）·若x属于VN，X→Y1Y2Y3….YN若FIRST（Y1）、FIRST（Y1）、

13、FIRST（Y1）….FIRST（Yn）都含有“空串”那么把FIRST（Y1）、FIRST（Y1）、FIRST（Y1）….FIRST（Yn）都加入到FIRST（x）；如果只是前几个含有“空串”，如到Yk，那么把FIRST（Y1）、FIRST（Y1）、FIRST（Y1）….FIRST（Yk）中非“空串”元素加入FIRST（x）。2）计算FOLLOW（x）集：·若x为开始符号，则把#加入FOLLOW（x）；·若A→axp，则把FIRST（p）除“空串”加入FOLLOW（x）·若A→ax，或者A→axp中p有限步→“

14、空串”，则把FOLLOW（A）加入到FOLLOW（x）3）如何判断文法是否是LL（1）的：假设是的，那么，考察非终结符号A→a

15、p：·则FIRST（a）∩FIRST（p）=Φ·若p间接推导到“空串”，则FIRST（a）∩FOLLOW（A）=Φ14.如何消除左递归：·把n个非终结符号排序·从第一个到第n个依次处理，对于既不间接左递归又不是直接左递归的跳过保持不变·对于间接左递归的几个产生