编译原理课件

1、编 译 原 理 LR分分析析编 译 原 理 LR分分析析本章知识点本章知识点(内容内容)LR分析概述分析概述LR（0）分析）分析SLR（1）分析）分析LR（1）分析）分析LALR（1）分析）分析二义文法在二义文法在LRLR分析中的应用分析中的应用编 译 原 理 LR分分析析算符优先分析法存在的问题算符优先分析法存在的问题 强调算符之间的优先关系的唯一性，这使得它的强调算符之间的优先关系的唯一性，这使得它的适应面比较窄；算法在发现最左素短语的尾时，需要适应面比较窄；算法在发现最左素短语的尾时，需要返回来寻找对应的最左素短语头。返回来寻找对应的最左素短语头。LR分析法：分析法：1 对文法限制少；对

2、文法限制少；2 适用范围广；适用范围广；3 分析速度快；分析速度快； 4报错准确。报错准确。5 易于实现自动生成。由于构造分析器的工作量很大，易于实现自动生成。由于构造分析器的工作量很大，不大可能手工构造；如用软件工具不大可能手工构造；如用软件工具Yacc-Yet Another Compiler Compiler,Bell，这些软件工具叫，这些软件工具叫LR生成器生成器。 首页首页结束结束编 译 原 理 LR分分析析一、一、LR(k)LR(k)分析法分析法 L L ：从左到右扫描输入符号，：从左到右扫描输入符号， R R ：最右推导对应的最左归约：最右推导对应的最左归约, , k k ：超前

3、读入：超前读入k k个符号，用以确定归约所用的规则个符号，用以确定归约所用的规则。LR分析法在自左至右扫描输入串时就能发现其中分析法在自左至右扫描输入串时就能发现其中的任何错误并能准确地指出出错地点。的任何错误并能准确地指出出错地点。 大多数用上下文无关文法描述的程序语言都可用大多数用上下文无关文法描述的程序语言都可用LR分析器予以识别。分析器予以识别。主要缺点是，用手工构造分析程序则工作量相当主要缺点是，用手工构造分析程序则工作量相当大。因此，必须求助于自动产生这种分析程序的产大。因此，必须求助于自动产生这种分析程序的产生器。生器。 编 译 原 理 LR分分析析二、二、LRLR分析法分类：分

4、析法分类：LR(0)表构造法。这种方法的局限性极大、但它是建立表构造法。这种方法的局限性极大、但它是建立其它较一般的其它较一般的LR分析法的基础。分析法的基础。SIR表构造法。虽然，有一些文法构造不出表构造法。虽然，有一些文法构造不出SLR分析表，分析表，但是，这是一种比较容易实现又极有使用价值的方法。但是，这是一种比较容易实现又极有使用价值的方法。规范规范LR表构造法。这种分析表能力最强，能够适用一大表构造法。这种分析表能力最强，能够适用一大类文法，但实现代价过高，或者说，分析表的体积非常大。类文法，但实现代价过高，或者说，分析表的体积非常大。向前向前LR表构造法（简称表构造法（简称LAIR

5、）。这种分析表的能力介）。这种分析表的能力介于于SIR和规范和规范LR之间，稍加努力，就可以高效地实现。之间，稍加努力，就可以高效地实现。 首页首页结束结束编 译 原 理 LR分分析析规范归约（最左归约一最右推导的逆过程）的关键规范归约（最左归约一最右推导的逆过程）的关键问题是寻找句柄。问题是寻找句柄。 LR方法的基本思想是方法的基本思想是:在规范归约的过程中，一方在规范归约的过程中，一方面要记住已移进和归约出的整个字符串，也就是说面要记住已移进和归约出的整个字符串，也就是说要记住历史；一方面能够根据所用的产生式的推测要记住历史；一方面能够根据所用的产生式的推测未来可能碰到的输入符号，也就是说

6、能够对未来进未来可能碰到的输入符号，也就是说能够对未来进行展望。这样，当一串貌似句柄的字符串出现在分行展望。这样，当一串貌似句柄的字符串出现在分析栈的顶部时，我们希望能够根据历史和展望以及析栈的顶部时，我们希望能够根据历史和展望以及现实的输入符号这三部分的材料，决定出现在栈顶现实的输入符号这三部分的材料，决定出现在栈顶的这一串符号是否就是我们要找的的这一串符号是否就是我们要找的句柄。句柄。 首页首页结束结束编 译 原 理 LR分分析析三、三、LR分析器的逻辑结构分析器的逻辑结构 一个一个LR分析器包括两部分：一个总控分析器包括两部分：一个总控(驱动驱动)程序和一张分析表。注意：所有程序和一张分

7、析表。注意：所有LR分析器的总分析器的总控程序都是一样的，只是分析表各有不同。因此控程序都是一样的，只是分析表各有不同。因此产生器的主要任务就是产生分析表。产生器的主要任务就是产生分析表。LRLR分析器的分析器的核心部分是一张分析表。核心部分是一张分析表。采用下推自动机这种数据模型。包括以下几个部采用下推自动机这种数据模型。包括以下几个部分：分： 1.输入带。输入带。 2.分析栈：包括状态栈和文法符号栈两部分。分析栈：包括状态栈和文法符号栈两部分。 3.LR 分析表：包括动作表和状态转移表两张表。分析表：包括动作表和状态转移表两张表。首页首页结束结束编 译 原 理 LR分分析析a1 ai an

