当前位置：文档之家 › 编译原理课件语法制导翻译__SDD_定义__例__表达式的解释执行

编译原理课件语法制导翻译__SDD_定义__例__表达式的解释执行

  • 格式：ppt
  • 大小：721.00 KB
  • 文档页数：14

下载文档原格式

  / 14

合集下载

编译原理课件Chapter_5

编译原理课件Chapter_5

•
•
结点N的属性值由N的产生式所关联的语义规则来定义 通过N的子结点或N本身的属性值来定义
结点N的属性值由N的父结点所关联的语义规则来定义 依赖于N的父结点、N本身和N的兄弟结点上的属性值 不允许N的继承属性通过N的子结点上的属性来定义， 但允许N的综合属性依赖于N本身的继承属性 终结符号有综合属性 (来自词法分析)，但无继承属性
–
每个语义规则都根据产生式体中的属性值来计算头部 非终结符号的属性值
栈中的状态/文法符号可以附加相应的属性值 归约时，按照语义规则计算归约得到的符号的属性值 要求副作用不影响其它属性的求值 没有副作用的SDD称为属性文法
•
S属性的SDD可以和LR语法分析器一起实现
– –
•
语义规则不应该有复杂的副作用
•
•
•
抽象语法树的表示方法
– –
叶子结点中只存放词法值 内部结点中存放了op值和参数 (通常指向其它结点)
30
构造简单表达式的抽象语法树的SDD

属性E.node指向E对应的抽象语法树的根结点
31
表达式抽象语法树的构造过程
•
输入
•
a–4+c
•
步骤
p1 = new Leaf(id, entry_a); p2 = new Leaf(num, 4); p3 = new Node('–', p1, p2); p4 = new Leaf(id, entry_c); p5 = new Node('+', p3, p4);
–
–
9
语法分析树上的SDD求值 (1)
•
•
实践中很少先构造语法分析树再进行SDD求值， 但在分析树上求值有助于翻译方案的可视化，便 于理解 注释语法分析树
编译原理 第5章语法制导的翻译

编译原理 第5章语法制导的翻译


属性和文法符号相关联 规则和产生式相关联

根据需要，将文法符号和某些属性相关联， 并通过语义规则来描述如何计算属性的值


E→E1+T E.code=E1.code || T.code || ‘+’ code表示了我们关心的表达式的逆波兰表示，规则说明 加法表达式的逆波兰表示由两个分量的逆波兰表示并置， 然后加上‘+’得到。
digitlexval=3
18
适用于自顶向下分析的SDD


前面的表达式文法存在直接左递归，因 此无法直接用自顶向下方法处理。 消除左递归之后，无法直接使用属性val 进行处理：


比如规则：T→FT’ T’→*FT’ T对应的项中，第一个因子对应于F， 而运算符在T’中。
19
相同表达式的不同文法的比较
38
例5.15 分析栈实现的例子

假设语法分析栈存放在一个被称为stack 的记录数组中，下标top指向栈顶；


stack[top]指向这个栈的栈顶；stack[top-1] 指向栈顶下一个位置； 如果不同的文法符号有不同的属性集合，我 们可以使用union来保存这些属性值。（归 约时，我们知道栈顶向下的各个符号分别是 什么）
语义翻译的流程
输 入 符 号 串 分 析 树 依 赖 图
语
义
规
则
的 计
实际上，编译中语义翻译的实现并不是 按图中的流程处理的；而是随语法分析 的进展，识别出一个语法结构，就对它 的语义进行分析和翻译。
算
9
5.1 语法制导定义

4.什么是语法制导定义（SDD） 上下文无关文法和属性/规则的结合；
《编译原理》课件

《编译原理》课件

