当前位置：文档之家 › 06第6章语法制导翻译技术概论

06第6章语法制导翻译技术概论

  • 格式：ppt
  • 大小：4.71 MB
  • 文档页数：78

下载文档原格式

  / 78

合集下载

第6章语法制导

第6章语法制导
• 方法
–编写说明语句的文法 编写说明语句的文法 –将类型信息作为类型描述 T 的属性 type 将类型信息作为类型描述 in。 和变量表 L 的属性 in。
• 目的
–分析说明语句 D，为变量指定类型 分析说明语句
13
addtype
addtype
addtype
例：real id1,id2,id3 的分析树和 属性计算 14
2
语义分析的任务
• 语义检查
–例：类型、运算、维数、越界 例 类型、运算、维数、
• 语义处理
–例：变量的存储分配 例 –例：表达式的求值 例 –例：语句的翻译（中间代码的生成） 例 语句的翻译（中间代码的生成）
• 总目标：生成等价的中间代码 总目标：
3
处理方法
• 对应每一个产生式编制一个语义子程序， 对应每一个产生式编制一个语义子程序， 当一个产生式获得匹配时， 当一个产生式获得匹配时，调用相应的语 义子程序实现语义检查与翻译。 义子程序实现语义检查与翻译。 • 在产生式的右部的适当位置，插入相应的 在产生式的右部的适当位置， 语义动作，按照分析的进程， 语义动作，按照分析的进程，执行遇到的 语义动作。 语义动作。
第六章
• • • • •
属性文法和语法制导翻译
语法制导翻译概述 属性文法 翻译模式 自顶向下翻译方法 自底向上翻译方法
1
6.1 语法制导翻译概述
• 语法制导翻译以属性文法为基础 • 语法结构具有规定的语义 • 在进行语法分析的同时，完成相应的语 在进行语法分析的同时， 义处理 • ？？？如何根据被识别出的语法成分进 ？？？如何根据被识别出的语法成分进 行语义处理
消除左递归后的翻译模式： 消除左递归后的翻译模式： E → T {R.i := T.val} R{E.val:=R.s} R → + T {R1 .i:=R.i+T.val} } R → - T {R1 .i:=R.i+T.val} } R → ε {R.s:=R.i} R T → num T → ( E )

语法制导翻译概括

语法制导翻译概括
一般来讲，对出现在产生式右边的继承属性和出现在
产生式左边的综合属性都必须提供一个计算规则，属性
计算规则中只能使用相应产生式的文法符号的属性，这
有利于产生式范围内“封装属性的依赖性。然而，出
现在产生式左边的继承属性和出现在产生式右边的综合
属性不由所给的产生式的属性计算规则进行计算，它们 由其它产生式的属性规则计算,由属性计算器的参数提 供。
• 则表达式(*)*e的四元式为：
•
(1) t1
•
(2) t21*c
•
(3) t32
•
(4) t43*e
•
(5) t54
• 同样要将算法语言翻译成相应的四元式， 也要将四元式扩充到其他运算符，如()表
示无条件转向第L条四元式。
6.1.4 汇编代码
汇编语言是依赖于机器的低级程序设计语 言，它是面向具体的计算机系统或相应 的计算机系列的，它和三元式相比有以 下优点：
逆波兰、四元式、三元式、树型
6.1.1 逆波兰记号（后缀式）
• 将运算对象写在前面，把运算符号写在后面
表达式
*c ()*c **d
逆波兰式
*+ * **
• 后缀式的计算机处理
• 后缀式的最大优点是易于计算机处理
• 处理过程：
• 从左到右扫描后缀式，每碰到运算对象就推进 栈；碰到运算符就从栈顶弹出相应目数的运算对象 施加运算，并把结果推进栈。最后的结果留在栈
2．b是 中的符号的一个继承属性并且c1， c2，…，是A或 中的任何文法符号的属性。
在两种情况下，都说 属性b依赖于属性c1，c2，…，。
要特别强调的是：
（1）终结符只有综合属性，它由词法分析器提供； （2）非终结符既可以有综合属性也可以有继承属性， 文法开始符号的所有继承属性作为属性计算前的初始值。

