第5章-语法制导翻译和中间代码生成习题

第五章语法制导翻译与中间代码生成典型习题第五章语法制导翻译与中间代码生成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，分别表示在句子中，该文法符号推出的字符序列的前面有多少个字符，和该文法符号推出的字符序列的最后一个字符在句子中是第几个字符。所求的翻译方案如下：第五章语法制导翻译与中间代码生成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.total}L→{S.in=L.in}S{L.total=S.total}S→（L）|aL→L，S|S(d)写一个翻译方案，它打印出每个a在句子中是第几个字符。例如：当句子是（a，（a，（a，a），（a））时，打印的结果是2581014。为文法符号S和L分别定义一个继承属性in和一个综合属性total，分别表示在句子中，该文法符号推出的字符序列的前面有多少个字符，和该文法符号推出的字符总数（即：out=in+total）。所求的翻译方案如下：第五章语法制导翻译与中间代码生成2、给出下列文法的适合自底向上翻译的语义动作，使得当输入串是acb时，其输出串是102。S→aA{}S→c{}A→Sb{}SaAbSc123print“1”print“0”print“2”第五章语法制导翻译与中间代码生成3、文法G[S]及相应的翻译方案如下：S→bAb{print“1”}A→cB{print“2”}A→a{print“3”}B→Aad{print“4”}当输入串是bcaadb时，该翻译方案的输出是多少？SbbcAa123ABad43421第五章语法制导翻译与中间代码生成4、文法G[S]如下：S→S(S)S→ε试写出一个语法制导定义，它对输入符号串翻译的结果是输出配对的括号个数。为S引入一个综合属性num，用以表示该文法符号所表示的语法成分中配对的括号数。首先将文法扩展，并设计语法制导的语义动作为：S’→S{print(S.num)}S→S1(S2){S.num=S1.num+S2.num+1}S→ε{S.num=0}第五章语法制导翻译与中间代码生成5、有一语法制导翻译方法如下：其中“+”表示符号连接运算：S→B{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、给出文法G[S]的语法制导定义，功能是统计句子中a和b的个数。G[S]:S→aBS|bAS|εB→aBB|bA→bAA|aS、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=0}B→aB1B2{B.num_a=1+B1.num_a+B2.num_a;B.num_b=B1.num_b+B2.num_b}B→b{B.num_a=0;B.num_b=1}A→bA1A2{A.num_a=A1.num_a+A2.num_a;A.num_b=1+A1.num_b+A2.num_b}A→a{A.num_a=1;A.num_b=0}