SDD的应用

判断类型分析只是SDD的一个应用，SDD的其他编译相关应用：

• 抽象语法树构造

• 代码翻译

语法分析树（Parse Tree）

具体语法树（Concrete Syntax Tree）：保留所有词法元素，所有词法元素都有对应节点，完整地还原非终结符到串的推导过程，严格符合源语言的上下文无关文法。

但是保留所有词法元素会带来对语义分析无用的噪音，节点数量会很大；包含所有中间推导过程会引入大量中间节点；上下文无关文法可以根据文法自动生成，实际中很少在CST上直接进行分析/处理。

抽象语法树（Abstract Syntax Tree）：

• 只保留必要的词法元素

• 某些词法元素存入父节点的属性

• 移除没有实际信息的中间推导过程

• 不符合源语言的上下文无关文法

AST的优势：更少的节点数量和种类；更易于分析和处理；独立于具体文法

AST和CST

每个节点代表一个语法结构，对应于运算符；节点的每个子节点代表其子结构，对应于运算分量；表示这些子结构按照特定的方式组成了较大的结构；可以忽略掉一些标点符号等非本质的东西。

抽象语法的表示方式：每个节点用一个对象表示，对象有多个域，叶子节点中只存放词法值，内部节点中存放了op值和参数（通常指向其他节点）。

构造简单表达式的抽象语法树的SDD

语法制导的翻译方案

语法制导的翻译方案（SDT）是在产生式体中嵌入语义动作（程序片段）的上下文无关文法。

SDT的基本实现方法：

• 建立语法分析树（CST）

• 将语义动作看作是虚拟节点（绑定语义动作）

• 深度优先、从左到右地遍历分析树，在访问虚拟节点时执行相应的语义动作

用SDT实现两类重要的SDD：

• 基本文法是LR的，SDD是S属性的（自底向上）

• 基本文法是LL的，SDD是L属性的（自顶向下，递归程序）

实现SDT时，实际上并不会真的构造语法分析树，而是在分析过程中执行语义动作。即使基础文法可以应用某种语法分析技术，仍可能因为动作的缘故导致此技术不可用。

判断可否在分析过程中实现：

• 将每个语义动作替换为一个独有的非终结符号Mi，其产生式为Mi->空串。

• 如果新的文法可以由某种方法进行分析，那么这个SDT就可以在这个分析过程中实现。

判断SDT可否用特定分析技术实现的例子

L属性的SDT

如果基础文法是LL的，则可以将L属性SDD转换成一个SDT，该SDT可以在自顶向下的分析过程中实现。

从L属性的SDD到SDT的转换：

• 将每个语义规则看作是一个赋值语义动作

• 将赋值语义动作放到相应产生式的适当位置 A->X1X2..Xn

  • 计算Xi继承属性的动作插入到产生式体中的Xi的左边

  • 计算产生式头A综合属性的动作在产生式的最右边

举例：while语句的SDD和SDT

while语句产生式：

$$S\rightarrow \text{while} (C) S_1$$

while语句的含义：

• 首先对C求值，若为真，则控制转向S1的开始处

• 若为假，则转向while语句的后续语句开始处

• S1结束时，要能够跳转到while语句的代码开始处

边扫描边生成属性

当属性值的体积很大，对其进行运算会效率很低。比如上面例子中的code可能是一个上百K的串，许多代码片段会被反复复制，很低效。

所以可以逐步生成属性的各个部分，并增量式地添加到最终的属性值中。

三个条件：

1. 存在一个主属性，且其为综合属性

2. 在产生式中，主属性是通过产生式体中各非终结符号的主属性连接得到，同时还会连接一些其他元素

3. 各个非终结符号的主属性的连接顺序与它们在产生式体中的顺序相同

基本思想：在适当的时候发出元素，保证其能被适当地拼接，