【Compilation Principle】Semantic Analysis

发表于 | 分类于 ， | | 阅读次数:

属性文法

如果X是一个文法符号，a是X的一个属性，那么我们把与X关联的a的值记作X.a

在语法制导语义(syntax-directed semantics)中，属性直接与语言的文法符号相联系(终结符号或非终结符号)，若有一个属性的集合$a_1 , . . . , a_k$ ，语法制导语义的原理应用于每个文法规则$X_0→X_1 X_2 . . . X_n$（这里$X_0$ 是一个非终结符号，其他的$X_i$都是任意符号），每个文法符号$X_i$ 的属性$X_i .a_j$ 的值与规则中其他符号的属性值有关。每个关系用属性等式(attribute equation)或语义规则(semantics rule) 表示，形式如下：
$$
X_i .a_j = f_{ij} (X_0.a_1 , . . . , X_0.a_k ，X_1.a_1 , . . . , X_1.a_k , . . . , X_n .a_1 , . . . , X_n .a_k )
$$
image-20200615113519905

eg.

number → number digit | digit
digit → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

属性文法：

image-20200615113808216

语法树：

image-20200615113824187

相关图（associated dependency graph）

表示属性计算时值的传递关系（有向无环图DAG），计算顺序遵循拓扑排序

image-20200615142459552

合成和继承属性

  • 综合属性(synthesized)：在语法树中所有的相关都从子节点指向父节点。

    等价地，给定一个文法规则$A →X_1 X_2 . . . X_n $，左边仅有一个a 的相关属性等式有以下形式$A.a = f (X_1.a_1，. . . ，X_1 .a_k，. . . ，X_n .a_1，. . . ，X_n .a_k )$。

    一个属性文法中所有的属性都是合成的，就称作S-属性文法(S-attributed grammar)。

    S属性文法的属性计算可以通过对语法树自底向上的后续遍历来进行

    1
    2
    3
    4
    5
    6
    procedurepostEval(T:treenode);
    begin
    	foreachchildCofTdo
    	postEval(C);
    	computeallsynthesizedattributesofT;
    end

  • 继承属性(inherited)：一个属性如果不是合成的，则称作继承属性

    • inheritance from parent to siblings
    • inheritance from sibling to sibling

    image-20200615145554033

    使用前序遍历或者前序中序遍历相结合的方式来进行属性计算

    1
    2
    3
    4
    5
    6
    procedurepreEval(T:treenode);
    begin
    	foreachchildCofTdo
    		computeallinheritedattributesofC;
    	preEval(C);
    end;

语法分析时的属性计算

L-属性文法（L-attributed）：如果对每个继承属性$a_j$和每个文法规则$X_0 →X_1 X_2 . . . X_n$，$a_j$ 的相关等式都有以下形式$X_i .a_j = f_{i j} (X_0 .a_1 , . . . , X_0 .a_k ，X_1 .a_1 , . . . , X_1 .a_k ，. . . ，X_{i -1} .a_1 , . . . , X{i -1} .a_k )$，也就是说，在$X_i$ 处$a_j$ 的值只依赖于在文法规则中Xi 左边出现的符号$X_0 , . . . , X_{i -1}$ 的属性。

S-属性文法是L-属性文法的特例

L-属性文法的继承属性不依赖于综合属性

  • LR分析中综合属性的计算：LR分析程序中通常由一个值栈存储综合属性（如果对每个文法符号有不止一个属性，可能是联合或结构）。值栈将和分析栈并行操作，根据属性等式每次在分析栈出现移进或规约来计算新值。

    image-20200615154418372

    image-20200615154428144

  • 在LR分析中继承前面计算的综合属性：因为LR分析使用从左向右的赋值策略，因为这些值已经被压进了值栈，所以与规则右边非终止符相关的动作可以把符号的综合属性使用到规则的左边。为了简要说明这一点，可考虑产生式选择$A→B C$，假设$C$有一个继承属性$I $和以某种方式依赖于$B：C.i = f (B.s) $的综合属性$s$。通过在$B$ 和$C$ 之间引入一个$\epsilon$-产生式安排值栈栈顶的存储，在识别C 之前的$C.i$ 值可以存进一个变量中

    image-20200615155447855

通常在计算属性时，利用参数和返回的函数值与属性值进行通信，而不是把它们作为字段存储在语法树的记录结构中。

给定一个属性文法，通过适当地修改文法，而无须改变文法的语言，所有的继承属性可以改变成合成属性。

eg.

decl → type var-list
type → int | float
var- list → id , var- list | id

其中dtype属性是继承属性，重写如下：

decl → var-list id
var- list → var- list id, | type
type → int | float

image-20200615163842027

dtype属性的依赖图：

image-20200615163923025

在图中父节点或兄弟节点值的两个id.dtype值的依赖用虚线画出。而这些依赖的出现违反了在这个属性文法中没有继承属性的要求，事实上这些依赖总是留在语法树中(即是非递归的)，并且可能由相应的父节点的操作实现。因此，这些操作不看成是继承的。

符号表

结构

  • 线性表

    insert: O(1), lookup: O(n), delete: O(n)

    效率不高，可以应用在不追求效率的编译器上

  • 搜索树（二叉树、AVL树、B树…）

    delete非常麻烦

    少见

  • 哈希表

    insert, lookup, delete都在O(1)时间

    稳定性好，效率高，首选

哈希表中每一项可以是一个桶（桶相当于线性表，用于解决冲突），桶的大小应当是质数

哈希函数：

image-20200615162944658

α的一种合理的选择是2的幂，这样乘法可以通过移位来完成

类型检查

说明等价(declaration equivalence)：

image-20200615175632759