分析表的构造(编译原理)

1、LR（0）分析表的构造分析表的构造u步骤步骤一：一： 构造识别文法活前缀的确定有穷自动机（构造识别文法活前缀的确定有穷自动机（DFADFA）u步骤步骤二二： 根据根据DFADFA构造相应的构造相应的LRLR（0 0）分析表）分析表识别活前缀的确定的有穷自动机识别活前缀的确定的有穷自动机 方法方法1 1：根据形式定义求出活前缀的正规表达式，然后由此正根据形式定义求出活前缀的正规表达式，然后由此正规表达式构造规表达式构造NFANFA再确定化为再确定化为DFADFA，a，ab，a，aA，aAb， a，aA，aAc，aAcd， a， aA，aAc，aAcB，aAcBe，S 对于一个适用的高级语言的文法

2、，用方法对于一个适用的高级语言的文法，用方法1 1构造识别活前缀的构造识别活前缀的有限自动机从理论的角度讲是很严格的，实现起来却是很复有限自动机从理论的角度讲是很严格的，实现起来却是很复杂的。杂的。识别活前缀的确定的有穷自动机识别活前缀的确定的有穷自动机 方法方法2 2：求出文法的所有求出文法的所有LRLR（0 0）项目，按一定规则构造识别）项目，按一定规则构造识别活前缀的活前缀的NFANFA再确定化为再确定化为DFADFA例如，文法例如，文法G：E aA|bBA cA| d B cB| d 步骤一：步骤一：用增广文法表示成用增广文法表示成文法文法G：SEE aA|bBA cA| d B cB

3、| d 文法文法G的项目有：的项目有：1.SE2.SE 3.E aA4.E aA5.E aA6. A cA7. A cA8. A cA9. A d10. A d 11. E bB12. E bB13. E bB14. B cB15. B cB16. B cB17. B d18. B d 1*1313 2 21313 5 51313 8 813131010131313131313181813131616步骤步骤三：三：初态（初始项目）初态（初始项目）句子识别句子识别态（接受项目）态（接受项目）句柄识别句柄识别态（规约项目）态（规约项目）文法文法G的项目有：的项目有：1.SE2.SE 3.E aA

4、4.E aA5.E aA6. A cA7. A cA8. A cA9. A d10. A d 11. E bB12. E bB13. E bB14. B cB15. B cB16. B cB17. B d18. B d 1*1313 2 21313 5 51313 8 813131010131313131313181813131616E34aA67cA9d1112bB1415cB17d步骤四：步骤四：找源自同一产找源自同一产生式的项目，生式的项目，添加状态间的添加状态间的连线连线文法文法G的项目有：的项目有：1.SE2.SE 3.E aA4.E aA5.E aA6. A cA7. A cA8.

5、 A cA9. A d10. A d 11. E bB12. E bB13. E bB14. B cB15. B cB16. B cB17. B d18. B d 1*1313 2 21313 5 51313 8 813131010131313131313181813131616E34aA67cA9d1112bB1415cB17d步骤四：步骤四：1.1.找待约项目找待约项目2.2.与以其后的非终与以其后的非终结符作为产生式头结符作为产生式头的圆点在最左的项的圆点在最左的项目，用空弧与之连目，用空弧与之连接接T0= 1, 3, 11T1= 2T2= 4, 6, 9T3= 12, 14, 17T4

6、= 6, 7, 9T5= 14, 15, 17T6= 5 T7= 13 T8= 8 T9= 16 T10= 10 T11= 18状态状态输入符号输入符号abcdABET0T2T3 T1T1 T2 T4T10T6 T3 T7T5T11 T4 T4T10T8 T5 T5T11 T9 T6 T7 T8 T9 T10 T11 步骤五：步骤五：运用运用子集法将其确子集法将其确定化定化01313 1 1E 确定化的确定化的DFA1313 6 61313 7 71313 9 913131010131311111313 8 84235abcdAcAdbdcdBc*E2abcdAcAdbdcdBcSEE aAE

7、 bBA cAA cAA dE aAA cAA dSE E bBB cBB dB cBB cBB dA cAA d E aAE bBB d B cB 步骤六：步骤六：把每个子把每个子集所含状集所含状态集对应态集对应的项目写的项目写在新的状在新的状态中，得态中，得到识别活到识别活前缀的有前缀的有限自动机限自动机DFA* 使用方法使用方法2 2构造识别活前缀的构造识别活前缀的DFADFA，需要列出拓广文法的所有，需要列出拓广文法的所有项目，按规定规则构造其项目，按规定规则构造其NFANFA，然后再确定化为，然后再确定化为DFADFA，这样做，这样做确定化的工作量较大。确定化的工作量较大。E2abc