代码生成
编译器可以将高级语言编写的源代码转换成机器语言或低级语言，以便在特定的硬件平台上运行。编 译器还可以生成可执行文件或动态链接库等二进制文件。
编译器在人工智能领域的应用
机器学习编译器
机器学习编译器可以将机器学习模型转换成可执行代码，以便在嵌入式设备或边缘计算 设备上运行。这种编译器可以优化模型的计算性能和内存占用，提高模型的运行效率。
3
缺点
对于某些复杂文法，可能导致大量的无用推导和 状态爆炸。
自底向上的语法分析
分析步骤
从输入符号序列的最后一个符号开始，逐步向上构建语法树，直 到找到与文法中的某个产生式右部匹配的符号串。
优点
可以充分利用已知信息，避免不必要的推导和状态爆炸。
缺点
对于某些复杂文法，可能导致大量的无用归约和状态爆炸。
04
中间代码生成
中间代码生成的定义和任务
定义
中间代码生成是编译器的一个阶段，将源代码转换成中间代码的过程。
任务
将源代码转换成一种中间表示形式，以便进行后续的优化和目标代码生成。
三地址代码的生成
01
三地址代码是一种中间代码形 式，由一系列的三元式组成。
02
三元式的形式为(op, arg1, arg2)，表示执行一个操作(op) 并产生一个结果，操作数arg1 和arg2来自寄存器、常数或之 前的计算结果。
语义分析
检查AST是否有语义错误，如类型错 误、未定义的变量等。
中间代码生成
将AST转换为中间代码，通常是三地 址代码。
代码优化
对中间代码进行优化，提高执行效 率。
代码生成
将中间代码转换为机器语言代码， 能够在特定硬件上执行。
编译器的分类
编译原理chapter5 语法制导翻译

编译原理chapter5 语法制导翻译


for 结点n所用产生式对应的每一条
语义规则 b:＝f（c1，c2，…，ck ) do
精品文档
14
5.1.5 计算顺序
◆拓扑排序
一个有向非循环图的拓扑排序是图中
结点的任何顺序m1，m2，…，mk，使得
边必须是从序列中前面的结点指向后面的
结点，也就是说，如果mi→mj是mi到mj的
一条边,那么在 序列中mi必须出现在mj的
规则来计算综合属性值，即在 用哪个产生
式进行归约后，就执行那个产生式的s-属性
定义计算属性的值，从叶结点到根结点进行
计算。
5.1.3 继承属性
继承属性值是由此结点的父结点和／或兄
弟结点的某些属性值来决定的。
例5 . 3 变量说明的类性定义
int a,b,c
精品文档
11
表5.2 带有继承属性L.in的语法制导定义
精品文档
3
要求：随着语法分析，分析树逐步被构造出 来，进展到每一步，定义的文法符号的属性 值是可以计算出来的。一个重要的属性定义 类称作“L—属性”定义，满足上述要求。
精品文档
4
语
输
义
入
分
依
规
符
析
赖
则
号
树
图
的
串
计
算
图5.1 语法制导翻译的概观
精品文档
5
5.1 语法制导定义(Syntax-directed definitions) ◆语法制导定义是对上下文无关文法的推广 综◆合属属性性 继承属性 ◆依赖图 语义规则建立了属性之间的依赖关系，这些关 系可以用图来表示，这样的图称为依赖图。
语法树是常用的一种中间表示形式。
编译原理课件语法制导翻译__翻译方案_SDD

编译原理课件语法制导翻译__翻译方案_SDD

语法制导翻译
描述一棵语法树中结点的属性之间的 相互依赖关系 词法分析 语法分析 依赖图 输入串 语法树 语义规则计算次序 ( 拓扑排序) 树遍历
一遍扫描:在语法分析的同时完成语义规则的 计算, 无需构造实际的语法树
1. 依赖图的拓扑排序
• 依赖图 • 拓扑排序
2. 树遍历的属性计算方法
练习: 以下SDD是L-属性的吗？
产生式 语义规则
ALM
AQR
L.i := l(A.i) M.i := m(L.s) A.s := f(M.s) R.i := r(A.i) Q.i := q(R.s) A.s := f(Q.s)
• 表达式2 ☆
dependencygraph edges can go from left to right
(2) 产生式 Xj 的左边符号 X1，X2，…，Xj-l 的属性
(3) Xj 自己的属性
• S-属性文法一定是L-属性文法 表达式 ☆
Example 非L-属性文法
产生式 A BC 语义规则 A.s = B.b B.i = f ( C.c , A.s )
Fig. Syntax-directed definition of a simple desk calculator
L-属性文法 D TL 和自上而下 T int 语法分析 T real
L L1, id D T .type = real real
综T.type T. type := integer T. type := real L1.in := L.in; addtype (id.entry,L.in ) addtype (id.entry,L.in )
(a)初始状态 (b)VisitNode(S)第一次调用后 (c)VisitNode(S)第二次调用后 (d)VisitNode(S)第三次调用后 的最终状态
编译原理课件语法制导翻译__SDD_依赖图_拓扑排序__例__变量声明语句_继承属性