8、 #动作表动作表 action转移表转移表 goto状态栈状态栈 符号栈符号栈输入缓冲区输入缓冲区分析表分析表SmSm-1S1S0XmXm-1X1#首页首页结束结束编 译 原 理 LR分分析析分析表包括两部分：分析表包括两部分：一部分是（一部分是（ACTION)表，另一部分是表，另一部分是状态转状态转换换(GOTO)表。它们都是二维数组。表。它们都是二维数组。ACTIONS，a中规定了当状态中规定了当状态S面临输入符号面临输入符号a时应采取什么动作。时应采取什么动作。GOTOS，X规定了状态规定了状态S面对文法符号面对文法符号X(终结终结符或非终结符符或非终结符)时下一状态是什么。时下一状态是

9、什么。显然，显然，GOTOS，X定义了一个以文法符号为定义了一个以文法符号为字母表的字母表的DFA。 【例】演示【例】演示首页首页结束结束编 译 原 理 LR分分析析每一项每一项ACTIONSACTIONS，aJaJ所规定的动作是下述所规定的动作是下述4 4种可能之种可能之-： (1)(1)移进移进：把：把(S(S，a)a)的下一状态的下一状态S =ACTIONSS =ACTIONS，aa和输和输入符号入符号a a推进栈（对终结符，推进栈（对终结符，GOTOSGOTOS，aa的值已放入的值已放入ACTIONSACTIONS，aa中中) )，下一个，下一个输入符号变成现行输入符号。输入符号变成现

10、行输入符号。 (2)(2)归约：归约：指用某一产生式指用某一产生式A A 进行归约。假若进行归约。假若 的长的长度为度为 ，归约的动作是去掉栈顶的，归约的动作是去掉栈顶的 个项，然后把个项，然后把(Sm(Sm- - ，A)A)的下一状态和文法符号的下一状态和文法符号A A推进栈。归约动作不改变现行推进栈。归约动作不改变现行输入符号。执行归约的动作意味着呈现于栈顶的符号串是输入符号。执行归约的动作意味着呈现于栈顶的符号串是一个相对于一个相对于A A的句柄。的句柄。 (3)(3)接受：接受：宣布分析成功，停止分析器的工作。宣布分析成功，停止分析器的工作。 (4)(4)报错报错：报告发现源程序含有错

11、误，调用出错处理程：报告发现源程序含有错误，调用出错处理程序。序。首页首页结束结束编 译 原 理 LR分分析析 对于对于-个文法，如果能构造一张分析表，使得它的每个个文法，如果能构造一张分析表，使得它的每个入口均是唯一确定的，则把这个文法称为入口均是唯一确定的，则把这个文法称为LR文法。对于文法。对于一个一个LR文法，当分析器对输入串进行自左至右扫描时，文法，当分析器对输入串进行自左至右扫描时，一旦句柄呈现于栈顶，就能及时对它实行归约。一旦句柄呈现于栈顶，就能及时对它实行归约。 一个一个LR分析器有时需要分析器有时需要“展望展望”和实际检查未来和实际检查未来的的k个输入符号才能决定应采取什么样

12、的个输入符号才能决定应采取什么样的“移进一归约移进一归约”决策。一般而言，决策。一般而言， 一个文法如果能用一个每步顶多向前一个文法如果能用一个每步顶多向前检查检查K个输入符号的个输入符号的LR分析器进行分析，则这个文法就分析器进行分析，则这个文法就称为称为LR(k)文法。文法。 对于一个文法，如果它的任何对于一个文法，如果它的任何移进一归约移进一归约分析器都分析器都存在尽管栈的内容和符号都已了解，但存在尽管栈的内容和符号都已了解，但无法确定是无法确定是“移移进进”还是还是“归约归约”；或者，无法从几种可能的规约中确或者，无法从几种可能的规约中确定其一的情形，那么这个文法就是非定其一的情形，那

13、么这个文法就是非LR(1)的。的。 首页首页结束结束编 译 原 理 LR分分析析【例【例】已知文法已知文法GS，分析符号串，分析符号串abbcde是否是是否是GS的句子的句子 。 (1) S aAcBe1 (2) A b2 (3) A Ab3 (4) B d4【解【解】这里每个产生式的右部字符串末尾的编号是为了这里每个产生式的右部字符串末尾的编号是为了方便查看在最右推导中是选择哪个产生式推导的，并不是方便查看在最右推导中是选择哪个产生式推导的，并不是产生式的一部分。产生式的一部分。 句子的最右推导过程为：句子的最右推导过程为： S =aAcBe1 =aAcd4e1=aAb3cd4e1=ab2b

14、3cd4e1首页首页结束结束编 译 原 理 LR分分析析 由于最右推导就是规范推导，因此句型由于最右推导就是规范推导，因此句型aAcBe、aAcde、aAbcde、abbcde为规范句型。为规范句型。 规范句型的规范句型的这种前部分符号串称为可归前缀这种前部分符号串称为可归前缀。【例如【例如】符号串符号串aAcBe是规范句型是规范句型aAcBe的可归前缀，的可归前缀，aAcd是规范句型是规范句型aAcd4e1的可归前缀，的可归前缀，aAb是规范句型是规范句型aAb3cd4e1的可归前缀，的可归前缀，ab是规范句型是规范句型ab2b3cd4e1的可归前缀。的可归前缀。 我们把形成可归前缀之前包括

15、可归前缀在内的我们把形成可归前缀之前包括可归前缀在内的所有规范句型的前缀都称为所有规范句型的前缀都称为活前缀。活前缀。所谓前缀所谓前缀就就是是符号串的任意首部。活前缀符号串的任意首部。活前缀就是就是可归前缀可归前缀的任意首部的任意首部。首页首页结束结束编 译 原 理 LR分分析析【例如【例如】可归前缀可归前缀ab的活前缀为的活前缀为,a,ab可归前缀可归前缀aAb的活前缀为的活前缀为,a,aA,aAb可归前缀可归前缀aAcd的活前缀为的活前缀为,a,aA,aAc,aAcd可归前缀可归前缀aAcBe的活前缀为的活前缀为,a,aA,aAc,aAcB,aAcBe首页首页结束结束编 译 原 理 LR分

