本章介绍了语法制导翻译概念和技术，是在抽象层次上讲的。

• 翻译文法：在输入文法中插入语义动作符号（完成翻译任务的语义子程序）
• 属性翻译文法：文法符号（包括动作符号）可带有属性，并定义相应的属性求值规则，就成为属性翻译文法。比翻译文法能较细地描述翻译过程。（属性有综合属性和继承属性之分）

1 翻译文法(TG)和语法制导翻译

• 翻译的任务：把中缀表达式转化为逆波兰表示。

• 方法：在上述文法中插入相应的动作符号。如何加动作符号为经验决定

  例子

  
  

• 输入文法：未插入动作符号时的文法。
  由输入文法可以通过推导产生输入序列。

• 翻译文法：插入动作符号的文法。
  由翻译文法可以通过推导产生活动序列（输入序列&动作序列）

  例子

  

• 活动序列：由翻译文法推导出的符号串，由终结符和动作符号组成。

  • 从活动序列中，抽去动作符号则得输入序列（i+i)*i
  • 从活动序列中，抽去输入序列，则得动作序列。执行动作序列，则完成翻译任务：
    @i @i @+ @i @* => ii+i*

• 翻译文法是上下文无关文法，终结符号集由输入符号和动作符号组成。
  由翻译文法所产生的终结符号串称为活动序列。

  例子

  

• 符号串翻译文法：输入文法中的动作符号对应的语义子程序是输出动作符号标记@后的字符串的文法。

• 语法制导翻译：按翻译文法进行的翻译
  给定一个输入符号串，根据翻译文法获得翻译该符号串的动作序列，并执行该序列所规定的动作过程。

• 语法制导翻译的实现方法：
  在文法的适当位置插入语义动作符号。当按文法分析到动作符号时就调用相应的语义子程序，完成翻译任务。
  翻译文法所定义的翻译是由输入序列和动作序列组成的对偶集。
  

2 属性翻译文法 (ATG)

• 在翻译文法的基础上，我们可以进一步定义属性文法。
• 翻译文法中的符号，包括终结符、非终结符和动作符号均可带有属性，这样能更好地描述和实现编译过程。
• 属性可以分为两种：综合属性、继承属性

2.1 综合属性

• 综合属性用 表示
  表示自底向上，自右向左计算
  表示属性变量或属性值

2.2 继承属性

• 对于上述文法的说明语句：integer A, B1

• 该文法的翻译任务：将声明的变量填入符号表（语义）

• 完成该工作的动作符号：@set_table
  

• 填表时需要的信息：类型、名字、以及位置（可以用全程变量的指针）如何得到？

• 终结符（输入符号）的类型和名字在词法分析时得到，可设两个综合属性
  t中是类型值
  n是变量名
  填表动作符号也可带有属性：
  可从其前面的符号得到，称为继承属性，继承前面符号的值。
  变量表 同上

• 属性翻译文法
  

  例子

  
  

• 总结：输入文法 => （字符串）翻译文法 => 属性翻译文法

2.3 属性翻译文法的自顶向下翻译

2.3.1 L-属性翻译文法（L-ATG）

• L-属性翻译文法
  这是属性翻译文法中较简单的一种。其输入文法要求是LL(1)文法，可用自顶向下分析方法构造分析器。在分析过程中可进行属性求值。

  • LL(1)文法
    • 无左递归
    • A::=α|β，FIRST(α) ∩ FIRST(β) = Ф
    • 若β=> ε, 则FIRST(α) ∩ FOLLOW(A) = Ф
  • 特点：某个符号的继承属性只依赖于该符号左边的信息！

• L-属性翻译文法是带有下列说明的翻译文法：

  1. 文法中的终结符，非终结符及动作符号都带有属性，且每个属性都有一个值域。

  2. 非终结符及动作符号的属性可分为继承属性和综合属性。（终结符只能有综合属性）

  3. 开始符号的继承属性具有指定的初始值。

  4. 输入符号（终结符号） 的每个综合属性具有指定的初始值。

  5. 属性值的求值规则如下：
     继承属性——体现自顶向下，自左向右的求值特性。

     1. 产生式左部非终结符号的继承属性值，取前面产生式右部该符号已有的继承属性值。
        t 可以取 x 的值
     2. 产生式右部符号（非终结符、动作符号） 的继承属性值，用该产生式左部符号的继承属性或出现在该符号左部的符号的属性值进行计算
        a 可以用 t 和 b 算

     综合属性——体现自底向上，自右向左的求值特性。

     1. 产生式右部非终结符号的综合属性值，取其下部产生式左部同名非终结符号的综合属性值。
     2. 产生式左部非终结符号的综合属性值，用该产生式左部符号的继承属性或某些右部符号的（任意）属性进行计算。
     3. 动作符号的综合属性用该符号的继承属性或某些右部符号的（任意）属性进行计算。
        适合在自顶向下分析过程中求值

