大三下课程编译原理

Ch5Ch5 LR0)SLR1)LR1)第1Ch5Ch5语法分 5.7LALR(1)分LALR1LALR1)第2Ch5语法分 5.7LALR(1)分 LALR(1)分析实现思 LR(1)SLR(1)分析器开销：LR(1) SLR(1)LR(0)开销LR(0)、分析功能 第3Ch5Ch5语法分 5.7LALR(1)分 LALR(1)分析实现思Look-AheadLALR(1)分析表状态数LR(0)LALR(1)分析功能第4Ch5Ch5语法分 5.7LALR(1)分 LALR(1)分析实现思 S→S→LL→R→第5Ch5语法分 5.7LALR(1)分 LALR(1)分析实现思S→SS→S→LL→R→0： L→R→4：L4：LR→L→·*L→

6：S→L=·2：S→2：S→Ｌ·=ＲR→L·3：S→3：S→ L→·*LLR7：L7：LL

8：R→第6CCh5语法分 5.7LALR(1)分 LALR(1)分析实现思6S6SL＝R，#Li，#LRL，#

RSL＝R

Li，＝/# R

13L*R，# LLi，#L*R，＝/#8

第7Ch5语法分 5.7LALR(1)分 LALR(1)分析实现思S→SS→S→LL→R→0： L→R→4：L4：LR→L→·*L→

6：S→L=·2：S→2：S→Ｌ·=ＲR→L·3：S→3：S→ L→·*LLR7：L7：LL

8：R→第8CCh5语法分 5.7LALR(1)分 LALR(1)分析实现思6S6SL＝R，#Li，#LRL，#

RSL＝R

Li，＝/# R

13L*R，# LLi，#L*R，＝/#8

第9Ch5语法分 5.7LALR(1)分 LALR(1)分析实现思S→SS→S→LL→R→0： L→R→4：L4：LR→L→·*L→

6：S→L=·2：S→2：S→Ｌ·=ＲR→L·3：S→3：S→ L→·*LLR7：L7：LL

8：R→第10CCh5语法分 5.7LALR(1)分 LALR(1)分析实现思6S6SL＝R，#Li，#LRL，#

SSL＝R

Li，＝/# R

13L*R，# LLi，#L*R，＝/#8

第11Ch5语法分 5.7LALR(1)分 LALR(1)分析实现思S→SS→S→LL→R→0： L→R→4：L4：LR→L→·*L→

6：S→L=·2：S→2：S→Ｌ·=ＲR→L·3：S→3：S→ L→·*LLRL

8：R→第12CCh5语法分 5.7LALR(1)分 LALR(1)分析实现思6S6SL＝R，#Li，#LRL，#

SSL＝R

Li，＝/# R

13L*R，# LLi，#L*R，＝/#8

第13Ch5语法分 5.7LALR(1)分 LALR(1)分析实现思S→SS→S→LL→R→0： L→R→4：L4：LR→L→·*L→

6：S→L=·2：S→2：S→Ｌ·=ＲR→L·3：S→3：S→ L→·*LLRL

8：R→第14CCh5语法分 5.7LALR(1)分 LALR(1)分析实现思6S6SL＝R，#Li，#LRL，#

SSL＝R

Li，＝/# R

13L*R，# LLi，#L*R，＝/#8

第15CCh5语法分 5.7LALR(1)分 LALR(1)分析实现思

CCh5语法分 5.7LALR(1)分 LALR(1)分析实现思