16、分析析 因为规范归约实际上就是规范推导的逆过程。因为规范归约实际上就是规范推导的逆过程。可归前缀就是存放在文法符号栈中的内容可归前缀就是存放在文法符号栈中的内容，它和它和输入缓冲器的剩余内容合在一起如果刚好就是规输入缓冲器的剩余内容合在一起如果刚好就是规范句型，就能够保证我们的归约是一个规范归约范句型，就能够保证我们的归约是一个规范归约的过程。的过程。即栈内符号串总是规范句型的前缀即栈内符号串总是规范句型的前缀,且且不含句柄右侧的符号。原因不含句柄右侧的符号。原因:句柄一旦在栈顶形句柄一旦在栈顶形成成,就不再移进新符号就不再移进新符号,而是要进行归约了。而是要进行归约了。我们把具有上述性质的符

17、号串称为规范句型的活我们把具有上述性质的符号串称为规范句型的活前缀。前缀。 为什么要引进活前缀的概念？为什么要引进活前缀的概念？ 首页首页结束结束编 译 原 理 LR分分析析一、活前缀和可归前缀的形式定义一、活前缀和可归前缀的形式定义 若若S A ,则称则称为可归前缀为可归前缀; 若有串若有串W是是的前缀，则称的前缀，则称W是是G的一个活前缀（的一个活前缀（S为文法拓广后的为文法拓广后的开始符，它只出现在规则左部）。可归前缀是包含句柄的开始符，它只出现在规则左部）。可归前缀是包含句柄的活前缀。活前缀。 二、说明：二、说明： 规范句型的活前缀有两个要点规范句型的活前缀有两个要点:(1)它是规范句

18、型的前缀它是规范句型的前缀; (2)它不含句柄右侧符号它不含句柄右侧符号编 译 原 理 LR分分析析 由于活前缀实际上就是满足一定要求的符号由于活前缀实际上就是满足一定要求的符号串，因此识别活前缀的工作和识别单词的工作非串，因此识别活前缀的工作和识别单词的工作非常类似，所以我们可以采用常类似，所以我们可以采用有穷自动机有穷自动机这种数这种数据模型来实现活前缀的识别。据模型来实现活前缀的识别。 如何识别文法符号栈中的内容就是活前缀如何识别文法符号栈中的内容就是活前缀 首页首页结束结束编 译 原 理 LR分分析析 基本思想基本思想是我们可以把文法的终结符和非是我们可以把文法的终结符和非终结符都看成

19、有穷自动机的输入符号，每次把一终结符都看成有穷自动机的输入符号，每次把一个符号进栈看成已识别过了该符号，同时状态进个符号进栈看成已识别过了该符号，同时状态进行转换，当识别到可归前缀时，相当于在栈中形行转换，当识别到可归前缀时，相当于在栈中形成句柄，达到了识别句柄的终态。成句柄，达到了识别句柄的终态。首页首页结束结束编 译 原 理 LR分分析析实现识别活前缀的有穷自动机的构造有两种实现识别活前缀的有穷自动机的构造有两种方法：方法：方法方法1： 由文法的产生式直接构造识别活前缀和可归前由文法的产生式直接构造识别活前缀和可归前缀的有穷自动机缀的有穷自动机 方法方法2： 通过构造文法通过构造文法G的的

20、LR(0)的项目集规范族来直的项目集规范族来直接构造识别活前缀的接构造识别活前缀的DFA 【说明】由于【说明】由于NFA确定化为确定化为DFA的工作量较大，我的工作量较大，我们考虑直接构造出项目集规范族作为们考虑直接构造出项目集规范族作为DFA的状态，的状态，来构造来构造DFA。 首页首页结束结束编 译 原 理 LR分分析析LR(0)项目集规范族的构造项目集规范族的构造 定义：构成识别一个文法活前缀的定义：构成识别一个文法活前缀的DFA项目集项目集（状态）的全体，称为这个文法的（状态）的全体，称为这个文法的LR(0)项目集项目集规范族。规范族。 ( (一一) LR) LR（0 0）项目）项目在

21、每个产生式的右部适当位置添加一个圆点构成在每个产生式的右部适当位置添加一个圆点构成项目（项目（item）。每个项目的含义和圆点的位置有）。每个项目的含义和圆点的位置有关。项目圆点的左部表示分析过程的某个时刻用关。项目圆点的左部表示分析过程的某个时刻用该产生式归约时句柄已识别的部分，圆点右部表该产生式归约时句柄已识别的部分，圆点右部表示待识别的部分。示待识别的部分。首页首页结束结束编 译 原 理 LR分分析析根据圆点所在的位置和圆点后是终结符还是非终根据圆点所在的位置和圆点后是终结符还是非终结符把项目分为以下几种：结符把项目分为以下几种： 1、移进项目，形如、移进项目，形如 A a . ab 2

22、、待约项目，形如、待约项目，形如 A a . Bb 3、归约项目，形如、归约项目，形如 A a . 4、接受项目，形如、接受项目，形如 SS .首页首页结束结束编 译 原 理 LR分分析析【例】产生式【例】产生式S SaAcBe对应的对应的6个项目是：个项目是：0S S.aAcBe1S Sa.AcBe 2S SaA.cBe3S SaAc.Be4S SaAcB.e5S SaAcBe. 首页首页结束结束编 译 原 理 LR分分析析一个产生式可对应的项目为它的右部符号长度加一个产生式可对应的项目为它的右部符号长度加1，对空产生式，对空产生式 A- 仅有一个项目仅有一个项目 A-.【例】产生式【例】产

