编译原理作业集-第六章-修订

编译原理作业集 第六章 属性文法和语法制导翻译

第六章 属性文法和语法制导翻译

本章要点

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 -

编译原理作业集 第六章 属性文法和语法制导翻译

三、判断题：

1. 非终结符只有综合属性，由词法分析器提供。（ ） 2. S—属性文法一定是L—属性文法。（ ） 3. 只含有综合属性的属性文法是S-属性文法。（ ） 4. 只含有继承属性的属性文法称为-L属性文法。( )

5. 语法制导翻译可以基于语法分析树，也可以基于抽象语法树，两种情况所采用的基本方法是一样的。（ ）

6. 翻译模式既适于自顶向下分析，又适于自底向上分析。（ ） 7. 用于自顶向下分析的翻译模式，其基础文法中不能含有左递归。（ ） 8. 在基础文法中增加标记非终结符不会导致新的语法分析冲突。（ ） 9. 对L－属性文法，不用显式构造语法树就可以实现翻译。（ ） 10. 在翻译模式中，和文法符号相关的属性和语义规则（语义动作），用花括号括起来，插入到产生式右部或左部的合适位置上。（ ） 11. 语法制导定义中文法符号的一个属性，既可以是综合属性，同时又可以是继承属性。（ ） 12. 在抽象语法树中，操作符和关键字都不作为叶子结点出现，而是把它们作为内部结点。（ ）

13. 一般来说，语法制导翻译是基于语法分析树的，基于抽象语法树无法进行语法制导翻译。（ ）

14. 在必要的时候引进标记非终结符，可以实现LR分析过程中对L-属性文法进行计算。虽然任何LL(1)文法也是LR(1)文法，但是，当标记非终结符加入到LL(1)文法时可能会引起分析冲突。（ ）

15. 尽管把和文法符号相关的属性和语义动作用花括号括起来插入到了产生式右部的合适位置上，翻译模式还是不能给出使用语义规则进行计算的顺序。

三．答案：1. ×；2. ?；3. ?；4. ×；5. ?；6. ?；7. ?；8. ×；9. ?；10. ×；11. ×；12. ?；13. ×；14. ×；15. ×；

四、名词解释：

1. 属性，属性文法，综合属性，继承属性； 2. 语法制导翻译法； 3. 属性依赖图；

4. S－属性文法，L－属性文法； 5. 翻译模式；

四．答案：

1. 为每个文法符号（终结符或非终结符）所配备的、代表与文法符号相关信息的“值”，称为文法符号的属性。

在上下文无关文法的基础上，给每个文法符号配备相关属性，并对每个产生式配备一组称为语义规则的属性计算规则，所形成的文法称属性文法。

在一个属性文法中，对应于每个产生式A→?都有一套与之相关的形式为b:=f(c1，c2，…，ck)的语义规则，这里f是一个函数：

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM

- 5 -

编译原理作业集 第六章 属性文法和语法制导翻译

（1）若b是A的一个属性，且c1，c2，…，ck是产生式右边文法符号的属性，则称b是A的综合属性；

（2）若b是产生式右边某个文法符号的一个继承属性，且c1，c2，…，ck是A或者产生式右边任何文法符号的属性，则称若b是该文法符号的继承属性。

2. 基于属性文法的处理过程，首先对单词符号进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。这种由源程序的语法结构所驱动的翻译方法称语法制导翻译法。

3. 把一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系用一个有向图来描述，这个有向图称为属性依赖图。

4. 仅仅使用综合属性的属性文法称为S－属性文法。 如果一个属性文法，其每个语义规则中文法符号的每个属性，或者是综合属性，或者是一个仅依赖于该文法符号左边符号（包括箭头左边的那个非终结符）的继承属性，则称该熟悉该属性文法是L－属性文法。

5. 对于一个上下文无关文法的产生式，把和文法符号相关的属性和语义规则，用花括号｛｝括起来插入到产生式右部的合适位置上，从而得到语法制导翻译的另一种描述形式，称为翻译模式。

五、简答题：

