大工-编译原理课程总复习----贾棋靠谱~~

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

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

3、造法19开始开始 0ab ab6782345 子集构造法子集构造法19开始开始 0ab ab6782345 子集构造法子集构造法19开始开始 0ab ab6782345 子集构造法子集构造法19开始开始 0ab ab6782345 子集构造法子集构造法19开始开始 0ab ab6782345 子集构造法子集构造法19开始开始 0ab ab6782345 子集构造法子集构造法19开始开始 0ab ab6782345 子集构造法子集构造法19开始开始 0ab ab6782345 子集构造法子集构造法19开始开始 0ab ab6782345 子集构造法子集构造法19开始开始 0ab ab678234

4、5 子集构造法子集构造法19开始开始 0ab ab6782345 BD开始开始aAabbabCba19开始开始 0ab ab6782345 12开始开始a0abbabBD开始开始aAabbaa, bCbaEbBD开始开始aAabbabCbaBD开始开始aAabbabCbaBD开始开始aAabbabCbaBD开始开始aAabbabCba12开始开始a0abbab0123aabbabbbstart45aaa, b012bbbb4aastart最简最简DFA正规式正规式状态转换图状态转换图19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19开始开始 0a

5、b ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab 19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab19开始开始 0ab ab6782345 r9r7r8r4r3r5r6*)(r2r1a|bab12开始开始a0abb19开始开始 0ab ab67

6、82345 0123开始开始40123开始开始400123开始开始4100123开始开始41000123开始开始410010123开始开始4100100123开始开始41001010123开始开始410010100123开始开始4100101010123开始开始41001010100123开始开始410010101010123开始开始41001010101构造构造DFA, ,接受接受 0和和1的个数都是偶数的字符串的个数都是偶数的字符串312011110000开始开始偶偶0偶偶1奇奇0奇奇1奇奇0偶偶1偶偶0奇奇1正规式正规式状态转换图状态转换图第三章 语法分析器qE E A E | (E )

7、 | E | idqA + | * *qletter A-Za-zqdigit 0-9qid letter(letter|digit)* q串的特点串的特点 ba . . . aba . . . aA b b A A a a A | A abab1 | abab2A+Aa FIRST集、FOLLOW集！自下而上分析 S rm aABe rm aAde rm aAbcde rm abbcde句柄与某个产生式的右部符号串相同句柄与某个产生式的右部符号串相同句柄是句型的一个子串句柄是句型的一个子串把句柄归约成非终结符代表了最右推导逆过程的一步把句柄归约成非终结符代表了最右推导逆过程的一步n构造拓广文

8、法n构造DFAq若是SLR直接构造即可q若是LR需要求取搜索符q若是LALR需要在LR的基础上进行合并n根据DFA构造分析表判断文法属于哪类文法n证明文法 SA a | bAc | dc | bdan A dn是LALR(1)文法，但不是SLR(1)文法。：通过构造分析表来回答，如果表中不存在冲突则说明属于某文法，否则不属于该文法。：当文法很简单时，可通过直观分析。先说明该文法不是SLR(1)文法。从产生式很容易看出FoLLow(A) a，c。若输入句子是dc，在d进栈后，面临的是c，这时出现移进一归约冲突。因为项目Sd.c要求移进，而项目A d.要求归约(这两个项目出现在同一项目集中)，因为

9、c在FOLLOW(A)中。n 而上面的移进一归约冲突在规范LR(1)情况下不存在，因为只有在面临a时才进行d到A的归约。该文法还有另一个移进归约冲突，在bd进栈后，面临c的情况，其冲突的原因和上面的类似。该冲突在规范LR(1)情况下也不存在。这样，该文法是LR(1)文法。n 显然该文法的规范LR(1)项目集的集合中没有同心项目集，因此该文法也是LALR(1)文法。id1L,id2L,id3LrealTD4type5in6 - addtype(id.entry, L.in)7in8 addtype9in10addtype1entry2entry3entry产产 生生 式式 语语 义义 规规 则则

10、 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) 建立翻译模式建立翻译模式n如果既有如果既有综合属性综合属性又有又有继承属性继承属性，在建立翻译模式，在建立翻译模式时就必须保证：时就必须保证：1. 产生式右边的符号的产生式右边的符号的继承属性继承属性必须在先于这个符号必须在先于这个符号的动作中计算出来。的动作中计算出来。2. 一个动作不能引用这个动作右边的符号的一个动作不能

