南邮 2020 编译原理期末复习.pdf-资料库

qq_27094507-12768474-16359647281064618002.pdf-第1页.png

第1页 / 共35页

qq_27094507-12768474-16359647281064618002.pdf-第2页.png

第2页 / 共35页

qq_27094507-12768474-16359647281064618002.pdf-第3页.png

第3页 / 共35页

qq_27094507-12768474-16359647281064618002.pdf-第4页.png

第4页 / 共35页

qq_27094507-12768474-16359647281064618002.pdf-第5页.png

第5页 / 共35页

qq_27094507-12768474-16359647281064618002.pdf-第6页.png

第6页 / 共35页

qq_27094507-12768474-16359647281064618002.pdf-第7页.png

第7页 / 共35页

qq_27094507-12768474-16359647281064618002.pdf-第8页.png

第8页 / 共35页

《编译原理》期末复习大纲可以猜想一下(LR) 一、题型与分值（可能会微调） 1、填空题：10 题 20 分文法对应的语言等 2、判断题：5-6 题 10 分基础概念 2、简答题：6-7 题 40 分求 first 集 follow 集、语法树等，证明二义性消除左递归 4、解答题：2 题 20 分比较大的题分析句子、构造 DFA、构造 LR 5、设计题：1 题 10 分二、知识点梳理（不考死记硬背的题目） 01、汇编程序、解释程序、编译程序的概念（记忆） P2-3【小题】汇编程序：把汇编语言写的源程序翻译成机器语言的目标程序。解释程序：将高级语言写的源程序作为输入数据，但并不产生目标程序，而是边解释边执行源程序本身的一种程序。编译程序：是将高级语言写的源程序翻译成目标语言（汇编语言、机器语言）的程序。 02、编译过程的八大组成部分的名称（记忆） P5【小题】 1、词法分析 2、语法分析 3、语义分析 4、中间代码生成 5、代码修饰优化 6、信息表格管理 7、错误检查和出错处理 8、目标代码生成 03、分遍（趟程）的概念及其适用情况（记忆） P9【小题】从头到尾扫描一遍源程序或等价源程序，并做有关加工处理，称趟程(遍) 。每经过一趟源程序都要进行等价变换并更接近目标程序。如果通过对源程序一遍扫描直接生成目标代码程序，则说编译程序是单遍的。把源程序分为几遍来编译，每遍只完成编译程序中的一部分或几个部分工作，称为多遍的。 04、系统程序设计语言、自编译、交叉编译，会利用 T 型图描述自编译和交叉编译过程 P10【简答题】系统程序设计语言：能够编写编译程序或其他系统软件的高级语言称系统程序设计语言。

05、符号、符号串、符号串集合以及相关运算（联结、乘积、方幂）P17-19【基础，不单独考】有限个元素的非空集合称字母表，也称符号集。它是组成一个语言最基本的成分。字母表中元素称为符号。符号串是字母表中的符号所组成的任何有穷序列。符号串集合：若集合 A 中的一切元素都是字母表上符号串，则称 A 为该字母表上的符号串集合。 A={a,b}，则 A0={ε},A1={a,b},A2={a,b}{a,b}={aa,ab,ba,bb} A3={aaa,aab,aba,abb,baa,bab,bba,bbb} 06、产生式、文法、推导（推导的长度）与归约（理解） P21-23【小题】产生式就是一个符号与另一个符号串的有序偶(U,x)，通常记为 U∷=x 文法是规则的有穷集合,形式定义为四元组形式为 G=(VN,VT,P,Z) 其中：VN 是非终结符集合, VT 是终结符集合, P 代表产生式集, Z∈VN是文法 G 开始符号，也称识别符号，它至少要在一条产生式左部出现。文法 G 通常记为 G［Z］。一个产生式就是一个直接推导。设 u0,u1,u2,…,un 均为 V*上符号串,若 w 是 v 经过一系列直接推导得到的。即：v= u0⇒u1⇒u2⇒···⇒un-1⇒ un =w (n>0)则称 v 推导到 w，或称 w 归约到 v，记作：v ⇒+w，称这个直接推导序列为长度为 n 的推导。如果 v ⇒ +w 或者 v=w（表示 0 步推导），则记作 v ⇒*w，称 v 广义推导到 w 或称 w 广义归约到 v。 07、第一次采用形式化体系方法巴科斯—瑙尔范式定义语法规则的语言是 ALGOL 语言 08、句型、句子、语言的概念 P24【小题】设 G［Z］是一文法，若符号串 x 是由识别符 Z 推导而得，即 Z⇒*x，x∈V*。则称