1. 一般情况下，为什么语义分析部分仅产生中间代码？

2. 什么是语法制导翻译？为什么把这种方法叫语法制导翻译？ 3. 给定一个L－属性文法，建立翻译模式要满足哪些条件？ 4. 什么叫基于属性文法的处理方法？

5. 如何从翻译模式中去掉嵌入在产生式中间的动作？

五．答案：

1. 一般情况下，语义分析部分仅产生中间代码，其原因是： （1）可使难点分解，分别解决；

（2）可对语义分析产生的中间代码进行优化，以产生高效率的目标代码；

（3）语义分析通常与机器无关，目标代码往往与机器有关。把语义分析与目标代码生成分开，可让一个语义分析程序适用于多个目标代码生成程序。

2. 所谓语法制导翻译，是指在语法规则的指导下，通过语义规则，完成对输入符号串的翻译。 由于使用属性文法时把语法规则和语义规则分开，但在使用语法规则进行推导或归约的同时又使用这些语义规则来指导翻译与最终产生目标代码，所以称为语法制导翻译。

3. 当只需要综合属性的时候，为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。

如果既有综合属性又有继承属性，在建立翻译模式时要满足三个条件：

（1）产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来； （2）一个动作不能引用这个动作右边的符号的综合属性； （3）产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算，

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM

- 6 -

编译原理作业集 第六章 属性文法和语法制导翻译

计算这种属性的动作通常放在产生式右端的末尾。

六、应用题：

1. 欲打印表达式(4*7+1)*2的值。写出属性文法，根据该属性文法建立一棵带注释的分析树，并在该分析树上用箭头标出属性计算次序。 答案：1. 产生式 L?En E ?T T ?T1*F T?F F?(E) F?digit

E?E1+T 语义规则 print(E.Val) E.Val=E1.Val+T.Val E.Val=T.Val T.Val=T1.Val+F.Val T.Val=F.Val F.Val=E.Val F.Val=digit.lexVal

2. 已知上下文无关文法： E→E+T E→E-T E→T T→(E) T→id T→num

已知表达式((a)+(b))。不对文法进行修改，写出为表达式建立抽象语法树的属性文法；并画

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM

- 7 -

编译原理作业集 第六章 属性文法和语法制导翻译

出带注释的语法分析树来描绘抽象语法树的构造。 2. 答案： 产生式 E?E1+T E ? E1-T E ? T T ?(E) T ? id T ? num

根据该语法制导定义建立表达式((a)+(b))的分析树和抽象语法树：

语义规则 E.nptr:=mknode(?+?，E1.nptr，T.nptr) E.nptr :=mknode(?-?，E1.nptr，T.nptr) E.nptr :=T.nptr T.nptr :=E.nptr T.nptr :=mkleaf(id，id.entry) T.nptr :=mkleaf(num，num.val)

3. 已知上下文无关文法： E→E+T E→E-T E→T T→(E) T→id T→num

已知表达式((a)+(b))。采用自顶向下的翻译模式，写出构造抽象语法树的、消除了左递归的翻译模式，并画出带注释的语法分析树来描绘抽象语法树的构造。 3. 答案：翻译文法

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM - 8 -

编译原理作业集 第六章 属性文法和语法制导翻译

E?E1+T {E.val:=E1.val+T.val} E?E1-T ｛E.val:=E1.val-T.val｝ E?T {E.val:=T.val} T?(E) ｛T.val:=E.val｝ T?num ｛T.val:=num.val} 消除左递归的翻译文法： E→T {R.i:=T.val} R {E.val:=R.s｝ R→＋ T｛R1.i:=R.i+T.val} R1{R.s:=R1.s} R→- T｛R1.i:=R.i-T.val} R1{R.s:=R1.s} R→ε{R.s:=R.i} T→（ E ）{T.val:=E.val} T→num{T.val:=num.val}

4. 试给出把中缀表达式转换成没有多余括号的中缀表达式的语法制导定义。例如，由于+和*都是左结合的，((a*(b+c))*(d))可以写成a*(b+c)*d。 4. 答案；