23、生式A-X YZ 对应对应4个项目个项目 A-.XY Z A-XY Z A-X YZ A-X YZ编 译 原 理 LR分分析析（二）（二）LR(0)LR(0)项目集规范族的构造项目集规范族的构造对于构成识别一个文法活前缀的对于构成识别一个文法活前缀的DFA项目集的全体项目集的全体称为这个文法的称为这个文法的LR（0）项目集规范族）项目集规范族 （1）首先，为了使）首先，为了使接受接受状态易于识别，总是状态易于识别，总是将文法将文法G进行拓广。假定文法进行拓广。假定文法G是一个以是一个以S为开始符为开始符号的文法，我们构造一个号的文法，我们构造一个G，它包含了整个，它包含了整个G并引并引进了一个

24、不出现在进了一个不出现在G中的非终结符中的非终结符S；同时加进了；同时加进了一个新产生式一个新产生式S一一S，而这个，而这个S是是G的开始符号，的开始符号，称称G是是G的拓广文法。会有一个仅含项目的拓广文法。会有一个仅含项目S-S的的状态，这就是唯一状态，这就是唯一的的接受接受态。态。 编 译 原 理 LR分分析析如果如果I是文法是文法G的一个项目集，定义和构造的一个项目集，定义和构造I的闭包的闭包CLOSURE(I)如下：如下： a)I的项目都在的项目都在CLOSURE(I)中中 b)若若Aa . Bb属于属于CLOSURE(I)，则每一，则每一形如形如B. g的项目也属于的项目也属于CLO

25、SURE(I) c)重复重复b)直到直到CLOSURE(I)不再扩大。不再扩大。【说明【说明】求闭包函数的过程实际上就是求求闭包函数的过程实际上就是求所有等价状态的过程。所有等价状态的过程。（2）闭包函数）闭包函数CLOSURE(I)编 译 原 理 LR分分析析（3）转换函数）转换函数GOTO（I，X) 定义转换函数如下：定义转换函数如下： GOTO（I，X）= CLOSURE（J） 其中：其中：I为包含某一项目集的状态，为包含某一项目集的状态，X为一文法符为一文法符号号 J=任何形如任何形如AaX . b的项目的项目| Aa . X b属于属于I 定义两个函数后，就可以通过定义两个函数后，就

26、可以通过闭包函数闭包函数CLOSURE求求DFA一个状态的项目集，通过转换函一个状态的项目集，通过转换函数求数求DFA一个状态的项目集一个状态的项目集 【例【例】A-a.XbA-aX.bX首页首页结束结束编 译 原 理 LR分分析析构造文法构造文法G的的LR(0) 项目集规范族的方法项目集规范族的方法 :把文法的所有产生式的项目都引出，每个项目都把文法的所有产生式的项目都引出，每个项目都为为NFA的一个状态。其中文法的第一个产生式的的一个状态。其中文法的第一个产生式的第一个项目第一个项目S . S为文法的初态集的核心项。为文法的初态集的核心项。 a)置项目置项目S . S为初态集的核心项后，对

27、核心为初态集的核心项后，对核心项求闭包项求闭包CLOSURE（S . S）得到初态的项目）得到初态的项目集集 b)对初态集或其它所构造的项目集应用转换函对初态集或其它所构造的项目集应用转换函数数GOTO(I，X)= CLOSURE(J)求出新状态求出新状态J的项的项目集目集 c)重复重复b)直到不出现新的项目集为止直到不出现新的项目集为止首页首页结束结束编 译 原 理 LR分分析析【例】文法【例】文法GS: 0SEE1EaA1EaA2EbB2EbB3AcA3AcA4Ad4Ad5BcB5BcB6Bd 6Bd 其规范项目集族构造如其规范项目集族构造如下：下：首页首页结束结束编 译 原 理 LR分分

28、析析编 译 原 理 LR分分析析 假定假定C=I。，。，I1，In)。由于我们已。由于我们已经习惯用数字表示状态，因此令每个项目经习惯用数字表示状态，因此令每个项目集集Ik的下标的下标k作为分析器的状态。特别是作为分析器的状态。特别是令包含项目令包含项目SS(表示整个句子还未输表示整个句子还未输入入)的集合的集合Ik的下标的下标k为分析器的初态。为分析器的初态。 LR(0)分析表的构造分析表的构造编 译 原 理 LR分分析析分析表的分析表的ACTION子表和子表和GOTO子表可按如下方子表可按如下方法构造：法构造： (1)若项目若项目A- a 属于属于Ik 且且GO(Ik,a)= Ij ，a为

