大连理工大学编译技术总复习

1、编译原理课程总复习大连理工大学软件学院23词法分析器词法分析器记号（记号（token）流）流源代码源代码源程序源程序字符流字符流词法词法单元单元词法词法记号记号非形式非形式化描述化描述形式化形式化描述描述正规式正规式字母字母串串语言语言字母表字母表名名字字4n复杂的例子复杂的例子( 00 | 11 | ( (01 | 10) (00 | 11) (01 | 10) ) ) 句子：句子：010011010000100000101110015Pascal语言的标识符集合语言的标识符集合letter A | B | | Z | a | b | | zdigit 0 | 1 | | 9id lette

2、r( (letter| |digit) )* 6r+=rr*r?=r| a-z=a|b|c|z(1) abc=a|b|c7源程序源程序字符流字符流词法词法单元单元词法词法记号记号非形式非形式化描述化描述形式化形式化描述描述正规式正规式字母字母串串语言语言字母表字母表名名字字8 051624837return(relop, LE)return(relop, NE)return(relop, LT)return(relop, GE)return(relop, GT)return(relop, EQ)开始开始=*otherother9正规式正规式状态转换图状态转换图1012开始开始a0abb11 1

3、2开始开始a0abbab12子集构造法子集构造法19开始开始 0ab ab6782345 13子集构造法子集构造法19开始开始 0ab ab6782345 14子集构造法子集构造法19开始开始 0ab ab6782345 15子集构造法子集构造法19开始开始 0ab ab6782345 16子集构造法子集构造法19开始开始 0ab ab6782345 17子集构造法子集构造法19开始开始 0ab ab6782345 18子集构造法子集构造法19开始开始 0ab ab6782345 19子集构造法子集构造法19开始开始 0ab ab6782345 20子集构造法子集构造法19开始开始 0ab a

4、b6782345 21子集构造法子集构造法19开始开始 0ab ab6782345 22子集构造法子集构造法19开始开始 0ab ab6782345 23BD开始开始aAabbabCba19开始开始 0ab ab6782345 12开始开始a0abbab24BD开始开始aAabbaa, bCbaEbBD开始开始aAabbabCba25BD开始开始aAabbabCba26BD开始开始aAabbabCba27BD开始开始aAabbabCba12开始开始a0abbab28290123aabbabbbstart45aaa, b30012bbbb4aastart最简最简DFA3132正规式正规式状态转换

5、图状态转换图3319开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab3419开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab35 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab3619开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab3719开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab3819开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|ba

6、b3919开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab4012开始开始a0abb19开始开始 0ab ab6782345 410123开始开始4420123开始开始40430123开始开始410440123开始开始4100450123开始开始41001460123开始开始410010470123开始开始4100101480123开始开始41001010490123开始开始410010101500123开始开始4100101010510123开始开始41001010101520123开始开始4100101010153构造构造DFA, ,接受接受 0和

7、和1的个数都是偶数的字符串的个数都是偶数的字符串312011110000开始开始偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇154正规式正规式状态转换图状态转换图55第三章 语法分析器56qE E A E | (E ) | E | idqA + | * *qletter A-Za-zqdigit 0-9qid letter(letter|digit)*57 q串的特点串的特点 ba . . . aba . . . aA b b A A a a A | 58 59 60A abab1 | abab2A+Aa 61FIRST集、FOLLOW集626364656667686970717273747

8、57677787980！81自下而上分析 S rm aABe rm aAde rm aAbcde rm abbcde句柄与某个产生式的右部符号串相同句柄与某个产生式的右部符号串相同句柄是句型的一个子串句柄是句型的一个子串把句柄归约成非终结符代表了最右推导逆过程的一步把句柄归约成非终结符代表了最右推导逆过程的一步828384858687888990919293拓广文法G的LR(0)项目集规范族为：I0:SSSV=ESEV*EVidEVI1:SSI2:SV =EEV I3:SEI4:V*EEVV*EVidI5:VidI6:SV=EEVV*EVidI7:V*EI8:EVI9:SV=EidS SS V

9、=ES EV *EV idE VV id S V =EE V S S I0I1I2I5S E I3V * EE VV idV * EI4SV*idES V = EE VV *EV idI6=ES V=E E V VVI8idI3*V *E EI7I9识别产生式文法活前缀的DFAI1I0I3I2I6I9I8I7I5I4startSRLid*=ididLLR*R识别产生式文法活前缀的DFASLR(1)文法的弱点nSLR(1)文法描述能力有限98LR(1)分析练习题目LR(1)分析练习解答过程n解答：nStep 1. 拓广文法 (添加产生式S-S)nStep 2: 构造识别文法活前缀的DFALR(1

10、)分析练习解答过程102状态状态actiongoto= *id$SVE0s4s51231acc2s6r53r24s4s5875r4r46s12s111097r3r38r5r59r110r511r412s12s11101313r3103n拓广文法n构造DFAq若是SLR直接构造即可q若是LR需要求取搜索符q若是LALR需要在LR的基础上进行合并n根据DFA构造分析表104判断文法属于哪类文法n证明文法 SA a | bAc | dc | bdan A dn是LALR(1)文法，但不是SLR(1)文法。：通过构造分析表来回答，如果表中不存在冲突则说明属于某文法，否则不属于该文法。：当文法很简单时，