设置下面的函数和属性：

expr1||expr2：把表达式expr2拼写在表达式expr1后面。

- 9 -

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM

编译原理作业集 第六章 属性文法和语法制导翻译

deletp(expr)：去掉表达式expr左端的?（?和右端的?)?。

E.expr，T.expr，F.expr：属性变量，分别表示E，T，F的表达式。 E.add，T.add，F.add：属性变量，若为true，则表示其表达式中外层有?＋?号，否则无?＋?号。

E.pmark，T.pmark，F.pmark：属性变量，若为true，表示E，T，F的表达式中左端为?（?，右端是?）?。

语法制导定义如下： 产生式 语义规则

E → E1 +T if(T.pmark==true)

THEN E.expr=E1.expr||'+'||deletep(T.expr) ELSE E.expr:=E1.expr||'+'||T.expr; E.add:=true; E.pmark:=false;

E → T if(T.pmark==true)

THEN E.expr:=deletep(T.expr) ELSE E.expr:=T.expr; E.add:=T.add; E.pmark:=false;

T → T1*F T.expr:=T1.expr||'*'||F.expr;

T.add:=false; T.pmark:=false;

T → F T.expr:=F.expr;

T.add:=F.add;

T.pmark:=F.pmark;

F → (E) if(E.add==false)

THEN BEGIN F.expr:=E.expr; F.add:=false; F.pmark:=false; END

ELSE BEGIN

F.expr:='('||E.expr||')'; F.add:=true; F.pmark:=true; END;

F → id F.expr:=id.lexval;

F.add:=false; F.pmark:=false;

5. 下面文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时,结果为整数，否则为实数。 E→E+T | T

T→num.num | num

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM

- 10 -

编译原理作业集 第六章 属性文法和语法制导翻译

产生式 E → TR 语义规则 R.itype:=T.type; R.ipf:=T.pf; E.pf:=R.spf; E.type:=R.stype; if(R.itype==int) AND (T.type==int) THEN R1.itype:=int ELSE BEGIN R1.itype:=real; if(R.itype==real) AND (T.type==int) THEN T.pf:='inttoreal'||T.pf ELSE if(R.itype==int)AND(T.type==real) THEN R.ipf:='inttoreal'||R.if END; R1.ipf:='+'||R.ipf||T.pf; R.stype:=R1.stype; R.spf:=R1.spf; R.stype:=R.itype; R.spf:=R.ipf; T.type:=int; T.pf:=int.lexval; R → +TR1 R → ε T → num T → num.num T.type:=real; T.pf:=real.lexval; 注： R.ipf是R的继承属性，是它的前缀表示。R.spf是R的综合属性，是它的前缀表示。

10. 给出一个检查同一个标识符不在标识符表中出现两次的翻译模式。

10. 答案：设计两个函数lookup(name)和enter(name,type)。lookup(name)查找符号表，若查到，则返回name在符号表中的地址；否则返回NULL。enter(name,type)在符号表中建立name的符号表项，并填写上name的类型type。翻译模式如下：

D → T {L.in:=T.type} L L → {L1.in:=L.in}

L1,id {if(lookup(id.name)) then error

else enter(id.name,L.in)} L → id {if(lookup(id.name)) then error

else enter(id.name,L.in)} T → int {T.type:=int} T → real {T.type:=real}

11. 假设说明是由下列文法产生的： D→id L L→,id L|:T T→ingeger |real

（1）建立一个翻译模式，把每一个标识符的类型加入到符号表中。 （2）从（1）中的翻译模式构造一个预翻译程序。

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM

- 16 -

编译原理作业集 第六章 属性文法和语法制导翻译

11.答案： (1) 翻译模式如下：

D → id L {addtype(id.entry,L.type)}

L → , id L1 {L.type:=L1.type; addtype(id.entry,L.type)} L → : T {L.type:=T.type} T → integer {T.type:=integer} T → real {T.type:=real}

(2) 预测翻译程序由如下过程组成： PROCEDURE D;

VAR L.type:(integer,real); id.entry:^id-entry; BEGIN