注意：

1. 终结符只有综合属性（它们由词法分析器提供）。
2. 非终结符和动作符号既可以有综合属性也可有继承属性。
3. 文法开始符号的所有继承属性作为属性计算前的初始值。

• 一般来说，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个求值规则。
• 属性求值规则中只能使用相应产生式中的文法符号的属性（这有助于在产生式范围内“封装”属性的依赖性）。
• 但出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性求值规则进行计算。它们由其它产生式的属性规则计算。

2.3.2 简单赋值形式的L-属性翻译文法(SL-ATG)

• 一般情况 x := f(y, z) x的属性值是y和z的属性值的函数
• SL-ATG: x := 某符号的属性值或常量
  例 x := y x, y, z := 17 —— 称为复写规则
• 为了实现上的方便，常希望文法符号的属性求值规则为上述简单形式的。为此，我们对现有的L-ATG的定义做一点改变，从而形成一个称为简单赋值形式的SL-ATG。
• 一个L-ATG被定义为简单赋值形式的(SL-ATG)，当且仅当满足如下条件:
  1. 产生式右部符号的继承属性是一个常量，它等于左部符号的继承属性值，或等于出现在所给符号左部某个符号的综合属性值。
  2. 产生式左部非终结符号的综合属性是一个常量，它等于其自身的继承属性值或等于右部某个符号的综合属性值。
• 目的：一个简单赋值形式的L-ATG除动作符号外，其余符号的属性求值规则右部是属性或是常量（——简单化）。

给定一个L-ATG ，如何找一个等价的简单赋值形式的L-ATG?

3 自顶向下语法制导翻译

先介绍翻译文法的自顶向下翻译，然后介绍属性翻译文法的自顶向下翻译。

3.1 翻译文法的自顶向下翻译——递归下降翻译器

按翻译要求，在文法中插入语法动作符号，在分析过程中调用相应的语义处理程序，完成翻译任务。

3.2 属性翻译文法的自顶向下翻译的实现——递归下降翻译器

我们把处理翻译文法的递归下降翻译器进行适当扩展，便可得到处理属性（翻译）文法的递归下降翻译器。

• 方法：对于每个非终结符号都编写一个翻译子程序（过程）。根据该非终结符号具有的属性数目，设置相应的参数。
  • 继承属性：声明为赋值形参
  • 综合属性：声明为变量形参
    
• 过程调用语句的实参：
  • 继承属性: 继承属性值（传实参值）
  • 综合属性: 属性变量名（传地址，返回时有值）
• 关于属性名的约定：
  1. 具有相同值的属性取相同的属性名。（这样可省去不少属性求值规则）
     
  2. 产生式左部的同名非终结符使用相同的属性名。（递归下降分析法规定每个非终结符只编写一个子程序!）
     具有简单赋值形式的属性变量名取相同的属性名，可删去属性求值规则。
     
     

如何构造属性文法的递归下降翻译器

例 1

下面通过一个例子，详细介绍如何构造属性文法的递归下降翻译器。（该文法应是具有L-属性的符号串翻译文法）

1. 对简单赋值形式的属性变量取相同的属性名，其求值规则可以删去。
   开始符号的继承属性 R = 7。
   
2. 设计递归下降程序
   1. 全局变量的过程声明
      
   2. 主程序
      
   3. 其它代码
      
      
      
      

例 2

构造将算术表达式翻译成四元组的属性翻译文法，并写出递归下降分析程序。由该属性翻译文法来描述翻译过程。

1. 翻译文法设计
   
2. 属性翻译文法的设计
   在翻译文法的基础上可设计其属性翻译文法，以便语义分析过程中生成完整的四元式，完成翻译。
   • 输入符号（操作数） 有一综合属性，它是该符号在数据区的地址。
   • 每个非终结符有一个综合属性，该属性是由它产生的代表该子表达式在数据区中的地址（中间结果）。
   • 动作符号有三个继承属性，它们分别是左右操作数和运算结果在数据区的地址