9. （1）表达式a*b-c-d$e$f-g-h*I中，运算符 表达式a*b- d$e$f- h*I中 的优先级由高到低依次为的优先级由高到低依次为-、*、$，且相应 的后缀式为abcd
- - *efgh - -I*$$。
（2）表达式-a+b*c+d+(e*f)/d*e，如果运算 表达式-a+b*c+d+(e*f)/d*e， 符的优先级由高到低依次为符的优先级由高到低依次为-、+、*、/，且 均左结合， 均左结合，则其后缀式为
5.有文法G[E]：E T|E+T|E-T 5.有文法 有文法G[E]： T|E+T|ET F|T*F|T/F F i/(E) 请判断(E+T)*i+F是 的一句型吗？ 请判断(E+T)*i+F是G的一句型吗？ 如果是，请画出它的推导的语法树。 如果是，请画出它的推导的语法树。 并写出语法树的短语、简单短语、 并写出语法树的短语、简单短语、 句柄。 句柄。
a-b+cd+ef*+*de*/。
10.试写出算术表达式 10.试写出算术表达式 a+b*c-(c*b+aa+b*c-(c*b+a-e)/(b*c+d) 优化后的四元式序列。 优化后的四元式序列。
11.目标代码 11.目标代码 写出下列表达式的目标代码 T := C*（A+B）+（A+B） C*（A+B） A+B） C := A+B A :=（C*D）+（E-F） :=（C*D）
7. 设有文法G[S]： 设有文法G[S]： S→E E→Aa | bB A→cA|d B→cB|d 构造其LR(0)分析表并利用分析表判断 分析表并利用分析表判断acccd是否为 构造其LR(0)分析表并利用分析表判断acccd是否为 文法G[S]的句子。 文法G[S]的句子。 的句子
解： （1）识别活前缀的自动机 LR分析表 （2）LR分析表 LR分析过程 分析过程——即判断acccd是 （3）LR分析过程——即判断acccd是 否为文法G[S]的句子 否为文法G[S]的句子
E,R2 F,R2 C,R1 D,R1 R2,R1 A,R2
编译器设计方案
• C －惯用的词法 • C －语言的Tiny Machine 运行时环境 语言的Tiny • C －的语法和语义 • 使用C －和T M 的编程设计 使用C • C －的程序例子 这里定义了一个编程语言称作C 这里定义了一个编程语言称作C －M i n u s (或简称为C －)，这是一种适合编译器设计方案 或简称为C 的语言，它比T 语言更复杂， 的语言，它比T I N Y 语言更复杂，包括函数和 数组。本质上它是C 的一个子集， 数组。本质上它是C 的一个子集，但省去了一 些重要的部分，因此得名。 些重要的部分，因此得名。
Z → aAb A → aAb | b
上述文法可以产生语言L 上述文法可以产生语言L。 设有文法G[I]： （3）设有文法G[I]： I→I1 | I0 | Ic | a | b | c 该文法的句子有 ②③④ 。 该文法的句子 句子有 ①ab0 ②a0c01 ③aaa ④bc10
7. 设有文法G[S]： 设有文法G[S]： S→E E→Aa | bB A→cA|d B→cB|d 构造其LR(0)分析表并利用分析 构造其LR(0)分析表并利用分析 表判断acccd是否为文法 是否为文法G[S]的句 表判断acccd是否为文法G[S]的句 子。
• 语言惯用的词法(包括语言标记的描 语言惯用的词法( 述) • 每个语言构造的B N F 描述 每个语言构造的B • 相关语义的英语描述 • C －的两个示例程序 • C －的一个Tiny Machine 运行时环 的一个Tiny 境 • C －和T M 的编程设计方案
8 .在一个移入-规约的分析中采用 .在一个移入 在一个移入以下的语法制导的翻译模式， 以下的语法制导的翻译模式，在按 一产生式规约时， 一产生式规约时，立即执行括号中 的动作。 的动作。 A → aB {print “0”} 0 } A → c {print “”} } B → Ab {print “2”} 2 } 当分析器的输入为aacbb aacbb时 当分析器的输入为aacbb时，打印 的字符串是什么？ 的字符串是什么？
编译程序总复习——例题 编译程序总复习——例题
1. 编译程序的功能和组织结构 2. 编译和解释程序 3. 正则表达式 4. NFA → DFA → DFA 最小化 5. 句型→推导的语法树→短语→简单短语→ 句型→推导的语法树→短语→简单短语→ 句柄
6.文法 6.文法←→语言←→句子 文法← 语言← 7.语法分析 7.语法分析——自顶向下和自底向上 语法分析——自顶向下和自底向上 LL法 LR法 （LL法、 LR法） 8.语法制导翻译 8.语法制导翻译 9.中间代码 9.中间代码 10.中间代码优化 10.中间代码优化 11.目标代码 11.目标代码
6. 设有文法G[S]=({b},{S,B},S, （1）设有文法G[S]=({b},{S,B},S, {S →b|bB,B→bS}),该文法所描述的语言是 →b|bB,B→bS}),该文法所描述的语言是 2i+1|i ≥0} L（G[S]={b （2）已知语言L={anbbn|n ≥1}，则 已知语言L={a ≥1}，
1 . 编译程序的功能和组织结构
表 处 理 前 端 中
源 程 序
词 法 分 析
语 法 目 端 间 标 代 代 码 码 优 生 化 成
目 标 程 序
错 误 处 理
2. 编译和解释程序
源 程 序 编 译 程 序
初始数据
目标程序
计 算 结 果
源程序
初始数据
解: [(a|b)(a|b)*] ([(a|b)(a|b)*])*
4.请构造与正则式R=(a*b)*ba(a|b)* 4.请构造与正则式 请构造与正则式R=(a*b)*ba(a|b)* 等价的状态最少的DFA（ 等价的状态最少的DFA（确定有限自 动机）。 动机）。
解： (1) NFA (2) NFA → DFA (3) DFA 最小化
解 释 程 序
计 算 结 果
解释程序和编译程序的区别
功能 解释 程序 编译 程序 源程序的一 执行系统 个执行系统 源程序的一 转换系统 个转换系统 工作结果 源程序的 执行结果 源程序的 目标代码 实现技术上 执行中间代码 把中间代码转 换成目标程序
解释程序和编译程序的根本区别： 是否生成目标代码
3. 正则表达式
设文法G[A]: 设文法G[A]: A → [B B → X] | BA X → Xa | Xb | a | b 试求出文法G[A] G[A]产生的语言对应的 试求出文法G[A]产生的语言对应的 正则式。 正则式。
3. 设文法 设文法G[A]: A→[B B →X] | BA X →Xa | Xb | a | b 试求出文法G[A]产生的语言对应的正则式。 产生的语言对应的正则式。 试求出文法 产生的语言对应的正则式
有文法G[E]： 有文法G[E]： E T|E+T|E-T T|E+T|ET F|T*F|T/F F i/(E) (E+T)*i+F是 (E+T)*i+F是G的一句型 T 每棵子树的 叶组成短语 叶组成短语 (E+T)*i+F (E+T)*I (E+T) E+T i F
F ( E E +
E E T * F i ) T + T F
A a A a A c B B
⑤ b ④ ③
b
A → aB {print “0”} 0 } A → c {print “”} } B → Ab {print “2”} 2 }
②
①
分析器输入 分析器输入 aacbb， 为aacbb，打 印的字符为 12020
9. 表达式a*b- d$e$f- h*I中 （1）表达式a*b-c-d$e$f-g-h*I中， 运算符的优先级由高到低依次为由高到低依次为 运算符的优先级由高到低依次为-、 *、$，且均右结合，且相应的后 且均右结合 右结合， 缀式为______。 缀式为______。 表达式-a+b*c+d+(e*f)/d*e, （2）表达式-a+b*c+d+(e*f)/d*e, 如果运算符的优先级由高到低 由高到低依 如果运算符的优先级由高到低依 次为且均左结合 左结合， 次为-、+、*、/，且均左结合，则 其后缀式为______。 其后缀式为______。
每棵简单 子树的叶 组成简单 组成简单 短语 E+T i F
最左简单子树的叶组成句柄 最左简单子树的叶组成句柄 E+T
6.（ 6.（1）设有文法G[S]=({b},{S,B},S, 设有文法G[S]=({b},{S,B},S, →b|bB,B→bS}), {S →b|bB,B→bS}),该文法所描述的 语言是_________。 语言是_________。 （2）已知语言L={anbbn|n ≥1}，则 已知语言L={a ≥1}， _______文法可以产生语言L 文法可以产生语言 _______文法可以产生语言L。 （3）设有文法G[I]： 设有文法G[I]： I→I1 | I0 | Ic | a | b | c 该文法的句子有 该文法的句子 句子有 ________ ①ab0 ②a0c01 ③aaa ④bc10
写出下列表达式的目标代码 T := C*（A+B）+（A+B） C*（A+B） A+B） C := A+B A :=（C*D）+（E-F） :=（C*D） 解答： 解答：
LOAD ADD LOAD MULT ADD STORE