编译原理课件语法制导翻译__SDD_依赖图_拓扑排序__例__变量声明语句_继承属性


T type real in
L addtype ,
id3 entry
L addtype id1 entry
id2 entry
L L1, id L1.in := L.in; addtype (id.entry,L.in ) L id addtype (id.entry, L.in )
文法 ☆
real id1, id2, id3
id1.entry 1
参考
依赖图 Dependency Graph
• 语义规则的形式 b := f(c1，c2，…，ck)
可以为每一个包含过程调用的语义规则引入一 个虚综合属性 b， L E n print (E.val)
• 依赖图中为每一个属性设置一个结点， 如果属性b依赖于属性c， c1 则从属性c的结点 有一条有向边连到属性b的结点。…
如何确定属性的计算顺序？ T.type 4 7 L.in 9 L.in 5 L.in addtype 8
依赖图
拓扑排序
addtype 6 id3.entry 3
addtype 10
id2.entry 2 a4 := real; a5 := a4; addtype (id3.entry, a5 ) a7 := a5; addtype (id2.entry, a7 ) a9 := a7; addtype (id1.entry, a9 )
T real
L L1, id L id
计算继承属性
D TL T int T real L L1, id
L id
D
T .type = real real
综合 属性
L.in := T.type T. type := integer T. type := real L1.in := L.in; addtype (id.entry,L.in ) addtype (id.entry,L.in )
编译原理课件语法制导翻译__SDD_例__表达式__综合属性_继承属性

编译原理课件语法制导翻译__SDD_例__表达式__综合属性_继承属性


T .val
依赖图 .inh T’.syn
F .val
digit .lexval *
F .val digit .lexval
inh T1’.syn ε
Production Semantic Rules T → FT’ T’.inh = F.val T.val = T’.syn T’→ *FT1’ T1’.inh = T’.inh * F.val T’.syn = T1’.syn
Production T → FT’ T’→ *FT1’ T’→ ε F → digit Semantic Rules T’.inh = F.val T.val = T’.syn T1’.inh = T’.inh * F.val T’.syn = T1’.syn T’.syn = T’.inh F.val = digit.lexval
T F T’
补充练习: 构造 3*5*7 的带 注释的语法树
digit
*
F
digit *
T’
F T’
digit
Production T → FT’ T’→ *FT1’ T’→ ε F → digit Semantic Rules T’.inh = F.val T.val = T’.syn T1’.inh = T’.inh * F.val T’.syn = T1’.syn T’.syn = T’.inh F.val = digit.lexval
6
7
Production Semantic Rules T → FT’ T’.inh = F.val T.val = T’.syn T’→ *FT1’ T1’.inh = T’.inh * F.val T’.syn = T1’.syn
编译原理01-本讲教学课件(PDF文档)_3

编译原理01-本讲教学课件(PDF文档)_3


语法制导翻译方案SDT
➢语法制导翻译方案(SDT )是在产生式右部中嵌入了 程序片段(称为语义动作)的CFG
➢SDT可以看作是SDD的具体实施方案 ➢本节主要关注如何使用SDT来实现两类重要的SDD，
因为在这两种情况下，SDT可在语法分析过程中实现
➢ 基本文法可以使用LR分析技术，且SDD是S属性的
{stack[top-2].val = stack[top-2].val × stack[top].val ; top=top-2; }
{stack[top-2].val = stack[top-1].val; top=top-2; }
输入： 3*5+4
状态 符号属性
0 $_ 1 E 135 6 +_ 5 d4
E.val = E1.val + T.val E.val = T.val T.val = T1.val × F.val
T.val = F.val
(6) F ( E ) F.val = E.val
(7) F digit F.val = digit.lexval
当归约发生时执行相应的语义动作
扩 展 的 LR 语 法 分 析 栈
SLR自动机
产生式
例(1)E′ → E
(2)E → E1 + T
(3) E → T (4) T → T1 * F
(5) T → F (6)F → ( E )
(7)F → digit
语义动作 { print (stack[top].val );} {stack[top-2].val = stack[top-2].val + stack[top].val ; top=top-2; }
例(1)E′ → E
编译原理 语法制导翻译

