编译原理重点4.ppt

《编译原理重点4.ppt》由会员分享，可在线阅读，更多相关《编译原理重点4.ppt（113页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 AnIntroductiontoDatabaseSystem中南民族大学计算机科学学院中南民族大学计算机科学学院编译原理编译原理Compilers Principles第七章第七章 自下而上的自下而上的LR(K)LR(K)分析分析方法方法Bottom-up parsingBottom-up parsingAnIntroductiontoDatabaseSystem概述概述一一.自底向上的分析方法是一种移进自底向上的分析方法是一种移进-规约过程，规约过程，关键问题是：如何确定句柄。关键问题是：如何确定句柄。二二.LR(k).LR(k)方法于方法于19651965年由年由KnuthKnuth提出

2、。提出。三三.LR(k).LR(k)分析器：从分析器：从左左到右扫描输入串，进行到右扫描输入串，进行规规范归约范归约。分析过程中，至多向前查看。分析过程中，至多向前查看k k个输入个输入符号，即可决定当前的动作是归约还是移进。符号，即可决定当前的动作是归约还是移进。若为归约，能选择唯一一个产生式进行归约。若为归约，能选择唯一一个产生式进行归约。编译原理CompilersPrinciples第7章3概述概述(续续1)1)四四.LR(k).LR(k)分析器功能较强，主要优缺点为：分析器功能较强，主要优缺点为：1.1.优点优点:(1)(1)对文法的限制比较少对文法的限制比较少(与自顶向下的与自顶向下

3、的LL(K)LL(K)、自底向上的优先分析方法相比而言）。自底向上的优先分析方法相比而言）。(2)(2)分析速度快，能准确、即时地指出出错位分析速度快，能准确、即时地指出出错位置。置。2.2.缺点：对于一个实用语言文法的分析器来说，构缺点：对于一个实用语言文法的分析器来说，构造工作量很大。造工作量很大。编译原理CompilersPrinciples第7章4概述概述(续续2)2)五五.LR(k).LR(k)分析器由一个总控程序和一个分分析器由一个总控程序和一个分析表以及析表以及2 2个分析栈构成。个分析栈构成。六六.4.4种分析表的构造方法：种分析表的构造方法：LR(0),SLR(1),LR(1

4、),LALR(1)LR(0),SLR(1),LR(1),LALR(1)编译原理CompilersPrinciples第7章57.1 LR7.1 LR分析方法概述分析方法概述LR(k)LR(k)分析器由一个总控程序和一个分析表以及分析器由一个总控程序和一个分析表以及2 2个分析栈个分析栈构成。构成。LRLR分析器的总控程序相同。分析器的总控程序相同。不同文法，分析表不同；同一文法，采用不同不同文法，分析表不同；同一文法，采用不同LRLR分析分析法，分析表也不同。法，分析表也不同。分析表可分为动作表分析表可分为动作表(ACTION)(ACTION)和状态转换表和状态转换表(GOTO)(GOTO)。

5、分析栈包括文法符号栈和相应的状态栈。分析栈包括文法符号栈和相应的状态栈。LR(k)LR(k)分析器的工作过程为：分析器的工作过程为：编译原理CompilersPrinciples第7章6LRLR分析器工作过程示意图分析器工作过程示意图Sn Xn.S1 X1S0 X0LR驱动程序动作表 转移表action goto输出输入串XXX$编译原理CompilersPrinciples第7章7LRLR分析器工作过程示意图的说明分析器工作过程示意图的说明 移进 ai 和s=gotosm,ai进栈actionsm,ai=归约 rj:AXm-r+1Xm-r+2Xms=gotosm-r,A 接受 出错gotoS