语义分析和语法制导翻译

语义分析和语法制导翻译
语义分析和语法制 导翻译
第六章 语义分析和语法 制导翻译
语义分析的任务：检查语义错误
类型检查：
运算数类型
一致性检查： 名字声明与引用
控制流检查： 转移目标
名字检查：
作用域
翻译的任务：建立等价的目标程序
生成中间语言的指令序列
名字绑定：
变量名、过程名
建立运行环境
6.1 属性文法
语义分析与语法制导翻译的描述方法
属性文法的定义：
Ａ＝（Ｇ，Ｖ，Ｆ）
Ｇ 是上下文无关文法 Ｖ 属性的有穷集 Ｆ 关于属性的断言和谓词
用法
针对语义，为文法符号设置属性
终结符使用单词的属性
为每个产生式设置语义规则
通过描述各属性的关系 将语义分析和翻译步骤定义为产生式的 断言和谓词
例6-1: 计算器的算法设计
需求：算术表达式的求值 设计：
属性的计算
构造语法分析树，填加响应的语义规则 综合属性
自底向上按照语义规则来计算各结点的综 合属性值
继承属性
需要探讨计算次序
例6-3：3*5+4 的
语法树与属性计算
Ｌ P rin t(1 9 )
E .v a l= 1 9
E .v a l= 1 5
＋
T .v a l= 4
T .v a l= 1 5
编制算术表达式的文法 引入属性表示语义信息
将值 val 作为表达式 E、项 T 和因子 F 的属性
用语义规则描述表达式的求值
属性文法（语法制导定义）
产生式 L→E
语义规则 print( E.val )
E → E1 + T E.val := E1.val + T.val
E→T

6-1-语义分析和语法制导翻译

6-1-语义分析和语法制导翻译
（Inherited Attributes）。
2022/2/4
7
属性文法的定义
定义6.3 属性文法AG是一个四元组：AG=(G,A,R,B), 其中, G是已简化的CFG;
A=∪X∈VA(X)是属性的有限集合;
R= ∪p∈PR(p)是属性定义规则的有限集;
B=∪p∈PB(p)是条件的有限集合，B(p)用于描述使R(p)有效 的条件；
1．每个文法符号和语义动作符X都有一个相关的有限属性集合A(X)，且每 个属性都有一个允许值的集合（属性的值域，可以是无限集）。
2．非终结符和动作符的属性可分为继承属性与综合属性两类。
3．继承属性的定义规则为：
①开始符号的继承属性具有指定的初始值；
②对于给定的产生式p:Y→X1X2…Xn∈P,Xi的继承属性值由p中其它符号 的属性值进行计算：Xi.a=f(Y.b, Xk1.ak1,…,Xkm.akm) i{k1,…,km}
2022/2/4
2
中间代码
中间代码生成：
–指把单词符号串形式的源程序转换为另一种等价的便于 代码优化处理和目标代码生成表示。
两个主要问题：
–如何描述语言的语义（语法制导翻译方法）； – 中间代码如何表示（逆波兰表示、三元式、四元式等）。
2022/2/4
3
语法制导翻译方法概述
语法制导翻译方法
– 在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的 语义子程序进行翻译（产生中间代码）的方法。
– 实质就是根据文法中每个产生式的语义，为其配备若干个语义子程序， 对所要完成的功能进行描述。
产生式语义：
– 由组成该产生式所有文法符号的语义决定。
语义：
– 文法符号X的语义信息，称之为语义属性或简称为属性。 – 可用形如X.ATTR的记号来表示文法符号X的相关语义属性。

语法制导翻译及属性文法-编译原理-06-(一)讲诉

语法制导翻译及属性文法-编译原理-06-(一)讲诉

