编译原理总复习

编译原理总复习 第 1 页 共 8 页 编译原理试题整理编译原理试题整理 考试题型 简答 4 道 计算 4 道 综合 3 道 一 简答题 1 什么是编译程序 其分为几个阶段 编译程序 也称为编译器 能够直接将高级语言程序翻译为对应的低级语言程序 编译程序通常分为 词法分析 语法分析 语义分析与中间代码生成 代码优化 目标代 码生成 5 个阶段 2 文法的形式定义是什么 文法的形式定义为 G P S 其中为非终结符集 是终结符集 P 是 N V T V N V T V 产生式集合 S 是开始符号 3 什么是上下文无关文法 若在文法的定义中限定文法的产生式左部只有一个非终结符 则该文法称为上下文无关文 法 4 什么是文法的语言 从文法 G 的开始符号 S 出发 所能推导出的句子的全体称为文法 G 产生的语言 5 文法的分类 乔姆斯基把文法分为 0 型文法 短语文法 1 型文法 上下文有关文法 2 型文法 上下 文无关文法 3 型文法 正规文法 四类 这几类的差别在于对产生式施加不同的限制 6 词法分析的功能 1 按规则识别单词 输出单词本身及其类别码 主要任务 2 滤掉程序中的无用成分 3 调用出错处理程序 识别并定位错误 4 调用符号管理程序 将识别出来的单词及其属性进行管理 7 什么是符号表 有何作用 符号表 是一种用于保存源程序中出现的标识符和常数的各种信息的数据结构 作用 编译器在分析阶段收集信息放入符号表中 在综合阶段生成目标代码时使用符号表 中的信息 8 什么是正规文法 若文法 G P S 中的每个产生式 P 的形式都是 A aB 或 A a 其中 N V T V A B a 则 G 是正规文法 N V T V 9 语义分析的主要任务 1 对语法分析所识别出的各类语法短语进行静态语义审查 2 若无语义错误 再根据识别出的语法单位的类型进行处理 若是说明语句 则将变量的 类型等属性填入符号表 若是可执行语句 则进行初步的翻译 将其翻译为中间代码 10 什么是属性文法 属性文法 包含一个上下文无关文法和一系列的语义规则 为每个文法符号配备若干相关 的 值 属性 11 什么是语法制导翻译 若遍历语法树的操作和建立语法树的操作同时进行 称为语法制导翻译 12 什么是代码优化 编译原理总复习 第 2 页 共 8 页 代码优化 指的是为了提高目标程序的质量而对源程序或中间代码进行的各种合理的等价 变换 使得变换后的程序能生成更有效的目标代码 13 代码优化要遵循哪些原则 遵循如下原则 等价原则 有效原则 合算原则 14 局部优化常用哪些技术 包括 删除公共子表达式 删除无用赋值 合并已知量 对临时变量改名 对语句变换位 置 代数变换等 15 循环优化常用哪些技术 包括 代码外提 强度削弱 删除归纳变量等 16 什么是短语文法 若对文法中的产生式 的要求是 至少含有一个非终结符 则称该文法为短语文 法 二 计算题 1 推导 画语法树 二义性的证明 5 已知表达式的文法 G 为 i 给出 i i i 和 i i i 的最左推导 最右推导和语法树 解答 解答 用 E 表示 T 表示 F 表示 上述文法可以写为 E T E T T F T F F E i 最左推导 E E T E T T T T T F T T i T T i F T i i T i i F i i i E E T T T F T i T i T F i F F i i F i i i 最右推导 E E T E F E i E T i E F i E i i T i i F i i i i i E E T E T F E T i E F i E i i T i i F i i i i i i i i 和 i i i 的语法树如下图所示 编译原理总复习 第 3 页 共 8 页 i i i i i i 的语法树 8 考虑文法 G S S aSbS bSaS 1 试用最左推导说明此文法的二义性 2 对于句子 abab 构造两个相应的最右推导 3 对于句子 abab 构造两棵相应的分析树 4 此文法所产生的语言是什么 解答 解答 1 句子 abab 有如下两个不同的最左推导 S aSbS abS abaSbS ababS abab S aSbS abSaSbS abaSbS ababS abab 所以此文法是二义性的 2 句子 abab 的两个相应的最右推导 S aSbS aSbaSbS aSbaSb aSbab abab S aSbS aSb abSaSb abSab abab 3 句子 abab 的两棵分析树 a b 4 此文法产生的语言是 在 a b 上由相同个数的 a 和 b 组成的字符串 2 给出短语写文法 7 试构造生成下列语言的上下文无关文法 1 n 1 i 0 1 L inn cba 6 语言 x x a b c x 是重复对称排列的 aabcbaa aabbaa 等 6 L 编译原理总复习 第 4 页 共 8 页 解答 解答 1 把 anbnci分成 anbn和 ci两部分 分别由两个非终结符号生成 因此 生成此文法的 产生式为 S AB A aAb ab B cB 6 G S S aSa bSb cSc a b c 3 短语 素短语 最左素短语 firstVT lastVT 例 4 19 P92 例 4 20 P93 12 已知文法 G E 拆成两道大题出 拆成两道大题出 E T E T T F T F F E i 1 给出句型 T F i 的最右推导 并画出语法树 2 给出句型 T F i 的短语 素短语和最左素短语 3 证明 E T F 是文法的一个句型 指出这个句型的所有短语 直接短语和句柄 解答 解答 最右推导 E T F E E T E F E i T i T F i 语法树 图 4 1 句型 T F i 的语法 树 短语 T F i T F i T F i 素短语 T F i 最左素短语 T F 由于 E E T E T F 故 E T F 为该文法的句型 短语 T F E T F 直接短语 T F 句柄 T F 13 给定文法 G S 其产生式如下 S T a T T S S 1 给出输入串 a a a 的最左和最右推导过程 编译原理总复习 第 5 页 共 8 页 2 计算该文法各非终结符的 FirstVT 集和 LastVT 集 解答解答 最左推导 S T T S S S a S a T a T S a S S a a S a a a 最右推导 S T T S T T T T S T T a T T a T a a S a a a a a 文法中 S 和 T 的 FirstVT 和 LastVT 集为 FirstVT S a FirstVT T a lastVT S a lastVT T a 4 给语句写四元式序列 四选一 例 5 12 P156 11 将下面的语句翻译为四元式序列 1 if A C and B D then if A 1 then c c 1 else if A D then A A 2 4 for i b 2 to 100 do x a b c d a b c 解答 解答 1 四元式序列为 1 j A C 3 8 T C 2 j 14 9 j 14 3 j i t1 15 7 a b t3 8 c d t4 9 t3 t4 t5 10 a b t6 11 t6 c t7 12 t5 t7 t8 13 t8 x 14 j 4 15 三 综合题 1 NFA DFA 例 3 9 P44 2 自上而下分析 四选一 例 4 12 P79 8 已知文法 G S 其产生式如下 S L a 编译原理总复习 第 6 页 共 8 页 L L S S 从 G S 中消除左递归 并为之构造一个非递归预测分析器 LL 1 分析表 并说明对输入符 号串 a a a 的分析过程 解答 解答 消除所给文法的左递归 得 G S L a L SL L SL 实现预测分析器的不含递归调用的一种有效方法是使用一张分析表和一个栈进行联合 控制 下面构造预测分析表 根据文法 G 有 First S a Follow S First L a Follow L First L Follow L 按以上结果 构造预测分析表 M 如下 文法 G 是 LL 1 的 因为它的 LL 1 分析表不含多重定义入口 预测分析器对输入符号串 a a a 做出的分析动作如下 步骤栈剩余输入串输出 1 S a a a 2 L a a a S L 3 La a a 4 L Sa a a L SL 5 L aa a a S a 6 L a a 7 L S a a L SL 8 L S a a 9 L L a a S L 10 L La a 11 L L Sa a L SL 12 L L aa a S a 13 L L a 14 L L S a L SL 15 L L Sa 16 L L aa S a 17 L L 18 L L 19 L 20 L 编译原理总复习 第 7 页 共 8 页 21 9 求下述文法中各非终结符号的 First 集 Follow 集 各候选式的 First 集 1 S AB bC 2 A b 3 B aD 4 C AD b 5 D aS c 解答解答 各非终结符的 First 集 First S First A First B b a b First A b b First B a a First C First A First D First b a b c First D a c a c 各个候选式的 First 集为 First AB a b First bC b First First b b First aD a First AD a b c First b b First aS a First c c 各非终结符的 Follow 集的计算 Follow S Follow D Follow A First B Follow S First D a c Follow B Follow S Follow C Follow S Follow D Follow B Follow C 11 下述文法中哪个是 LL 1 的 说明理由 1 S Abc A a B b 2 S Ab A a B B b 解答解答 1 a 文法不含左递归 b S A B 各候选式的 First 集不相交