6、i,X=SjX为文法符号 编译原理CompilersPrinciples第7章8回顾：移进回顾：移进-规约分析规约分析 例例1 1文法文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B d步骤步骤符号栈符号栈输入符号串输入符号串动作动作 1）#abbcde#移进移进 2）#a bbcde#移进移进 4）#aA bcde#移进移进 6）#aA cde#移进移进 7）#aAc de#移进移进 9）#aAcB e#移进移进11）#S#接受接受对输入串对输入串abbcdeabbcde#的移进的移进-规约分析过程规约分析过程 5）#aAb cde#归约归约(AAb)3）#ab bcde#归

7、约归约(Ab)8）#aAcd e#归约归约(Bd)10）#aAcBe#归约归约(SaAcBe)编译原理CompilersPrinciples第7章9移进移进-归约中的问题归约中的问题在步骤在步骤3中，用中，用Ab归约归约在步骤在步骤5中，用中，用AAb归约归约问题：何时移进？何时归约？用哪个产生式归约问题：何时移进？何时归约？用哪个产生式归约？在优先分析方法中如何解决这个问题的？在优先分析方法中如何解决这个问题的？编译原理CompilersPrinciples第7章10移进移进-归约中的问题分析归约中的问题分析分析：已分析过的部分在栈中的前缀不同，而且移分析：已分析过的部分在栈中的前缀不同，而

8、且移进和归约后栈中的状态会发生变化进和归约后栈中的状态会发生变化我们引入一个新的状态栈来表示符号栈中的符号目我们引入一个新的状态栈来表示符号栈中的符号目前状态，用前状态，用LR分析表来表示不同状态下对于各输入符分析表来表示不同状态下对于各输入符号应采取的动作号应采取的动作 3）#ab bcde#归约归约(Ab)5）#aAb cde#归约归约(AAb)4）#aA bcde#移进移进 6）#aA cde#移进移进编译原理CompilersPrinciples第7章117.2 LR(0)7.2 LR(0)分析分析例例1 文法文法GS：(1)S aAcBe(2)A b(3)A Ab(4)B dS Si

9、 i:移进，并将状态移进，并将状态i i进进栈栈r ri i:用第用第i i个产生式归约，个产生式归约，同时状态栈与符号同时状态栈与符号栈退出相应个符号，栈退出相应个符号，根据根据GOTOGOTO表将相应表将相应状态入栈状态入栈文法文法GS的的LR(0)分析表分析表(注：该表没有填写完注：该表没有填写完)编译原理CompilersPrinciples第7章12对输入串对输入串abbcdeabbcde#的的LR(0)LR(0)分析过程分析过程输入串输入串abbcdeabbcde#的的分析过程分析过程步骤步骤 符号栈符号栈输入符号串输入符号串 动作动作 1）#abbcde#移进移进 0 S2 2）

10、#a bbcde#移进移进 02 S4 3）#ab bcde#归约归约(Ab)024 r2 3 4）#aA bcde#移进移进 023 S6 6）#aA cde#移进移进 023 S5 7）#aAc de#移进移进 0235 S8 9）#aAcB e#移进移进 02357 S911）#S#接受接受 01 acc 5）#aAb cde#归约归约(AAb)0236 r3 3 8）#aAcd e#归约归约(Bd)02358 r4 710）#aAcBe#归约归约(SaAcBe)023579 r1 1状态栈状态栈ACTIONGOTO编译原理CompilersPrinciples第7章13LR(0)LR(

11、0)分析分析的的问题问题n对于一个文法，会有一些什么样对于一个文法，会有一些什么样的状态呢？这些状态又是如何确的状态呢？这些状态又是如何确定的？定的？nLRLR分析表是如何得到的？分析表是如何得到的？编译原理CompilersPrinciples第7章14可归前缀与活前缀可归前缀与活前缀文法文法GS：(1)S aAcBe1(2)A b2(3)A Ab3(4)B d4每次归约句型的每次归约句型的前部分前部分依次为：依次为：ab2aAb3aAcd4aAcBe1规范句型的这种前部分符号串称为规范句型的这种前部分符号串称为可归前缀可归前缀我们把形成可归前缀之前包括可归前缀在内我们把形成可归前缀之前包括