id.entry:=id.lexval; match(id); L.type:=L;

addtype(id.entry,L.type) END;

FUNCTION L:(integer,real);

VAR L.type,L1.type:(integer,real); id.entry:^id-entry; BEGIN

if(lookahead==',') THEN BEGIN match(','); match(id);

id.entry:=id.lexval; L1.type:=L; L.type:=L1.type;

addtype(id.entry,L.type); END

ELSE BEGIN match(':'); L.type:=T; END;

return(L.type); END;

FUNCTION T:(integer,real); VAR T.type:(integer,real); BEGIN

if(lookahead=='integer') THEN BEGIN match(integer); T.type:=id.lexval

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM

- 17 -

编译原理作业集 第六章 属性文法和语法制导翻译

END ELSE

if(lookahead=='real') THEN BEGIN match(real);

T.type:=id.lexval; END;

ELSE ERROR; return (T.type); END;

12. 已知关于盒子大小和高度的属性文法如下： 产生式 S?B 语义规则 B.ps:=10 S.ht:=B.ht B1.ps:=B.ps B2.ps:=B.ps B.ht:=max(B1.ht,B2.ht) B ? B1 B2 B ? B1 sub B2 B1.ps:=B.ps B2.ps:=shrink(B.ps) B.ht:=disp(B1.ht,B2.ht) B ? text B.ht:=text.h*B.ps

下面的文法是上表中上下文无关文法的无二义性形式，其中的花括号｛ ｝只用于把盒子分组，并将在翻译过程中被消除。 S→L L→LB|B B→B sub F|F F→{L}|text

（1）用上面的文法修改上表中的语法制导定义。 （2）把（1）中的语法制导定义转化成翻译模式。 （3）消除翻译模式中的左递归。

12. (1) 对于F1 sub F2 sub F3,其最左推导和分析树如下： S => L => B

=> B sub F3

=> B sub F2 sub F3 => F1 sub F2 Sub F3

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM - 18 -

编译原理作业集 第六章 属性文法和语法制导翻译

显然，F3.ps:=shrink(F2.ps); F2.ps:=shrink(F1.ps);

为此，为B设一个综合属性B.pt，其值等于其下标F的继承属性F.ps。语法制导定义如下：

产生式 S → L L → B L → L1B 语义规则 L.ps:=10; S.ht:=L.ht; B.ps:=L.ps; L.ht:=B.ht; L1.ps:=L.ps; B.ps:=L.ps; L.ht:=max(L1.ht,B.ht); B1.ps:=B.ps; F.ps:=shrink(B1.pt); B → B1 sub F B.ht:=disp(B1.ht,F.ht); B.pt:=F.ps; B → F F → {L} F → text F.ps:=B.ps; B.ht:=F.ht; B.pt:=B.ps; L.ps:=F.ps; F.ht:=L.ht; F.ht:=text.h*F.ps (2) 翻译模式如下：

S → {L.ps:=10} L {S.ht:=L.ht} L → {B.ps:=L.ps} B {L.ht:=B.ht}

L → {L1.ps:=L.ps} L1 {B.ps:=L.ps} B {L.ht:=max(L1.ht,B.ht)}

B → {B1.ps:=B.ps} B1 sub {F.ps:=shrink(B1.pt)} F {B.ht:=disp(B1.ht,F.ht); B.pt:=F.ps}

B → {F.ps:=B.ps} F {B.ht:=F.ht; B.pt:=B.ps} F → {L.ps:=F.ps} {L}{F.ht:=L.ht} F → text {F.ht:=text.h*F.ps}

（3）S → {L.ps:=10; L.iht:=0} L {S.ht:=L.ht}

L → {B.ps:=L.ps} B {L.ht:=max(L.iht,B.ht)}

L → {B.ps:=L.ps} B {L1.iht:=max(L.iht,B.ht); L1.ps:=L.ps} L1 {L.ht:=L1.ht} B → {F.ps:=B.ps} F sub {B1.ps:=shrink(B.ps)} B1 {B.ht:=disp(F.ht,B1.ht)} B → {F.ps:=B.ps} F {B.ht:=F.ht} F → {L.ps:=F.ps} {L} {F.ht:=L.ht} F → text {F.ht:=text.h*F.ps}

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM

