语法制导翻译

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kJR2EhaU-1641910974690)(…/picture/1.png)]

编译器在做语法分析的过程中，除了回答程序语法是否合法，还必须完成

• 类型检查：语法正确但是语义不正确
• 目标代码生成
• 中间代码生成

以上工作一般可以通过语法制导的翻译完成

语法制导翻译是一种使用最广泛的上下文相关分析技术

编译器需要进行更深入的分析（程序表示的值，这些值在哪里，值如何从一个名字流动到另一个名字，这需要用到上下文知识）

本质是上下文相关分析所需的操作可以围绕着语法的结构进行组织，将上下文相关分析集成到解析上下文无关语法的过程中。

语法制导翻译：由语法分析程序的分析过程来主导语义分析以及翻译的过程。

提供在语法分析时要执行的代码片段，关联到产生式。

每一次语法分析器发现自身处于语法中的特定位置时，会调用对应的操作

• 自顶向下的语法分析器：只需向语法分析例程中添加适当的代码，控制操作执行的时机。
• • 一个代码片段
• 自顶向上的语法分析器：在每次执行归约操作时执行。
• • 即当右部分析完毕时刻即将规约时，如：由右部的值计算左部的值。

如下图所示

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JsqHLy91-1641910974691)(…/picture/2.png)]

实现方式：在分析栈上维护三元组<symbol, value,state>

symbol:表示终结符或非终结符

value：symbol所拥有的值，对应语义栈中内容。

state：当前的分析状态

实例如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OViJ9d5h-1641910974692)(…/picture/3.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-waoVf4jN-1641910974692)(…/picture/4.png)]

抽象语法树

语法分析树编码了句子的推导过程

但是包含很多对理解树要表达的语义不必要的信息：并且占用额外的存储空间

表达式只需要知道运算符和运算数：优先级、结合性已经在语法分析部分处理掉了。

抽象语法树：在语法树中去掉那些对翻译不必要的信息，从而获得更有效地源程序中间表示

例子如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-avczpTzR-1641910974693)(…/picture/5.png)]

具体语法是语法分析器使用的语法

• 适合于语法分析，如各种分隔符，消除左递归，提取左公因子

抽象语法用来表达语法结构的内部表示

• 抽象语法（前端）+ 后端（代码生成）

LR分析中生成抽象语法树

在语法动作中，加入生成语法树的代码片段：片段是语法树的构造函数。

在产生式归约的时候，会自底向上构造整棵树

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kG92SSR5-1641910974694)(…/picture/6.png)]

基于属性文法的语义计算

如果对$G[S]$附加某种限定条件，使其只产生满足这一限定条件的字符串，则可能接受语言$L$。这一想法可以通过属性文法来实现。

在文法$G[S]$的基础上，为文法符号关联有特定意义的属性，并为产生式关联相应的语义动作或条件谓词，称之为属性文法。

例如文法符号$X$关联一个属性$a$，我们用$X.a$表示对属性的访问。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-pmyYXtqT-1641910974694)(…/picture/7.png)]

每一个产生式$A\to \alpha$都关联一个于一计算规则的集合，如上图中花括号内的部分。

$b:=f(c_1,c_2\dots ,c_k)$ $f$称为语义函数，通过实际的代码片段实现。

条件谓词：AND OR

复写规则：$X.a:=Y.b$的语义动作称为复写规则

输入串属于$L$，结果accepted；不属于refused。

综合属性

对于关联于产生式$A\to \alpha$的语义动作$b:=f(c_1,c_2,\dots ,c_k)$，如果$b$是$A$的某个属性，则称$b$是$A$的一个综合属性。

分析树角度，计算综合属性是对父节点的属性赋值，所以是自底向上传递信息。

根据产生式右部的符号计算左部被定义的符号的综合属性。

在分析树结点$N$上的非终结符$A$的综合属性只能通过==$N$的子节点或$N$本身的属性值==来定义。

终结符可以具有综合属性，综合属性值是由词法分析器提供的词法值，因此没有计算终结符属性值的语义规则。

继承属性

对关联于产生式$A\to \alpha$的语义动作$b:=f(c_1,c_2,c_k)$，如果$b$是产生式右部某个文法符号$X$的某个属性，则称$b$是文法符号$X$的一个继承属性。

分析树角度，计算继承属性是根据父节点和兄弟节点对子节点的属性赋值，所以是自顶向下传递信息。

根据右部候选式中的符号的属性和左部被定义符号的属性计算右部候选式中的符号的继承属性

在分析树节点$N$上的非终结符$A$的继承属性只能通过$N$的父节点、$N$的兄弟节点、$N$本身的属性值来定义。

终结符没有继承属性。

对于左侧分析树，对于综合属性值进行自底向上计算，对继承属性进行自顶向下计算。

在产生式$A\to BC$中，只能计算出$A$的综合属性和$B、C$的继承属性。

$A$的继承属性和$B、C$的综合属性在其他产生式中计算。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Zm8OF2WD-1641910974695)(…/picture/10.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BQv4hy7M-1641910974695)(…/picture/8.png)]

