属性文法课堂练习

属性文法课堂练习第一页，共二十二页，2022年，8月28日1、写出下面文法的属性文法：Number→Number1

DigitNumber→DigitDigit→0|1|2|3|4|5|6|7|8|9|文法规则语义规则Number→Number1DigitNumber.val=Number1.val*10+Digit.valNumber→DigitNumber.val=Digit.valDigit

→0Digit.val=0…………Digit

→9Digit.val=9第二页，共二十二页，2022年，8月28日2、写出下面文法的属性文法：Number→DigitNumber1Number→DigitDigit→0|1|2|3|4|5|6|7|8|9|文法规则语义规则Number→DigitNumber1Number.mul=Number1.mul*10Number.val=Digit.val*Number.mul+Number1.valNumber→DigitNumber.mul=1Number.val=Digit.valDigit

→0Digit.val=0…………Digit

→9Digit.val=9第三页，共二十二页，2022年，8月28日3、给出下列文法中S产生的二进制数值的语义规则，并用堆栈说明该语义的实现过程，例如输入1101.011时，S.val=13.375：S->L.L|LL->LB|BB->0|1第四页，共二十二页，2022年，8月28日{B.Val:=0}B->0{B.Val:=1}B->1{L.val:=B.val；L.length=1}L->B{L.val:=L.val*2+B.valL.length=L.length+1}L->LB{S.val:=L.val}S->L{S.val:=L1.val+L2.val/2^L2.length}S->L1.L2语义规则产生式第五页，共二十二页，2022年，8月28日13_._1_1L.L1L.Val:=L.val*2+B.val(L.ength=2)13_._1L.L1B.Val:=113_._0_1L.LB113_._0_1L.L11L.Val:=B.val(L.length=1)13_._0L.L11B.Val:=113_._0L.B1113_._0L.01113_.L.011L.Val:=L.val*2+B.val(L.length=4)13L.011B.Val:=16_1LB.0116_1L1.011L.val:=L.val*2+B.val(L.length=3)6L1.011B.val:=03_0LB1.0113_0L01.011L.val:=L.val*2+B.val(L.length=2)3L01.011B.val:=11_1LB01.0111_1L101.011L.val:=B.val(L.length=1)1L101.011B.val:=11B101.01111101.011--1101.011使用的语义规则valstate输入第六页，共二十二页，2022年，8月28日S.Val:=L1.val+L2.val/2^L2.length13.375SL.Val:=L.val*2+B.val(L.ength=3)13_._3L.LB.Val:=113_._1_1L.LB13_._1_1L.L1使用的语义规则valstate输入第七页，共二十二页，2022年，8月28日1101.011的分析树1B.val=1L1.val=11B.Val=1L1.val=30B.Val=0L1.val=60B.Val=0L2.val=01B.Val=1L2.val=11B.Val=1L2.val=3.S=13.3751B.Val=1L1.val=13第八页，共二十二页，2022年，8月28日4、十进制浮点数的文法修改如下：

dnum→num.snum num→num1digit|digit snum→digitsnum1|digit digit→0|1|2|3|4|5|6|7|8|9(注意：整数、小数分别用左、右递归文法)第九页，共二十二页，2022年，8月28日文法规则语义规则dnum→num.snumdnum.val=num.val+snum.valnum→num1

digitnum.val=num1.val*10+digit.valnum→digitnum.val=digit.valsnum→digitsnum1snum.val=(snum1.val+digit.val)/10snum→digitsnum.val=digit.val/10digit→0digit.val=0…………digit→9digit.val=9第十页，共二十二页，2022年，8月28日5、下面文法给出是Pascal说明的文法，写出变量类型的一个属性文法。

decl->var-list:type var-list->var-list,id|id type->int|float第十一页，共二十二页，2022年，8月28日文法规则语义规则decl→var-list:type{var-list.dtype=type.dtype}var-list1→var-list2,idvar-list→idtype→integer{type.dtype=integer}type→real{type.dtype=real}{var-list2.in=var-list1.dtype}{var-list2.dtype=var-list2.inid.in=var-list1.dtype}{id.in=var-list.dtype}{var-list2.dtype=var-list1.dtypeid.dtype=var-list1.dtype}{id.dtype=var-list.dtype}第十二页，共二十二页，2022年，8月28日6、对于输入的表达式(4*7+1)*2，根据下表的语法制导定义建立一棵带注释的分析树。

