1、！溫故知新溫故知新回顧回顧v活前綴活前綴v活前綴的識別活前綴的識別vLR(0)LR(0)項目集項目集v構建識別活前綴的構建識別活前綴的DFADFA2LR(1)LR(1)分析練習題目分析練習題目3LR(1)LR(1)分析練習解答過程分析練習解答過程v1.1.對原文法進行拓廣對原文法進行拓廣 ( (添加產生式添加產生式S-S-S S ) )v2.2.拓拓廣廣文法文法S S 的的LR(0)LR(0)項目集規范族項目集規范族4拓廣文法拓廣文法G G 的的LR(0)LR(0)項目集規范族項目集規范族5I0:S SS V=ES EV *EV idE VI1:SS I2:SV =EEV I3:SE I4:V

2、* EE V V *EV idI5:Vid I6:SV= EE VV *EV idI7:V*E I8:EV I9:SV=E 識別產生式文法活前綴的識別產生式文法活前綴的DFADFAidS SS V=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 EI7I96本講綱要本講綱要vSLR(1)SLR(1) SLR(1)SLR(1)分析表的構造分析表的構造 SLR(1)SLR(1)文法描述能力有限文法描述能力有限v

3、LR(1)LR(1)分析分析vLALRLALRvLRLR文法和文法和LRLR分析方法的特點分析方法的特點73.53.5 LRLR分析器分析器83.53.5 LRLR分析器分析器93.53.5 LRLR分析器分析器10v一般性構造過程一般性構造過程 首先對文法進行拓廣首先對文法進行拓廣 添加產生式添加產生式S-SS-S 構建識別活前綴的構建識別活前綴的DFADFA 基于基于DFADFA構建分析表構建分析表11121314本講綱要本講綱要vSLR(1)SLR(1) SLR(1)SLR(1)分析表的構造分析表的構造 SLR(1)SLR(1)文法描述能力有限文法描述能力有限vLR(1)LR(1)分析分

4、析vLALRLALRvLRLR文法和文法和LRLR分析方法的特點分析方法的特點15SLR(1)SLR(1)文法的弱點文法的弱點vSLR(1)SLR(1)文法描述能力有限文法描述能力有限16每個SLR(1)文法都不是二義的，但是，有許多非二義的文法不是SLR(1)。SLR(1)SLR(1)文法的弱點文法的弱點vSLR(1)SLR(1)文法描述能力有限文法描述能力有限17溫故知新溫故知新本講綱要本講綱要vSLR(1)SLR(1) SLR(1)SLR(1)分析表的構造分析表的構造 SLR(1)SLR(1)文法描述能力有限文法描述能力有限vLR(1)LR(1)分析分析vLALRLALRvLRLR文法和

5、文法和LRLR分析方法的特點分析方法的特點19LR(1)LR(1)文法文法v與與SLR(1)SLR(1)文法的區別文法的區別 項目集的定義發生了改變項目集的定義發生了改變v添加了前向搜索符添加了前向搜索符v項目集改變的目的是增強描述能力項目集改變的目的是增強描述能力2021有效有效22有效有效23LR(1)文法v怎么加前向搜索符？初始項目集I0： SS, $ 將$作為向前的搜索符計算閉包CLOSURE(I) (a) I中的任何項目都屬于CLOSURE(I) (b) 若有項目 AB, a在CLOSURE(I)中，而B 是文法中的產生式，b是FIRST(a)中的元素，則B, b也屬于CLOSURE

6、(I)通過這個來保證在用B 進行歸約后，出現的輸入字符b是句柄B中B的后繼符號，或者是B歸約為A后可能出現的終結符24構建構建LR(1)LR(1)項目集項目集v例：例：25構建構建LR(1)LR(1)項目集項目集v例：例：26構建構建LR(1)LR(1)項目集項目集v例：例：27這一項的加入，這一項的加入，使得閉包中又要使得閉包中又要加入新元素！加入新元素！構建構建LR(1)LR(1)項目集項目集v例：例：28LR(1)LR(1)分析分析v從另一個例子來完整地看一下構建識別活從另一個例子來完整地看一下構建識別活前綴的前綴的DFADFA的過程的過程29構造規范的構造規范的LRLR分析表分析表30

7、構造規范的構造規范的LRLR分析表分析表31構造規范的構造規范的LRLR分析表分析表32S SS BBB bBB aS S, $ I0S BB, $B bB, b/aB a, b/aS S, $ I1SS BB, $B bB, $B a, $ I2BB bB, b/aB bB, b/aB a, b/a I3B a, b/a I4aabbS BB, $ I5B bB, $B bB, $B a, $ I6B bB, $ I9B a, $ I7B bB, b/a I8BbbBaaB構造規范的構造規范的LRLR分析表分析表 如果如果 A A , , a a 在在I Ii i中，且中，且A A S S

8、，那么置那么置actionaction i i, , a a 為為rjrj . .33構造規范的構造規范的LRLR分析表分析表34本講綱要本講綱要vLR(1)LR(1)分析分析vLALRLALRvLRLR文法和文法和LRLR分析方法的特點分析方法的特點35LALRLALRv從前面的例子看到，從前面的例子看到，LR(1)LR(1)分析表的狀態數目比較分析表的狀態數目比較大大vLALRLALR是在是在SLR(1)SLR(1)和和LR(1)LR(1)之間進行了文法描述能力之間進行了文法描述能力與分析表緊湊程度之間做的折衷與分析表緊湊程度之間做的折衷 SLR(1)SLR(1)文法描述能力稍弱，而由于狀

9、態數目較小能夠文法描述能力稍弱，而由于狀態數目較小能夠得到高效實現（不必消耗太多內存）得到高效實現（不必消耗太多內存） LR(1)LR(1)文法描述能力較強，但是由于狀態數目多，分析文法描述能力較強，但是由于狀態數目多，分析表較大表較大 LALRLALR的描述能力與分析表大小介乎的描述能力與分析表大小介乎SLR(1)SLR(1)與與LR(1)LR(1)之間之間36LALRLALRvLALRLALR的做法：的做法：v合并識別 LR(1)文法的活前綴的DFA中的同心項目集v同心的同心的LR(1)LR(1)項目集項目集B B bBbB, $, $ 與與 373.53.5 LRLR分析器分析器383.

10、53.5 LRLR分析器分析器39B bB, b/aB bB, b/aB a, b/a I3B bB, $B bB, $B a, $ I63.53.5 LRLR分析器分析器40LALR41LALR42LALR43LALR44LALR45LALR46LALR47LALR48LALR49構造LR(1)項目集規范族C = I0, I1, , In。尋找LR(1)項目集規范族中同心的項目集，用它們的并集代替它們。按構造規范的LR(1)分析表的方式進行構造。50LR(1)LR(1)分析練習題目分析練習題目51LR(1)LR(1)分析練習解答過程分析練習解答過程v答：答：vStep 1. Step 1.

11、對原文法進行對原文法進行拓廣拓廣 ( (添加產生式添加產生式S-SS-S) )52拓廣文法拓廣文法G G 的的LR(0)LR(0)項目集規范族為：項目集規范族為：53I0:S SS V=ES EV *EV idE VI1:SS I2:SV =EEV I3:SE I4:V* EE V V *EV idI5:Vid I6:SV= EE VV *EV idI7:V*E I8:EV I9:SV=E 識別產生式文法活前綴的識別產生式文法活前綴的DFADFAidS SS V=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 EI7I954LR(1)LR(1)分析練習解答過程分析練習解答過程vStep 2: Step 2: 構建識別（拓廣）文法活前綴構建識別（拓廣）文法活前綴的的DFADFA55作業