翻译模式题目总结

1.给出文法，写翻译模式

**（06年/20年）**已知文法G(P):

P→ D
D→ D; D|id: T|proc id; D; S

1.写一个翻译模式，打印该程序声明了多少个id

2.写一个翻译模式，打印该程序每个变量id的嵌套深度

1. 综合属性

   P→D { print (D.idnum) }
   D→D1; D2 { D.idnum:=D1.idnum+D2.idnum }

   D→id: T { D.idnum:=1 }

   D→proc id; D1; S {D.idnum:=D1.idnum+1}

2. 继承属性获取深度

   P→{D.depth:=0}D

   D→{D1.depth:=D.depth}D1;{D2.depth:=D.depth}D2

   D→id:T{print(id.name, D.depth)}

   D→proc id{print(id.name, D.depth)}; {D1.depth:=D.depth+1}D1; S

**（07年）**已知文法：

D→TL

T→int | float

L→L,id | id

构造翻译模式，使其输出类型为float的变量个数，简要说明设计思想。

D→TL{ if T.type=‘float’ then print(L.idnum) }

T→int{ T.type:=‘int’ }

T→float{ T.type:=‘float’ }

L→L1,id{ L.idnum:=L1.idnum+1}

L→id{ L.idnum:=1}

**（09年）**已知文法G(P)

P→S

S→(L) | a

L→L,S | S

1.打印每个a在括号中的嵌套深度

2.检测左右括号匹配并打印匹配出错信息，如“第X个字符)未匹配”

1. 继承属性实现

   P→{S.depth:=0}S

   S→( {S.depth:=S.depth+1; L.depth:=S.depth} L ) {S.depth:=S.depth-1}

   S→a{print(a,S.depth)}

   L→{ L1.depth:=L.depth }L1, { S.depth:=L.depth }S

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

