1. IT分享知识网首页
  2. 未分类

【编译技术】第九章-语法制导翻译

老牧童 • • 未分类

【编译技术】第九章-语法制导翻译属性文法是指在翻译文法的基础上 为各个符号 包括终结符 非终结符和动作符号 带上属性 并规定求值规则 能够更好的描述和实现编译过程

大家好，欢迎来到IT知识分享网。

目录

语法制导翻译的概念

输入文法和翻译文法

  • 输入文法：未插入动作符号的文法。即先前在语法分析阶段使用的文法。由输入文法可以通过推导产生输入序列。
    • 输入序列：仅由终结符组成的序列
  • 翻译文法：插入了动作符号的文法。由翻译文法可以通过推导产生活动序列，包括输入序列和动作序列。
    • 活动序列：包含终结符和动作符号的序列。执行活动序列中的动作序列，就完成了规定的翻译任务。

Example：
对于一个仅由i,+,*,(,)组成的算术表达式，其输入文法可以是：

  1. E → \rightarrow →E+T
  2. E → \rightarrow →T
  3. T → \rightarrow →T*F
  4. T → \rightarrow →F
  5. F → \rightarrow →(E)
  6. F → \rightarrow →i

而其翻译为后缀波兰表达式的翻译文法可以是：

  1. E → \rightarrow →E+T@+
  2. E → \rightarrow →T
  3. T → \rightarrow →T*F@*
  4. T → \rightarrow →F
  5. F → \rightarrow →(E)
  6. F → \rightarrow →i@i

对于符号串(i+i)*i而言：

  • 其输入序列即为(i+i)*i
  • 其活动序列为(i@i+i@i@+)*i@i@*
  • 其动作序列为@i@i@+@i@*

执行动作序列，得到ii+i*，即完成了翻译任务。

语法制导翻译

属性翻译文法

综合属性

自右向左、自底向上计算的属性。用 ↑ \uparrow ↑标记综合属性，加上综合属性常量或变量 c c c，就是综合属性符号 ↑ c \uparrow_c ↑c​。

Example：
将之前的翻译文法加上综合属性，变为属性翻译文法：

  1. E ↑ p _{\uparrow p} ↑p​ → \rightarrow → E ↑ q _{\uparrow q} ↑q​+F ↑ r _{\uparrow r} ↑r​
  2. E ↑ p _{\uparrow p} ↑p​ → \rightarrow → T ↑ q _{\uparrow q} ↑q​
  3. T ↑ p _{\uparrow p} ↑p​ → \rightarrow → T ↑ q _{\uparrow q} ↑q​*F ↑ r _{\uparrow r} ↑r​
  4. T ↑ p _{\uparrow p} ↑p​ → \rightarrow → F ↑ q _{\uparrow q} ↑q​
  5. F ↑ p _{\uparrow p} ↑p​ → \rightarrow → (E ↑ q _{\uparrow q} ↑q​)
  6. F ↑ p _{\uparrow p} ↑p​ → \rightarrow → i ↑ q _{\uparrow q} ↑q​

各条产生式对应的求值规则为：

  1. p p p:= q q q+ r r r
  2. p p p:= q q q
  3. p p p:= q q q* r r r
  4. p p p:= q q q
  5. p p p:= q q q
  6. p p p:= q q q

注：属性变量 p p p, q q q, r r r均为局部变量，作用于本产生式。

则对于输入序列(i ↑ 3 _{\uparrow 3} ↑3​+i ↑ 9 _{\uparrow 9} ↑9​)*i ↑ 2 _{\uparrow 2} ↑2​，
其综合属性的计算过程如下：
在这里插入图片描述

继承属性

自顶向下、自左向右计算的属性。用 ↓ \downarrow ↓标记继承属性。

Example：
给定声明语句的输入文法：

  1. <声明> → \rightarrow → Type id <变量表>
  2. <变量表> → \rightarrow → id <变量表>
  3. <变量表> → \rightarrow → ϵ \color{darkred}{\epsilon} ϵ

为了完成填写符号表的翻译任务，将输入文法改写为属性翻译文法：

  1. <声明> → \rightarrow → Type id @set_table <变量表>
  2. <变量表> → \rightarrow → id @set_table <变量表>
  3. <变量表> → \rightarrow → ϵ \color{darkred}{\epsilon} ϵ

仅有动作符号是不够的，要完成动作符号所规定的填表动作还需要参数，因此为动作符号带上类型和标识符两个属性，它们由@set_table左边的两个终结符Type和id得到。注意Type和id为底层的终结符，因此它们的属性记为综合属性：

  1. <声明> → \rightarrow → Type ↑ t _{\uparrow t} ↑t​ id ↑ n _{\uparrow n} ↑n​ @set_table ↓ t 1 , n 1 _{\downarrow t_1, n_1} ↓t1​,n1​​ <变量表> ↓ t 2 _{\downarrow t_2} ↓t2​​
  2. <变量表> ↓ t 2 _{\downarrow t_2} ↓t2​​ → \rightarrow → id ↑ n _{\uparrow n} ↑n​ @set_table ↓ t 1 , n 1 _{\downarrow t_1, n_1} ↓t1​,n1​​ <变量表> ↓ t 3 _{\downarrow t_3} ↓t3​​
  3. <变量表> ↓ t 2 _{\downarrow t_2} ↓t2​​ → \rightarrow → ϵ \color{darkred}{\epsilon} ϵ

对应的赋值规则为：

  1. t 1 t_1 t1​, t 2 t_2 t2​:= t t t; n 1 n_1 n1​:= n n n
  2. t 1 t_1 t1​, t 3 t_3 t3​:= t 2 t_2 t2​; n 1 n_1 n1​:= n n n

应用：对于声明语句int A, BC 翻译如下：
在这里插入图片描述

得到的动作序列为 @set_table ↓ i n t , A _{\downarrow int, A} ↓int,A​ @set_table ↓ i n t , B C _{\downarrow int, BC} ↓int,BC​。执行该序列即可完成填符号表的翻译任务。

L属性翻译文法(L-ATG)

L-属性翻译文法定义为带有下列说明的翻译文法：

  1. 文法中的终结符，非终结符及动作符号都带有属性，且每个属性都有一个值域。
  2. 非终结符及动作符号的属性可分为继承属性和综合属性。
  3. 开始符号的继承属性具有指定的初始值。
  4. 输入符号（终结符号）的每个综合属性具有指定的初始值。
  5. 给定属性的求值规则。

因此，L-ATG是属性翻译文法中较简单的一种。其输入文法要求是LL(1)文法，可用自顶向下分析构造分析器。在分析过程中可进行属性求值。

简单赋值形式的L属性翻译文法(SL-ATG)

其定义为：

  1. 产生式右部符号的继承属性是一个常量，它等于左部符号的继承属性值或等于出现在所给符号左边符号的一个综合属性值。
  2. 产生式左部非终结符号的综合属性是一个常量，它等于左部符号的继承属性值或等于右部符号的综合属性值。

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/118012.html

赞 (0)
老牧童老牧童
0
上一篇 2025-11-16 14:20
下一篇 2025-11-16 14:33

相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注微信