符号串 x 为该文法 G 的一个句型。如果一个句型 x 仅由终结符组成，即——Z⇒*x，x∈VT*，则称句型 x 为该文法一个句子。 G[Z]为一文法，由该文法所产生的一切句子的集合称为由该文法所定义的语言，记为 L(G[Z])。 09、给出文法，会求出语言 P24【小题】(填空选择) 直接代入推导（注意 n 次方幂的数量限制） 10、文法非终结符号、终结符号非终结符号：出现在规则左部，且能派生出符号或符号串的那些符号称为非终结符，也称语法实体或语法单位，它们的全体构成一个非终结符的集合，记为 VN 终结符号：规则中不属于 VN的那些符号称为终结符，它们的全体组成终结符的集合，记为 VT 。终结符一般出现在规则的右部。 11、递归规则、递归文法的含义，会利用该写法消除文法的左递归（注意，不是利用扩展 BNF 范式改写）对于一个文法,若有一个规则 U∷=…U…,则称直接递归,若有规则 U∷=U…,则称直接左递归,若有规则 U∷=…U,则称直接右递归。若有推导式 U⇒+…U…,则称间接递归,若有推导式 U⇒+U…,则称间接左递归, 若有推导式 U⇒+…U,则称间接右递归。非终结符 U 称递归非终结符。如果一个文法中至少含有一个递归非终结符,则将此文法称为递归文法。消除左递归： 1）用重复表示法（扩充的ＢＮＦ表示法）改写语法规则假定一个文法中有关于非终结符的规则为Ａ∷＝Ａα｜β，其中α非空，β不以Ａ开头，则等价地改写为Ａ∷＝β｛α｝ 例如，下述直接左递归规则：Ｅ∷＝Ｅ＋Ｔ｜Ｔ 可改写为Ｅ∷＝Ｔ｛＋Ｔ｝同样，规则Ｔ∷＝Ｔ*Ｆ｜Ｔ／Ｆ｜Ｆ可改写为Ｔ∷＝Ｆ｛*Ｆ｜／Ｆ｝ 2）消除直接左递归还可用另一种方法来改写形如文法规则Ａ∷＝Ａα｜β的直接左递归。对Ａ引入一个新的非终结符Ａ′，将Ａ∷＝Ａα｜β等价写成 Ａ∷＝βＡ′，Ａ′∷＝αA′｜ε 由于β不以 A 开头，α不以 A′开头，因此改写后两条规则不是直接左递归。 3）消除间接左递归对于间接左递归先将间接左递归变成直接左递归，然后消除直接左递归例如；A ∷＝aB|Bb (1)，B ∷＝Ac|d (2)先将（1）代入（2）中，得 B ∷＝Bbc|aBc|d (3)

13、规范推导和规范归约的定义最右推导叫规范推导，即在规范推导过程中，每步直接推导 xUy⇒xuy 中，符号串 y 只含有终结符。如果推导 v⇒+w 中每一步直接推导是规范的，则称推导 v⇒+w 为规范推导。规范归约：我们把最左推导的逆过程称最右归约，最右推导的逆过程称最左归约，最左归约也称为规范归约。 14、文法二义性和语言二义性的区别如果一个文法中某个句型对应两棵不同的语法树，则称这个文法是二义性的。产生该语言的文法都是二义性文法，称该语言为二义性语言。至少有一个非二义文法产生该语言称此语言为非二义性语言。 15、证明文法的二义性（掌握） P29【小题或简答】 16、文法和语言的分类、文法与自动机的对应（掌握） P33-35【小题或简答】若在文法 G 中，P 中规则具有如下形式：α∷=β其中α∈V+，且至少含一个非终