遍历分析树进行语义计算（属性计算）

依赖图：

基于属性文法，通过遍历分析树进行语义计算步骤：

• 构造输入串的语法分析树
• 构造依赖图
• 若依赖图无圈，按此无圈图一种拓扑排序对分析树进行遍历；若还有圈，则进一步失效。

依赖图算法描述：

• 有向图，用来描述分析树中的属性和属性之间的依赖关系
• 在语法树中，为每个节点新建几个属性节点，分析树中每个标号为$X$的结点的每个属性$a$都对应着依赖图中的一个节点
• 如果属性$X.a$的值依赖于$Y.b$的值，则依赖图中有一条$Y.b$的结点指向$X.a$的结点的有向边。

输入串 -> 语法树 -> 依赖图 ->语义规则的计算顺序（拓扑顺序）

树遍历：

输入串 -> 语法树 -> 遍历语法树计算属性

• 假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性
• 以某种次序遍历语法树，直至计算出所有属性

深度优先（从左到右）-》 递归

算法思想：如果有还未被计算的属性，则从左到右深度优先的计算以这个节点为根的这个子树。

贪心算出能算出来的属性，然后直到所有子节点的所有属性算出来之后，计算根结点的。

标注：

• 语法分析树中各个节点属性取值的计算过程被称为对语法分析树进行标注
• 可以用带标注语法分析树表示属性的计算结果。

一边扫描的处理方法：

通过遍历分析树进行语义计算是在语法分析遍之后进行的，不能体现语法制导方法的优势。

实际中，语法制导的语义计算大都采用单遍的过程，及语法分析过程的同时就完成相应的语义动作，这样属性计算仅对应一个自顶向下或自底向上的简单过程。

• 自上而下分析，一个产生式匹配输入串成功时，执行语义动作
• 自下而上分析时，一个产生式被用于进行归约时，执行语义动作

在实践中一般会对属性文法进行限制：

• $S-$属性文法

只包含综合属性的属性文法成为$S-$属性文法

• $L-$属性文法

对于某个属性文法，如果对其中每一个产生式$A\to X_1{X}_2\dots X_n$

其每个语义动作所涉及的属性或者是综合属性，或者是某个$X_i$的继承属性，这个继承属性只能依赖于：

• $X_i$左边的符号的属性
• $A$的继承属性

既可以包含综合属性，也可包含继承属性，但要求产生式右端某文法符号的继承属性的计算只取决于该符号左边符号的属性

• 对于产生式左边的符号，只能是继承属性
• 还有$X_i$本身的属性，但$X_i$的全部属性不能在依赖图中形成环路
• $S-$属性文法是$L-$属性文法的一个特例

$S-$属性文法

由于综合属性是自底向上传递信息，所以基于$S-$属性文法的语义计算通常采用自底向上的方式

• 可以在自底向上的语法分析过程中实现
• 语义栈存放综合属性的当前取值
• 综合属性值的计算发生在每一步规约发生之前

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-xR9Ax6Vs-1641910974696)(…/picture/9.png)]

如图所示

基于$S-$属性文法的语义计算$LR$分析表如下图所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dDh1Fg6y-1641910974697)(…/picture/11.png)]

$S\to E$	{print(E.val)}\{print(E.val)\}{print(E.val)}
$E\to E_1+T$	{E.val:=E1.val+T.val}\{E.val := E_1.val + T.val\}{E.val:=E1​.val+T.val}
$E\to T$	{E.val:=T.val}\{E.val:=T.val\}{E.val:=T.val}
$T\to T_1\ast F$	{T.val:=T1.val∗F.val}\{T.val:=T_1.val * F.val\}{T.val:=T1​.val∗F.val}
$T\to F$	{T.val:=F.val}\{T.val := F.val\}{T.val:=F.val}
$F\to (E)$	{F.val:=E.val}\{F.val:=E.val\}{F.val:=E.val}
$F\to d$	{F.val:=d.lexval}\{F.val:=d.lexval\}{F.val:=d.lexval}

基于$S-$属性文法的语义计算：需要有$DFA$表

$2+3\ast 5$

步骤	分析栈（状态，符号，语义值）	余留符号串	分析动作	语义动作
0	0#-	2+3*5#	$S_5$
1	0#- 522	+3*5#	$r_6$	$F.val:=d.lexval$
2	0#- 3F2	+3*5#	$r_4$	$T.val:=F.val$
3	0#- 2T2
4
5
6
7
8
9
10
11
12
13

$L-$属性文法的语义计算

通过自顶向下深度优先从左到右遍历分析树计算属性值。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-crIfgst0-1641910974697)(…/picture/16.png)]

 |            |          |                   |

| 12 | | | | |
| 13 | | | | |

$L-$属性文法的语义计算

通过自顶向下深度优先从左到右遍历分析树计算属性值。

[外链图片转存中…(img-crIfgst0-1641910974697)]