5. S-属性定义(S-属性文法)
S-属性定义：仅包含综合属性的属性
文法（语法制导定义）
S-attributed S-attributed
Definition Grammar
如：算术表达式求值的属性文法
2018/11/19 25
非S-属性定义
D→T L
T→int
L.in := T.type
要解决的问题： 1. 纪录标识符的类型 2. 类型信息传递 方法：用T.type记录类 型信息，并传给L.in
14
例6-2 说明语句的属性文法
D→TL
T → int T → real L → L1,id L → id
L.in := T.type
T.type := ‘integer’ T.type := ‘real’ L1.in := L.in addtype( id.entry, L.in ) addtype( id.entry, L.in )
2018/11/19
F.val := E.val
F.val := digit.lexval lexval 是单词 digit 的属性
13
例6-2 说明语句的属性文法
说明语句的文法
D→TL T → int T → real L → L1,id L → id
2018/11/19
real operand, length, sum int add, sub, mult
是一种接近形式化的语义描述方法 长于描述静态语义、短于描述动态语义 每个语法符号有相应的属性符号 每个产生式有相应计算属性的规则
属性变量:=属性表达式
2018/11/19 8
属性文法举例
产生式 E → E1 + E2 属性（计算）规则/语义规则 E.val := E1.val + E2.val

最新六章语法制导翻译与属文法

最新六章语法制导翻译与属文法

2021/1/11
10
典型处理方法二
翻译模式
通过将属性与文法符号关联，并将语义规则插入到产生式 的右部来描述语言结构的翻译方案
在产生式的右部的适当位置，插入相应的语义动 作，按照分析的进程，执行遇到的语义动作
D → T { L.inh := T.type } L
T → int { T.type := integer }
这两种情况下，都说属性b依赖于属性c1，c2，…，ck
2021/1/11
14
例6.1 台式计算器的语法制导定义
产生式 LEn E E1+T E T T T1*F T F F (E) F digit
语义规则 print(Eval)(可看作是L的虚属性) Eval := E1val+Tval Eval := Tval Tval := T1val+Fval Tval := Fval Fval := Eval Fval := digitlexval
E→E1 + E2
E.val:=E1.val+E2.val
语法结构具有规定的语义
问题：如何根据被识别出的语法成分进行 语义处理？
亦即怎样将属性值的计算及翻译工作同产生式 相关联？
2021/1/11
9
典型处理方法一
语法制导定义
通过将属性与文法符号关联、将语义规则与产生 式关联来描述语言结构的翻译方案
2021/1/11
16
继承属性
当分析树的结构同源代码的抽象语法不“匹 配”时，继承属性将非常有用。下面的例子 可以说明怎样用继承属性来解决这种不匹配 问题，产生这种不匹配的原因是因为文法通 常是为语法分析而不是为翻译设计的。
例6.2

06-语法制导翻译技术市公开课特等奖市赛课微课一等奖PPT课件

第7页
自顶向下语法制导翻译有递归下降翻译和LL(1)翻译。
6.3.1 递归下降翻译
递归下降翻译器实现思绪与递归下降分析基本相同，要求也一样，即不能有左 递归，头符号集不能相交，只需在适当位置插入实现动作符号子程序。
比如，算术表示 因 为 文 法 中 存 在 左
式翻译文法以下： 递 归 ， 所 以 要 修 改
① <A>→@v a@w<B>@x c@y<D>@z
② <A>→b
③ <B>→c@r
④ <B>→a@m<A>
⑤ <D>→C<D>@n
⑥ <D>→@s b 第10页
假定动作符号动作是输出动作标识后面符号串,其翻译器分析表结构方 法与第四章介绍相同，只不过加入了动作符号。
比如，对上面翻译文法中产生式：
比如，对于符号串(a+b)*b
用输入文法推导输入序列(a+b)*c过程以下:
E =>T=>T*F=>F*F=>(E)*F=>(E+T)*F=>(T+T)*F=>(F+T)*F=>(a+T)*F
=>(a+F)*F=>(a+b)*F==>(a+b)*c
用翻译文法推导得到活动序列(a @a +b @b@+)*c @c@*过程以下:
被翻译符号串(即输入序列)，第二个元素是翻译成新符号串。当我们是按翻译文
法得到这种对偶时，则称为语法制导翻译。假如给出由输入符号和动作符号所组
成活动序列，经过从活动序列中删掉全部动作符号则可得到“输入序列，而从活