结符，β∈Ｖ*，则文法 G 称为 0 型文法或称短语结构文法。若在文法 G 中，P 中规则具有如下形式： αAβ∷=αwβ，其中α,β∈V*,A∈ＶＮ,w∈Ｖ＋,则称文法 G 为 1 型文法或上下文有关文法。(只有当非终结符 A 的上下文为α和β时，方可用 w 去替换 A) 若在文法 G 中，P 中规则具有如下形式：A∷=w,其中 A∈VN, w∈V*, 则称文法 G 为 2 型文法或称上下文无关文法。(无需考虑 A 的上下文出现情况) 若在文法 G 中，P 中规则具有如下形式：A∷=aB 或 A∷=a 其中 A , B∈VN , a∈VT, 则称文法 G 为右线性文法。类似地，如 P 中规则有如下形式: A∷=Ba 或 A∷=a,则称文法 G 为左线性文法。通常，我们把左线性文法和右线性文法称 3 型文法或正规文法。产生式中含有左部两个符号必为 0 型或 1 型，其中左部比右部长，必为 0 型，长度相等即可转换为至少 1 型。右部只有两个非终结符，必不为 3 型。由某种类型文法生成的语言称为对应文法类型的语言能识别或生成语言的识别器（某种算法或过程）称为自动机。 17、会求一个文法的压缩过文法（掌握） P36【小题】 1、在文法中不含有形如 A∷=A 的规则 2、在文法中不包含多余规则(非终结符必须在文法中出现，否则不可到达，并且非终结符必然推出终结符串) 否则将该规则以及包含该规则的左部符号的产生式一并删除。 18、扫描缓冲区，超前搜索的概念和作用扫描缓冲区就是在内存中开辟一部分单元，供识别单词用。所谓超前读字符（也称超前搜索），是指仅向前读取字符，判别该字符类型以后，再处理已读过的字符。 19、正规文法和状态转换图转换(全套理解+掌握)P46-50【小题或简答或解答】正规文法就是乔姆斯基文法分类中的 3 型文法。转换图实际上是一个有线方向图，图中结点代表状态，用圆圈表示。状态之间用箭

弧连接，箭弧上标记代表射出结状态下可能出现的输入字符。对于左线型文法 G[E]：U∷=a 或 U∷=Ba U, B∈VN ，a∈VT 右线性文法 G[E]：U∷=aB 或 U∷=aU, B∈VN ，a∈VT 左右线性文法的等价产生式 20、有穷自动机的概念和特点（DFA 和 NFA 的各自特点））（理解+掌握） P55-58 【小题或简答】一个确定的有穷自动机（DFA）M 是一个五元组，即 M＝（K，VT，M，S，Z）其中：Ｋ是状态有穷的非空集合，K 中每一个元素是一个状态；VT是一个有穷输入字母表，VT中的每一个元素称为输入字符；M 是 K×VT到Ｋ的单值映射（或函数），即 M(q ,a)=p 。q ,p ∈K, a∈VT。它表示：当前状态为 q，输入字符为 a 时，将转到下一状态 p, p 是 q 的一个后继状态。由于映射是单值，所以称确定有穷自动机。Ｓ为开始状态，是唯一一个初态 S∈K；Z 是终止状态集合，Ｚ是 K 的子集。(单值映射，初态唯一) 一个有穷自动机 DFA 可唯一表示一张确定的状态转换图。 M(q,a)＝{p1，p2，…，pn}∈2K，q∈K，a∈VT它表示：当前状态为 q，输入字符为 a 时，映射Ｍ将产生一个状态集合{p1, p2,…，pn｝（可能是空集），而不是单个状态，

所以称非确定有穷自动机。(多值映射) 一个非确定的有穷自动机(NFA)M 是一个五元组，即Ｍ＝(K，VT，M，S，Z),M 是 K×VT 到 K 子集上映射，即{K× VT ∈ 2k},2k是幂集，是 K 中所有子集组成。(初态为符号集合) 凡是一个语言被 NFA 接受，一定能被 DFA 接受。对于任一个(NFA)M，我们总能构造出与其等价的(DFA)M′ 21、正规表达式、正规文法、自动机的等价问题 Kleen 定理描述：L 是正规集 ⇔存在一个有穷自动机（FA）M，使得 L=L（M） ⇔存在一个正规文法 G，使得 L（M）=L（G） ⇔存在一个正规表达式 e，使得 L（e）=L（G） 22、正规表达式（与转换系统的互转，会求其正规集）和有穷自动机（含利用子集法把 NFA 转 DFA）（全套理解+掌握）P62-70【小题或简答或解答】所谓转换系统是一个具有唯一开始状态 S 和唯一最终状态 Z 的一种特殊状态图。1. 没有弧引向开始状态 S 2. 没有弧从终止状态 Z 引出 3. )转换系统的弧可以用空符号 ε标记。

资料库

南邮 2020 编译原理期末复习.pdf

相关推荐

行业

热门标签

最新资料