编译原理 语法制导翻译

搜索方法：hash技术…
TinyC中的语法树
typedef enum {StmtK,ExpK} NodeKind; typedef enum {IfK,RepeatK,AssignK,ReadK,WriteK} StmtKind; typedef enum {OpK,ConstK,IdK} ExpKind; typedef enum {Void,Integer,Boolean} ExpType; #define MAXCHILDREN 3 typedef struct treeNode { struct treeNode * child[MAXCHILDREN]; struct treeNode * sibling; int lineno; NodeKind nodekind; union { StmtKind stmt; ExpKind exp;} kind; union { TokenType op; int val; char * name; } attr; ExpType type; /* for type checking of exps */ } TreeNode;
作为中间表示形式——分离分析与翻译
在进行语法分析的同时进行翻译存在缺
陷：
适合分析的文法可能未反映自然的语言结构 分析顺序可能与翻译顺序不一致
利用语法制导翻译方法来构造语法树
5.2.1 语法树
（抽象）语法树，压缩形式
关键字和运算符均在内部节点
链式结构会被压缩
语法树压缩例
digit.lexval：终结符只有综合属性，由词法分 析器提供 开始符号通常没有继承属性
5.1.2 综合属性
只有综合属性：S-属性定义
语法树自底向上计算属性
《编译原理课件》PPT课件

《编译原理课件》PPT课件

