Question

很多编译程序采用的基于属性文法的语义处理过程称为什么

Answer 1

　　首先，我们给出语义属性的定义。
定义 5.1一文法符号X∈VN∪VT的语义性质称为该文法符号的语义属性(Semantic Attributes)，简称为属性。我们用A(X)表示X的所有属性的集合。每个属性表示X的一个特定性质，并可任意指定其取值范围。下面，我们将用X.a表示A(X)中的属性a。
由定义5.1可知，文法符号的属性就是它的语义性质。属性可表征诸如数、符号串、类型、存储空间和其它需表征的实体。就终结符号而言，它至少有一种属性，即词文。当然，它还可能具有其它属性，例如，对3.2.1中所定义的无符号数，单词“123”就是它的词文；而其数值和类型(整型)是它的另外两个属性。一般来说，终结符号的属性是其内在性质；当然也有些属性将从其它符号的属性中获取。例如，变量标识符的类型属性，将从类型定义语句中获取，也就是说，它是通过语法树从其它符号的属性中获取的。对非终结符号而言，其属性之值均须从其它符号的属性经计算而得，或者说，是由其它符号的属性定义的。
可见，各个文法符号的属性之间，可能存在某种依赖关系，这种依赖关系可用属性规则(语义规则)来定义。
定义 5.2设p:X0→X1X2…Xn∈P是文法G的一个产生式，则与p相关联的属性规则集合
定义 5.3对每个产生式p：X0→X1X2…Xn∈P，设属性定义性出现的集合为
AF(p)={Xi.a|Xi.a=f(Xk1.ak1,Xk2.ak2,…,Xkm.akm)∈R(p)，而0≤kj≤n}
若Xi是产生式左部的非终结符号(即i=0)，则称属性Xi.a是综合属性(Synthesized Attributes)；若Xi出现在产生式的右部(即1≤i≤n)，则称Xi.a是继承属性(Inherited Attributes)。
如果在一棵语法树中将每个结点均视为由若干个域组成的记录(或结构)，则可将其中的一些域用来存放相应文法符号诸属性之值，并可用属性来为这些域命名。通常我们将每个结点都标注相应属性值的语法树称为加注语法树(Annotated Syntax Tree)或染色树(Decorted Syntax Tree)。于是，由定义5.3可知：在加注语法树中，一个文法符号X在相应结点的综合属性之值，由其子结点的属性和(或)X的其它属性，通过相关属性规则经计算而得，故综合属性的求值在语法树中是按自下而上的方式进行的；X的继承属性之值则由X的父结点和(或)其它兄弟结点来定义,故继承属性的求值将按自上而下的方式进行。
在引入属性的概念之后，我们就可以定义属性文法了。
定义 5.4属性文法AG是一个形如
AG=(G,A,R,B)
的四元组，其中：G=(VN,VT,P,S)是已简化的前后文无关文法；A=∪X∈VA(X)是属性的有限集合；R=∪p∈PR(p)是属性定义规则的有限集；而B=∪p∈PB(p)是条件的有限集合，B(p)用于描述使规则R(p)有效的条件(请注意，并非每条规则R(p)都必须有条件B(p)。若B(p)缺省，则意味着无条件使用该规则)；且同时满足：
(1) 对G中任意两个不同的文法符号X和Y而言，属性集合A(X)和A(Y)不相交，即
A(X)∩A(Y)=(X≠Y)
(2) 在G的任意一个语法树中，对文法符号X的每一次出现，可用于计算X的每个属性Xa(Xa∈A(X))之值的规则至多有一条。
由定义5.4可知，属性文法实际上就是对前后文无关文法的一种拓广。另外，定义还表明，每个产生式中的任一文法符号的属性计算规则只能是惟一的，且任一文法符号的综合属性集与继承属性集不相交，即
AS(X)∩AI(X)=
其中：
AS(X)={X.a|p:X→α∈P,X.a∈AF(p)}
AI(X)={X.a|q:Y→μXυ∈P,X.a∈AF(q)}
下面，我们以一个简单赋值语句的文法为例，来说明属性文法的应用。为便于理解，我们用一英语单词(或词组)而不再像前几章那样用字母表示文法符号。并且约定，用大写字母开头的符号为非终结符号，而用小写字母开头的符号为终结符号。