第06章 语法制导翻译技术


6.2 语法制导翻译
语法制导翻译：按翻译文法进行的翻译。 给定一输入符号串，根据翻译文法获得翻译该符号串 的动作序列，并执行该序列所规定的动作的过程。 例： 输入序列：a+b*c 活动序列：a@a+b@b*c@c@*@+ 动作序列：@a@b@c@*@+ 翻译结果：abc*+
17
6.2 语法制导翻译
11
例：符号串(a+b)*b
用输入文法推导：
E=>T =>T*F =>F*F =>(E)*F =>(E+T)*F =>(T+T)*F =>(F+T)*F =>(a+T)*F =>(a+F)*F =>(a+b)*F =>(a+b)*b T F ( E ) E T * F b
E
T F a
+
T
F b
12
翻译文法：
① A→@va@wB@xc@yD@z ③ B→c@r ⑤ D→cD@n
② A→b ④ B→a@mA ⑥ D→@sb
翻译文法的LL(1)分析表
符 号 输入符号 a
POP,PUSH(@zD@yc POP, PUSH(b) POP, PUSH(@rc) POP, PUSH(b@s) POP, PUSH(@nDc)
7
分别给出下列表达式的后缀表示
1. a+b*(c-d)
2. (a-b)*c+d 3. -a+b*(-c+d) 4. X:=-(a+b)/(c-d)-(a+b*c) 1. abcd-*+ 2. ab-c*d+
3. a-bc-d+*+

第6章 属性文法和语法制导翻译 (编译原理 陈火旺).


3
CH.6 属性文法和语法制导翻译
• 在分析-综合模式的编译器中,语义分析是分 析过程的最后一个步骤，只有在这一步才真 正开始考虑程序语言的意义，并着手把它们 翻译成某种中间代码。这一过程通常采用的 方法是属性文法和语法制导翻译方法。 • 语法制导翻译方法的基本思想是，根据翻译 的需要设置文法符号的属性，用属性描述语 法结构的语义，用属性的计算完成翻译。 • 属性文法使文法符号属性值的计算和产生式 相联系。随着语法分析的进行，执行属性值 的计算，从而完成语义分析和翻译的任务。
37
抽象语法树：简例
• 例，为下面文法的句子 a-4+c 建立抽象语法树。 E E+T | E－T | T T (E) T id | num • 为每个运算量或运算符号都建立一个结点。 E • 可以根据表达式的运算顺序自下而上的构造 --+ 语法树 E + T 手工构造。 抽象语法树

9
属性文法、语义规则(2)
• 属性文法的形式： 产生式 语义规则 . 综合属性 A b:=f(c1,c2,…,ck) – 例如 P137.表6.1的属性文法: 继承属性 • EE1+ T E.val := E1.val+ T.val 综合属 – 例如 P139.表6.2的属性文法: 性 DTL L.in := T.type LL1 , id L .in := L.in 1 继承属性 继承属性
10
• 例, P137.
假设：
产生式 ABC
语义规则 A.b:=A.a+B.c C.d:=B.c+1 A有综合属性b和继承属性a B有综合属性c C有继承属性d
继承属性A.a和综合属性B.c在其他适当的地方计算。

6-第六章_语义分析-1-2-3节


2.语义分析程序 2.语义分析程序
为每个产生式，构造一个语义子程序Subi , 为每个产生式，构造一个语义子程序Sub 语义程序包括： 针对每一条产生式) 语义程序包括：⑴ Subi (针对每一条产生式) 公共子程序) ⑵ Comj (公共子程序)
语法分析程序 Par1,Par2…Park 语义 分析 程序 Sub1 Sub2 Ret1,Ret2…Reth
L.in= real L.in= real , , id2 id3
L.in= real id1
语 义 规 则 L.in:=T.type T.type=integer T.type:=real L1.in:=L.in；addtype(id.entry,L.in) ； addtype(id.entry,L.in)
…
Subn 中间代码Leabharlann Com1… Com m
例：E→E1 ＋ E2 入口参数(Par) (Par)： .PLACE， 入口参数(Par)： E1.PLACE， E2.PLACE (存放E1 、E2 的值的单元地址) 存放E 的值的单元地址) 返回参数(Ret)： E.PLACE (存放E值的单元地址) 返回参数(Ret)： (存放E值的单元地址) (Ret) 存放 生成中间代码 ( +, E1.PLACE, E2.PLACE, E.PLACE)
例： E → E1 ＋ E2 E .code —— E的中间代码序列 E .val —— E的值 存放E E .PLACE —— 存放E的值的单元地址
说明： 不同的中间代码形式、不同的语言成份， 说明： 不同的中间代码形式、不同的语言成份， 使用的属性不同。 使用的属性不同。
属性 • 综合属性(synthesized attribute) 综合属性(synthesized
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

① E→E+T ② E→T ③ T→T*F ④ T→F
⑤ F→(E) ⑥ F→a ⑦ F→b ⑧ F→c
① E→E+T@+ ② E→T ③ T→T*F@* ④ T→F
⑤ F→(E) ⑥ F→a@a ⑦ F→b@b ⑧ F→c@c
2020/11/13
8
语法制导翻译的基本思想 通俗地讲，以语法分析为基础，伴随语法分析的各个步骤，执 行相应的语义动作。 具体方法： 1．将文法符号所代表的语言成分的意思，用隶属于该文法符 号的属性表示； 2．用语义规则(语义规则的执行就是语义动作)规定产生式所 代表的语言成分之间的关系（即属性之间的关系），即用语义 规则实现属性计算。 3.语义动作(语义规则的执行)： 在语法分析的适当时刻（如推导或归约）执行附在对应产生 式上的语义规则，以实现对语言结构语义的处理，如计算、查 填符号表、生成中间代码、发布出错信息等。
10
－对改写后文法的每个非终结符号编写一个函数。
代标 码代 优码 化生
目 标 代 码
成
成
➢ 词法分析和语法分析仅仅对源程序做形式变换和检查。
➢ 语义分析检查程序语义是否正确。
➢ 中间代码生成将语义分析后的结果翻译成代码。
☻上述工作过程采用串行处理方式 ☻实际应用中语法分析、语义分析、中间代码生成采用并
行处理方式
2020/11/13
3
并行处理方式：
消除左递归得到： E→TE’ E’ →+T@+E’|ε T→FT’ T’ →*F @* T’|ε F→(E)|a@a| b@b| c@c
求FIRST集和 FOLLOW集不 考虑动作符号
FIRST(TE’)={(,a,b,c} FIRST(+T@+E’)={+} FOLLOW(E’)={#,)} FIRST(FT’ )={(,a,b,c} FIRST(*F @* T’)={*} FOLLOW(T’)={#,+,)} FIRST((E))={(} FIRST(a@a)={a} FIRST(b@b)={b} FIRST(c@c)={c}
2020/11/13
① E→E+T ② E→T ③ T→T*F ④ T→F
⑤ F→(E) ⑥ F→a ⑦ F→b ⑧ F→c
① E→E+T@+ ② E→T ③ T→T*F@* ④ T→F
⑤ F→(E) ⑥ F→a@a ⑦ F→b@b ⑧ F→c@c
7
语法制导翻译
➢由于翻译文法是在输入文法的产生式右部的适当位置插入动 作符号形成的，因此，翻译文法产生的动作序列受输入语言的 文法控制（语法制导）。 ➢语法制导翻译：根据输入文法，分析各条产生式的语义(要求 计算机所完成的操作)，分别编出完成这些操作的子程序或程序 段(称为语义子程序或语义动作)，并把这些子程序或程序段的 名字作为动作符号插入到输入文法各产生式右部的适当位置上， 从而实现翻译文法。
⑤ F→(E) ⑥ F→a@a ⑦ F→b@b ⑧ F→c@c
@为动作符号标记，由符号@开始的符号串称为一个动作符号。
2020/11/13
5
① E→E+T ⑤ F→(E)
① E→E+T@+
② E→T
⑥ F→a
② E→T
③ T→T*F ⑦ F→b
③ T→T*F@*
④ T→F
⑧ F→c
④ T→F
➢把中缀表达式文法叫做输入文法；
第6章 语法制导翻译技术
2020/11/13
1
内容提要
➢ 引言 ➢ 翻译文法 ➢ 语法制导翻译
自顶向下语法制导翻译 自底向上语法制导翻译 ➢ 属性翻译文法 属性文法的自顶向下翻译 属性文法的自底向上翻译
2020/11/13
2
引言
编译程序的逻辑工作过程
中
目
源 程 序
词 法 分 析
语语 间 法义 代 分分 码 析析 生
2020/11/13
6
例：对于符号串(a+b)*c 用输入文法推导输入序列(a+b)*c: E =>T=>T*F=>F*F=>(E)*F=>(E+T)*F=>(T+T)*F=>(F+T)*F
=>(a+T)*F=>(a+F)*F=>(a+b)*F=>(a+b)*c 用翻译文法推导活动序列(a@a+b@b@+)*c@c@*: E =>T=>T*F@*=>F*F@*=>(E)*F@*=>(E+T@+)*F@*=>(T+T@+)*F@*
对文法中的每个产生式都附加一些动作(语义分 析、操作符号表、代码生成等),在语法分析过程 中，每当需要使用一个产生式进行推导或归约， 语法分析程序除执行相应的语法分析动作外，还 要执行相应的其它动作，完成语义分析和代码生 成等工作。（边分析边翻译）
并行处理方式涉及几个概念
➢ 翻译文法 ➢ 语法制导翻译 ➢ 属性翻译文法
2020/11/13
9
自顶向下语法制导翻译
自顶向下的语法制导翻译：递归下降翻译、LL(1)翻译。 递归下降翻译(在适当位置插入实现动作符号的子程序）:
例:算术表达式翻译 文法如下：(@为输 出其后的符号串) ① E→E+T@+ ② E→T ③ T→T*F@* ④ T→F ⑤ F→(E) ⑥ F→a@a ⑦ F→b@b ⑧ F→c@c
2020/11/13
4
翻译文法
翻译文法：在描述语言规则的文法产生式右部的适当位置加入动 作而得到的文法 。
例：构造中缀表达式文法的翻译文法，得到其后缀表达式。
① E→E+T ② E→T ③ T→T*F ④ T→F
⑤ F→(E) ⑥ F→a ⑦ F→b ⑧ F→c
① E→E+T@+ ② E→T ③ T→T*F@* ④ T→F
⑤ F→(E) ⑥ F→a@a ⑦ F→b@b ⑧ F→c@c
➢在输入文法上添加动作后形成的文法叫做翻译文法
➢使用中缀表达式文法推导得到终结符号串叫做输入序列；
➢使用翻译文法推导得到的符号串称为活动序列。
➢从活动序列中去掉所有动作符号得到输入序列，而所有动 作符号组成的符号串称为动作序列。
➢从动作序列中去掉动作符号标记得到输出序列（翻译结果）
=>(F+T@+)*F@*=>(a@a+T@+)*F@*=>(a@a+F@+)*F@* =>(a@a+b@b@+)*F@*=>(a@a+b@b@+)*c@c@* 将活动序列(a@a+b@b@+)*c@c@*中的动作符号去掉得到输入序 列：(a+b)*c 所有动作符号组成的符号串即动作序列为：@a@b@+@c@* 去掉动作符号标记得到：ab+c*