它是源程序的一种内部表示形式。 设计中间代码的原则：一是容易生成，二是
容易翻译成目标代码。 常用的中间代码有三地址码、四元式、三元
式、间接三元式、逆波兰表示（后缀式）、 树形表示等。
14
中间代码：四元式
例： id1:=id2+id3*10
sum:=first+count*10 翻译为四元式中间代码的形式：
5
1.2 编译程序的工作过程与结构
一个编译程序的整个工作过程是划分成阶段 进行的，每个阶段将源程序从一种表示形式 转换成另一种表示形式。
编译阶段的典型划分方法是划分为5个基本阶 段：词法分析、语法分析、语义分析产生中 间代码、代码优化、代码生成。
掌握编译过程的5个基本阶段，是学习编译原 理课程的基本内容。
29
自编译：T形图表示
PASCAL2
A代码
PASCAL2
A代码
PASCAL1 PASCAL1
A代码 A代码
用PASCAL1语言 编写的功能更
强的PASCAL2语 言编译程序的
Ａ代码
已有的PASCAL1 语言的编译程序
自编译得到
功能更强的
PASCAL2语言 的编译程序
源程序
注意：T形图的组合规则：① ②
Java语言的操作平台无关性的实现就是如此。
26
1.3 编译程序的开发
构造编译程序，可以：
1. 使用机器语言或汇编语言作工具构造 2. 使用高级语言作工具构造 3. 使用机器语言或汇编语言构造编译程序的核心
部分，使用高级语言构造编译程序的扩充部分 4. 使用编译程序自动生成工具构造
使用高级语言作工具构造编译程序可以大大节 省程序设计的时间，并且编译程序易于阅读、 维护和移植。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
表达式的解释执行
产 生 式 LEn E E1 + T ET T T1 * F TF F (E) F digit
digit+digit*digit n
L E E T F digit +
18+5*2n
n T
T * F F digit digit
语法制导定义 SDD Syntax-Directed Definition
F.val := digit.lexval
E .val = 8
T.val = 8 F.val = 8
+
T .val = 10 T .val = 5 *
F.val = 5 F .val = 2 digit .lexval = 2
digit .lexval = 8
digit .lexval = 5
SDD与属性文法
• 副作用 • 引用透明
LEn
print (E.val)
E E1 + T E.val := E1 .val + T.val
ET
T T1 * F TF
E.val := T.val
T.val := T1.val * F.val T.val := F.val
F (E)
F digit
F.val := E.val
TF
F(E) Fdigit
翻译输入 3*5+4n 所作的动作
L E n { print (statck[top-1].val ); top = top -1; } EE1 + T { statck[top-2].val = statck[top-2].val + statck[top].val; top = top -2; } TT1 * F { statck[top-2].val = statck[top-2].val * statck[top].val; top = top -2; } { statck[top-2].val = F(E) statck[top-1].val top = top -2; }
Semantic Rules L.val := 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
带注释的语法树 Annotated Parse Tree - 结点带有语义信息 L E .val = 18 n
一个语法制导定义(SDD) 是一个配备了属性和规则的上下文无关文法
产 生 式 LEn E E1 + T ET T T1 * F TF F (E) F digit 语 义 规 则 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*5+4n － *5+4n 3
－ 3
*5+4n F
*5+4n T 5+4n T* +4n T*5
3
3 3－ 3－5 3－5 15 15 15－ 15－4
F dight
T F
+4n T*F
+4n T +4n E 4n E+ n E+4
F dight
T T*F E T
E .val = 8 +
F (E)
F digit
F.val := E.val
F.val := digit.lexval
T .val = 10 T .val = 5 * F.val = 5 digit .lexval = 5 F .val = 2 digit .lexval = 2
T.val = 8 F.val = 8
n E+F
n E+T n E En L
15－4
15－4 19 19－ 19
F dight
T F E E+T L En
计算综合属性
• 先构造语法树，再进行后序遍历 • 一遍扫描的处理方法 在自下而上语法分析过程中计算综合属性
Production LEn E E1 + T ET T T1 * F TF F (E) F digit
计算综合属性
从左到右深度优先遍历语法树 L
LEn
print (E.val)
E E1 + T E.val := E1 .val + T.val
ET
T T1 * F TF
E.val := T.val
T.val := T1.val * F.val T.val := F.val
E .val = 18 n
ቤተ መጻሕፍቲ ባይዱ
属性的传递方向
综合属性和继承属性
• 综合属性 Synthesized Attributes
用于“自下而上”传递信息 一个结点的综合属性的值由其子结点的属性值确定
• 继承属性 Inherited Attributes
用于“自上而下”传递信息 或者在兄弟之间传递信息 综合属性
A→BC
A.b := A.a+B.c C.d := A.a+B.c+1
digit .lexval = 8
8+5*2n
~~ 计算综合属性
I. 后序遍历语法树 Postorder Traversal
postorder (N) { for ( each child C of N, from the left ) postorder(C); evaluate the attributes associated with node N; }
综合属性
Production LEn E E1 + T ET T T1 * F TF F (E) F digit Semantic Rules L.val := 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
~~ 计算综合属性
II.一遍扫描的处理方法 • 在进行自下而上语法分析的同时计算属性 • LR分析
val
A→XYZ A. a := f( X.x, Y.y, Z.z)
top
... ... X X.x
Y
Z
Y. y
Z. z
... ...
例: 用LR分析器实现台式计算器
Productions Actions { print (statck[top-1].val ); L E n top = top -1; } { statck[top-2].val = statck[top-2].val + statck[top].val; E E 1 + T top = top -2; } E T TT1 * F { statck[top-2].val = statck[top-2].val * statck[top].val; top = top -2; } { statck[top-2].val = statck[top-1].val top = top -2; }
继承属性
注意
• 终结符 只有综合属性,它们由词法分析器提供 • 非终结符 既可有综合属性也可有继承属性
语义规则的形式
在一个语法制导定义中，对应于每个产生式A→α都有一 套与之相关联的语义规则， 每条规则的形式为 b := f(c1，c2，…，ck) 属性b依赖于属性 c1，c2，…，ck （1）或者 b是A的一个综合属性, 并且c1，c2，…，ck 是产生式右边文法符号的属性(或A的其他属性)； （2）或者 b是产生式右边某个文法符号的一个继承属性, 并且c1, c2，…, ck 是A或产生式右边任何文法符号的 属性。