当前位置：文档之家 › 第8章 中间代码与语法制导方法

第8章 中间代码与语法制导方法

  • 格式：pdf
  • 大小：4.55 MB
  • 文档页数：31

下载文档原格式

  / 31

合集下载

第8章 语法制导翻译和中间代码生成

第8章 语法制导翻译和中间代码生成

例8.2 描述说明语句中各种变量的类型信息的语义规则
产生式
DTL
语义规则
Lin:=T type
T int
T real
T type :=integer
T type :=real
L L1,id
L id
L1 in :=L in
addtype(id entry,L in) addtype(id entry,L in)
1） 2） 3） 4） 5） 6） 7） 8） 9） 10） 11） 12） 13） 14） 15）
r6 r4 r2 r6 r4
r6 r3 r1 接受
016975 01697(10) 169 01
—2—3— — —2—3—5 —2—(15) -17
#E+T*5 #E+T*F #E+T #E
2+3*5# +3*5# +3*5# +3*5# +3*5# 3*5# *5# *5# *5# 5# # # # #
自下而上的。在用某一产生式进行归约的同时就
执行相应的语义动作，在分析出一个句子时，这
个句子的“值”也就同时产生了，例如输入串是 3*5+4。
L
E.val=19 E.val=15
+
T.val=4 F.val=4 F.val=5 digit.lexval=4 digit.lexval=5
T.val=15
8.3 中间代码形式
所谓“中间代码”是一种结构简单、含义明 确的记号系统，这种记号系统可以设计为多种多 样的形式，重要的设计原则为两点：一是容易生 成；二是容易将它翻译成目标代码。编译程序所 使用的中间代码有多种形式。 常见的有逆波兰记号、三元式、四元式和树 形表示。

第8章语法制导翻译与中间代码生成ppt课件