29、终结符，置为终结符，置ACTIONk,a 为将为将(j，a)移进栈移进栈”，简记为简记为“Sj (2)若项目若项目A-. 属于属于Ik，则对任何终结符，则对任何终结符a(或或结束符结束符#)，置，置ACTIONk,a 为用产生式为用产生式A-a进行进行归约，简记为归约，简记为“rj”(注意：注意：j是产生式的编号而不是产生式的编号而不是项目集的状态号，即是项目集的状态号，即A-a是文法是文法G的第的第j个产生个产生式式)。编 译 原 理 LR分分析析 （3）若项目）若项目S-S 属于属于Ik (S 表示整个句子已表示整个句子已输入并归约结束输入并归约结束)，则置，则置ACTIONK，#为可为可

30、“接接受受”，简记为，简记为“acc”。 (4)若若GO(Ik ,A)=Ij , A为非终结符，则置为非终结符，则置GOTOk，A=j。 (5)分析表中凡不能用规则分析表中凡不能用规则(1)一一(4)填入的空白填入的空白格均置上格均置上“报错标志报错标志”。首页首页结束结束编 译 原 理 LR分分析析首页首页结束结束编 译 原 理 LR分分析析1 1、置输入指针、置输入指针 ipip 指向输入串的第一个符号；指向输入串的第一个符号；令令 s s 是栈是栈顶状态，顶状态， a a 是是 ipip 所指向的符号所指向的符号; ;将将# #压入符号栈，将开始状态压入符号栈，将开始状态0 0压入状态栈

31、；压入状态栈； 2 2、重复执行如下过程：、重复执行如下过程： ifif（actions,a=sjactions,a=sj） 把符号把符号a a入符号栈，把状态入符号栈，把状态j j入状态栈；入状态栈； 使使 ipip 指向下一个输入符号。指向下一个输入符号。 else if else if （actions,a=rjactions,a=rj）首页首页结束结束编 译 原 理 LR分分析析 从栈顶弹出第从栈顶弹出第j j条规则右部串长条规则右部串长|个符个符号；号； 把归约得到的非终结符把归约得到的非终结符A A压入符号栈；压入符号栈； 将将gotos,Agotos,A 的值的值j j压入状态栈

32、；压入状态栈； 并输出规则并输出规则 AA。 else if else if （actions,a=accactions,a=acc） returnreturn； else else error() error()； 首页首页结束结束编 译 原 理 LR分分析析【例】文法【例】文法GS: 0SE1EaA2EbB3AcA4Ad5BcB6Bd,对输入串对输入串bccdbccd# #分析如下：分析如下：首页首页结束结束编 译 原 理 LR分分析析步骤步骤状态栈状态栈符号栈符号栈输入串输入串actionGoto1 0#bccd#S32 03#bccd#S53 035#bccd#S54 0355#bcc

33、d#S115 0355(11)#bccd#r696 03559#bccB#r597 0359#bcB#r578 037#bB#r219 01#E#acc首页首页结束结束编 译 原 理 LR分分析析 1、如果、如果 I 中至少含两个归约项目，则称中至少含两个归约项目，则称 I 有有归约归约归约冲突归约冲突（Reduce/Reduce Conflict） 2、如果、如果 I 中既含归约项目，又含移进项目，则称中既含归约项目，又含移进项目，则称 I 有有移进移进归约冲突归约冲突（Shift/Reduce Conflict） 3、如果、如果 I 既没有归约既没有归约归约冲突，又没有移归约冲突，又没有移

34、进进归约冲突，则称归约冲突，则称 I 是相容的是相容的(Consistent)，否，否则称则称 I 是不相容的。是不相容的。 4、对文法、对文法G，如果，如果 IC,都是相容的，则称都是相容的，则称G为为LR(0)文法。文法。编 译 原 理 LR分分析析【例】有产生式如下【例】有产生式如下 SBB BaB|b构造该文法的构造该文法的LR(0)分析表分析表 将文法将文法G拓广为文法拓广为文法G 0)S一一S 1)SBB 2)BaB 3)Bb 列出列出LR(0)的所有项目的所有项目 1、SS 5、SBB 9、B-.b 2、S一一S. 6、 BaB 10、B-b. 3、S一一.BB 7、BaB 4、

35、SBB 8、BaB.编 译 原 理 LR分分析析用用e_CLOSURE办法构造文法办法构造文法G的的LR(0)项目集规范族项目集规范族 I0: S-.S S-.BB B-.aB B-.b I1: S-S. I2：SBB B一一.aB B.b I3: B-a.B B-.aB B-.b I4: B-b. I5: S-BB. I6: B-aB.编 译 原 理 LR分分析析 状态状态 ACTlONACTlON GOTO GOTO a b # S B a b # S B 0 s3 S4 1 2 0 s3 S4 1 2 1 aCC 1 aCC 2 s3 S4 5 2 s3 S4 5 3 S3 s4 6 3

36、 S3 s4 6 4 r3 r3 r3 4 r3 r3 r3 5 r1 r1 rl 5 r1 r1 rl 6 r2 r2 r2 6 r2 r2 r2 LR(0)分析表分析表编 译 原 理 LR分分析析【练习】设有文法【练习】设有文法GS： S-E E-Aa |bB A-cA |d B-cB |d 构造构造LR(0)分析表，并利用此分析表判断符号串分析表，并利用此分析表判断符号串acccd是否是文法是否是文法GS的句子。的句子。编 译 原 理 LR分分析析 LR(0)文法是一类非常简单的文法，没有文法是一类非常简单的文法，没有查看下一符号查看下一符号(Token),决定分析动作仅仅根据决定分析动

37、作仅仅根据到目前已经看到的东西，分析能力弱。即使到目前已经看到的东西，分析能力弱。即使是定义算术表达式这样的简单文法也不是是定义算术表达式这样的简单文法也不是LR(0)。改进办法改进办法:向前查看下一符号向前查看下一符号-SLR(1),LR(1),LALR(1)7.3 SLR(1)7.3 SLR(1)分析分析首页首页结束结束编 译 原 理 LR分分析析一、一、LR(0)LR(0)分析存在的问题分析存在的问题 【例】已知文法【例】已知文法G,开始符号为开始符号为S,判断该文法是判断该文法是否为否为LR(0) 文法。文法。 (0) S S (1) S rD (2) DD,i (3) D i单击演示