11、可通过直观分析。先说明该文法不是SLR(1)文法。从产生式很容易看出FoLLow(A) a，c。若输入句子是dc，在d进栈后，面临的是c，这时出现移进一归约冲突。因为项目Sd.c要求移进，而项目A d.要求归约(这两个项目出现在同一项目集中)，因为c在FOLLOW(A)中。n 而上面的移进一归约冲突在规范LR(1)情况下不存在，因为只有在面临a时才进行d到A的归约。该文法还有另一个移进归约冲突，在bd进栈后，面临c的情况，其冲突的原因和上面的类似。该冲突在规范LR(1)情况下也不存在。这样，该文法是LR(1)文法。n 显然该文法的规范LR(1)项目集的集合中没有同心项目集，因此该文法也是LAL

12、R(1)文法。105106107108id1L,id2L,id3LrealTD4type5in6 - addtype(id.entry, L.in)7in8 addtype9in10addtype1entry2entry3entry产产 生生 式式 语语 义义 规规 则则 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in) 109110111112113114115116117

13、建立翻译模式建立翻译模式n如果既有如果既有综合属性综合属性又有又有继承属性继承属性，在建立翻译模式，在建立翻译模式时就必须保证：时就必须保证：1. 产生式右边的符号的产生式右边的符号的继承属性继承属性必须在先于这个符号必须在先于这个符号的动作中计算出来。的动作中计算出来。2. 一个动作不能引用这个动作右边的符号的一个动作不能引用这个动作右边的符号的综合属性综合属性。3. 产生式左边非终结符的产生式左边非终结符的综合属性综合属性只有在它所引用的只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的的动作通常可放在产生式

14、右端的末尾末尾。 SA1A2A1.in:=1; A2.in:=2 Aaprint(A.in)118119120121122123124在写语法制导定义之前，首先分析清楚需要为文在写语法制导定义之前，首先分析清楚需要为文法符号定义一些什么属性，然后看这些属性的值法符号定义一些什么属性，然后看这些属性的值是否可以由文法符号本身所推出的串决定。若是，是否可以由文法符号本身所推出的串决定。若是，则应该只用综合属性就能解决。则应该只用综合属性就能解决。125S S. depth := 0 SS L. depth := S. depth + 1 ( L ) S a print (S. depth) L L

15、1. depth := L. depth L1 , S. depth := L. depth SL S. depth := L. depth S126S S print(S.max)S ( L ) S.max:=L.max+1S a S.max=0 L L1 , S L.max:=max(L1.max, S.max)L S L.max:=S.max127S S. in := 0 SS (L. in := S. in + 1 L ) S. num:= L.num+ 2 S a S. num := 1; print (S. in+1) L L1. in := L. in L1 , S. in :=

16、 L1. in + L1.num+1 S L.num := L1.num + S.num +1 L S. in := L. in S L. num := S.num 128n给出对表达式求导数的语法制导定义(习题4.5)产产 生生 式式语语 义义 规规 则则 E E print(E.d) E E1 + T E.d := E1.d+T.d; E.exp := E1.exp + T.exp E T E.d := T.d; E.exp := T.exp T T1* *F T.d := T1.d * *F.exp + T1.exp * *F.d; T.exp := T1.exp * *F.exp T

17、F T.d := F.d ; T.exp := F.exp F (E) F.d := E.d ; F.exp := (E.exp) F x F.d := 1; F.exp := x F num F.d := 0; F.exp:=num129P DD D;D | id:T | proc id; D; S(1)一共声明多少个一共声明多少个idP D print(D.sum)D D1;D2 D.sum= D1.sum+D2.sumD id:TD.sum= 1D proc id; D1; SD.sum=D1.sum+1130P DD D;D | id:T | proc id; D; S(2)变量变量i

18、d的嵌套深度的嵌套深度P D.depth= 1D D D1.depth= D.depthD1; D2.depth= D.depthD2D id:T print(, D.depth)D proc id; D1.depth= D.depth+1D1; S131n用用S的综合属性的综合属性val给出下面文法中给出下面文法中S产生的二产生的二进制数的值。例如，输入进制数的值。例如，输入101.101时，时，S.val5.625。nS L.L | L L L B | B B 0 | 1 1324.7 用用S的综合属性的综合属性val给出下面文法中给出下面文法中S产生的二进产生的二进制数的值

19、。例如，输入制数的值。例如，输入101.101时，时，S.val5.625。S L.L | LL L B | BB 0 | 1 (1) 仅使用仅使用综合属性综合属性决定决定S.val.如果只有整数部分，很显然，可以定义如下：如果只有整数部分，很显然，可以定义如下：S L S.val = L.val;L L1 B L.val = L1.val *2 + B.val;L B L.val = B.val; B 0 B.val = 0;B 1 B.val = 1;133为了求小数部分的值，为了求小数部分的值，引入引入L的综合属性的综合属性b记录记录2的的L的位数次幂值的位数次幂值(2 length o

20、f L)S L1.L2 S.val = L1.val + L2.val / L2.b;S L S.val = L.val;L L1 B L.val = L1.val *2 + B.val; L1.b = L.b*2;L B L.val = B.val; L.b = 2;B 0 B.val = 0;B 1 B.val = 1;134SvalLv.LbvLvBvLb vBvBv0LbvBv11Bv01135SvalLv.LbvLvBvLb vBvBv0LbvBv11Bv01=1=1=0=2=1=1=0=1=2=5=2=4=8=2+5/8=2.625136nS L.L | L L L B | B B

