发布时间 : 星期二 文章编译原理作业集-第六章-修订更新完毕开始阅读8ec67fa4d1f34693daef3e32
编译原理作业集 第六章 属性文法和语法制导翻译
第六章 属性文法和语法制导翻译
本章要点
1. 属性文法，基于属性文法的处理方法； 2. S-属性文法的自下而上计算; 3. L-属性文法的自顶向下翻译； 4. 自下而上计算继承属性；
本章目标
掌握和理解属性方法、基于属性文法的处理方法、S-属性文法和自下而上计算、L-属性文法和自顶向下翻译、自下而上计算继承属性等内容。
本章重点
1．语法制导翻译基本思想。
2．语义规则的两种描述方法：语法制导的定义和翻译方案。语法制导的定义没有指明语义规则的计算次序，而翻译方案显式给出语义规则（或叫语义动作）的计算次序和位置。 3．基于属性文法的处理方法，综合属性定义（S属性定义）和L属性定义。
4．设计简单问题的语法制导定义和翻译方案，这是本章的重点和难点。这种设计可看成是一种程序设计，是一种事件驱动形式的程序设计，因此它比一般的编程要难得多。这里的事件是句子中各种语法结构的识别。
5．语义规则的三种计算方法：分析树方法、基于规则的方法和忽略规则的方法。 6．S属性的自下而上计算（边语法分析边属性计算，忽略规则的方法）。 7．L属性的自上而下计算（边语法分析边属性计算，忽略规则的方法）。 8．递归计算（先语法分析后属性计算，基于规则的方法）。
本章难点
1. 设计简单问题的语法制导定义和翻译方案；
作业题
一、单项选择题：
1. 文法开始符号的所有________作为属性计算前的初始值。
- 1 -
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM
编译原理作业集 第六章 属性文法和语法制导翻译
a. 综合属性 b. 继承属性 c. 继承属性和综合属性 d. 都不是
2. 对应于产生式A→XY继承属性Y.y的属性计算，可能正确的语义规则是________。
a. A.a:=f(X.x，Y.y)；b. )Y.y:=f(A.a，Y.y)；c. Y.y:=f(X.x)；d. A.a:=f(Y.y)；
3. 描述文法符号语义的属性有两种，一种称为__ __，另一种称为__ ___。
a. L-属性 b. R-属性 c. 综合属性 d. 继承属性
4. 出现在产生式________和出现在产生式________不由所给的产生式的属性计算规则进行计算，而是由其他产生式的属性规则计算或者由属性计算器的参数提供。
a. 左边的继承属性；b. 左边的综合属性；c. 右边的综合属性；d. 右边的继承属性
5. 描述文法符号语义的属性，综合属性值的计算依赖于分析树中它的 的属性值；
a. 父结点 b. 子结点 c. 兄弟结点 d. 父结点与子结点 e. 父结点与兄弟结点
6. 描述文法符号语义的属性，继承属性值的计算依赖于分析树中它的______的属性值。
a. 父结点 b. 子结点 c. 兄弟结点 d. 父结点与子结点 e. 父结点与兄弟结点
7. 一般来说，对出现在产生式右边的 和出现在产生式左边的 都必须提供一个计算规则。
a. 综合属性， b. 继承属性， c. L-属性， d. R-属性
8. 考虑非终结符A、B和C，其中A有一个继承属性a和一个综合属性b，B有综合属性c，C有继承属性d。产生式A→BC可能的属性计算规则中， 属性要在其它地方计算，不是在本产生式的属性计算规则中计算的。
a. C.d和A.b；b. A.a和A.b；c. A.a和B.c；d. C.d和A.a
9. 通常使用 的方法在每一个结点处使用语义规则计算综合属性的值。
a. 自顶向下，b. 自底向上，c. 从左到右，d. 从右到左；
10. S-属性文法的计算中，设当前的栈顶由指针top指示，假设综合属性刚好在每次归约前计算的。假定产生式为A?XYZ，相应的语义规则为A.a:=f(X.x, Y.y，Z.z)。 在把XYZ归约成A以前，属性Z.z的值放在val[top]中，Y.y的值放在val[top-1]中， X.x的值放在val[top-2]中。归约以后，A的状态存放在 中（即X的位置）。综合属性A.a的值存放在 中。
a. state[top]，val[top]； b. state[top-1]，val[top-1]； c. state[top-2]，val[top-2]； d. state[top-3]，val[top-3]；
11. 一个简单的翻译模式
E→TR
R→addop T {print(addop.lexeme)} R1|ε T→num {print(num.val)} addop→+|-
该文法的作用是 。
a. 把一个带加号和减号的前缀表达式翻译成相应的后缀表达式
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM
- 2 -
编译原理作业集 第六章 属性文法和语法制导翻译
b. 把一个带加号和减号的后缀表达式翻译成相应的前缀表达式 c. 把一个带加号和减号的后缀表达式翻译成相应的中缀表达式； d. 把一个带加号和减号的中缀表达式翻译成相应的后缀表达式；
12. 有一语法制导翻译如下所示:（第8章） S→bAb {print “1” } A→(B {print “2” } A→a {print “3” } B→Aa) {print “4” }
若输入序列为b(((aa)a)a)b，则采用自下而上的分析方法，则输出是 。
a. 32224441 b. 34242421 c. 12424243 d. 34442212
13. 在属性文法中，终结符只具有 属性。
a. 传递 b. 继承 c. 抽象 d. 综合
14. 设，有以下左递归翻译模式
A→A1Y {A.a:=g(A1.a,Y.y)} A→X {A.a:=f(X.x)}
它的每一个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数。消除左递归，再考虑语义动作，翻译模式变为：
A→X { R.i:=f(X.x) } R { A.a:=R.s }
R→Y { R1.i:=g(R.i, Y.y) } R1 R→ε a. { R.s:=R1.s } ，{ R.s:=R.i }；b. { R.s:=R.i }，{ R.s:=R1.s }； c. { R.s:=R1.i } ，{ R.s:=R.s }；d. { R.s:=R.s }，{ R.s:=R1.i }；
15. ________________可用于一遍扫描的自上而下分析，而________________则适合于一遍扫描的自下而上分析。
a. S-属性文法，L-属性文法； b. 继承属性文法，综合属性文法； c. L-属性文法，S-属性文法； d. 综合属性文法，继承属性文法；
一．答案：1. b；2. c；3.c，d； 4. a， c；5. b；6. e；7. b，a；8. c；9. b；10. a；11. d；12. b； 13. d；14. a；15. c；
二、填空题：
1. ________属性用于“自下而上”传递信息；而________属性用于“自上而下”传递信息。 2. 如果一属性文法不存在属性之间的________，那么称该文法为良定义的。 3. 按照________________的编译程序模型来理解语法制导翻译方法，所谓的语法制导翻译，直观上说，就是为文法中每个_____________配上一组语义规则，并在________________的
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM
- 3 -
编译原理作业集 第六章 属性文法和语法制导翻译
同时执行这些语义规则。 4. 下面语义规则：
T?T1*F T?val:=T1 ?val*F?val
，改写成翻译模式为： 。 5. S－属性文法中的每个文法符号，只含有________属性。
6. 与树遍历的属性计算方法不同，一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语法 分析构造语法树之后进行属性计算。 ________________可用于一遍扫描的自上而下分析，而________________则适合于一遍扫描的自下而上分析。
7. 已知表达式文法的一条语法规则E?E1+T，对每个文法符号引入nptr属性，可以写出为该文法建立抽象语法树的、对应于这条规则的语义规则为： 。 8. 在S-属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时 。
9. 通过在基础文法中新引入非终结符M，加入形式为____________的新的产生式，可以使嵌入的语义动作出现在产生式的末尾。
10. 属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内“封装”属性的依赖性。然而，出现在产生式左边的 和出现在产生式右边的 不由所给的产生式的属性计算规则进行计算，它们由其他产生式的属性规则计算或者由属性计算器的参数提供。
11. 语义规则可能产生副作用（如产生代码），也可能不是变元的严格函数（入某个规则给出可用的下一个数据单元的地址）。这样的语义规则通常写成 。 12. 我们可以用一个 来跟踪一个标识符，看它是出现在赋值号的左边还是右边，以确定是需要这个标识符的地址还是值。
13. 在自下而上语法分析中，若一个产生式匹配输入串成功，或者，在自下而上分析中，当一个产生式被用于进行归约时， ，完成相关的语义分析和代码产生工作。
14. S-属性文法自下而上计算属性时，在分析栈中使用一个附加的域val来存放综合属性值。文法符号是隐含在state中而不是存储在栈中。当把文法符号放入栈中时，那么当第i个state对应符号为A时，val[i]中就存放 。
15. 对于一个属性文法，?A→X1X2…Xn?P, 其每个语义规则中的每个属性都是一个综合属性;或者，Xj(1?j ? n)是一个继承属性，这个继承属性仅依赖于: ① ② 则，该属性文法是L-属性文法。
二．答案
1. 综合，继承；2. 循环依赖关系；3. 一遍扫描，产生式，语法分析；4. T?T1*F {T?val:=T1 ?val*F?val}；6. L－属性文法，S－属性文法；7. E?nptr :=mknode(′+′,E1 ? nptr,T ?nptr)；8. 对属性进行计算；9. M→?；10. 继承属性，综合属性；11. 过程调用或过程段；12. 继承属性；13. 此产生式相应的语义规则就被计算；14. 语法树中与结点A对应的属性值；15. 产生式中Xj的左边符号X1，X2，…Xj-1的属性；A的继承属性。
西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM - 4 -