学习地址:
属性文法
概念
属性文法:
- 也称作属性翻译文法
- 以上下文无关文法为基础
- 为每个文法符号(终结符或非终结符)配备若干相关的 “值”(称为属性),代表与文法符号相关的信息,如类型、值、代码序列、符号表内容等。
- 对于文法的每个产生式都配备了一组属性的语义规则,对属性进行计算和传递。
综合属性:
- 自下而上传递信息
- 从语法规则角度看:根据右部候选式中的符号的属性计算左部被定义符号的综合属性
- 从语法树角度看:根据子节点的属性和父节点自身的属性计算父节点的综合属性
继承属性:
- 自上而下传递信息。
- 从语法规则角度看:根据右部候选式中的符号的属性和左部被定义符号的属性计算右部候选式。
- 从语法树角度看:根据父节点和兄弟结点的属性计算子节点的继承属性。
属性依赖
属性依赖:
对于没和产生式 $$A \rightarrow \alpha $$ 都有一套与之相关联的语义规则,每条规则的形式为:$$b := f(c_1, c_2, … c_k)$$,则我们说:属性 b 依赖于属性 $$c_1, c_2, …, c_k$$。其中有两种可能性:
b 是 A 的一个综合属性并且 $$c_1, c_2, …, c_k$$ 是产生式右边文法符号的属性
b 是产生式右边某个文法符号的一个继承属性并且 $$c_1, c_2, …, c_k$$ 是 A 或产生式右边任何文法符号的属性
终结符只有综合属性,由词法分析器提供。
非终结符既可以有综合属性也可以有继承属性,文法开始符号的所有继承属性作为属性计算前的初始值。
语义规则:
- 对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性。
- 出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给产生式的属性计算规则进行计算,由其他产生式的属性计算规则进行计算或者由属性计算器的参数提供。
- 语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等。
属性计算
由源程序的语法结构所驱动的处理办法就是语法制导翻译法。
基于属性文法的处理办法:依赖图、树遍历、一遍扫描。
依赖图
在一棵语法树中,结点的继承属性和综合属性之间的相互依赖关系可以用依赖图来描述。
依赖图的构造:
- 依赖图中为每一个属性设置一个结点;
- 如果属性 b 依赖与属性 c,则从属性 c 的结点有一条有向边链接到属性 b 的结点。
S-属性文法
S-属性文法:只含有综合属性的文法。
适合一遍扫描的自下而上分析。
计算(在自下而上的分析器分析输入符号串的同时计算综合属性):
- 在分析栈中添加一个附加域存放综合属性值
L-属性文法
L-属性文法:继承属性依赖父节点,或左兄弟结点。