2. 需要记录是第几个字符

   P→{S.lp:=0; S.rp:=0} S{ if S.lp>S.rp then : for(k=1;k<=S.lp-S.rp;k++)

   ​ print(‘第k个字符(未匹配’}

   ​ else: for(k=2*S.lp+1;k<=S.lp+S.rp;k++)

   ​ print(‘第k个字符)未匹配’}

   S→( { S.lp:=S.lp+1 }L) { S.rp:=S.rp+1 }

   S→a

   L→L1,S

   L→S

**（11年）**已知文法G[P]：

expr→expr+term

expr→expr-term

expr→term

term→term*factor

term→term/factor

term→factor

factor→id

factor→num

factor→(expr)

写一个翻译模式，将中缀表达式翻译为前缀表达式

在回溯的时候翻译即可，因此用S翻译模式

expr→expr1+term{expr.code:=‘+’ || expr1.code || term.code}

expr→expr1-term{expr.code:=‘-’ || expr1.code || term.code}

expr→term{expr.code:=term.code}

term→term1*factor{term.code:=‘*’ || term1.code || factor.code}

term→term1/factor{term.code:=‘/’ || term1.code || factor.code}

term→factor{term.code:=factor.code}

factor→id{factor.code:=id.name}

factor→num{factor.code:=id.value}

factor→(expr){factor.code:=expr.code}

**（老师给的例题）**某语言描述的是十进制值4的倍数的二进制串。对应的文法G(S)为:

S→List 100

List→ListB

List→B

B→0

B→1

请给出求解该二进制串对应的十进制的翻译模式，并概述其基本设计思想。

能直接用S属性做，没必要和答案一样求pos

S→List 100{S.val:=List.val*8+4}

List→List1 B{List.val:=List1.val*2+B}

List→B{List.val:=B.val}

B→0{B.val:=0}

B→1{B.val:=1}

生成二进制小数的语法G[N]如下：

N→S.S

S→SB

S→B

B→0

B→1

请给出将二进制小数转为十进制小数的翻译模式，令N.val是生成的二进制数的值，如101.101=5.625

N→S1.S2{N.val:=S1.val+$2^{-S2.len}\times$S2.val}

S→S1 B{S.val:=2*S1.val+B.val; S.len:=S1.len+1}

S→B{S.val:=B.val; S.len:=1}

B→0{B.val:=0}

B→1{B.val:=1}

2.结合一遍扫描和回填，写控制语句的翻译

**常见控制语句的L翻译模式（不带回填）：**if E then S，if E then S1 else S2，while E do S，while中带有break

P→D;{ S.next:=newlabel; S.break:=newlabel} S { gen(S.next ‘:’) }

S→if {E.true:=newlabel; E.false:=S.next} E then {S1.next:=S.next; S1.break:=S.break} S1 {S.code:=E.code || gen(E.true ‘:’) || S1.code }

S→if {E.true:=newlabel; E.false:=newlabel} E then {S1.next:=S.next; S1.break:=S.break} S1 else {S2.next:=S.next; S2.break:=S.break} S2 {S.code:=E.code || gen(E.true ‘:’) || S1.code || gen(‘goto’ S.next) || gen(E.false ‘:’) || S2.code }

S→while {E.true:=newlabel; E.false:= S.next} E do {S1.next:=newlabel; S1.break:=S.next} S1 {S.code:=gen(S1.next ‘:’) || E.code || gen(E.true ‘:’) || S1.code || gen(‘goto’ S1.next) }

S→{S1.next:=newlabel; S1.break:=S.break}S1; {S2.next:=S.next; S2.break:=S.break}S2 {S.code:= S1.code || gen(S1.next ‘:’) || S2.code }

S→break;{S.code:=gen(‘goto’ S.break)}

常见布尔表达式和控制语句的S翻译模式（带回填）：
前面设计了将布尔表达式和控制语句翻译为TAC语句序列的L—翻译模式片段（通过控制流体现布尔表达式的语义）。本小节介绍一种可处理同样问题的S翻译模式。这一翻译模式用到下列属性值和语义函数:

• 综合属性E.truelist(真链)：表示一系列跳转语句的地址,这些跳转语句的目标语句标号是体现布尔表达式E为“真”的标号
• 综合属性E.falselist(假链)：表示一系列跳转语句的地址,这些跳转语句的目标语句标号是体现布尔表达式E为“假”的标号
• 综合属性S.nextlist(next链)：链表中的元素表示一系列跳转语句的地址,这些跳转语句的目标语句标号是在执行序列中紧跟在S之后的下条TAC语句的标号
• 综合属性N.nextlist是仅含一个语句地址的链表,对应于处理到N时的跳转语句
• 综合属性S.breaklist(break链)：链表中的元素表示一系列跳转语句的地址,这些跳转语句的目标语句标号是跳出直接包围S的while语句后的下条TAC语句的标号
• 综合属性M.gotostm中记录处理到M时下一条待生成语句的标号
• 语义函数 makelist(i)：创建只有一个结点i的表,对应于一条跳转语句的地址
• 语义函数 merge(p1,p2)：链接两个链表p1和p2,返回结果链表
• 语义函数 backpatch(p,i)：将链表户中每个元素所指向的跳转语句的标号置为i
• 语义函数nextstm：返回下一条 TAC语句的地址
• 语义函数emit(…)：输出一条TAC语句,并使nextstm加1

布尔表达式：

E→E1 or M E2 { backpatch(E1.falselist, M.gotosym)

​ E.truelist:=merge(E1.truelist, E2.truelist)

​ E.falselist:=E2.falselist }

E→E1 and M E2{ backpatch(E1.truelist, M.gotosym)

​ E.truelist:=E2.truelist

​ E.falselist:=merge(E1.falselist, E2.falselist) }

E→ not E1{ E.truelist:=E1.falselist;  E.falselist:=E1.truelist }

E→(E){ E.truelist:=E1.truelist; E.falselist:=E1.falselist }

E→id1 rop id2{ E.truelist:=makelist (nextsym) ;

​ E.falselist:=makelist (nextsym+1);

​ emit(‘if’ id1.place rop id2.place ‘goto _’);

​ emit(‘goto _’);

E→true{ E.truelist:=makelist (nextsym) ; emit(‘goto _’) }

E→false{ E.falselist:=makelist (nextsym) ; emit(‘goto _’) }

M→ε{M.gotosym:= nextsym}

控制语句：见书

**（23年补）**构造下列文法的翻译模式

S→Do S Loop While E（条件E成立循环继续，否则退出）

**（24年）**已知循环语句文法G(S)：

S→do {S} while (E);（直到条件不成立时退出循环）

1.采用继承属性为该文法构建两遍扫描的属性文法

2.采用回填技术为该文法构建一遍扫描的翻译模式

**（25年编译原理选修）**同上

以24为例，

1. 两遍扫描，不需要考虑回填，用L翻译模式

   E.true:	---------------
       	   S1.code
   	   	---------------
   		    E.code
   E.false:---------------也就是S.next
       		...

   进入E前先将E.true设置为新标号，E.false设置为S.next。注意S.next是在进入S前就获取到的标号。

   S→do S1 while { E.true:=newlabel ;  E.false:=S.next } E { S.code:=gen(E.true ‘:’) || S1.code || E.code }

   因为E.false不是新的标号，所以最后生成代码不需要gen(E.false,':')

2. 回填，用S翻译模式

   只需要回填E.truelist为进入S1前的语句的标号就行，这个标号用M S1的M获取。

   S→do M S1 while E{  backpatch(E.truelist, M.gotostm);

   ​ S.nextlist:=E.falselist; }

   M→ε { M.gotostm:=nextstm }