《四川大学编译原理期末复习.docx》由会员分享，可在线阅读，更多相关《四川大学编译原理期末复习.docx（16页珍藏版）》请在金锄头文库上搜索。
1、四川大学编译原理期末复习一、简答题1.什么是编译程序答：编译程序是一种将高级语言程序(源程序 )翻译成初级语言 (目标程序 )的程序。将高级程序设计语言程序翻译成逻辑上等价的初级语言 (汇编语言 ,机器语言 )程序的翻译程序。2.请写出文法的形式定义答：一个文法 G 抽象地表示为四元组G=（Vn,Vt,P,S） 其中 Vn 表示非终结符号 Vt 表示终结符号， VnVt=(字母表 )，VnVt= S 是开始符号， P 是产生式，形如： ( V+且最少含有一个非终结符号， V*) 3.语法解析阶段的功能是什么答：在词法解析的基础上，依照语言的语法规则，将单词符号串分解成各样语法短语(例：程序、语
2、句、表达式 )。确定整个输入串可否组成语法上正确的程序。4.局部优化有哪些常用的技术答：优化技术 1删除公共子表达式优化技术 2复写流传优化技术 3删除无用代码优化技术 4对程序进行代数恒等变换（降低运算强度）优化技术 5代码外提优化技术 6强度削弱优化技术 7删除归纳变量优化技术简介 对程序进行代数恒等变换（代数简化）优化技术简介 对程序进行代数恒等变换（合并已知量）5编译过程分哪几个阶段答：逻辑上分五个阶段：词法解析、语法解析、语义解析与中间代码生成、代码优化、目标代码生成。每个阶段把源程序从一种表示变换成另一种表示。6. 什么是文法答：文法是描述语言的语法构造的形式规则。 是一种工具，它
3、可用于严格定义句子的构造；用有穷的规则刻划无量的会集； 文法是被用来精确而无歧义地描述语言的句子的组成方式；文法描述语言的时候不考虑语言的含义。7. 语义解析阶段的功能是什么答：对语法解析所鉴别出的各样语法范围解析其含义， 进行初步的翻译 (翻译成中间代码 )；并对静态语义进行审查。8.代码优化须依照哪些原则答：等价原则：不改变运行结果有效原则：优化后时间更短，占用空间更少合算原则：应用较低的代价获取较好的优化收效9.词法解析阶段的功能是什么答： / 逐个 入源程序字符并依照构 切分成一系列 任 ： 入源程序， 出 符号 掉空格，跳 注 、 行符 追踪 行 志，指出源程序出 的行列地址 宏张开
4、， 10.什么是符号表答：符号表在 程序工作的 程中需要不断收集、 和使用源程序中一些 法符号的 型和特色等相关信息。 些信息一般以表格形式存 于系 中。如常数表、 量名表、数 名表、 程名表、 号表等等， 称 符号表。 于符号表 、构造和管理方法的利害会直接影响 系 的运行效率。11.什么是属性文法答：是在上下文没关文法的基 上， 每个文法符号 (含 符和非 符 )配 若干个属性 ， 文法的每个 生式都配 了一 属性 算 (称 )。在 法解析 程中，完成 所描述的 作，从而 理。12.什么是基本 答：是指程序中一 序 行的 句序列，其中只有一个入口 句和一个出口 句，入口是其第一个 句，出口
5、是其最后一个 句。13.代 化 段的功能是什么答： 已 生的中 代 行加工 ，使生成的目 代 更 高效( 和空 )。14.文法分哪几 答：文法有四种 : 有 G=(Vn,Vt,P,S),不相同 型的文法可是 生式的要求不相同：型文法 (短文文法 )： G 的每个 生式 足： V+且中最少含有一个非 符 , V*型文法 (上下文相关文法 )：若是 G 的每个 生式均 足 | |=| |, 当除外，但 S 不得出 在任何 生式的右部型文法 (上下文没关文法 )：G 的每个 生式 A, A 是一非 符， V*型文法 (正 文法 )：G 的每个 生式的形式都是：AB 或 A，其中 A,B 是非 符，是
6、 符串。(右 性文法 )。15.循 化常用的技 有哪些答：代 外提； 度削弱； 除 量。16.什么是算符 先文法答： 算符文法G 的任何 符a,b 之 要么没有 先关系，若有 先关系,至多有中的一种成立 ,G 一算符 先文法。二、计算题（一）推导、最左推导、最右推导和语法树,复习表达式文法及相关例题。1. 表达式的推导例： G = (E, i, +, *, (, ) , P , E)P： EE+E | E*E| (E) | i答：表达式 (i)和(i+i)*i 的推 ：E(E)(i)EE*E(E)*E(E + E)*E (i + E)*E (i + i)*E (i + i)*iEE*EE*i(
7、E)* i (E + E)*i (E+ i)*i (i + i)*i(i+i)*i 的最左推导过程：EE*E(E)*E(E + E)*E(i + E)*E(i + i)*E(i + i)*i(i+i)*i的最右推导过程：EE*EE*i(E + E)*i(E+ i)*i(i + i)*i2语法树例：对文法 G = (E, i, +, *, (, ) , P , E)P： EE + E | E * E | ( E ) | i答： 句子 (i+i)*i 的语法树：例： G = (E, i, +, *, (, ) , P , E)P： EE + E | E * E | ( E ) | i答：句子 (
8、i * i + i)的语法树：(1)E(E)(E + E)(E * E + E) (i * E+ E)(i *i + i)（二）给定语言求文法（三）逆波兰式（四）将 for 语句和 if 语句翻译成相应的四元式序列(五 ) 短语、素短语、最左素短语，FirstVT 集和 LastVT 集的求解方法(复习第四章算符优先文法相关内容)1. 短语、素短语、最左素短语集和 LastVT集的求解方法例：设文法为：E #E#；TF； EE+T；F PF | P； ET ； P (E)；TT*F； P i；3. 算符优先文法优先关系的定义 :算符优先文法的定义 :三、综合题的确定化和最小化 (参看课件第三章
9、 62 页：例 5)2.自顶向下解析 (参看课件第四章（ 1）67 页：综合练习 )例：求对应于下述文法的展望解析表:ETEE+TE |TFTT*FT | F(E) |i答：1） 第一求 first 集:2） 由于First(E), First(T), 求 E和 T的 Follow 集:3） 依照会集的值填表，获取:例:设文法 G(S)： S (L) | aS | aLL，S | S(1) 除掉左递归和回溯；(2) 计算每个非终结符的 First 和 Follow 集；(3) 构造展望解析表。答： (1) 除掉左递归和回溯：(2)(3)构造展望解析表：解析方法 (参看课件第四章（ 3）28 页及 30 页 )(附 )1.短语、直接短语、句柄例：考虑以下文法：E =T | E+TT =F | T*FF =i|(E)求句型i1 * i2 + i3 的短语、直接短语和句柄答： E = F * i2 + i3E = i1 * F + i3E = T + i3（T =T*F =i1 * i2）F=iE = i1 * i2 + i3E = i1 * i2 + F因此：短语有： i1,i2,i3,直接短语有： i1, i2 , i3句柄是：i1i2 + i3 不是短语，由于i1