38、单击演示首页首页结束结束编 译 原 理 LR分分析析这里仅仅凭这里仅仅凭LR(0) LR(0) 项目本身的信息已经无法项目本身的信息已经无法解决项目之间的冲突，需要向前查看一个解决项目之间的冲突，需要向前查看一个符号，再来决定到底是采取移进动作还是符号，再来决定到底是采取移进动作还是归约动作。归约动作。首页首页结束结束编 译 原 理 LR分分析析 二、解决方法二、解决方法对含有移进对含有移进-归约和归约归约和归约-归约冲突的项目集归约冲突的项目集I=Xa.bb , Ag. ,Bd. 若有：若有：FOLLOW(A) FOLLOW(B) = FOLLOW(A) b = FOLLOW(B) b =

39、状态状态I面临某输入符号面临某输入符号a 1) 若若a=b，则移进，则移进 2) 若若aFOLLOW(A), 则用产生式则用产生式 A g 进行归约进行归约 3) 若若aFOLLOW(B), 则用产生式则用产生式 B d 进行归约进行归约 4) 此外，报错此外，报错 首页首页结束结束编 译 原 理 LR分分析析若一个文法的若一个文法的LR(0)LR(0)分析表中所含有的分析表中所含有的动作冲突都能用上述方法解决，则称动作冲突都能用上述方法解决，则称这个文法是这个文法是SLR(1)SLR(1)文法。文法。SLR(1)SLR(1)文法文法是无二义的。是无二义的。编 译 原 理 LR分分析析 对任给

40、的一个文法对任给的一个文法G，我们可用如下的，我们可用如下的办法构造它的办法构造它的SLR(1)分析表：分析表：首先把首先把G拓广为拓广为G，对，对G构造构造LR(0)项目集项目集规范族和活前缀识别自动机的状态转换函数规范族和活前缀识别自动机的状态转换函数GO，使用闭包函数和函，使用闭包函数和函数，然后再按下面的算法构造数，然后再按下面的算法构造G的的SLR分析分析表。表。SLR(1)SLR(1)分析表构造方法分析表构造方法编 译 原 理 LR分分析析 (1)若项目若项目A- a 属于属于Ik 且且GO(Ik,a)= Ij ，a为终结符，为终结符，置置ACTIONk,a 为将为将(j，a)移进

41、栈移进栈”，简记为，简记为“Sj。 (2)若项目若项目A-. 属于属于Ik，则对任何终结符，则对任何终结符a(或结束符或结束符#)，且，且aFOLLOW（A)，置，置ACTIONk,a 为用产生式为用产生式A-a进行归进行归约，简记为约，简记为“rj”。(3)若项目若项目S-S 属于属于Ik (S 表示整个句子已输入并归约结表示整个句子已输入并归约结束束)，则置，则置ACTIONK，#为可为可“接受接受”，简记为，简记为“acc”。(4)若若GO(Ik ,A)=Ij , A为非终结符，则置为非终结符，则置GOTOk，A=j；。；。(5)分析表中凡不能用规则分析表中凡不能用规则(1)一一(4)填

42、入的空白格均置上填入的空白格均置上“报错报错标志标志”。分析表的分析表的ACTION子表和子表和GOTO子表构造方法：子表构造方法：首页首页结束结束编 译 原 理 LR分分析析【练习】判断下列文法是否是【练习】判断下列文法是否是LRLR（0 0），如），如不是说明理由，判断是否是不是说明理由，判断是否是SLRSLR（1 1）文法。）文法。文法文法GSS-iSeSS-iSS-a编 译 原 理 LR分分析析【练习】文法个【练习】文法个GE为：为：EE+T|TT-T*F|FF-(E)|i分析它是分析它是LR（0）文法还是）文法还是SLR（1）文法。）文法。编 译 原 理 LR分分析析SLRSLR（1

43、 1）的局限性：）的局限性： 在在SLR方法中，若项目集方法中，若项目集Ik含有含有A- .，那么在状态，那么在状态k时，只要所面临的输入时，只要所面临的输入符号符号a FOLLOW(A)，就确定采取，就确定采取“用用A- 归约归约”的动作。但是在某种情况下，当状的动作。但是在某种情况下，当状态态k呈现于栈顶时，栈里的符号串所构成的活呈现于栈顶时，栈里的符号串所构成的活前缀前缀未必允许把未必允许把归约为归约为A，因为可能没有，因为可能没有一个规范句型含有前缀一个规范句型含有前缀 Aa。因此，在这种。因此，在这种情况下，用情况下，用A- 进行归约未必有效。进行归约未必有效。 即在即在SLR方法中

44、存在无效归约。方法中存在无效归约。7.4 LR（1）分析）分析【例】下列文法【例】下列文法G为为0)S-S1)S一一aAd2)S-bAc3)Saec4)S一一bed5)A-elo：S-S S一一aAd S-.bAc Saec S一一bedaI2：SaAd Sa.ec A一一eeI5：S-aec A-e AI4： SaA . dcI9: S-aec.I1:S-S.SI3：SbAc Sbed A-e bI8:S-aAd .dI6： S-bA. cAI7：S-bed A-e eI10: SbAc.cI11: S-bed .d LR(0)识别识别G的活前缀的的活前缀的DFA编 译 原 理 LR分分析析

45、项目项目I5 、I7 中的移进中的移进-归约冲突，不能用归约冲突，不能用SLR(1)解决。解决。I5：S-aec A-e 因因S=S=aAd=aedRRS=S=aec对活前缀对活前缀ae，面临输入符号，面临输入符号c时应移进，面临时应移进，面临d时时应用应用A-e 归约归约FOLLOW(A)=c,d,其中面临其中面临c 时时存在无效归约。存在无效归约。首页首页结束结束编 译 原 理 LR分分析析 LRLR（1 1）项目的一般形式）项目的一般形式 重新定义项目，使得每个项目都附带有重新定义项目，使得每个项目都附带有K个终结符。每个项目的个终结符。每个项目的一般形式是一般形式是: A- ，ala2