- 19 -

编译原理作业集 第六章 属性文法和语法制导翻译

13. 自定向下翻译模式中，有下面翻译模式： A→A1Y {A.a:=g(A1.a,Y.y)} A→X {A.a:=f(X.x)} 该翻译模式消除左递归后变为： A→X { R.i:=f(X.x) } R { A.a:=R.s } R→Y { R1.i:=g(R.i,Y.y) } R1 { R.s:=R1.s } R→ε { R.s:=R.i }

下面要求扩充上面消除左递归的转换，使上面的翻译模式中的非终结符号A允许：（1）由复写规则决定的继承属性。 （2）继承属性。

13. 答案：

(a) 假设基础文法含左递归的翻译模式如下：

A → {A1.i:=A.i} A1 {Y.i:=A.i} Y {A.a:=g(A1.a,Y.y)} A → {X.i:=A.i} X {A.a:=f(X.x)}

消除基础文法左递归后的翻译模式如下：

A → {X.i:=A.i} X {R.i:=f(X.x); R.yi:=A.i} R {A.a:=R.s}

R → {Y.i:=R.yi} Y {R1.i:=g(R.i,Y.y); R1.yi:=R.yi} R1 {R.s:=R1.s} R → ε {R.s:=R.i}

属性R.yi用于传递A.i给Y。

(b) 设基础文法含左递归的翻译模式如下：

A－> {A1.i:=h1(A.i)} A1 {y.i:=h2(A.i)} Y {A.a:=g(A1.a,Y.y)} A → {X.i:=h3(A.i)} X {A.a:=f(X.x)}

考虑XY1Y2Y1，其继承属性的计算如下：

消除基础文法中的左递归后，基础文法为： A → XR R → YR | ε

继承属性的计算如下图所示：

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM - 20 -

编译原理作业集 第六章 属性文法和语法制导翻译

当识别出X后，并不能计算出X的继承属性，因而，也就无法计算有关X的其他属性。只好把X的源表示或中间表示作为继承传给R，继续沿R传下去，然后再作为综合属性传回来。直到能计算出X.i,再对X的成分进行翻译。Y1,Y2,Y3的翻译思想和X类似，具体的翻译模式省略。

14. 对于带有继承属性的自底向上的分析和翻译，使用标记非终结符号来保存继承属性的值于分析栈中可预定的位置上。如果这样的值放在与分析栈分开的栈中，就可能需要较少的标记非终绪符号。

已知数学格式语言EQN的所有继承属性都由复写规则赋值的属性文法如下： 产生式 S?LB L?? B?B1MB2 B?B1subNB2 语义规则 B.ps:=L.s S.ht:=B.ht L.s:=10 B1.ps:=B.ps M.i:=B.ps B2.ps:=M.s B.ht:=max(B1.ht,B2.ht) B1.ps:=B.ps N.i:=B.ps B2.ps:=N.s B2.ht:=disp(B1.ht,B2.ht) B.ht:=text.h*B1.ps M.s:=M.i N.s:=shrink(N.i) B?text M?? N??

（1）把上表中的语法制导定义转化为翻译模式。

（2）修改（1）中的翻译模式，使继承属性ps的值出现在分开的栈中。在处理过程中消除标记非终结符号M。

14.答案：(1) 把上表中的语法制导定义改写成下面的翻译模式：

S → L {B.ps:=L.s} B {S.ht:=B.ht}

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM

- 21 -

编译原理作业集 第六章 属性文法和语法制导翻译

L → ε {L.s:=10}

B → {B1.ps:=B.ps} B1 {M.i:=B.ps} M {B2.ps:=M.s} B2 {B.ht:=max(B1.ht,B2.ht)} M → ε { M.s:=M.i}

