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

第五章语法制导翻译与中间代码生成典型习题第五章语法制导翻译与中间代码生成1、为文法：S→（L）|aL→L，S|S(a)写一个翻译方案，它输出配对括号的个数。如对于句子（a，（a，a）），输出结果为2。(b)写一个翻译方案，它输出配对括号的最大嵌套深度。如对于句子（a，（a，a）），输出结果为2。(c)写一个翻译方案，它输出每个a的嵌套深度。例如：对于句子（a，（a，a）），输出的结果是122。(d)写一个翻译方案，它打印出每个a在句子中是第几个字符。例如：当句子是（a，（a，（a，a），（a））时，打印的结果是2581014。第五章语法制导翻译与中间代码生成S→（L）|aL→L，S|S(a)写一个翻译方案，它输出配对括号的个数。如对于句子（a，（a，a）），输出结果为2。根据输出配对括号个数的要求，从下到上分析每条规则可知：当采用规则L→S进行归约时，L中的括号对数等于S中的括号对数；当采用规则L→L1，S进行归约时，L1与S用“，”连接，因此L中的括号对数等于S中的括号对数与L1中的括号对数之和；当采用规则S→a进行归约时，S中的括号对数等于0；当采用规则S→（L）进行归约时，S中的括号对数等于L中的括号对数加1；为输出总的括号对数，需对原文法进行拓广，增加一条文法规则：S’→S，对应的语义规则为输出总的括号对数。根据上述分析，为S和L引入属性num（表示括号对数），可写出每条规则的语义动作如下：第五章语法制导翻译与中间代码生成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）|aL→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）|aL→L，S|S(b)写一个翻译方案，它输出配对括号的最大嵌套深度。如对于句子（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}SS→（L）|aL→L，S|S(c)写一个翻译方案，它输出每个a的嵌套深度。例如：对于句子（a，（a，a）），输出的结果是122。由于a的嵌套深度不是由a本身能决定的，所以一定要用继承属性。用继承属性depth表示嵌套深度，所求的翻译方案如下：第五章语法制导翻译与中间代码生成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.out}L→{S.in=L.in}S{L.out=S.out}S→（L）|aL→L，S|S(d)写一个翻译方案，它打印出每个a在句子中是第几个字符。例如：当句子是（a，（a，（a，a），（a））时，打印的结果是2581014。为文法符号S和L分别定义一个继承属性in和一个综合属性out，分别表示在句子中，该文法符号推出的字符序列的前面有多少个字符，和该文法符号推出的字符序列的最后一个字符在句子中是第几个字符。所求的翻译方案如下：