对文法G的LR(1)项目集规范族，若存在两个(或同心项目集。或称I0、I1具有相同的心。 第17Ch5语法分 5.7LALR(1)分Ch5语法分 5.7LALR(1)分 LALR(1)分析实现思SL＝RSSLR

RLRL，# L

iLLL

*LL*RL*R

第18Ch5语法分 5.7LALR(1)分 LALR(1)分析实现思 注意

第19Ch5Ch5语法分 5.7LALR(1)分LALR1LALR1第20Ch5语法分 5.7LALR(1)分 LALR(1)分析表构 方法：设C＝｛I0，I1，…，In｝,分析表的状态＝｛0，1，…n｝①若GOIka)＝Ij，aVTactionK若GOIk，A)＝IjAVN，则置GOTO[KA］＝j②若［②若［A·,a］∈Ik，则置action(Ka)＝rjA为文法G的第j［S’→S·，＃Ik，则置actionK④分析表中不能用①至③规则填入信息的元素，则置“出错标志第21Ch5

5.7LALR(1)分 LALR(1)分析表构输入 输出：文法G的LALR(1)方法：设状态集Q＝｛0，1，…n｝＝f(k,a)＝j，aVTaction(k,a)＝Sj；若f(k，A)＝j，AVN，则置GOTO[KA］＝j。②若［②若［A·,a］∈k，则置action(Ka)＝rjA为文法G的第j［S→S·，＃k，则置actionK第22Ch5语法分 5.7LALR(1)分Ch5语法分 5.7LALR(1)分 LALR(1)分析实现思SL＝RSSLR RL

SL＝ L

iLLL

*LL*RL*R

第23S→S→LL→R→Ch55.7LALR(1 LALR(1=*i#LRS0231123699第24Ch5语法分 5.7LALR(1)分 LALR(1)分析表构法G的LALR(1)分析表，如果每个不含文法。使用LALR(1)分析表的语法分析器第25Ch5语法分 5.7LALR(1)分 LALR(1)分析表构 C={I0,I1,I2,…,InMM0M1M2Mm 第26CCh5语法分 5.7LALR(1)分 LALR(1)分析表构 能是归约—归

[A[A•,W1[A•,W2[B•a,b[B•a,c W1∩{a}= W2∩{a}= (W1∪W2)∩{a}=第27Ch5语法分 5.7LALR(1)分 LALR(1)分析表构Ik/j[A•,W1∪W2][B•a,{b}∪{c}若此时Ik/j有“移进—归约 (W1∪W2)∩{a} 第28Ch5语法分 5.7LALR(1)分 LALR(1)分析表构

YN N

NG为LRG为SLR N

G为G为LR

第29Ch5语法分 5.7LALR(1)分 LALR(1)分析表构 S→Aa|bAc|Bc|bBa第30Ch5语法分 5.7LALR(1)分 LALR(1)分析表构S'→S'→•S→•Aa|•bAcBc|•A→•B→• A→dB→d

S→Aa|bAc|Bc|bBaS→Aa|bAc|Bc|bBa第31S'S'→S•,S5ddSS→Aa|bAc|Bc|bBaCh5105.7LALR(1) LALR(1S'→•S,S→•Aa|•bAcBc|•bBa,A→•d,B→•d,A→d•,B→d•,A2S→A•a,a6S→Aa•,3b9B4S→B•c,cdABS→bB•a,S→b•Acb•Ba,A→•d,B→•d,A→d•,B→d•,S→bA•c,S→bAc•,S→Bc•,

S→bBaS→bBa•,

第32CCh5语法分 5.7LALR(1)分 LALR(1)分析表构S'→•S'→•S,S→•Aa|•bAcBc|•bBa,A→•d,B→•d,AA→d•,B→d•, SS→b•Acb•Ba,A→•dB→•d,

。第33Ch5Ch5 LR0)SLR1)LR1)第34Ch5语法分 5.8LR分析对二义文法的应 第35Ch5Ch5语法分 5.8LR分析对二义文法的应G：G：EE+E|E*E|(E)| ET|TF|T*FF(E)|i G：SiSeS|iS| G'：S{iSeS}|{iS}|第36①②③④⑤Ch5语法分 ①②③④⑤ 设有文法G(E)Ch5语法分 5.8Ch5语法分 5.8LR分析对二义文法的应

11 +

EE **E E

＋

3E

E 9

(6E(E)

Ei+*

第38E’E’E①④EE②⑤E③Ch55.8LR1178 ｛＋，*,),#}∩{{＋}∪{*}}≠Ch5语法分 5.8Ch5语法分 5.8LR分析对二义文法的应①E’②E③E④E⑤EFOLLOW(Ｅ)＝｛＋，*,),#状i+*()#E01126347586789第40$:$:i+i+iCh5语法分 Ch5语法分 5.8LR分析对二义文法的应EP7E4+1E0#action(7,+)=$:i+i*iFaction(7,*)=

P5*7E4+5*7E4+1E0#Ch5 Ch55.8LRS’→S→iSeS|iS|①i:ifere:aS第42Ch5Ch55.8LRS·SSS·SS·iSeSS·iSS·aSi·SeSSi·SS·iSeSS·iSS·aSaSSSai SiSSiSSiS0iSieS’→①SS’→①S→iSeS|iS|②|③|SiSe·SS·iSeSS·iSS·aa33 SSiSeS

第43Ch5Ch55.8LRiea#S0iea#S0112434566

第44Ch5Ch55.8LR对$对$eife1 ife2 S1elsee②|②|③|S→iSeS|iS|①S’→i$:iiaeaFaction(4,e)=

5e4S2i2i0#

P第45Ch5Ch5LR0)SLR1)LR1)第46Ch5语法分 5.9LR分析的的错误处理与恢统环境生疏…第47Ch5Ch5语法分 5.9LR分析的的错误处理与恢 迅速从每个错误中恢复过来，以便诊断后面第48Ch5Ch5语法分 5.9LR分析的的错误处理与恢 第49Ch5Ch5语法分 5.9LR分析的的错误处理与恢；、}；、}、end第50Ch5Ch5语法分 5.9LR分析的的错误处理与恢第51Ch5Ch5语法分 5.9LR分析的的错误处理与恢(i+ii(i+i)i+第52Ch5语法分 5.9LR分析的的错误处理与恢 第53Ch5Ch5语法分 5.9LR分析的的错误处理与恢 第54Ch5语法分 5.8Ch5语法分 5.8LR分析对二义文法的应

Ei

11 +4

**E EiEi

( *+*

E(E））

第55Ch5语法分Ch5语法分 5.8LR分析对二义文法的应状i+状i+*()#E01126347586789第56Ch5语法分 5.8Ch5语法分 5.8LR分析对二义文法的应

11

Ei

E EiiEi

( *+*

E(E））

第57Ch5Ch5语法分 5.9LR分析的的错误处理与恢i或（E）,此时若遇到+、*i和状态3入栈；(shift第58Ch5Ch5语法分 5.8LR分析对二义文法的应状i+* #E01126347586789第59Ch5语法分 5.8Ch5语法分 5.8LR分析对二义文法的应

11

Ei

E EiiEi

( *+*

E(E））

第60Ch5Ch5语法分 5.9LR分析的的错误处理与恢处于状态0、1、2、4、5时，若遇到“）”，删除输入的“）”；(F++)第61Ch5Ch5语法分 5.8LR分析对二义文法的应状i+* #E01126347586789第62Ch5语法分 5.8Ch5语法分 5.8LR分析对二义文法的应

11

Ei

E EiiEi

( *+*

E(E））

第63Ch5Ch5语法分 5.9LR分析的的错误处理与恢算符或“)i”(则将假设的“+4入栈(P第64Ch5Ch5语法分 5.8LR分析对二义文法的应状i+* #E01126347586789第65Ch5语法分 5.8Ch5语法分 5.8LR分析对二义文法的应

11

Ei

E EiiEi

( *+*

E(E））

第66Ch5Ch5语法分 5.9LR分析的的错误处理与恢或“）”，但遇到“#e4。）第67状i+* #E01126347586789①E’E②EE+E③E①E’E②EE+E③EE*E④E(E)⑤E e2:删除输入的“）(F；出错信息：）e3:+4入栈(P+；出错信息：e4:将假设的“）”和状态9入栈(P；出错信息：）

第68CCh5语法分 5.9LR分析的的错误处理与恢$1:(i+iF

$:(i+i)7E4+7E4+6E2(0#

action(9,#)=PE6)9PPE6)9(2P(2E

0#0#E)action(

#)=

action(6,#)=

第69CCh5语法分 5.9LR分析的的错误处理与恢 ii#

i+i#

action(4,i)=i#E10+4i#E10+4action(1,i)= 第70Ch5Ch5 LR0)SLR1)LR1)第71 Ch5 第72Ch5语法分 5.10.1YACC简YACC(YetAnother piler)parsergenerator 第73 5.10.1YACC Ch5CompilerCompilerCompiler—Compiler—

第74Ch5语法分

语言x

y.tab.c

语言x的 y.tab.c 第75 5.10.1YACC Ch5

①

③第76 5.10.1YACC Ch5②使用命令yaccPAS.y运行YACC，正确则输出y.tab.c；③调用C编译器编译ccy.tab.c，并与其它C模第77 5.10.1YACC Ch5

①

③第78 5.10.1YACC Ch5

构造LR(1)的C(ITEMSET1算法5.9的C（ITEMSET1'）；构造LALR(1)的分析表(CT1算法第79 5.10.1YACC Ch5G第80 Ch5 第81 5.10.2YACC Ch5第82Ch5语法分 5.10.2YACC语％｛％｝Ｃ语言程序的常规说明(/ ％说明内容％说明内容第83Ch5语法分 5.10.2YACC语 #include #include #defineYYSTYPEdouble /*YACC栈定义 token left‘+’‘- left‘*’ right

第84