val:表示非终结符的整数值,综合属性,lexval是单词digit的属性 语法制导定义

产生式

语义规则

LE

print(E.val)EE1+TE.val:=E1.val+T.valET

E.val:=T.valTT1*FT.val:=T1.val*F.valTF

T.val:=F.valF(E)F.val:=E.valFdigit

F.val:=digit.lexval

第十三页，共二十二页，2022年，8月28日第十四页，共二十二页，2022年，8月28日7、请按语法制导的定义，将后缀表达式翻译成中缀表达式。注意，不允许出现冗余括号，后续表达式的文法如下：

E->EE+E->EE*E->id第十五页，共二十二页，2022年，8月28日语法制导定义

产生式

语义规则

S->EprintE.codeE->E1E2+E.code=E1.code||'+'||E2.code;E.op='+'E->E1E2*IFE1.op='+'ANDE2.op='+'THENE.code="("||E1.code||')'||'*'||'('||E2.code||')';ELSEIFE1.op='+'THENE.code="("||E1.code||')'||'*'||E2.code;ELSEIFE2.op='+'THENE.code=E1.code||'*'||'('||E2.code||')';ELSEE.code=E1.code||'*'||E2.code||;E一>idE.code:=id.lexeme;第十六页，共二十二页，2022年，8月28日8、假设变量的说明是由下列文法生成的：DiLL,iL|:TTinteger|real1）建立一个语法制导定义，把每一个标志符的类型加在符号表中2）为1）构造一个预翻译程序

第十七页，共二十二页，2022年，8月28日1)type为综合属性，代表类型属性，

函数addtype实现向符号表中i对应项填类型信息。

语法制导定义

产生式

语义动作

DiL

D.Type:=L.Typeaddtype(i.entry,D.type)L,iL1L.Type:=L1.Typeaddtype(i.entry,L.type)L:T

L.type:=T.typeTinteger

T.type:=integerTreal

T.type:=real第十八页，共二十二页，2022年，8月28日b)采用递归下降分析法编写预翻译程序：

ProcedureD; begin iflookahead=idthenbeginmatch(id);D.type=L;addtype(id.entry,D.type)endelseerror endFunctionL:DataType;beginiflookahead=’,’thenbeginmatch(‘,’);iflookahead=idthenbeginmatch(id);L.Type=L;addtype(id.entry,L.type);return(L.type)endelseerrorendelseiflookahead=’:’thenbeginmatch(‘:’);L.Type=T;return(L.Type)endelseerrorend

FunctionT:DataType;beginiflookahead=integerthenbeginmatch(integer);return(integer)endelseiflookahead=realthenbeginmatch(real);return(real)endelseerrorend

第十九页，共二十二页，2022年，8月28日9、下面文法产生的表达式是对整型和实型常数应用算符+形成的。当两个整数相加时,结果为整数，否则为实数。ETRR+TR|εTnum.num|numa)给出语法制导定义确定每个子表达式的类型。b)把表达式翻译成前缀形式，并且决定类型。试用一元运算符inttoreal把整型值转换为相等的实型值，以使得前缀表达式中两个运算对象是同类型的。

第二十页，共二十二页，2022年，8月28日a)设type是综合属性，代表各非终结符的“类型”属性

设in是继承属性，

翻译方案

产生式

语义规则

ET

R{R.in:=T.type}{E.Type:=R.s}R+T

R1

{IF(R.in=integer)and(T.type=integer)THENR1.in:=integerELSER1.in:=real}{R.s:=R1.s}Rε

{R.s:=R.in}Tnum.num

T.type:=realTnum

T.type:=integer第二十一页，共二十二页，2022年，8月28日b)设属性s和i用于传递属性type，属性t和j用于传递属性val。

翻译方案

产生式

语义规则

ET

R{R.i:=T.type}{R.j:=T.val}{E.Type:=R