8、dAcAdbdcdBcSEE aAE bBA cAA cAA dE aAA cAA dSE E bBB cBB dB cBB cBB dA cAA d E aAE bBB d B cB* 分析分析使用方法使用方法2 2构造识别构造识别活前缀的活前缀的DFADFA中每个状态中每个状态中项目集的构成，发现中项目集的构成，发现如下规律：如下规律： 如果状态中包含形如如果状态中包含形如X X A A 的项目，则形的项目，则形如如A Ar r的项目也在此状态的项目也在此状态中。中。 因此可以用因此可以用闭包函数闭包函数（CLOSURECLOSURE）来求来求DFADFA的的项目集。项目集。方法方法3 3

9、：把增广文法的第一个项目把增广文法的第一个项目SS S S作为初态集的作为初态集的内核项内核项，通过求内核项的，通过求内核项的闭包函数闭包函数直接求出直接求出LRLR（0 0）项目）项目集规范族，再由集规范族，再由转换函数转换函数建立状态之间的连接关系得到建立状态之间的连接关系得到识别活前缀的识别活前缀的DFADFA第一步：找出第一步：找出内核项内核项第二步：第二步：通过通过闭包函数闭包函数求得求得DFA的项目集的项目集规范族规范族第三步：求出各项目集的第三步：求出各项目集的GOTO函数函数第四步：第四步：画出确定的有穷自动机画出确定的有穷自动机例如，文法例如，文法G：E aA|bBA cA|

10、 d B cB| d 用增广文法用增广文法表示成表示成文法文法G：SEE aA|bBA cA| d B cB| d 文法文法G的内核项有：的内核项有：SESE E aAE aA A cA A cA A d E bBE bBB cBB cBB d 内核项：内核项：包括初始项包括初始项SS S S以及圆点不在最左端的所有项以及圆点不在最左端的所有项项目集的闭包项目集的闭包 文法文法G G已表示为增广文法已表示为增广文法GG，如果，如果I I是文法是文法GG的一个项目集，的一个项目集，定义和构造定义和构造I I的闭包的闭包CLOSURECLOSURE（I I）如下：）如下：1 1）一开始，将）一开始

11、，将I I中的各个项加入到中的各个项加入到CLOSURECLOSURE（I I）中）中2 2）若）若项目项目X X A 属于属于CLOSURECLOSURE（I I），那么形如，那么形如A Ar的项的项目也要加入到目也要加入到CLOSURECLOSURE（I I）中。）中。3 3）不断应用规则）不断应用规则2 2），直到没有新的项目可以加入到），直到没有新的项目可以加入到CLOSURECLOSURE（I I）中为止。）中为止。例如，文法例如，文法G：E aA|bBA cA| d B cB| d 用增广文法用增广文法表示成表示成文法文法G：SEE aA|bBA cA| d B cB| d 文法文

12、法G的内核项有：的内核项有：SESE E aAE aA A cA A cA A d E bBE bBB cBB cBB d 例如，文法例如，文法G：E aA|bBA cA| d B cB| d 用增广文法用增广文法表示成表示成文法文法G：SEE aA|bBA cA| d B cB| d SE的闭包为：的闭包为：SEE aAE bBE aA的闭包为：的闭包为：E aAA cAA d 例如，文法例如，文法G：E aA|bBA cA| d B cB| d 用增广文法用增广文法表示成表示成文法文法G：SEE aA|bBA cA| d B cB| d A cA的闭包为：的闭包为：A cA A cAA d

13、 B cB的闭包为：的闭包为：B cB B cBB d E bB的闭包为：的闭包为：E bB B cBB d 例如，文法例如，文法G：E aA|bBA cA| d B cB| d 用增广文法用增广文法表示成表示成文法文法G：SEE aA|bBA cA| d B cB| d I0： SE E aA E bBI4： A cA A cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 通过闭包函数求得通过闭包函数求得DFA的项目集的项目集规范族规范族I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I

14、11： B d 转换函数（转换函数（GOTOGOTO函数）函数） 转换函数的定义如下：转换函数的定义如下：GOTO(I,X)=closure(J) GOTO(I,X)=closure(J) 其中：其中：I I是是G G的一个的一个LR(0)LR(0)项目集项目集X X为一个文法符号为一个文法符号, X, X VVT TVVN N J=J=当当AAXX I I时时, ,任意形如任意形如AXAX的项目的项目 即即GOTO (I,X)GOTO (I,X)为为I I中所有形如中所有形如AAXX的项目所对应的项的项目所对应的项目目AXAX的集合的闭包的集合的闭包I0： SE E aA E bBI4： A

15、 cA A cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 文法文法G通过闭包函数求得通过闭包函数求得DFA的项目集的项目集有：有：I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I11： B d I0=S E, EaA, EbB1）GOTO GOTO (I0, E)= closure(J)=closure(SE)= SE = I12）GOTO GOTO (I0, a)= closure(J)=closure(EaA) = EaA, AcA, Ad )=I23）GOTO GOTO (I0

16、, b)= closure(J)=closure (E b.B) =E b B, B cB, B d= I3I0： SE E aA E bBI4： A cA A cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 文法文法G通过闭包函数求得通过闭包函数求得DFA的项目集的项目集有：有：I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I11： B d I2=E aA， A cA，A d1） GOTO GOTO(I2, A)= closure(J)=closure(E aA ) = E aA =

