编译原理第4章5剖析.ppt

4.5 LR分析法 4.5 LR分析法 4.5 LR分析法 4.5.1 LR分析器的逻辑结构和工作过程 4.5.1 LR分析器的逻辑结构和工作过程 4.5.1 LR分析器的逻辑结构和工作过程 4.5.1 LR分析器的逻辑结构和工作过程 4.5.1 LR分析器的逻辑结构和工作过程 4.5.1 LR分析器的逻辑结构和工作过程 4.5.1 LR分析器的逻辑结构和工作过程 4.5.1 LR分析器的逻辑结构和工作过程 4.5.1 LR分析器的逻辑结构和工作过程 4.5.1 LR分析器的逻辑结构和工作过程 4.5.1 LR分析器的逻辑结构和工作过程 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 4.5.2 LR（0）分析法 通过闭包函数（CLOSURE）和状态转移函数(GO)很容易构造出文法 G 的识别文法规范句型活前缀的DFA。 (3) 构造识别文法规范句型活前缀DFA的方法 : (a) 求CLOSURE{S→?S}，得到初态 项目集。 (b) 对初态项目集或其它已构造的项 目集，应用状态转移函数GO(I,X) 求出新的项目集（后继状态）。 (d) 转移函数GO建立状态之间的连 结关系。 对前例中的文法，构造识别文法所有规范句型活前缀的DFA如下图所示： (c) 重复(b)直到不出现新的项目集 （新状态）为止。 0. S→S 1. S→A 2. S→B 3. A→aAb 4. A→c 5. B→aBb 6. B→d S→·S S→·A S→·B A→·aAb A→·c B→·aBb B→·d I0: I1: S→S· I2: S→A· I4: A→·aAb A→·c B→·aBb B→·d A→a·Ab B→a·Bb I5: A→c· I6: B→d· 识别文法G 活前缀的DFA S A B a c d c d a I3: S→B· I7: A→aA·b I8: A→aAb· I9: B→aB·b 识别文法G 活前缀的DFA I10: B→aBb· b b A B a S→·S S→·A S→·B A→·aAb A→·c B→·aBb B→·d I0: I1: S→S· I2: S→A· I4: A→·aAb A→·c B→·aBb B→·d A→a·Ab B→a·Bb I6: B→d· S A B a c d c d I3: S→B· I5: A→c· 注意，DFA中的每一个状态都是终态，当M到达它们时，识别出某规范句型的一个活前缀，对那些只含归约项目的项目集，如I2、I3、I5 、 I6、I8、I10，当M到达这些状态时，表示已识别出一个句柄，这些状态称为句柄识别态。 当M处于状态I1时，M识别的活前缀为S，表示输入串已成功分析完毕，用S→S进行最后一次归约，称状态为接受状态。 构成识别一个文法活前缀的DFA的状态（项目集）的全体称为这个文法的LR(0)项目集规范族。 (4) LR(0)分析表的构造 : 若一个文法G的拓广文法G的LR(0)项目集规范族中的每个项目集不存在移进项目和归约项目同时并存或多个归约项目同时并存，则称G为LR(0)文法。 I7: A→aA·b I8: A→aAb· I9: A→aB·b 识别文法G 活前缀的DFA I10: B→aBb· b b A B a S→·S S→·A S→·B A→·aAb A→·c B→·aBb B→·d