12、可归前缀在内的所有规范句型的前缀都称为的所有规范句型的前缀都称为活前缀活前缀 ,a,ab ,a,aA,aAb ,a,aA,aAc,aAcd ,a,aA,aAc,aAcB,aAcBeS aAcBe1 aAcd4e1 aAb3cd4e1 ab2b3cd4e1编译原理CompilersPrinciples第7章15活前缀（活前缀（Viable Prefixes）的）的定义定义n活前缀：活前缀：S=*A =是文法是文法G中的一个规中的一个规范推导，如果符号串范推导，如果符号串是是的前缀，则称的前缀，则称是是G的一的一个个活前缀活前缀。其中，其中，S是对原文法拓广后的开始符号，即有：是对原文法拓广后的开

13、始符号，即有：S-S编译原理CompilersPrinciples第7章16识别活前缀的有限自动机识别活前缀的有限自动机LR方法中，并不是直接分析文法符号栈中的符号是否形成方法中，并不是直接分析文法符号栈中的符号是否形成句柄，但是，我们可以把文法的终结符和非终结符都句柄，但是，我们可以把文法的终结符和非终结符都看成有穷自动机的输入符号，每次把一个符号进栈看看成有穷自动机的输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到成已识别过了该符号，同时状态进行转换，当识别到可归前缀时，相当于在栈中形成句柄，认为达到了识可归前缀时，相当于在栈中形成句柄，认为达到了识别句柄的终态