B → {B1.ps:=B.ps} B1 sub {N.i:=B.ps} N {B2.ps:=N.s} B2 {B.ht:=disp(B1.ht,B2.ht)} B → text {B.ht:=text.h*B.ps} N → ε {N.s:=shrink(N.i)}

(2) 设一个栈ps，管理继承属性B.ps的值。栈的三个操作为push(ps,值),pop(ps),top(ps).翻译模式如下：

S → L {B.ps:=top(ps)} B {S.ht:=B.ht} L → ε {push(ps,10)}

B → {B1.ps:=top(ps)} B1 {B2.ps:=top(ps)} Bsub>2 {B.ht:=max(B1.ht,B2.ht)} B → {B1.ps:=top(ps)} B1 sub N (B2.ps:=top(ps)} Bsub>2 {B.ht:=disp(B1.ht,B2.ht); pop(ps)} B → text {B.ht:=text.h*B.ps} N → ε {push(ps,shrink(top(ps)))}

15. 文法G的产生式如下： S → (L) | a L → L , S | S

(1)试写出一个语法制导定义，它输出配对括号个数;

(2)写一个翻译方案，打印每个a的嵌套深度。如((a),a),打印2,1。 【解】解题思路 本题包括两部分，第1部分要求写语法制导定义，第2部分要求写翻译方案。语法制导定义（或属性文法）可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。翻译方案（也称翻译模式）给出了使用语义规则进行计算的次序，把某些实现细节表示出来。读者从下面解答中可体会两者的区别。 解答

为S、L引入属性h,代表配对括号个数。语法制导定义如下：

产生式 语义规则

S.h:=L.h+1 S → (L)

S.h:=0 S → a

L → L1 , S L.h:=L1.h+S.h

L.h:=S.h L → S

print(S.h) S’→S

(2)为S、L引入d，代表a的嵌套深度。翻译方案如下： S’→｛S.d:=0;｝S

S →‘(’{L.d:=S.d+1;} L ‘)’ S →a{print(S.d);} L → {L1.d:=L.d;} L1

{S.d:=L.d;} S

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM

- 22 -

编译原理作业集 第六章 属性文法和语法制导翻译

L → {S.d:=L.d} S

16. 由下列文法 S→E E→E:=E | E+E | (E) | id

产生的表达式，其语义如C语言，包含赋值运算。就是说，b:=c是一个表达式，把c的值赋给b；该表达式的右值为c的右值。进而，a:=(b:=c)先把c的值赋给b，然后再赋给a。 (1) 试建立一个属性文法，用非终结符E的继承属性side表示由E生成的表达式出现在赋值运算的左边还是右边，检查表达式的左部是一个左值。 (2) 扩充（1）中的属性文法，产生某种形式的中间代码 解：

（1）语法制导定义如下

S → E { E.side = right; }

E → E1 := E2 { if (E.side == left) error;

else { E1.side = left; E2.side = right; }}

E → E1 + E2 { if (E.side == left) error;

else { E1.side = E2.side = right; }}

E → ( E1 ) { if (E.side == left) error;

else { E1.side = right; }}

E → id

（2）扩充 （1）中语法制导定义，使得在检查同时将表达式翻译为抽象堆栈机代码 解：语法制导定义如下，其中，valcode 表示取表达式右值的代码 S → E { E.side = right; S.code = E.code; } E → E1 := E2 { if (E.side == left) error;

else { E1.side = left; E2.side = right; }

E.code = E1.code || E2.code || ':=' || E1.valcode; }

E → E1 + E2 { if (E.side == left) error;

else { E1.side = E2.side = right; } E.code = E1.code || E2.code || '+'; }

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM - 23 -

编译原理作业集 第六章 属性文法和语法制导翻译

E → ( E1 ) { if (E.side == left) error;

else { E1.side = right; } E.code = E1.code; }

E → id{ E.code = 'lvalue' id.lexeme; E.valcode = 'rvalue' id.lexeme; }

西安理工大学计算机科学与工程学院 张发存编写 5/20/2013 9:37:06 AM - 24 -

本文来源：https://www.bwwdw.com/article/j4d3.html