语法制导翻译和中间代码生成习.ppt

《语法制导翻译和中间代码生成习.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译和中间代码生成习.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第五章 语法制导翻译与中间代码生成典型典型习题第五章 语法制导翻译与中间代码生成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，a），（a）时，打印的结果是2 5 8 10 14。第五章 语法制导翻译与中间代码生成 S（L）|a L

2、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中的括号对数加1；为输出总的括号对数，需对原文法进行拓广，增加一条文法规则：SS，对应的语义规则为输出总的括号对数。根据上述分析，为S和L引入属性num（表示括号对数），可写出每

3、条规则的语义动作如下：第五章 语法制导翻译与中间代码生成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.numL S L.num=S.num S（L）|a L L，S|S(a)写一个翻译方案，它输出配对括号的个数。如对于句子（a，（a，a），输出结果为2。第五章 语法制导翻译与中间代码生成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)写

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

5、法制导翻译与中间代码生成S S.in=0 SS 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=L1.out+1 S L.out=S.outL 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，分别表示在句子中，该文法符号推出的字符序列的前面有多少个字符

6、，和该文法符号推出的字符序列的最后一个字符在句文法符号推出的字符序列的最后一个字符在句子中是第几个字符子中是第几个字符。所求的翻译方案如下：第五章 语法制导翻译与中间代码生成S S.in=0 SS 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.totalL S.in=L.in S L.total=S.total S（L）|a L L，S|S (d)写一个翻译方案，它打印出每个a在句子中是第几个字符。例如：

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

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

9、m=S1.num+S2.num+1S S.num=0第五章 语法制导翻译与中间代码生成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，则采用自底向上语法分析方法时，输出为什么？baba第五章 语法制导翻译与中间代码生成6、给出文法GS的语法制导定义，功能是统计句子中a和b的个数。GS:SaBS|bAS|BaBB|b AbAA|aS、A、B均是由均是由a和和

10、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_bS bAS1 S.num_a=A.num_a+S1.num_a;S.num_b=1+A.num_b+S1.num_bS S.num_a=0;S.num_b=0B aB1B2 B.num_a=1+B1.num_a+B2.num_a;B.num_b=B1.num_b+B2.num_bB b B.num_a=0;B.num_b=1A bA1A2 A.num_a=A1.num_a+A2.num_a;A.num_b=1+A1.num_b+A2.num_bA a A.num_a=1;A.num_b=0