语法制导翻译和中间代码生成习课件

1、语法制导翻译和中间代码生成习1 第五章 语法制导翻译与中间代码生成 典型习题典型习题 语法制导翻译和中间代码生成习2 第五章 语法制导翻译与中间代码 生成 1、为文法： S（L）| a L L，S| S (a)写一个翻译方案，它输出配对括号的个 数。如对于句子（a，（a，a），输出结 果为2。 (b)写一个翻译方案，它输出配对括号的最 大嵌套深度。如对于句子（a，（a，a）， 输出结果为2。 (c) 写一个翻译方案，它输出每个a的嵌套深 度。例如：对于句子（a，（a，a），输 出的结果是1 2 2。 (d) 写一个翻译方案，它打印出每个a在句子 中是第几个字符。例如：当句子是 （a，（a，（a

2、，a），（a）时，打印的结 果是2 5 8 10 14。 语法制导翻译和中间代码生成习3 第五章 语法制导翻译与中间代码 生成 S（L）| a L L，S| S (a)写一个翻译方案，它输出配对括号的个 数。如对于句子（a，（a，a），输出结 果为2。 根据输出配对括号个数的要求，从下到上分析每条规则可知： 当采用规则LS进行归约时，L中的括号对数等于S中的括号对数； 当采用规则LL1，S进行归约时，L1与S用“，”连接，因此L中的括号对数 等于S中的括号对数与L1中的括号对数之和； 当采用规则Sa进行归约时，S中的括号对数等于0； 当采用规则S（L）进行归约时，S中的括号对数等于L中的括号对

3、数加1； 为输出总的括号对数，需对原文法进行拓广，增加一条文法规则： SS， 对应的语义规则为输出总的括号对数。 根据上述分析，为S和L引入属性num（表示括号对数），可写出每条规则 的语义动作如下： 语法制导翻译和中间代码生成习4 第五章 语法制导翻译与中间代码 生成 S S print(S.num) S（L） S.num=L.num+1 S a S.num=0 L L1，S L.num=L1.num+S.num L S L.num=S.num S（L）| a L L，S| S (a)写一个翻译方案，它输出配对括号的个 数。如对于句子（a，（a，a），输出结 果为2。 语法制导翻译和中间代码

4、生成习5 第五章 语法制导翻译与中间代码 生成 S S print(S.num) S（L） S.num=L.num+1 S a S.num=0 L L1，S L.num=max(L1.num，S.num) L S L.num=S.num S（L）| a L L，S| S (b)写一个翻译方案，它输出配对括号的最 大嵌套深度。如对于句子（a，（a，a）， 输出结果为2。 语法制导翻译和中间代码生成习6 第五章 语法制导翻译与中间代码 生成 S S.depth=0 S S L.depth=S.depth+1 （L） S a print (S.depth) L L1.depth=L.depth L1

5、， S.depth=L.depth S L S.depth=L.depth S S（L）| a L L，S| S (c) 写一个翻译方案，它输出每个a的嵌套 深度。例如：对于句子（a，（a，a）， 输出的结果是1 2 2。 由于a的嵌套深度不是由a本身能决定的，所以一定要用继承属 性。用继承属性depth表示嵌套深度，所求的翻译方案如下： 语法制导翻译和中间代码生成习7 第五章 语法制导翻译与中间代码 生成 S S.in=0 S S L.in=S.in+1 （L）S.out=L.out+1 S a S.out=S.in+1；print (S.out) L L1.in=L.in L1， S.in

6、=L1.out+1 S L.out=S.out L S.in=L.in S L.out=S.out S（L）| a L L，S| S (d) 写一个翻译方案，它打印出每个a在句子 中是第几个字符。例如：当句子是 （a，（a，（a，a），（a）时，打印的结 果是2 5 8 10 14。 为文法符号S和L分别定义一个继承属性in和一个综合属性综合属性out， 分别表示在句子中，该文法符号推出的字符序列的前面有多少 个字符，和该文法符号推出的字符序列的最后一个字符在句该文法符号推出的字符序列的最后一个字符在句 子中是第几个字符子中是第几个字符。所求的翻译方案如下： 语法制导翻译和中间代码生成习8 第

7、五章 语法制导翻译与中间代码 生成 S S.in=0 S S L.in=S.in+1 （L）S.total=L.total+2 S a S.total=1；print (S.in+1) L L1.in=L.in L1， S.in=L.in+L1.total+1 S L.total=L1.total+1+S.total L S.in=L.in S L.total=S.total S（L）| a L L，S| S (d) 写一个翻译方案，它打印出每个a在句子 中是第几个字符。例如：当句子是 （a，（a，（a，a），（a）时，打印的结 果是2 5 8 10 14。 为文法符号S和L分别定义一个继承属

8、性in和一个综合属性综合属性total， 分别表示在句子中，该文法符号推出的字符序列的前面有多少 个字符，和该文法符号推出的字符总数（即：该文法符号推出的字符总数（即：out=in+total）。 所求的翻译方案如下： 语法制导翻译和中间代码生成习9 第五章 语法制导翻译与中间代码 生成 2、给出下列文法的适合自底向上翻译的语义 动作，使得当输入串是acb时，其输出串是 102。 SaA S c A Sb S aA bS c 1 2 3 print “1” print “0” print “2” 语法制导翻译和中间代码生成习10 第五章 语法制导翻译与中间代码 生成 3、文法GS及相应的翻译方

9、案如下： SbA b print “1” A cB print “2” A a print “3” B Aad print “4” 当输入串是bcaadb时，该翻译方案的输出是多少？ S bb c A a 1 2 3 A B ad 4 3421 语法制导翻译和中间代码生成习11 第五章 语法制导翻译与中间代码 生成 4、文法GS如下： S S(S) S 试写出一个语法制导定义，它对输入符号串翻译的 结果是输出配对的括号个数。 为为S引入一个综合属性引入一个综合属性num，用以表示该文法符号所表示的语，用以表示该文法符号所表示的语 法成分中配对的括号数。法成分中配对的括号数。 首先将文法扩展，并

10、设计语法制导的语义动作为：首先将文法扩展，并设计语法制导的语义动作为： S S print (S.num) S S1(S2) S.num=S1.num+S2.num+1 S S.num=0 语法制导翻译和中间代码生成习12 第五章 语法制导翻译与中间代码 生成 5、有一语法制导翻译方法如下：其中“+”表示符号连 接运算： SB print (B.reverse) B a B.reverse=a B b B.reverse=b B Ba B.reverse=a+B.reverse B Bb B.reverse=b+B.reverse 若输入符号串abab，则采用自底向上语法分析方法时， 输出为什

11、么？ baba 语法制导翻译和中间代码生成习13 第五章 语法制导翻译与中间代码生成 6、给出文法GS的语法制导定义，功能是统计句子 中a和b的个数。 GS: SaBS|bAS| BaBB|b AbAA|a S、A、B均是由均是由a和和b组成的字符串，所以分别为组成的字符串，所以分别为S、A、B引入引入 两个记录两个记录a和和b个数的属性个数的属性num_a和和num_b，将文法拓广后的，将文法拓广后的 语法制导定义为：语法制导定义为： S S print(S.num_a); print(S.num_b) S aBS1 S.num_a=1+B.num_a+S1.num_a; S.num_b=B.num_b+S1.num_b S bAS1 S.num_a=A.num_a+S1.num_a; S.num_b=1+A.num_b+S1.num_b S S.num_a=0; S.num_b=