14、。别句柄的终态。即用自动机中的状态来刻画分析过程中的某一种情形。即用自动机中的状态来刻画分析过程中的某一种情形。编译原理CompilersPrinciples第7章17如何构造识别活前缀的有限自动机如何构造识别活前缀的有限自动机n已经有了活前缀如何构造有限自动机?n活前缀及其可归前缀的一般计算方法编译原理CompilersPrinciples第7章18构造识别文法活前缀的构造识别文法活前缀的DFADFA的三种方法的三种方法一、根据形式定义求出活前缀的正规表达式，然一、根据形式定义求出活前缀的正规表达式，然后由此正规表达式构造后由此正规表达式构造NFANFA再确定化为再确定化为DFA(DFA(不

15、不实用，略实用，略)二、求出文法的所有项目，按一定规则构造识别二、求出文法的所有项目，按一定规则构造识别活前缀的活前缀的NFANFA再确定化为再确定化为DFA(DFA(了解了解)三、使用闭包函数（三、使用闭包函数（CLOSURECLOSURE）和转向函数和转向函数(GOTO(I,X)(GOTO(I,X)构造文法构造文法GG的的LR(0)LR(0)的项目集规的项目集规范族，再由转换函数建立状态之间的连接关系范族，再由转换函数建立状态之间的连接关系得到识别活前缀的得到识别活前缀的DFA(DFA(掌握掌握)编译原理CompilersPrinciples第7章19构造识别活前缀的有限自动机构造识别活前

16、缀的有限自动机 例子例子文法文法GS：S S0S aAcBe1A b2A Ab3B d4句子句子abbcdeabbcde的可归前缀如下：的可归前缀如下：S0S0ab1ab1aAb3aAb3aAcd4aAcd4aAcBe1aAcBe1构造识别其活前缀及可归前缀的有限自动机如下：构造识别其活前缀及可归前缀的有限自动机如下：104387131210182591461715161110SabaAbaAcdaAcBe*1*句子识别态句子识别态i句柄识别态句柄识别态SceBAadbAb编译原理CompilersPrinciples第7章20识别活前缀的有限自动机识别活前缀的有限自动机 例子例子104387

17、131210182591461715161110SabaAbaAcdaAcBe*X加上开始状态加上开始状态X确定化：确定化：X13246859SabAbcBed7*编译原理CompilersPrinciples第7章21例例1 1中中abbcdeabbcde#分析过程所对应的自动机分析过程所对应的自动机 步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1）#abbcde#移进移进 0 S2 2）#a bbcde#移进移进 02 S4 4）#aA bcde#移进移进 023 S6 6）#aA cde#移进移进 023 S5 7）#aAc de#移进移进 0235 S8 9）#aAcB e#

18、移进移进 02357 S911）#S#接受接受 01 acc 3）#ab bcde#归约归约(Ab)024 r2 3 5）#aAb cde#归约归约(AAb)0236 r3 3 8）#aAcd e#归约归约(Bd)02358 r4 710）#aAcBe#归约归约(SaAcBe)023579 r1 1状态栈状态栈ACTIONGOTO014235769SabAbcBed8*编译原理CompilersPrinciples第7章22步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1）#abbcde#移进移进 0 S2对输入串abbcde#的LR分析过程状态栈状态栈ACTIONGOTO014235

19、769SabAbcBed8*编译原理CompilersPrinciples第7章23步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1）#abbcde#移进移进 0 S2 2）#a bbcde#移进移进 02 S4 对输入串abbcde#的LR分析过程状态栈状态栈ACTIONGOTO014235769SabAbcBed8*编译原理CompilersPrinciples第7章24步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1）#abbcde#移进移进 0 S2 2）#a bbcde#移进移进 02 S4 对输入串abbcde#的LR分析过程 3）#ab bcde#归约归约(Ab)

20、024 r2 3状态栈状态栈ACTIONGOTO014235769SabAbcBed8*编译原理CompilersPrinciples第7章25步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1）#abbcde#移进移进 0 S2 2）#a bbcde#移进移进 02 S4 4）#aA bcde#移进移进 023 S6对输入串abbcde#的LR分析过程 3）#ab bcde#归约归约(Ab)024 r2 3状态栈状态栈ACTIONGOTO014235769SabAbcBed8*编译原理CompilersPrinciples第7章26步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作

21、1）#abbcde#移进移进 0 S2 2）#a bbcde#移进移进 02 S4 4）#aA bcde#移进移进 023 S6对输入串abbcde#的LR分析过程 3）#ab bcde#归约归约(Ab)024 r2 3 5）#aAb cde#归约归约(AAb)0236 r3 3状态栈状态栈ACTIONGOTO014235769SabAbcBed8*编译原理CompilersPrinciples第7章27步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1）#abbcde#移进移进 0 S2 2）#a bbcde#移进移进 02 S4 4）#aA bcde#移进移进 023 S6 6）#a

22、A cde#移进移进 023 S5对输入串abbcde#的LR分析过程 3）#ab bcde#归约归约(Ab)024 r2 3 5）#aAb cde#归约归约(AAb)0236 r3 3状态栈状态栈ACTIONGOTO*014235769SabAbcBed8编译原理CompilersPrinciples第7章28步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1）#abbcde#移进移进 0 S2 2）#a bbcde#移进移进 02 S4 4）#aA bcde#移进移进 023 S6 6）#aA cde#移进移进 023 S5 7）#aAc de#移进移进 0235 S8对输入串abb

23、cde#的LR分析过程 3）#ab bcde#归约归约(Ab)024 r2 3 5）#aAb cde#归约归约(AAb)0236 r3 3状态栈状态栈ACTIONGOTO*014235769SabAbcBed8编译原理CompilersPrinciples第7章29步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1）#abbcde#移进移进 0 S2 2）#a bbcde#移进移进 02 S4 4）#aA bcde#移进移进 023 S6 6）#aA cde#移进移进 023 S5 7）#aAc de#移进移进 0235 S8对输入串abbcde#的LR分析过程 3）#ab bcde#归

24、约归约(Ab)024 r2 3 5）#aAb cde#归约归约(AAb)0236 r3 3 8）#aAcd e#归约归约(Bd)02358 r4 7状态栈状态栈ACTIONGOTO014235769SabAbcBed8*编译原理CompilersPrinciples第7章30步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1）#abbcde#移进移进 0 S2 2）#a bbcde#移进移进 02 S4 4）#aA bcde#移进移进 023 S6 6）#aA cde#移进移进 023 S5 7）#aAc de#移进移进 0235 S8 9）#aAcB e#移进移进 02357 S9对输

25、入串abbcde#的LR分析过程 3）#ab bcde#归约归约(Ab)024 r2 3 5）#aAb cde#归约归约(AAb)0236 r3 3 8）#aAcd e#归约归约(Bd)02358 r4 7状态栈状态栈ACTIONGOTO014235769SabAbcBed8*编译原理CompilersPrinciples第7章31步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1）#abbcde#移进移进 0 S2 2）#a bbcde#移进移进 02 S4 4）#aA bcde#移进移进 023 S6 6）#aA cde#移进移进 023 S5 7）#aAc de#移进移进 0235

26、 S8 9）#aAcB e#移进移进 02357 S9对输入串abbcde#的LR分析过程 3）#ab bcde#归约归约(Ab)024 r2 3 5）#aAb cde#归约归约(AAb)0236 r3 3 8）#aAcd e#归约归约(Bd)02358 r4 710）#aAcBe#归约归约(SaAcBe)023579 r1 1状态栈状态栈ACTIONGOTO014235769SabAbcBed8*编译原理CompilersPrinciples第7章32步骤步骤 符号栈符号栈 输入符号串输入符号串动作动作 1）#abbcde#移进移进 0 S2 2）#a bbcde#移进移进 02 S4 4）

27、#aA bcde#移进移进 023 S6 6）#aA cde#移进移进 023 S5 7）#aAc de#移进移进 0235 S8 9）#aAcB e#移进移进 02357 S911）#S#接受接受 01 acc对输入串abbcde#的LR分析过程 3）#ab bcde#归约归约(Ab)024 r2 3 5）#aAb cde#归约归约(AAb)0236 r3 3 8）#aAcd e#归约归约(Bd)02358 r4 710）#aAcBe#归约归约(SaAcBe)023579 r1 1状态栈状态栈ACTIONGOTO014235769SabAbcBed8*编译原理CompilersPrincip

28、les第7章33LR(0)LR(0)项目集规范族项目集规范族由文法的产生式直接构造识别活前缀和可归前缀的有限由文法的产生式直接构造识别活前缀和可归前缀的有限自动机自动机项目（项目（itemitem）：）：在每个产生式的右部适当位置添加一个在每个产生式的右部适当位置添加一个圆点构成圆点构成项目项目例如：产生式例如：产生式S S aAcBeaAcBe对应有对应有6 6个项目个项目 0 S aAcBe 1 S a AcBe 2 S aA cBe 3 S aAc Be 4 S aAcB e 5 S aAcBe 有限自动机的每一个状态由一个有限自动机的每一个状态由一个项目项目构成构成编译原理Compil

29、ersPrinciples第7章34LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFANFA项目圆点的项目圆点的左部左部表示分析过程的某个时刻用该产生式归约表示分析过程的某个时刻用该产生式归约时时句柄已识别的部分句柄已识别的部分，圆点，圆点右部右部表示表示待识别的部分待识别的部分构造识别活前缀的构造识别活前缀的NFANFA：1 1、把文法的所有产生式的项目都引出，每个项目都为把文法的所有产生式的项目都引出，每个项目都为NFANFA的一个状态的一个状态2 2、确定、确定初态初态、句柄识别态句柄识别态、句子识别态句子识别态3 3、确定状态之间的转换关系、确定状态之间的转换关系(1)(1

30、)若项目若项目i i为为 X X X X1 1X X2 2.X.Xi-1i-1 X Xi i.X Xn n 项目项目j j为为 X X X X1 1X X2 2.X.Xi-1i-1 X Xi i X Xi+1i+1.X Xn n 则则从状态从状态i i到状态到状态j j连一条标记为连一条标记为X Xi i的箭弧的箭弧(2)(2)若若i i为为X X A A，k k为为A A ，则从状态则从状态i i画标记为画标记为 的箭弧到状态的箭弧到状态k k编译原理CompilersPrinciples第7章35LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NFA 例例1 1文法文法G：

31、S EE T+E E TT int*T T int T (E)文法的项目有：文法的项目有：1、S E2、S E 3、E T+E4、E T +E5、E T+E6、E T+E 7、E T8、E T 9、T int*T10、T int *T11、T int*T12、T int*T 13、T int 14、T int 15、T (E)16、T (E)17、T (E)18、T (E)2317eEe编译原理CompilersPrinciples第7章36LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NFA 例例1(1(续续1)1)S .E文法文法G：S EE T+E E TT int*T

32、 T int T (E)编译原理CompilersPrinciples第7章37LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NFA 例例1(1(续续2)2)S .ES E.EE.TeE .T+Ee文法文法G：S EE T+E E TT int*T T int T (E)编译原理CompilersPrinciples第7章38LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NFA 例例1(1(续续3)3)S E.E .T+ES .EE.TT .int*TeeET .(E)eT.inteeE T.T文法文法G：S EE T+E E TT int*T T int

33、T (E)编译原理CompilersPrinciples第7章39LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NFA 例例1(1(续续4)4)T .(E)S E.E .T+ES .EE.TE T.T.intT .int*TeeEE T.+ETeeeeeeT文法文法G：S EE T+E E TT int*T T int T (E)编译原理CompilersPrinciples第7章40LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NFA 例例1(1(续续5)5)T .(E)T (.E)(S E.E .T+ES .EE.TE T.T.intT .int*Tee

34、EeeeeeeTE T.+ET文法文法G：S EE T+E E TT int*T T int T (E)编译原理CompilersPrinciples第7章41LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NFA 例例1(1(续续6)6)T .(E)T (.E)(S E.E .T+ES .EE.TE T.T.intT .int*TeeeeEeeeeeeTE T.+ETT (E.)E文法文法G：S EE T+E E TT int*T T int T (E)编译原理CompilersPrinciples第7章42LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NF

35、A 例例1(1(续续7)7)T .(E)T (.E)(S E.E .T+ES .EE.TE T.T.intT .int*TeeeeEeeeeeeTE T.+ETT (E.)ET (E).)文法文法G：S EE T+E E TT int*T T int T (E)编译原理CompilersPrinciples第7章43LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NFA 例例1(1(续续8)8)T .(E)T (.E)(S E.E .T+ES .EE.TE T.T.intT .int*TeeeeEeeeeeeTE T.+ETT (E.)ET (E).)E T+.E+文法文法G：

36、S EE T+E E TT int*T T int T (E)编译原理CompilersPrinciples第7章44LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NFA 例例1(1(续续9)9)T .(E)T (.E)(S E.E .T+ES .EE.TE T.T.intT .int*TeeeeEeeeeeeTE T.+ETT (E.)ET (E).)E T+.E+eeE T+E.E文法文法G：S EE T+E E TT int*T T int T (E)编译原理CompilersPrinciples第7章45LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA

37、NFA 例例1(1(续续10)10)T .(E)T (.E)(S E.E .T+ES .EE.TE T.T.intT .int*TeeeeEeeeeeeTE T.+ETT (E.)ET (E).)E T+.E+eeE T+E.ET int.int文法文法G：S EE T+E E TT int*T T int T (E)编译原理CompilersPrinciples第7章46LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NFA 例例1(1(续续11)11)T .(E)T (.E)(S E.E .T+ES .EE.TE T.T.intT .int*TeeeeEeeeeeeTE T

38、.+ETT (E.)ET (E).)E T+.E+eeE T+E.ET int.intT int.*Tint文法文法G：S EE T+E E TT int*T T int T (E)编译原理CompilersPrinciples第7章47LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NFA 例例1(1(续续12)12)T .(E)T (.E)(S E.E .T+ES .EE.TE T.T.intT .int*TeeeeEeeeeeeTE T.+ETT (E.)ET (E).)E T+.E+eeE T+E.ET int.intT int.*TintT int*.T*文法文法G：

39、S EE T+E E TT int*T T int T (E)编译原理CompilersPrinciples第7章48LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NFA 例例1(1(续续13)13)T .(E)T (.E)(S E.E .T+ES .EE.TE T.T.intT .int*TeeeeEeeeeeeTE T.+ETT (E.)ET (E).)E T+.E+eeE T+E.ET int.intT int.*TintT int*.T*T int*T.Teee文法文法G：S EE T+E E TT int*T T int T (E)编译原理CompilersPrin

40、ciples第7章49LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的NFA NFA 例例1(1(续续14)14)15161718(E)2345617814139121110eeeeEeTeeeE+eintint*TeeeeeTe编译原理CompilersPrinciples第7章50LR(0)LR(0)中项目的分类中项目的分类根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为以下几种：移进项目，形如移进项目，形如 A a 待约项目，形如待约项目，形如 A B 归约项目，形如归约项目，形如 A 接受项目，形如接受项目，形如 S S 编译原理CompilersPrinciples第

41、7章51LR(0)LR(0)中构造识别活前缀的中构造识别活前缀的DFA DFA 例例1 1确定化确定化S .EE .TE .T+ET .(E)T .int*TT .intS E.E T.E T.+ET int.*TT int.T (.E)E .TE .T+ET .(E)T .int*TT .intE T+E.E T+.EE .TE .T+ET .(E)T .int*TT .intT int*.TT .(E)T .int*TT .intT int*T.T (E.)T (E).ET(intint*)EETint(intT+(T项目集项目集编译原理CompilersPrinciples第7章52LR

42、(0)LR(0)项目集规范族项目集规范族构成识别一个文法活前缀的构成识别一个文法活前缀的DFADFA项目集（状态）的项目集（状态）的全体称为这个文法的全体称为这个文法的LR(0)LR(0)项目集规范族项目集规范族NFANFA确定化为确定化为DFADFA的工作量较大，我们考虑直接构的工作量较大，我们考虑直接构造出项目集作为造出项目集作为DFADFA的状态，就可直接构造的状态，就可直接构造DFADFA通过通过闭包函数闭包函数(CLOSURE)(CLOSURE)来求来求DFADFA一个状态的项目一个状态的项目集集编译原理CompilersPrinciples第7章53LR(0)LR(0)项目集规范族

43、的构造项目集规范族的构造如果如果I I是文法是文法GG的一个项目集，定义和构造的一个项目集，定义和构造I I的闭包的闭包CLOSURE(I)CLOSURE(I)如下：如下：(1)(1)I I的项目都在的项目都在CLOSURE(I)CLOSURE(I)中中(2)(2)若若A A B 属于属于CLOSURE(I)CLOSURE(I)，则每一形如则每一形如B B 的项目也属于的项目也属于CLOSURE(I)CLOSURE(I)(3)(3)重复重复(2)(2)直到直到CLOSURE(I)CLOSURE(I)不再扩大不再扩大定义转换函数如下：定义转换函数如下：GOTOGOTO（I I，X X）=CLOS

44、URE=CLOSURE（J J）其中：其中：I I为包含某一项目集的状态，为包含某一项目集的状态，X X为一文法符号为一文法符号 J=J=任何形如任何形如A A X X 的项目的项目|A A X X 属于属于II编译原理CompilersPrinciples第7章54LR(0)LR(0)项目集规范族的构造项目集规范族的构造(续续)圆点不在产生式右部圆点不在产生式右部最左边最左边的项目称为的项目称为核核，唯一的例外是，唯一的例外是S S S S。因此用因此用GOTOGOTO（I I，X X）转换函数转换函数得到的得到的J J为转向后状态所含项目集的为转向后状态所含项目集的核。核。使用闭包函数（使

45、用闭包函数（CLOSURECLOSURE）和转向函数和转向函数(GOTO(I,X)(GOTO(I,X)构造文构造文法法GG的的LR(0)LR(0)的的项目集规范族项目集规范族，步骤如下：，步骤如下：(1)(1)置项目置项目SS S S为初态集的核，然后对核求闭包为初态集的核，然后对核求闭包 CLOSURECLOSURE（SS S S）得到初态的得到初态的项目集项目集(2)(2)对初态集或其它所构造的项目集应用转换函数对初态集或其它所构造的项目集应用转换函数GOTOGOTO(I(I，X)=CLOSURE(J)X)=CLOSURE(J)求出新状态求出新状态J J的项目集的项目集(3)(3)重复重复

46、(2)(2)直到不出现新的项目集为止直到不出现新的项目集为止编译原理CompilersPrinciples第7章55LR(0)LR(0)项目集规范族的构造项目集规范族的构造 例例1 1文法文法G：S EE T+E E TT int*T T int T (E)S .EE .TE .T+ET .(E)T .int*TT .intS E.E T.E T.+ET int.*TT int.T (.E)E .TE .T+ET .(E)T .int*TT .intE T+E.E T+.EE .TE .T+ET .(E)T .int*TT .intT int*.TT .(E)T .int*TT .intT i

47、nt*T.T (E.)T (E).ET(intint*)EETint(intT+(T编译原理CompilersPrinciples第7章56LRLR（0 0）项目集规范族项目集规范族 之之 例例2(1)2(1)识别文法识别文法G的活的活前缀的前缀的DFA文法文法G：(0)S E(1)E aA(2)E bB(3)A cA(4)A d(5)B cB(6)B d I1：S-E.I0：S-.EE-.aAE-.bBEI2：E-a.AA-.cAA-.dI3：E-b.BB-.cBB-.dba编译原理CompilersPrinciples第7章57LRLR（0 0）项目集规范族项目集规范族 之之 例例2(2)

48、2(2)识别文法识别文法G的活的活前缀的前缀的DFA文法文法G：(0)S E(1)E aA(2)E bB(3)A cA(4)A d(5)B cB(6)B d I1：S-E.I0：S-.EE-.aAE-.bBEI2：E-a.AA-.cAA-.dI3：E-b.BB-.cBB-.dbaI6：E-aA.I4：A-c.AA-.cAA-.dcI10：A-d.AdI5：B-c.BB-.cBB-.dcI7：E-bB.BI11：B-d.d编译原理CompilersPrinciples第7章58LRLR（0 0）项目集规范族项目集规范族 之之 例例2(3)2(3)识别文法识别文法G的活的活前缀的前缀的DFA文法文

49、法G：(0)S E(1)E aA(2)E bB(3)A cA(4)A d(5)B cB(6)B d I1：S-E.I0：S-.EE-.aAE-.bBEI2：E-a.AA-.cAA-.dI3：E-b.BB-.cBB-.dbaI6：E-aA.I4：A-c.AA-.cAA-.dcI10：A-d.AdI5：B-c.BB-.cBB-.dcI7：E-bB.BI11：B-d.dI8：A-cA.dcAI9：B-cB.Bdc编译原理CompilersPrinciples第7章59LR(0)LR(0)文法的定义文法的定义一个项目集可能包含多种项目一个项目集可能包含多种项目a)移进和归约项目同时存在。移进和归约项目

50、同时存在。移进移进-归约冲突归约冲突b)归约和归约项目同时存在。归约和归约项目同时存在。归约归约-归约冲突归约冲突LR(0)文法：若其文法：若其LR(0)项目集规范族不存在移进项目集规范族不存在移进-归约，或归约归约，或归约-归约冲突，称为归约冲突，称为LR(0)文法文法。LRLR（0 0）项目集规范族的项目类型分为如下四种：项目集规范族的项目类型分为如下四种：1 1）移进项目）移进项目 A a 2 2）待约项目待约项目 A B 3 3）归约项目归约项目 A 4 4）接受项目接受项目 S S 编译原理CompilersPrinciples第7章60LR(0)LR(0)分析表的构造分析表的构造n