定义: 个语法制导的翻译模式是一个五元组T=(N,Z,△, R,S),其中 (1)N是非终结符的有限集。 (2)∑是有限的输入字母表。 (3)△是有限的输出字母表。 (4)R是形如A→>a,B的规则的有限集,其中 a∈(NU∑)B∈(NU△)*且β中那组非终结符是a中那 组非终结符的置换。 (5)S是N中一个特别的非终结符,即开始符
定义： 一个语法制导的翻译模式是一个五元组T=(N,,， R,S),其中 (1) N是非终结符的有限集。 (2) 是有限的输入字母表。 (3) 是有限的输出字母表。 (4) R是形如A→,的规则的有限集,其中 ∈(N∪ )*,∈(N∪ )*且中那组非终结符是中那 组非终结符的置换。 (5) S是N中一个特别的非终结符，即开始符
定义: 若T=(N,∑,△,R,S)是SDTS,(T)则称为语法制导的翻 译(SDT),文法G=(N,Σ,P,S),其中P={A→aA→αxB属 于R),称为 SDTS T的基础(或输入)文法。文法 G0=(N,△,P",S),其中P={A>βA→>a,β属于R},称 为T的输出文法。 把语法制导的翻译方法看成是将输入文法G中的 推导树变换成输出文法G0中的推导树。给了输入句子x, 可以按如下方式得到x的一个翻译:先为推导x构造 棵推导树,再变换该树到输出文法中的一棵树,然后 取此输出树的边缘作为x的一个翻译
定义： 若T= (N,,, R,S)是SDTS,(T)则称为语法制导的翻 译(SDT)，文法Gi=(N, ,P,S)，其中P={A→|A→,属 于R)，称为SDTS T的基础（或输入）文法。文法 G0=( N, ,P,S),，其中P ={A→ | A→,属于R} ，称 为T的输出文法。 把语法制导的翻译方法看成是将输入文法Gi中的 推导树变换成输出文法G0中的推导树。给了输入句子x， 可以按如下方式得到x的一个翻译：先为推导x构造一 棵推导树，再变换该树到输出文法中的一棵树，然后 取此输出树的边缘作为x的一个翻译
语义制导翻译中的规则A->O,β 对应于每一个文法产生式A→a都有 与之相关联的一套语义描述β 属性文法( attribute grammar)是一个三元 组A=(G,VF) 属性文法可以看作是关于语言翻译的高级 规范说明,其中隐去实现细节,使用户 从明确说明翻译顺序的工作中解脱出来
语义制导翻译中的规则A→, 对应于每一个文法产生式A 都有 与之相关联的一套语义描述 属性文法(attribute grammar)是一个三元 组:A=(G,V,F) 属性文法可以看作是关于语言翻译的高级 规范说明，其中隐去实现细节，使用户 从明确说明翻译顺序的工作中解脱出来
语法制导翻译实现 从概念上讲,语法制导翻译即基于属性文 法的处理过程通常是这样的:对单词符 号串进行语法分析,构造语法分析树, 然后根据需要遍历语法树并在语法树的 各结点处按语义规则进行计算 输入符号串 →分析树 →属性依赖图 →语义规则的计算顺序
语法制导翻译实现 从概念上讲，语法制导翻译即基于属性文 法的处理过程通常是这样的：对单词符 号串进行语法分析，构造语法分析树， 然后根据需要遍历语法树并在语法树的 各结点处按语义规则进行计算 输入符号串 → 分析树 → 属性依赖图 → 语义规则的计算顺序
依赖图 由称为依赖图的一个有向图描述分析树中的继承属性和 属性中间的相互依赖关系。 依赖图的构造算法: for分析树中每一个结点ndo for结点的文法符号的每一个属性ado 为a在依赖图中建立一个结点 for分析树中每一个结点ndo for结点n所用产生式对应的每一个语义规则 b: f(cl, C2,... ck) do for i: =1 to k do 从c结点到b结点构造一条有向边
依赖图 由称为依赖图的一个有向图 描述分析树中的继承属性和 属性中间的相互依赖关系。 依赖图的构造算法： for分析树中每一个结点n do for 结点的文法符号的每一个属性a do 为a在依赖图中建立一个结点； for 分析树中每一个结点n do for结点n所用产生式对应的每一个语义规则 b:=f(c1,c2,…ck) do for i :=1 to k do 从ci结点到b结点构造一条有向边