17、 I62） GOTOGOTO(I2, c)= closure(J)=closure(A c A ) =A c A ，A cA，A d =I43） GOTO GOTO(I2, d)= closure(J)=closure (A d ) =A d = I10I0： SE E aA E bBI4： A cA A cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 文法文法G通过闭包函数求得通过闭包函数求得DFA的项目集的项目集有：有：I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I11： B d

18、 I3=E bB，B cB，B d1）GOTO GOTO (I3, B)= closure(J)=closure(E bB ) = E bB = I72） GOTO GOTO (I3, c)= closure(J)=closure(B c B ) =B c B ，B cB，B d =I53）GOTO GOTO (I3, d)= closure(J)=closure (B d ) =B d = I11I0： SE E aA E bBI4： A cA A cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 文法文法G通过闭

19、包函数求得通过闭包函数求得DFA的项目集的项目集有：有：I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I11： B d I4=A cA，A cA， A d1）GOTO GOTO (I4, A)= closure(J)=closure(A cA ) = A cA = I82） GOTO GOTO (I4, c)= closure(J)=closure(A c A ) =A cA，A cA，A d =I43）GOTO GOTO (I4, d)= closure(J)=closure (A d ) =A d = I10I0： SE E aA E bBI4： A cA A

20、 cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 文法文法G通过闭包函数求得通过闭包函数求得DFA的项目集的项目集有：有：I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I11： B d I5=B cB，B cB，B d1）GOTO GOTO (I5, B)= closure(J)=closure(B cB ) = B cB = I92） GOTO GOTO (I5, c)= closure(J)=closure(B c B) =B cB，B cB，B d =I53）GOTO GOTO

21、(I5, d)= closure(J)=closure (B d ) =B d = I11 由转换函数建立状态之间的连接关系由转换函数建立状态之间的连接关系得到识别活前缀的得到识别活前缀的DFAI0： SE E aA E bBI4： A cA A cA A dI2： E aA A cA A dI3： E bB B cB B dI5： B cB B cB B dI1： SE 文法文法G通过闭包函数求得通过闭包函数求得DFA的项目集的项目集有：有：I6：E aAI7： E bBI8：A cAI9： B cBI10：A d I11： B d GOTOGOTO(I0, E)= I1 GOTO GOTO

22、 (I0, a)=I2 GOTO GOTO (I0, b)= I3GOTOGOTO(I2, A)= I6 GOTO GOTO (I2, c)=I4 GOTO GOTO (I2, d)= I10GOTOGOTO(I3, B)= I7 GOTO GOTO (I3, c)= I5 GOTO GOTO (I3, d)= I11GOTOGOTO(I4, A)= I8 GOTO GOTO (I4, c)= I4 GOTO GOTO (I4, d)= I10GOTOGOTO(I5, B)= I9 GOTO GOTO (I5, c)= I5 GOTO GOTO (I5, d)= I11EabcdAcAdBdc

23、dBcI0I4I2I1I3I5I8I10I6I7I11I9 得到识别活前缀的得到识别活前缀的DFAE2abcdAcAdBdcdBcSEE aAE bBA cAA cAA dE aAA cAA dSE E bBB cBB dB cBB cBB dA cAA d E aAE bBB d B cB 得到识别活前缀的得到识别活前缀的DFA*识别活前缀的确定的有穷自动机 方法方法1 1：根据形式定义求出活前缀的正规表达式，然后由此正根据形式定义求出活前缀的正规表达式，然后由此正规表达式构造规表达式构造NFANFA再确定化为再确定化为DFADFA 方法方法2 2：求出文法的所有求出文法的所有LRLR（0

24、0）项目，按一定规则构造识别）项目，按一定规则构造识别活前缀的活前缀的NFANFA再确定化为再确定化为DFADFA 方法方法3 3：把增广文法的第一个项目把增广文法的第一个项目SS S S作为初态集的核，作为初态集的核，通过求核的闭包函数直接求出通过求核的闭包函数直接求出LRLR（0 0）项目集规范族，再由转）项目集规范族，再由转换函数建立状态之间的连接关系得到识别活前缀的换函数建立状态之间的连接关系得到识别活前缀的DFADFA 方法方法1 1较严格确切，方法较严格确切，方法2 2和方法和方法3 3较直观较直观改进的方法：改进的方法：方法方法2+2+方法方法3 3思路：思路：u把增广文法的第一个把增广文法的第一个项目项目SS S S作为初态作为初态集的核集的核u对每读入对每读入一个符号后一个符号后产生的新的项目集进产生的新的项目集进行闭包运算行闭包运算u直至该项目集内的所直至该项目集内的所有项目均为规约项