46、 akA- 是一个是一个LR(0)项目，每一个项目，每一个a都是终结符。这样的一个项目都是终结符。这样的一个项目称为一个称为一个LRIk项目。项目中的项目。项目中的ala2ak称为它的向前搜索符串称为它的向前搜索符串(或或展望串展望串)。向前搜索符串仅对归约项目。向前搜索符串仅对归约项目A- ，ala2 ak有意有意义。对于任何移进或待约项目义。对于任何移进或待约项目A- ，ala2 ak， ，搜索符串搜索符串ala2 ak不起作用。归约项目不起作用。归约项目A- ，ala2 ak ，意味着当它所属的状态呈现在栈顶且，意味着当它所属的状态呈现在栈顶且后续的后续的k个输入符号为个输入符号为ala

47、2 ak，才可以把栈顶的，才可以把栈顶的 归约为归约为A。这。这里只对里只对k1的情形感兴趣，因为对多数程序语言的语法来说，向前搜的情形感兴趣，因为对多数程序语言的语法来说，向前搜索索(展望一个符号就基本可以确定展望一个符号就基本可以确定“移进移进”或或“归约归约”。编 译 原 理 LR分分析析构造有效的构造有效的LR(1)项目集族的办法本质上和构造项目集族的办法本质上和构造LR(0)项目项目集规范族的办法是集规范族的办法是样的。即也需要两个函数样的。即也需要两个函数CLOSURE和和GO。 假定假定I是一个项目集，它的闭包是一个项目集，它的闭包CLOSURE()可按如下方可按如下方式构造：式

48、构造： (1)I的任何项目都属于的任何项目都属于CLOSURE()。 (2)若项目若项目A- ，a属于属于CLOSURE()， B是一个产生式，对于是一个产生式，对于FIRST( a)中的每个终结符中的每个终结符b(即即 a 所有可能推导出的开头终结符所有可能推导出的开头终结符b，仅当，仅当 时时b=a)如果如果B. ，b原来不在原来不在CLOSURE(I)中，则把它加进去。中，则把它加进去。 (3)重复执行步骤重复执行步骤(2)，直到，直到CLOSURE(I)不再增大为止不再增大为止lo：S-S ，# S一一aAd，# S-.bAc ，# Saec ，# S一一bed，#eI5：S-aec

49、,# A-e ,dAI4： SaA . d,#cI9: S-aec. ,#aI2：SaAd ,# Sa.ec,# A一一e,dI1:S-S. ，#SI3：SbAc,# Sbed ,# A-e ,c bI8:S-aAd .,#dI6： S-bA. c,#AI7：S-bed ,# A-e ,ceI10: SbAc.,#cI11: S-bed .,#dLR（1）项目集和转换函数【例】下列文法【例】下列文法G为为0)S-S1)S一一aAd2)S-bAc3)Saec4)S一一bed5)A-e编 译 原 理 LR分分析析假定假定C=I。，。，Il，In。，令每个，令每个Ik的下标的下标k为分析表的状态，令

50、那个含有为分析表的状态，令那个含有S- S，#的的Ik的的k为分析器的初态。动作为分析器的初态。动作ACTION和状态转换和状态转换GOTO可按如下方法构造：可按如下方法构造： (1)若项目若项目A一一a，b属于属于Ik且且GO(Ik,a)=Ij，a为终结符，则置为终结符，则置ACTIONk，a为为将状态将状态i和符号和符号a移进栈移进栈，简记为，简记为Si。 (2)若项目若项目A一一 ，a属于属于Ik，则置，则置ACTIONk，a为为“用产生式用产生式A-归约归约”，简记为，简记为rj,其中，其中，j是是产生式的编号，即产生式的编号，即A-是文法是文法G的第的第j个产生式。个产生式。文法的文

51、法的LR(1)项目集族构造分析表的算法是：项目集族构造分析表的算法是：首页首页结束结束编 译 原 理 LR分分析析(3)若项目若项目S-S ，#属于属于Ik，则置，则置ACTIONk，#为为接受接受，简记为，简记为acc。(4)若若GO(Ik，A)=Ij，A为非终结符，则置为非终结符，则置GOTO(Ik，A)=j。(5)分析表中凡不能用规则分析表中凡不能用规则(1)(4)填入信息的空填入信息的空白栏均填上白栏均填上出错标志出错标志。文法的文法的LR(1)项目集族构造分析表的算法是：项目集族构造分析表的算法是：编 译 原 理 LR分分析析按上述算法构造的分析表，若不存在多重定按上述算法构造的分析

52、表，若不存在多重定义入口义入口(即动作冲突即动作冲突)的情形，则称它是文法的情形，则称它是文法G的一张规范的的一张规范的LR(1)分析表。使用这种分析表分析表。使用这种分析表的分析器叫做一个规范的的分析器叫做一个规范的LR分析器。具有规分析器。具有规范的范的LR(1)分析表的文法称为一个分析表的文法称为一个LR(1)文法。文法。编 译 原 理 LR分分析析【例【例】 (0) SS (1)SL=RL=R (2)SR (2)SR (3)L (3)L * *R R (4)Li (4)Li (5)RL (5)RLLR(1)比比SLR（1）能力强）能力强编 译 原 理 LR分分析析I0:S S,# S

53、L=R,# S R,# L *R,=/#L i,=/# R L,# I1:SS ,#sI9:SL=R ,#RI6:S L= R,# R L,# L *R,# L i,# =I2:S L =R,# R L,# LI3:SR ,#RI5:Li ,=/#iiI12:Li ,#iiI13:L*R ,#RLI10:RL ,#LI7:L*R ,=/#RI8:RL ,=/#LI4: L *R,=/# R L,=/#L i,=/# L *R,=/#*I11:L * R,# R L,# L *R,# L i,# *LR(1)LR(1)项目集及转换函数项目集及转换函数编 译 原 理 LR分分析析例：给定文法例：给

54、定文法GA： A-(A)|a1)画出画出LR（1）项目识别所有活前缀的）项目识别所有活前缀的DFA2)构造构造LR（1）分析表）分析表I0:A-.A,#A-.(A),#A-.a,#AI1:A-A.,#(I2:A-(.A),#A-.(A), )A- .a, )aI3:A- a. ,#AI4:A-(A.),#aI6:A- a. ,)AI8:A-(A.), )(I5:A-(.A), )A-.(A), )A- .a, )(a)I9:A-(A). ,)I7:A-(A). , #)LR（1）项目集和转换函数）项目集和转换函数编 译 原 理 LR分分析析每个每个SLR(1)SLR(1)文法都是文法都是LR(