11、引用这个动作右边的符号的综合属性综合属性。3. 产生式左边非终结符的产生式左边非终结符的综合属性综合属性只有在它所引用的只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的的动作通常可放在产生式右端的末尾末尾。 SA1A2A1.in:=1; A2.in:=2 Aaprint(A.in)在写语法制导定义之前，首先分析清楚需要为文在写语法制导定义之前，首先分析清楚需要为文法符号定义一些什么属性，然后看这些属性的值法符号定义一些什么属性，然后看这些属性的值是否可以由文法符号本身所推出的串决定。若是，是否可以由文法符号本身

12、所推出的串决定。若是，则应该只用综合属性就能解决。则应该只用综合属性就能解决。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 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.maxS S. in := 0 SS

13、 (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 := L1. in + L1.num+1 S L.num := L1.num + S.num +1 L S. in := L. in S L. num := S.num 导数导数产产 生生 式式语语 义义 规规 则则 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

14、 := T.exp T T1* *F T.d := T1.d * *F.exp + T1.exp * *F.d; T.exp := T1.exp * *F.exp T 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:=numP 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:

15、TD.sum= 1D proc id; D1; SD.sum=D1.sum+1P DD D;D | id:T | proc id; D; S(2)变量变量id的嵌套深度的嵌套深度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; Sn用S的综合属性val给出下面文法中S产生的二进制数的值。例如，输入101.101时，S.val5.625。nS L.L | L L L B | B B 0 | 1 nS L.L

16、| L L L B | B B 0 | 1n(1)仅使用综合属性仅使用综合属性S L1.L2 S.valL1.val+L2.val /2L2.lengthS L S.valL.valL L B 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=11. 产生式右边的符号的产生式右边的符号的继承属性继承属性必须在先必须在先于这个符号的动作中计算出来。于这个符号的动作中计算出来。2. 一个动作不能引用这个动作右边的符号一个动作不能引用这个动作右边的符号的的综合属性综合

17、属性。3. 产生式左边非终结符的产生式左边非终结符的综合属性综合属性只有在只有在它所引用的所有属性都计算出来以后才能它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常放在产生计算。计算这种属性的动作通常放在产生式右端的式右端的末尾末尾。产产 生生 式式语语 义义 规规 则则 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

18、.nptr F id F.nptr := mkleaf (id, id.entry) F num F.nptr := mkleaf (num, num.val) E 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 + +使用继承属性构造使用继承属

19、性构造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.nptr:=E.nptrT id T.nptr:=mkleaf(id,id.entr

20、y)T num T.nptr:=mkleaf(num,num.val)4.7令综合属性val表示S产生的二进制数的值。SL.L|LLLB|BB0|1(a)试用各有关综合属性决定S.val.如果只有整数部分，很显然，可以定义如下：SLS.val = L.val;LL1BL.val = L1.val *2 + B.val;LBL.val = B.val; L.b =2;B0B.val =0;B1B.val =1;为了求小数部分的值，引入L的综合属性b记录2的L的位数次幂值(2lengthofL)SL1.L2S.val =L1.val +L2.val /L2.b;SLS.val =L.val;LL1BL.val = L1.val *2 + B.val; L.b =L.b*2;LBL.val = B.val; L.b =2;B0B.val =0;B1B.val =1;访问链n访问链的使用及建立n动态作用域和静态作用域产生的不同输出n值调用、引用调用、复写恢复调用、换名调用例例 题题 n假定使