编译原理及实现技术：15-语法分析_LR(1)方法

第三章：语法分析 LR(1)方法2例子设有文法G：SL=RSRL*RLiRLS L=RS RL*RL iR LLSL=RRL 3SLR(1)问题所在w ZB1aB2bB3c w BdSLR(1)归约时向前看一个符号，但是不区分语法符号的不同出现。上述文法中，B出现了三次，很显然B1的后继符只能是a，B2 的后继符只能是b，B3的后继符只能是c，而Follow(B)=a,b,c，用SLR(1)就失去了精度。4几种LR方法的简单对比w LR(0)方法不依赖输入流，直接判定归约，容易出现冲突。w SLR(1)方法简单的把非终极符的follow集做为可归约的依据，并不精确。w 一个非终极符在不同的位置上出现，它所允许的后继符是不同的。LR(1)针对不同产生式上的非终极符，分别定义其后继符集，减少了移入/归约、归约/归约冲突。5LR(1)基本思想w 构造各种LR分析器的任务就是构造其action表和goto表，其他部分基本相同。LR(1)的基本思想是对非终极符的每个不同出现求其后继符，而不是给每个非终极符求其统一的后继符，我们称其为展望符集。6LR(1)项目、投影w LR(1)项目：A,a，即LR(0)项目及一个VT#的展望符组成的二元组。用IS表示LR(1)项目的集合，简称LR(1)项目集。其中，项Z的展望符为#w IS(X)：LR(1)项目集IS对于X的投影IS(X)=AX,a|AX,aIS 7LR(1)闭包集、GO函数w CLOSURE(IS)=ISA,a|B1A2,bCLOSURE(IS),A是产生式,a First(2b)w GO:若IS是一个LR(1)项目集，X是一个文法符号,则GO(IS,X)=CLOSURE(IS(X)。8可归前缀图的构造1.产生初始项目集IS0，且IS0ISS IS0=CLOSURE(Z,#),其中Z为开始符。2.若ISiISS，XVTVN，则定义ISj=GO(ISi,X)，若ISj不空且不属于ISS则将ISj加入ISS，建立ISi到ISj的X映射,重复该过程，直到ISS不产生新状态。9例子w 有文法：ZBBBaBBbb2ZBB#B0Z BB#B aB a/bB b a/bBb3Bb#1ZB B#B aB#B b#4Bb a/ba5Ba B#B aB#B b#bB8BaB#a6Ba B a/bB aB a/bB b a/baabB7BaB a/b11LR分析表action表goto表ab#B0S6S411S5S322AC3R34R3R35S5S386S6S477R2R28R2w 有文法：1ZBB2BaB3Bb状态栈 符号栈 输入串 Action GoTo0 abaab#S6 0,6 a baab#S40,6,4 ab aab#R3 70,6,7 aB aab#R210,1 B aab#S50,1,5 Ba ab#S50,1,5,5 Baa b#S30,1,5,5,3 Baab#R3 80,1,5,5,8 BaaB#R2 80,1,5,8 BaB#R2 20,1,2 BB#AC 13习题设文法GS为：SASSAaAAb 证明GS是LR(1)文法；构造它的LR(1)分析表；给出符号串abab#的分析过程02534AaGZ：ZS0SAS1S 2AaA3 Ab4 ZS0#S AS1S 2AaA3Ab4#ab#ab#1ZS#SSA S1#S AS1S 2AaA3Ab4#ab#ab#Aa A3AaA3Ab4Ab 4bab#ab#ab#ab#SA S 1#aSAa6ab#AaA 3Abbab#0S3S4R21Acc2S3S4R23S3S44R4R4R45R16R3R3R3AS021122536456actiongotoGZ：ZS0SAS1S 2AaA3 Ab4 状态栈符号栈输入流0#abab#03#a bab#034#ab ab#036#aA ab#02#A ab#023#Aa b#0234#Aab#0236#AaA#022#AA#0225#AAS#025#AS#01#S#