21、 0 | 1（1）仅使用综合属性）仅使用综合属性（写法二）（写法二）S L1.L2 S.valL1.val+L2.val /2L2.lengthS L S.valL.valL L1B L.val=L1.val * 2+B.val; L.length=L1.length+1L B L.val=B.val; L.length=1B 0 B.val=0B 1 B.val=1137nS L.L | L L L B | B B 0 | 1（2）用）用L属性决定属性决定S.val。B的唯一综合属性是的唯一综合属性是c，它给出由，它给出由B产生产生的位对最终值的贡献。的位对最终值的贡献。eg:101.101

22、最前和最后一位对最前和最后一位对5.625的的贡献分别是贡献分别是4和和0.125。（修改文法）（修改文法）S L.R S.valL1.val+R.valS L S.valL.valL B L1 B.i=L1.c * 2; L.c=L1.c * 2 ; L.val=L1.val+ B.c; L B B.i=1; L.c=1; L.val= B.cR R1 B B.i=R1.c / 2; R.c=R1.c /2 ; R.val=R1.val+ B.c; R B B.i=0.5; R.c=0.5; R.val= B.cB 0 B.c=0B 1 B.c=B.i138（2）试用一个语法制导定义来决定）

23、试用一个语法制导定义来决定S.val， 在这个定义中在这个定义中B仅有仅有综合属性综合属性c，给出由，给出由B生成的位对于最后的数值的分担额。生成的位对于最后的数值的分担额。引入引入B的继承属性的继承属性i，综合属性，综合属性c。（不修改文法）（不修改文法）S L1.L2 L1.i = 20; L2 .i = 2-1; S.val = L1.val +L2.valS L L.i = 20; S.val = L.val;L L1 B if L.i = 20 then begin L1.i = L.i *2 ; B.i = L.i end else begin L1.i = L.i ; L.s =

24、 L1.s/2; B.i = L1.s end L.val = L1.val +B.c L B B.i = L.i ; L.s= L.i/2; L.val = B.cB 0 B.c = B.i*0B 1 B.c = B.i*1139Sval Lv . Ls v Lv Bc Ls v Bc Bc 0 Ls v Bc 11 Bc 01=2=0*1=0.5=0*0.25=0.125=2.625140Sval iLv . iLs viLv iBciLs vi BciBc 0iLs v iBc 11i Bc 01141Sval iLv . iLs viLv iBciLs vi BciBc 0iLs v

25、iBc 11i Bc 01=20 =2-1 =21 =20 =21 =2-1 =2-1 =2-1 =2-2=2-2=2-3=2-3=2-4=2-1=0.5=0.5=2-2*0=0=2-3*1=0.125=0.5=0.5+0.125=0.625=2.6251421431441. 产生式右边的符号的产生式右边的符号的继承属性继承属性必须在先必须在先于这个符号的动作中计算出来。于这个符号的动作中计算出来。2. 一个动作不能引用这个动作右边的符号一个动作不能引用这个动作右边的符号的的综合属性综合属性。3. 产生式左边非终结符的产生式左边非终结符的综合属性综合属性只有在只有在它所引用的所有属性都计算出来

26、以后才能它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常放在产生计算。计算这种属性的动作通常放在产生式右端的式右端的末尾末尾。145产产 生生 式式语语 义义 规规 则则 E E1 + T E.nptr := mknode( +, E1.nptr, T.nptr) E T E.nptr := T.nptr T T1* *F T.nptr := mknode( * *, T1.nptr, F.nptr) T F T.nptr := F.nptr F (E) F.nptr := E.nptr F id F.nptr := mkleaf (id, id.entry) F num F.

27、nptr := mkleaf (num, num.val) 146E T R.i := T.nptr T + T + T + RE.nptr := R.sR +TR1.i := mknode ( +, R.i, T.nptr)R1R.s := R1.sR R.s := R.i T F W.i := F.nptrWT.nptr := W.sW * *FW1.i := mknode ( * *, W.i, F.nptr)W1W.s := W1.sW W.s := W.i + +147使用继承属性构造使用继承属性构造a4c的抽象语法树的抽象语法树ETRidTo entry for aidT.nptr-Tnumnum4T.nptrR. i-R+TRidTo entry for cidT.nptrR. i+R. i R. sR. sR. sE.nptrE T R.i:=T.nptr R E.nptr:=R.sR + T R1.i:=mknode(+,R.i,T.nptr) R1 R.s:=R1.sR - T R1.i:=mknode(,R.i,T.nptr) R1 R.s:=R.sR R.s:=R.iT ( E ) T.npt