《属性文法课堂练习.ppt》由会员分享,可在线阅读,更多相关《属性文法课堂练习.ppt(22页珍藏版)》请在金锄头文库上搜索。
1、属性文法课堂练习题2、写出下面文法的属性文法:Number Digit Number1Number DigitDigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9|1、写出下面文法的属性文法: Number Number1 Digit Number Digit Digit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9|1、写出下面文法的属性文法:NumberNumber1DigitNumberDigitDigit0|1|2|3|4|5|6|7|8|9|文法规则语义规则NumberNumber1Digit Number.val=Nu
2、mber1.val*10+Digit.valNumberDigitNumber.val=Digit.valDigit0Digit.val=0Digit9Digit.val=92、写出下面文法的属性文法:Number Digit Number1Number DigitDigit 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9| 文法规则语义规则NumberDigitNumber1Number.mul=Number1.mul*10Number.val=Digit.val*Number.mul+Number1.valNumberDigitNumber.mul=1Numbe
3、r.val=Digit.valDigit0Digit.val=0Digit9Digit.val=93、给出下列文法中S产生的二进制数值的语义规则,并用堆栈说明该语义的实现过程,例如输入1101.011时,S.val=13.375:S-L.L|LL-LB|BB-0|1B.Val:=0B-0B.Val:=1B-1L.val:=B.val;L.length=1L-BL.val:=L.val*2+B.valL.length=L.length+1L-LBS.val:=L.valS-LS.val:=L1.val+L2.val/2L2.lengthS-L1.L2语义规则产生式13_._1_1L.L1L.Va
4、l:=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.
5、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输入输入S.Val:=L1.val+L2.val/2L2.length13.375SL.Val:=L.val*2+B.val(L.ength=3)13_._3L.LB.Val:=113_._1_1L.LB13_._1_1L.L1使用的语义规则使用的语义规则valstate输入输入1101.011的分析树的分析树1B.val=
6、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=134、十进制浮点数的文法修改如下:dnumnum.snumnumnum1digit|digitsnumdigitsnum1|digitdigit0|1|2|3|4|5|6|7|8|9(注意:整数、小数分别用左、右递归文法)文法规则语义规则dnumnum.snumdnum.val=num.val+snum.valnumnum1digitnum.val=num1.val*1
7、0+digit.valnumdigitnum.val=digit.valsnumdigitsnum1snum.val=(snum1.val+digit.val)/10snumdigitsnum.val=digit.val/10digit0digit.val=0digit9digit.val=95、下面文法给出是Pascal说明的文法,写出变量类型的一个属性文法。decl-var-list:typevar-list-var-list,id|idtype-int|float文法规则语义规则declvar-list:typevar-list.dtype=type.dtypevar-list1var-
8、list2,idvar-listidtypeintegertype.dtype=integertyperealtype.dtype=realvar-list2.in=var-list1.dtypevar-list2.dtype=var-list2.inid.in=var-list1.dtypeid.in=var-list.dtypevar-list2.dtype=var-list1.dtypeid.dtype=var-list1.dtypeid.dtype=var-list.dtype6、对于输入的表达式、对于输入的表达式(4*7+1)*2,根据下表的语法制导定义建立一棵带注释,根据下表的语法
9、制导定义建立一棵带注释的分析树。的分析树。valval: :表示非终结符的整数值表示非终结符的整数值, ,综合属性综合属性, ,lexvallexval 是单词是单词 digit digit 的属性的属性 语法制导定义语法制导定义 产生式产生式语义规则语义规则LE print(E.val)EE1 1+T +T E.val:=E1.val+T.valET E.val:=T.valTT1 1*F *F T.val:=T1.val*F.valTF T.val:=F.valF(E)F.val:=E.valFdigit F.val:=digit.lexval7、请按语法制导的定义,将后缀表达式翻译成中缀
10、表达式。、请按语法制导的定义,将后缀表达式翻译成中缀表达式。注意,不允许出现冗余括号,后续表达式的文法如下:注意,不允许出现冗余括号,后续表达式的文法如下:E-EE+E-EE*E-id语法制导定义语法制导定义产生式产生式语义规则语义规则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.co
11、de=E1.code|*|(|E2.code|);ELSEE.code=E1.code|*|E2.code|;E一一idE.code:=id.lexeme;v8、假设变量的说明是由下列文法生成的:、假设变量的说明是由下列文法生成的:vDiLvL,iL|:TvTinteger|realv1)建立一个语法制导定义,把每一个标志符的类型加在符)建立一个语法制导定义,把每一个标志符的类型加在符号表中号表中v2)为)为1)构造一个预翻译程序)构造一个预翻译程序1)type为综合属性,代表类型属性,为综合属性,代表类型属性,函数函数addtype实现向符号表中实现向符号表中i对应项填类型信息。对应项填类型
12、信息。语法制导定义语法制导定义产生式产生式语义动作语义动作DiLD.Type:=L.Typeaddtype(i.entry,D.type)L,iL1L.Type:=L1.Typeaddtype(i.entry,L.type)L:TL.type:=T.typeTintegerT.type:=integerTrealT.type:=realvb)采用递归下降分析法编写预翻译程序:采用递归下降分析法编写预翻译程序:vProcedureD;vbeginviflookahead=idthenvbeginvmatch(id);vD.type=L;vaddtype(id.entry,D.type)vendv
13、elseverrorvendvFunctionL:DataType;vbeginviflookahead=,thenvbeginvmatch(,);viflookahead=idthenvbeginvmatch(id);vL.Type=L;vaddtype(id.entry,L.type);vreturn(L.type)vendvelseverrorvendelseiflookahead=:thenbeginmatch(:);L.Type=T;return(L.Type)endelseerrorendFunctionT:DataType;beginiflookahead=integerthen
14、beginmatch(integer);return(integer)endelseiflookahead=realthenbeginmatch(real);return(real)endelseerrorendv9、下面文法产生的表达式是对整型和实型常数应用算符、下面文法产生的表达式是对整型和实型常数应用算符+形形成的。当两个整数相加时成的。当两个整数相加时,结果为整数,否则为实数。结果为整数,否则为实数。vETRvR+TR|vTnum.num|numva)给出语法制导定义确定每个子表达式的类型。给出语法制导定义确定每个子表达式的类型。vb)把表达式翻译成前缀形式,并且决定类型。试用一元运算
15、把表达式翻译成前缀形式,并且决定类型。试用一元运算符符inttoreal把整型值转换为相等的实型值,以使得前缀表达把整型值转换为相等的实型值,以使得前缀表达式中两个运算对象是同类型的。式中两个运算对象是同类型的。a)设设type是综合属性,代表各非终结符的是综合属性,代表各非终结符的“类型类型”属性属性设设in是继承属性,是继承属性,翻译方案翻译方案产生式产生式语义规则语义规则ETRR.in:=T.typeE.Type:=R.sR+TR1IF(R.in=integer)and(T.type=integer)THENR1.in:=integerELSER1.in:=realR.s:=R1.sRR
16、.s:=R.inTnum.numT.type:=realTnumT.type:=integerb)设属性设属性s和和i用于传递属性用于传递属性type,属性,属性t和和j用于传递属性用于传递属性val。翻译方案翻译方案产生式产生式语义规则语义规则ETRR.i:=T.typeR.j:=T.valE.Type:=R.sE.val:=R.tR+TR1IF(R.i=integer)and(T.type=integer)THENBEGINR1.i:=integerPrint(+,R.j,T.val)R1.j:=R.j+T.valENDELSEBEGINR1.i:=realIFR.i=integerTHENBeginR.i:=realR.j:=inttoreal(R.j)EndIFT.type=integerTHENBeginT.type:=realT.val:=inttoreal(T.val)EndPrint(+,R.j,T.val)R1.j:=R.j+T.valENDR.s:=R1.sR.t:=R1.tRR.s:=R.iR.t:=R.jTnum.numT.type:=realT.val:=num.num.lexvalTnumT.type:=integerT.val:=num.lexval