第8章语法制导翻译与中间代码生成ppt课件
E.val=2 + E.val=4 n.lex=2 ( E.val=4 )
E.val=3 + E.val=1 n.lex=3 n.lex=1
例8.1 一个简单台式计算器的定义 综合属性val
产生 式
LE
E E1+T
ET T T1 * F TF
F (E) F digit
语 义 规 那么 Print(E.val)
r1 = [fp - 4] r2 = [r1 + 2] r3 = [fp - 8] r4 = r3 * 20 r5 = r4 + r2 r6 = 4 * r5 r7 = fp – 216 f1 = [r7 + r6]
8.3.1 逆波兰式
运算符跟在一切运算对象的后面的表 示法写出的式子称为后缀法或逆波兰 法。
#
.
a.
(b+c/d)#
* #
.
a.
b+c/d)#
( * #
.
ab.
+c/d)#
( * #
.
ab.
c/d)#
+ ( * #
.
abc.
/d)#
+ ( * #
.
abc.
d)#
/ + ( * / + ( * #
.
abcd/.
)#
+ ( * #
.
abcd/+.
)#
( * #
〔3〕一致性检查。在很多场所要求对象只能被 定义一次。例如Pascal言语规定同一标识符在一 个分程序中只能被阐明一次，同一case语句的标 号不能一样，枚举类型的元素不能反复出现等等。
〔4〕上下文相关性检查。比如，变量名字必 需先声明后援用；

语法制导翻译和中间代码生成

语法制导翻译和中间代码生成

A ∨ B→if A then true else B A ∧B→if A then B else false ┐ A →if A then false else true
这种翻译法涉及到如何翻译if-thenelse的问题，将在下面具体讨论。
33
控制语ห้องสมุดไป่ตู้中布尔表达式的翻译
if E then S1 else S2,其中E为布尔式
第8章 语法制导翻译和中间代码生成
经过词法分析、语法分析后，源程序 在静态结构上的正确性得到了保证，编译 程序接着要对源程序进行静态语义检查和 翻译。 语义检查：类型检查、控制流检查、 一致性检查等。 翻译：源程序→中间代码
1
本章主要内容
1. 属性文法 2. 语法制导翻译概念 3. 中间代码的几种形式 4. 几个语句的翻译：如赋值语句、条件语 句等。
26
翻译 a:= -b+c*d
Ｓ
t1:=uminus b t2:=c*d t3:=t1+t2
a
:=
Ｅ1
Ｅ
＋ Ｅ2 Ｅ 21 c ＊
a:=t3
－
Ｅ 11 b
Ｅ 22 d
27
类型转换
如：X := Y + I * J，X,Y为实型，I,J为整型， 则相应的四元式序列应为： – (*i , I , J , T1 ) – ( itr , T1 , _ , T2 ) – ( +r , Y , T2 , T3 ) – ( := , T3 , _ , X )
23
四元式
1. 四元式对中间结果的引用必须通过 给定的名字，而三元式是通过产生中间结 果的三元式编号。四元式之间的联系是通 过临时变量实现的。 2. 四元式出现顺序与原表达式计算顺 序一致。(同三元式)

第八章 语法制导翻译和中间代码生成

第八章 语法制导翻译和中间代码生成

目标代码
5
语义分析
语义分析的任务：在词法分析和语法分析的基础上，
盛 威 网 ： 专 业 的 计 算 机 学 习 网 站
分析所写源程序的含义，在理解含义的基础上为生成 相应的目标代码作好准备或直接生成目标代码。 1）静态语义检查 例：类型检查、运算、维数、越界 2）语义翻译（具体的动作） 例：语句的翻译（中间代码或目标代码生成）
16
简化定义
对每个产生式，设属性定义性出现的集合为
盛 威 网 ： 专 业 的 计 算 机 学 习 网 站
若Xi是产生式左部非终结符（即i=0），则称属性 Xi.a是综合属性（Synthesized Attributes） 若Xi出现在产生式的右部（即i≠0 ），则称Xi.a是 继承属性（Inherited Attributes）
2
教学内容
第一节
盛 威 网 ： 专 业 的 计 算 机 学 习 网 站
属性文法 语法制导翻译概论 中间代码的形式 简单赋值语句的翻译 布尔表达式的翻译 控制语句的翻译 说明语句的翻译 数组和结构的翻译
3
第二节 第三节 第四节 第五节 第六节 第七节 第八节
盛 威 网 ： 专 业 的 计 算 机 学 习 网 站
2.组成
语法树上的每个节点的所有属性在依赖图上各有 一个节点，如果属性y依赖于属性x，那么从x的节点 到y的节点有一条有向边。 【注】如果语法树一节点的属性y依赖某个节点的属 性x，那么属性y的语义产生式的计算必须在属性x的 语义产生式的计算之后进行。 24
盛 威 网 ： 专 业 的 计 算 机 学 习 网 站
13
盛 威 网 ： 专 业 的 计 算 机 学 习 网 站
3、文法规则number→number digit ,表明文法的个 数不止一个。我们必须表示出这个文法规则左边符 号的值和右边符号的值之间的关系。通过使用下标 进行区分，将文法写成如下形式： number1→number2 digit

编译原理,清华大学,第2版_第8章 语法制导翻译和中间代码生成

编译原理,清华大学,第2版_第8章 语法制导翻译和中间代码生成

将if-then-else看作一个完整的操作符，则e、x和 y 分别是三个操作数，这显然是一个三元运算。根据后缀式 的特点，它的后缀式可以写为：
exy if-then-else(记为: exy￥) 但是，这样的表示有个弱点。按照算法的计算次序，e、 x和y均需计算，而实际上，根据条件e的取值，计算x则不 计算y，计算y则不计算x。
一、逆波兰表示 典型特征是操作数在前，操作符紧跟其后。 特点:由于操作符紧跟操作数之后，因此只要知道操作 符有几个操作数，每一步的运算就可以确定。
1、 表达式的表示：
例：a+b 例：-a+b*c 例： (a+b)*c ab+ a@bc*+ ab+c* <左部><表达式的逆波兰式> ::=
2、 赋值语句的逆波兰表示：
E → E1 + E2
E → E1 * E2 E → (E1) E → num
E.val := E1.val + E2.val;
val[top] := val[top]+val[top+2];
E.val := E1.val * E2.val; E.val := E1.val; E.val := num.lexval;
第八章 语法制导翻译和中间代码生成
• 教学要求：本章介绍编译程序的第三个阶段语 义分析及中间代码生成的设计原理和实现方法，
要求理解语法制导翻译、语义动作的基本概念；
掌握语义规则和中间代码的表示形式。 • 教学重点：语义规则，中间代码的表示形式， 自下而上分析制导翻译概述。
语义处理功能： • 1、静态语义审查：验证语法结构合理 的程序是否真正有意义。 • 2、解释执行动态语义、生成代码：执 行真正的翻译（生成中间代码或目标代 码）。

编译原理-语法制导翻译和中间代码生成

编译原理-语法制导翻译和中间代码生成

例：类型、运算、维数、越界
–语义处理：
执行真正的翻译，生成程序的中间代码目标代码。
–例：变量的存储分配
–例：表达式的求值
–例：语句的翻译（中间代码的生成）
3
8.1 属性文法
• 语义分析的描述 –描述语法规则的同时，编写相应的语义 动作和计算顺序
• 语义的形式化描述 –操作语义学、公理语义学、指称语义学
例8-3 3*5+4 的 语法树与属性计算
T.val=3 F.val=3 digit.lexval=3
E.val=15 T.val=15
＊
Ｌ Print(19)
E.val=19 ＋
T.val=4
F.val=4
F.val=5
digit.lexval=4
dgit.lexval=5
19
T.type=real
• 继承属性 – 从其兄弟结点和父结点的属性值计算出来的 – 如：L.in
• 固有属性（单词属性）
17
属性的计算
• 语法制导翻译：作语法分析，构造语法树，然 后在树的每个结点上添加相应的语义规则
• 综合属性 – 自底向上按照语义规则来计算各结点的综合 属性值
• 继承属性 –需要探讨计算次序
18
文法
E→ -E1 E.p:= mknode('-', 0, E1.p)
E→ (E1) E.p:= E1.p E→ id E.p:= mkleaf(id, id.entry) E→ num E.p:=mkleaf(num,num.val)
37
生成后缀式的属性文法
产生式
语义规则
S→id:=E Print( || E.code || “:=”)

第八章语法制导翻译和中间代码生成

但文法开始符号没有继承属性。 终结符只有综合属性。
继承的和综合的属性
属性文法中，对应每一个产生式 A 都有 一套与之相关联的语义规则，每条规则的形 式为：b:=f(c1,c2,……,ck) 其中：f是一个函数，b和c1,c2,……,ck是该 产生式文法符号的属性。
(1)如果b是A的一个属性， c1,c2,……,ck是产 生式右部文法符号的属性或A的其它属性， 则称b是A的综合属性。
To relate each applied occurrence of an identifier in the source program to the corresponding declaration.
语义学
语义形式化、语义建模 文法模型—属性文法 命令式或操作式模型—操作语义学 公理式模型—公理语义学 应用式模型—指称语义学 目前在实际应用中比较流行的语义描述和语
语义规则
D TL T int T real L L1,id
L.in:=T.type T.type=integer T.type:=real L1.in:=L.in addtype(id.entry,L.in)
L id
addtype(id.entry,L.in)
继承属性
一个结点的继承
Real id1,id2,id3
属性文法
使用 N.t 的形式表示与非终结符N相连的属 性t。
T.t的值为int或bool。 与非终结符E的产生式相连的断言表明：两
个T的属性必须相同。
继承的和综合的属性
属性通常分为两类：综合属性和继承属性 综合属性用于“自下而上”传递信息， 继承属性用于“自上而下”传递信息。 非终结符既可有综合属性也可有继承属性，
语义规则 Print(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.val F.val:=E.val F.val:=digit.lexval

第八章_3语法制导翻译和中间代码生成-中间代码生成


8.5
控制语句中布尔表达式的翻译
1
控制语句 S→ if E then S E 的代码 E.true: S 1 的代码 goto out S 2 的代码 out:
else S 2 E.true E.false
E.false:
. 把条件转移的布尔表达式翻译成仅含 把条件转移的布尔表达式翻译成仅含 和无条件转 条件真转 (jrop,B,C,L) 和无条件 转 (jump,_,_,L)的四元式 E =a rop b ⇒ if a rop b goto E.true goto E.false 如 ：a<b or c<d and e<f 翻译成如下四元式： 可 翻译成如下四元式： (1) if a<b goto E.true (2) goto (3) (3) if c<d goto (5) (4) goto E.false (5) if e<f goto E.true (6) goto E.false
• 高级：最接近高级语言，保留了大部分源语言 的结构。 • 中级：介于二者之间，与源语言和机器语言都 有一定差异。 • 低级：最接近机器语言，能够反映目标机的系 统结构，因而经常依赖于目标机。
不同层次的中间代码
源语言 高级语言） （高级语言）
float a[10][20]; a[i][j+2];
中间代码 高级） （高级）
逆波兰 : 四元式 : ABCD-*+ECD–N^/+ (1) ( C D T1 D N T5 T1 ) T2) T4) T5) T6) T7)
(2) ( * B (3) ( + A (4) ( (6) ( / C E (5) ( ^ T4
T2 T3)

第08章语法制导翻译和中间代码生成

• 如：说明语句的属性文法
17
翻译模式
◆定义
翻译模式是语法制导定义的一种便于翻译的书写 形式。其中属性与文法符号相对应，语义规则或 语义动作用花括号｛ ｝括起来，可被插入到产生 式右部的任何合适的位置上。
这是一种语法分析和语义动作交错的表示法，他 表达在按深度优先遍历分析树的过程中何时执行 语义动作。
–将值 val 作为表达式 E、项 T 和因子 F 的属性
• 用语义规则描述表达式的求值
7
属性文法（语法制导定义）
•L → E
print( E.val )
• E → E1 + T E.val := E1.val + T.val
•E → T
E.val := T.val
• T → T1 * F T.val := T1.val * F.val
33
四元式（三地址代码）
一般形式 x := y op z
–其中 x, y, z 为变量名、常数或编译 产生的临时变量
–四元式（op, x, y, z）
种类：x := y op z
双目运算
x := op y
单目运算
x := y
赋值
if x relop y goto
条件转移
34
a∶=b*c+b*d的四元式表示
a Print(A.in) a Print(A.in)
24
如果计算A1.in和A2.in的值的动作分别被嵌入在产
生式SA1A2 的右部A1和A2之前，而不是后面，
那么A.in在执行Print（A.in）时已有定义。
S {A1in:=1 }A1{A2 in:=2} A2
A a
{ print(A in) }

编译第8章

–是一种接近形式化的语义描述方法 –长于描述静态语义、短于描述动态语义 –每个语法符号有相应的属性符号 –每个产生式有相应的计算属性的规则：
• 属性变量=属性表达式
1、属性文法定义
属性文法(attribute grammar)是一个三元 组:A=(G,V,F),其中 G:是一个上下文无关文法 V:有穷的属性集,每个属性与文法的一个终结符或非 终结符相连,这些属性代表与文法符号相关信息， 如它的类型、值、代码序列、符号表内容等等 .属 性与变量一样，可以进行计算和传递。属性加工 的过程即是语义处理的过程。 F:关于属性的属性断言或一组属性的计算规则(称为 语义规则) . 断言或语义规则与一个产生式相联,只 引用该产生式左端或右端的终结符或非终结符相 联的属性.
addtype
id3
addtype
例5-4：real id1,id2,id3 的分析树和属性计算
8.3 中间代码的形式
何谓中间代码： 源程序的一种内部表示，不依赖目标机的 结构，易于机械生成目标代码的中间表示。 为什麽要此阶段 逻辑结构清楚； 利于不同目标机上实现同一种语言； 利于进行与机器无关的优化； 这些内部形式也能用于解释；
• 语义处理
–例：变量的存储分配 –例：表达式的求值 –例：语句的翻译（中间代码的生成）
• 总目标：生成等价的中间代码
语义处理方法
• 对应每一个产生式编制一个语义子程序， 当一个产生式获得匹配时，调用相应的 语义子程序实现语义检查与翻译。 • 在产生式的右部的适当位置，插入相应 的语义动作，按照分析的进程，执行遇 到的语义动作。
8)若把语义子程序改成产生某种中间代 码的动作，就能在语法分析制导下，随 着分析的进展逐步生成中间代码。 9)若把语义子程序改成产生某种机器的 汇编语言指令，就能随着分析的进展逐 步生成某机器的汇编语言代码。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

例： Pos(A+B*C)＝Pos(A)‖Pos(B*C)‖+＝ABC*+ Pos(A*B+C)＝Pos(A*B)‖Pos(C)‖+＝AB*C+
13年5月12日星期日
表达式的逆波兰式及其语法制导生成
由于上述文法G（E）共包含8个产生式，因此在设 计翻译程序时需定义8个语义子程序。 调用对应语义子程序时，已生成相应语法对象的逆 波兰式，操作时应按照先调用后归约的顺序进行，语义 子程序要完成的工作只是将各语法对象对应的逆波兰式 以及文法终结符按照产生式对应的逆波兰式定义链接起 来生成新的逆波兰式即可。
第八章 中间代码与语法制导方法
1. 2. 3. 4. 5. 中间代码与语法制导方法 表达式的逆波兰式及其语法制导生成 表达式的三元式和语法制导生成 表达式的四元式及其语法制导生成 语句的中间代码及其语法制导生成
13年5月12日星期日
编译中的语义处理包含两方面内容： 1．审查每个语法结构的静态语义，即验证语 法结构合法的程序是否真正有意义，称为静态语义 分析或静态审查； 2．如果静态语义正确，语义处理则要执行真 正的翻译，即要么生成程序的一种中间表示形式 （中间代码），要么生成实际的目标代码。
13年5月12日星期日
表达式的逆波兰式及其语法制导生成
根据上述定义，可将文法G（E）各产生式对应的逆波兰式定义写出，如下表： 序号 1 2 3 4 5 6 7 8 产生式 E→T E→E+T E→E-T T→F T→T*F T→T/F F →i F→(E) 中缀表达式 E＝T E＝E(1)+T E＝E(1)-T T＝F T＝T(1)*F T＝T(1)/F F＝i F＝(E) 逆波兰式 Pos(E)=Pos(T) Pos(E)=Pos(E(1))‖Pos(T)‖+ Pos(E)=Pos(E(1))‖Pos(T)‖Pos(T)=Pos(F) Pos(T)=Pos(T(1))‖Pos(F)‖* Pos(T)=Pos(T(1))‖Pos(F)‖/ Pos(F)=i Pos(F)=Pos(E)
13年5月12日星期日
中间代码、语法制导方法
该文法中，可用B.Vers表示串B的逆串，则： G（B）： 1．B→a B.Vers=a 2．B→b B.Vers=b 3．B(1)→B(2)a B(1).Vers=a^B(2).Vers 4．B(1)→B(2)b B(1).Vers=b^B(2).Vers 按照上述规则求输入串的逆串计算过程如图所 示： 上述过程首先通过语法分析建立句子abb对应的 语法树，然后从叶子结点向树根逐步求每个非终结 符对应的逆串B.Vers，最后树根对应的逆串B.Vers 记为整个句子的逆串。
13年5月12日星期日
表达式的三元式及其语法制导生成
1. 三元式
（1）定义： 三元式的一般形式是： i：（ω，Opr1，Opr2） 其中：i为三元式编号；ω为运算符部分；Opr1和Opr2为 运算对象部分。 运算对象部分可以是变量名或三元式编号，如果是三元式 编号j，则表示该运算分量的值是对应三元式j的计算结果。 Tri（E）：表示表达式E对应的三元式序列； Last（E）：表示表达式E对应三元式序列中最后三元式编 号，如果E为一个变量x，则Last（E）＝x。法制导生成
如果设置一个逆波兰式区，将生成的逆波兰式依次放在该区中，便不需 进行逆波兰式之间的捻接错作，文法G（E）各语义子程序便更加简单，如 下表： 序号 1 2 3 4 5 6 7 8 产生式 E→T E→E+T E→E-T T→F T→T*F T→T/F F →i F→(E) 语义子程序 空 Write（+） Write（-） 空 Write（*） Write（/） Write（id） 空
13年5月12日星期日
表达式的逆波兰式及其语法制导生成
逆波兰式又称为后缀表达式，例如A*B的逆波兰式为AB*，A +B*C的逆波兰式为ABC*+。 逆波兰式主要用于表达式的中间代码生成，仍考虑上节给出 的文法G（E）： 1．E→T 2．E→E+T 3．E→E-T 4．T→F 5．T→T*F 6．T→T/F 7．F→i 8．F→(E) 这里用Pos（E）表示中缀表达式E对应的逆波兰式，因此，当 E＝E1ωT时，有： Pos(E)=Pos(E1)‖Pos(T)‖ω 其中，运算“‖”定义为串的“捻接”。
13年5月12日星期日
中间代码、语法制导方法
例：考虑文法G（B）： 1．B→a 2．B→b 3．B→Ba 4．B→Bb 设计一个翻译程序，将L（G(B)）的任一符号串翻译成其逆 串，如将abb翻译成bba。 分析： 语法制导翻译方法是严格地根据文法产生式导出翻译程序的一 种翻译方法。实现时应对每个产生式设计相应子程序（称为语义子 程序）用于实现自己那部分的翻译工作。 翻译过程中，当一个产生式被用于匹配（自顶向下）或归约 （自底向上）时，调用相应的语义子程序进行翻译。
13年5月12日星期日
表达式的三元式及其语法制导生成
算法：
序号 1 2 3 4 5 6 7 8 产生式 E→T E→E+T E→E-T T→F T→T*F T→T/F F→i F→(E) 空 GenTrip（+）; GenTrip（-）; 空 GenTrip（*）; GenTrip（/）; Sem[s]=id;s++; 空 语义子程序
A A A A A AB AB AB AB AB ABC ABC ABC+ ABC+ ABC+ ABC+* ABC+*
13年5月12日星期日
表达式的逆波兰式及其语法制导生成
小结： 理解语法制导翻译方法的基本概念，掌握表达 式的逆波兰式表示法及其语法制导生成方法，能够写 出给定表达式的逆波兰式翻译过程。
13年5月12日星期日
表达式的三元式及其语法制导生成
（3）语法制导翻译算法 定义： 语义栈（记为Sem）：用于存放运算对象信息，即变量标识符的地址或 三元式编号；堆栈指针为s，栈顶元素为Sem[s-1]。 语法栈（记为Syn）：用于进行语法分析；堆栈指针为k，栈顶元素为 Syn[k-1]。 三元式区（记为Trip）：用于存放生成的三元式序列；指针为j，Trip[j] 为下一个生成的三元式应该写入的空位置。 引入生成三元式的函数： Void GenTrip(ω) { Trip[j]=(ω,Sem[s-2],Sem[s-1]); Sem[s-2]=j; j++; s--; }
13年5月12日星期日
表达式四元式元式及其语法制导生成
2. 中缀式及其四元式定义
序号 1 产生式 E→T 中缀表达式 E＝T Four（T） Res(E)=Res(T) Four(E(1)) Four(T) (+，Res(E(1))，Res(T)，Temp) Res(E)=Temp Four(E(1)) Four(T) (-，Res(E(1))，Res(T)，Temp) Res(E)=Temp Four（F） Res(T)=Res(F) Four(T(1)) Four(F) (*，Res(T(1))，Res(F)，Temp) Res(T)=Temp Four(T(1)) Four(F) (/，Res(T(1))，Res(F)，Temp) Res(T)=Temp 空 Res(E)=id Four（F） Res(F)=Res(E) 四元式
13年5月12日星期日
中间代码、语法制导方法
定义 中间代码：又称为中间语言，是复杂性介于源程序和机器语言 之间的一种表示形式。 常见的中间代码形式有逆波兰式、三元式、四元式、树等。 翻译方法分类 1．语法制导翻译 语法制导翻译方法是一种形式化方法，它严格依赖于产生式结 构，产生式发生变化，语法制导翻译程序也要随之发生变化，否则便 不能正常工作。 2．非语法制导翻译 非语法制导翻译方法不依赖于产生式，而只依赖于输入。无论 产生式（语法）怎么变化，只要输入不变，该翻译程序照样可以正常 工作。 注：语法可以任意变化，但应保证语法所生成的语言不变。
注：文法中的符号i是一个语法符号，是标识符的抽象表示，并不表示 具体的标识符，因此语义子程序在翻译时不能将i写入逆波兰式，而应根 据到Token表中查找其具体信息，这里用id表示标识符自身。
13年5月12日星期日
表达式的逆波兰式及其语法制导生成
例：A*（B+C）的翻译过程：
序号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 语法栈 # #A #F #T #T* #T*( #T*(B #T*(F #T*(T #T*(E #T*(E+ #T*(E+C #T*(E+F #T*(E+T #T*(E #T*(E) #T*F #T #E 输入流 A*(B+C)# *(B+C)# *(B+C)# *(B+C)# (B+C)# B+C)# +C)# +C)# +C)# +C)# C)# )# )# )# )# # # # # 动作 移进 归约7 归约4 移进 移进 移进 归约7 归约4 归约1 移进 移进 归约7 归约4 归约2 移进 归约8 归约5 归约1 完成 逆波兰式区
13年5月12日星期日
表达式的三元式及其语法制导生成
（2）中缀式及其三元式定义 文法G（E）的中缀式及其三元式定义如下：
序号 1 2 3 4 5 6 7 8 产生式 E→T E→E+T E→E-T T→F T→T*F T→T/F F→i F→(E) 中缀表达式 E＝T E＝E(1)+T E＝E(1)-T T＝F T＝T(1)*F T＝T(1)/F F＝i F＝(E) Tri(E)=Tri(T) Last(E)=Last(T) Tri(E)=Tri(E(1))ǁ‖Tri(T)ǁ‖i:(+,Last(E(1)),Last(T)) Last(E)=i (i是新三元式编号) Tri(E)=Tri(E(1))ǁ‖Tri(T)ǁ‖i:(-,Last(E(1)),Last(T)) Last(E)=i (i是新三元式编号) Tri(T)=Tri(F) Last(T)=Last(F) Tri(T)=Tri(T(1))ǁ‖Tri(F)ǁ‖i:(*,Last(T(1)),Last(F)) Last(T)=i (i是新三元式编号) Tri(T)=Tri(T(1))ǁ‖Tri(F)ǁ‖i:(/,Last(T(1)),Last(F)) Last(T)=i (i是新三元式编号) Tri(F)=空 Last(F)=id Tri(F)=Tri(E) Last(F)=Last(E) 逆波兰式