编译程序总复习——例题.ppt

编译程序总复习编译程序总复习例题例题 1. 1. 编译程序的功能和组织结构编译程序的功能和组织结构 2. 2. 编译和解释程序编译和解释程序 3. 3. 正则表达式正则表达式 nfa dfa dfa nfa dfa dfa 最小化最小化 句型句型推导的语法树推导的语法树短语短语简单短语简单短语 句柄句柄 6.6.文法文法语言语言句子句子 7.7.语法分析语法分析自顶向下和自底向上自顶向下和自底向上 （llll法、法、 lrlr法）法） 8.8.语法制导翻译语法制导翻译 9.9.中间代码中间代码 10.10.中间代码优化中间代码优化 11.11.目标代码目标代码 1 . 编译程序的功能和组织结构 表 处 理 词 法 分 析 源 程 序 目 标 程 序 错 误 处 理 语 法 分 析 语 义 分 析 目 标 代 码 生 成 前前 端端 后 端 中 间 代 码 优 化 中 间 代 码 生 成 2. 编译和解释程序 目标程序 源 程 序 编 译 程 序 初始数据 计 算 结 果 源程序 解 释 程 序 初始数据 计 算 结 果 功能工作结果实现技术上 解释解释 程序程序 源程序的一源程序的一 个个执执执执行行系系统统统统 源程序的源程序的 执执执执行行结结结结果果 执执执执行中行中间间间间代代码码码码 编译编译 程序程序 源程序的一源程序的一 个个转换转换转换转换 系系统统统统 源程序的源程序的 目目标标标标代代码码码码 把把中中间间间间代代码转码转码转码转 换换换换成目成目标标标标程序程序 解释程序和编译程序的区别 解释程序和编译程序的根本区别根本区别： 是否生成目标代码 3. 正则表达式 设文法ga: a b b x | ba x xa | xb | a | b 试求出文法ga产生的语言对应 的正则式。 3. 设文法ga: ab b x | ba x xa | xb | a | b 试求出文法ga产生的语言对应的正则式 。 解解: : ( (a|b)(a|b)* (a|b)(a|b)*)*a|b)(a|b)* (a|b)(a|b)*)* 4. 4.请构造与正则式请构造与正则式r=(a*b)*r=(a*b)*baba(a|b)* (a|b)* 等价的状态最少的等价的状态最少的dfadfa（确定有限自确定有限自 动机）。动机）。 解：解： (1) (1) nfanfa (2) nfa dfa(2) nfa dfa (3) dfa (3) dfa 最小化最小化 5.5.有文法有文法gege：e et|e+t|e-tt|e+t|e-t t tf|t*f|t/ff|t*f|t/f f fi/(e)i/(e) 请判断请判断( (e+t)*i+fe+t)*i+f是是g g的一句型的一句型 吗？吗？ 如果是，请画出它的推导的语法如果是，请画出它的推导的语法 树。树。 并写出语法树的短语、简单短语并写出语法树的短语、简单短语 、句柄。、句柄。 有文法有文法gege： e et|e+t|e-tt|e+t|e-t t tf|t*f|t/ff|t*f|t/f f fi/(e)i/(e) ( (e+t)*i+fe+t)*i+f是是g g的一句型的一句型 ) ) e e ( ( + + e e t t e e + + e e t t t t f f f f * * t t i i f f 每棵子树的每棵子树的 叶组成叶组成短语短语 ( (e+t)*i+fe+t)*i+f (e+t)*i(e+t)*i (e+t)(e+t) e+te+t i i f f 每棵简单子每棵简单子 树的叶组成树的叶组成 简单短语简单短语 e+t e+t i i f f 最左简单子树的叶组成最左简单子树的叶组成句柄句柄 e+te+t 6.6.（1 1）设有文法）设有文法gs=(b,s,b,s, gs=(b,s,b,s, s b|s b|bbbb,b,bbsbs), ,该文法所描述的该文法所描述的 语言语言是是_。 （2 2）已知语言）已知语言l=l=a a n n bbbb n n |n 1|n 1，则则 _文法文法可以产生语言可以产生语言l l。 （3 3）设有文法设有文法gigi： ii1 | i0 | ii1 | i0 | ic ic | a | b | c | a | b | c 该文法的该文法的句子句子有有 _ ab0 ab0 a0c01 a0c01 aaa aaa bc10bc10 6.6. （1 1）设有文法）设有文法gs=(b,s,b,s, s gs=(b,s,b,s, s b|b|bbbb,b,bbsbs),),该文法所描述的语言是该文法所描述的语言是 l l（gs=bgs=b2i+1 2i+1|i 0 |i 0 （2 2）已知语言已知语言l=l=a a n n bbbb n n |n 1|n 1，则则 z z aabaab a a aabaab | b | b 上述文法可以产生语言上述文法可以产生语言l l。 （3 3）设有文法设有文法gigi： ii1 | i0 | ii1 | i0 | ic ic | a | b | c | a | b | c 该文法的该文法的句子句子有有 。 ab0 ab0 a0c01 a0c01 aaa aaa bc10bc10 7. 7. 设有文法设有文法gsgs： sese eeaaaa | | bb bb aacaca|d|d bbcbcb|d|d 构造其构造其lr(0)lr(0)分析表并利用分析分析表并利用分析 表判断表判断acccdacccd是否为文法是否为文法gsgs的句的句 子。子。 7. 7. 设有文法设有文法gsgs： sese eeaaaa | | bb bb aacaca|d|d bbcbcb|d|d 构造其构造其lr(0)lr(0)分析表并利用分析表判断分析表并利用分析表判断acccdacccd是否为是否为 文法文法gsgs的句子。的句子。 解解： （1 1）识别活前缀的自动机）识别活前缀的自动机 （2 2）lrlr分析表分析表 （3 3）lrlr分析过程分析过程即即判断判断 acccdacccd是否为文法是否为文法gsgs的句子的句子 8 .8 .在一个移入在一个移入- -规约的分析中采用规约的分析中采用 以下的语法制导的翻译模式，在按以下的语法制导的翻译模式，在按 一产生式规约时，立即执行括号中一产生式规约时，立即执行括号中 的动作。的动作。 a a ab print “0” a a c print “” b ab print “2” 当分析器的输入为aacbb时，打印 的字符串是什么？ 分析器分析器输 入为aacbb， 打印的字符打印的字符 为为 1202012020 b b b b c c a a a a a ab b a a a a b b a a ab print “0” a a c print “” b ab print “2” 9. 9. （1 1）表达式）表达式a*b-c-d$e$f-g-h*ia*b-c-d$e$f-g-h*i中中 ，运算符的优先级，运算符的优先级由高到低由高到低依次依次 为为- -、* *、$ $，且均，且均右结合右结合，且相应，且相应 的后缀式为的后缀式为_。 （2 2）表达式）表达式- -a+b*c+d+(e*f)/d*ea+b*c+d+(e*f)/d*e, , 如果运算符的优先级如果运算符的优先级由高到低由高到低依依 次为次为- -、+ +、* *、/ /，且均，且均左结合左结合，则，则 其后缀式为其后缀式为_。 9. 9. （1 1）表达式）表达式a*b-c-d$e$f-g-h*ia*b-c-d$e$f-g-h*i中，运算符的中，运算符的 优先级由高到低依次为优先级由高到低依次为- -、* *、$ $，且相应的后，且相应的后 缀式为缀式为abcdabcd - - * - - *efghefgh - -i*$ - -i*$。 （2 2）表达式表达式- -a+b*c+d+(e*f)/d*ea+b*c+d+(e*f)/d*e，如果运如果运 算符的优先级由高到低依次为算符的优先级由高到低依次为- -、+ +、* *、/ /，且，且 均左结合，则其后缀式为均左结合，则其后缀式为 a-b+a-b+cdcd+ +efef*+*de*/*+*de*/。 10.10.试写出算术表达式试写出算术表达式 a+b*c-(c*b+a-e)/(b*c+d)a+b*c-(c*b+a-e)/(b*c+d) 优化后的四元式序列。优化后的四元式序列。 11.11.目标代码目标代码 写出下列表达式的目标代码写出下列表达式的目标代码 t := c*t := c*（a+ba+b）+ +（a+ba+b） c := a+bc := a+b a :=a :=（c*dc*d）+ +（e-fe-f） 写出下列表达式的目标代写出下列表达式的目标代 码码 t t := := c*c*（a+ba+b）+ +（a+ba+b ） c := a+bc := a+b a :=a :=（c*dc*d）+ +（e-fe-f） 解答：解答： loadloada,r1a,r1 addaddb,r1b,r1 load load c,r2c,r2 mult mult r1,r2r1,r2 add add r1,r2r1,r2 store store g,r2g,r2 loadloade,r2e,r2 sub sub f,r2f,r2 storestorec,r1c,r1 mult mult d,r1d,r1 add add r2,r1r2,r1 store store a,r2a,r2 编译器设计方案编译器设计方案 c c 惯用的词法惯用的词法 c c 语言的语言的tiny machine tiny machine 运行时环境运行时环境 c c 的语法和语义的语法和语义 使用使用c c 和和t m t m 的编程设计的编程设计 c c 的程序例子的程序例子 这里定义了一个编程语言称作这里定义了一个编程语言称作c c m i n u s m i n u s ( (或简称或简称为为c c ) )，这是一种适合编译器设计方案这是一种适合编译器设计方案 的语言，它比的语言，它比t i n y t i n y 语言更复杂，包括函数和语言更复杂，包括函数和 数组。本质上它数组。本质上它是是c c 的一个子集，