55、1)LR(1)的，一个的，一个SLR(1)SLR(1)文法的规范文法的规范LRLR分析器比其分析器比其SLR(1)SLR(1)分析器的分析器的状态要多。状态要多。【例】【例】GSGS：(1)S (1)S BB BB (2)B(2)BaB aB (3)B (3)B b b 编 译 原 理 LR分分析析I0:S S,# S BB,#B aB,a/bB b,a/b I1:S S,#sI2:S BB,# B aB,#B b,# BI5:S BB,#BI6:S aB,# B aB,#B b,# aI7:B b,#bI4:B b,a/bbbI8:B aB,a/bBI9:B aB,#BI3:B aB,a/b

56、 B aB,a/b B b,a/b aaaLR(1)项目集和转换函数b编 译 原 理 LR分分析析ACTIONGOTOab#SB状态0 S3 S4 1 21 acc2 S6 S7 53 S3 S4 84 r3 r3 5 r1 6 S6 S7 97 r38 r2 r2 9 r2 LR(1)分析表分析表编 译 原 理 LR分分析析 对输入串对输入串ab#用用LR(1)分析的过程分析的过程 1 0 # ab# S3 2 03 #a b# S4 3 034 #ab # 出错 步骤状态栈符号栈输入串ACTIONGOTO编 译 原 理 LR分分析析 对输入串对输入串abb#用用LR(1)分析的过程分析的过

57、程步骤状态栈符号栈输入串ACTIONGOTO1 0 # abb# S32 03 #a bb# S43 034 #ab b# r3归约 8 4 038 #aB b# r2归约 25 02 #B b# S76 027 #Bb # r3 57 025 #BB # r1 18 01 #S # acc abb#是该文法的一个句子是该文法的一个句子编 译 原 理 LR分分析析7.5 LALR（1）分析）分析如果除去搜索符之后，这两个集合是相同的，我如果除去搜索符之后，这两个集合是相同的，我们称两个们称两个LR(1)项目集具有相同的心。把所有同项目集具有相同的心。把所有同心的心的LR(1)项日集合并为一，将

58、看到一个心就是项日集合并为一，将看到一个心就是一个一个LR(0)项目集，项目集，这种这种LR分析法称为分析法称为LALR(lookahead LR)方法。方法。LALR方法的特点方法的特点: 1）LALR分析表比规范分析表比规范LR分析表要小，能分析表要小，能力也差一点，但它却能解决一些力也差一点，但它却能解决一些SLR所不能解决所不能解决的情形。的情形。 2）对于同一个文法，）对于同一个文法，LALR分析表和分析表和LR(0)以及以及SLR分析表永远具相同数目的状态。分析表永远具相同数目的状态。编 译 原 理 LR分分析析LALR分析表的算法基本思想是分析表的算法基本思想是： 首先构造首先构

59、造LR(1)项目集族，如不存在冲突，项目集族，如不存在冲突，就把同心集合并在一起。若合并后的集族不就把同心集合并在一起。若合并后的集族不存在归约存在归约归约冲突归约冲突(即不存在同即不存在同个项目集个项目集中像中像 A一一 和和B一一 这样的产生式具有这样的产生式具有相同的搜索符相同的搜索符)，就按这个项目集规范族构造，就按这个项目集规范族构造分析表。分析表。编 译 原 理 LR分分析析LALRLALR分析表的主要步骤如下分析表的主要步骤如下: : (1)构造文法构造文法G的的LR(1)项目集族项目集族C=I0,I1,.In (2)把所有的同心集合并在一起，记把所有的同心集合并在一起，记C=J

60、0,J1,Jn含有项目含有项目S，一，一S，#的的Jk为分析表的初态。为分析表的初态。 (3)(3)从从CC构造构造ACTIONACTION表：表： A)若项目若项目A一一a，b属于属于Jk且且GO(Jk,a)=Jj，a为为终结符，则置终结符，则置ACTIONk，a为为将状态将状态i和符号和符号a移进栈移进栈，简记为简记为Sj。 B)若项目若项目A一一 ，a属于属于Jk，则置，则置ACTIONk，a为为“用产生式用产生式A-归约归约”，简记为，简记为rj,其中，其中，j是产生式的是产生式的编号，即编号，即A-是文法是文法G的第的第j个产生式。个产生式。 C)若项目若项目S-S ，#属于属于Jk