编译原理语法分析

1、编译原理语法分析第1页，共108页，2022年，5月20日，20点34分，星期二 自下而上分析法是一种移进-归约法。分析过程中采用了一个FIFO分析栈。分析开始后，把输入符号自左至右逐个移进分析栈，边移入边分析，一旦栈顶符号串形成句柄就进行一次归约，再继续查看栈顶是否形成新的句柄，若仍为句柄，则再归约，如此重复直至栈顶不是句柄。此时再继续向栈中移进后续输入符号。重复该过程，直到将整个输入串处理完毕。若此时分析栈只有文法开始符，则输入串是一个句子，否则输入串有错。 第2页，共108页，2022年，5月20日，20点34分，星期二 下面通过例子说明这种分析过程。 文法GS：SaAbB AcAc B

2、d 试对输入串accbd进行分析，检查该 符号串是否是GS的一个句子。 假设“#”为输入串界符，将输入串前的“#”放入分析栈，接着将输入串的符号依次进栈，具体分析过程如下:第3页，共108页，2022年，5月20日，20点34分，星期二步骤分析栈句柄输入串动 作1#accbd#移进2#accbd#移进3#accbd#移进4#aAccbd#归约(用Ac)5#aAcbd#移进6#aAAcbd#归约(用AAc)7#aAbd#移进8#aAbd#移进9#aAbBd#归约(Bd)10#SaAbB#归约(SaAbB)第4页，共108页，2022年，5月20日，20点34分，星期二SaccbdABA(d)ac

3、cbdABA(c)accAA(b)acA(a) 在自下而上分析过程中，每一步归约都可画出一棵子树，随着归约的完成，这些子树连成一棵完整的分析树。上述分析过程可用分析树表示如下:第5页，共108页，2022年，5月20日，20点34分，星期二 由上述建树过程知，自下而上分析过程的每一步归约都是对当前句型的句柄进行归约，即句柄一旦形成总是出现在分析栈栈顶。由于每一步归约都把栈顶符号串用某产生式左部符号替换，故把栈顶的这样一串符号称为可归约串。 上述第6步若不选AAc而选Ac进行归约，则无法归约到S。如何确知栈顶的Ac是可归约串而c不是呢？这需精确定义“可归约串”的概念。第6页，共108页，2022

4、年，5月20日，20点34分，星期二 若文法GS是无二义文法，则规范推导的逆过程必是规范归约(最左归约)。 对于移进-归约过程，句柄的最左性和分析栈栈顶相关。对于规范推导所得句型(规范句型)，句柄后面不会出现非终结符，故可用句柄刻画“可归约串”，规范归约的实质是在移进过程中当栈顶呈现句柄时进行归约。第7页，共108页，2022年，5月20日，20点34分，星期二 为加深对句柄和归约等概念的理解，用修剪语法树方法进一步阐明自下而上分析过程。 语法树的一个子树由该树的某结点及其所有子孙组成，子树的所有叶结点的自左至右排列形成一个相对于子树根的短语。一个句型的句柄是该句型对应的语法树中最左简单子树的

5、所有树叶的自左至右排列。第8页，共108页，2022年，5月20日，20点34分，星期二 可采用修剪语法树方法实现归约，即寻找当前语法树的句柄，将句柄中的树叶剪去(归约)，不断修剪直到只剩根结点，完成整个归约过程：SaAbBAcdcSaAbBAcdSaAbBdSaAbBS第9页，共108页，2022年，5月20日，20点34分，星期二 至此讨论了句柄和规范归约这两个基本概念，但并没有解决规范归约的问题，因为没有给出寻找句柄的算法。事实上，规范归约的中心问题就是如何寻找句柄。寻找句柄的不同算法对应不同的规范归约方法，这一点将在LR分析器中讨论。第10页，共108页，2022年，5月20日，20点

6、34分，星期二 算符优先分析法是一种简单直观、广为使用的自下而上分析法，特别适合于表达式分析且宜于手工实现。它实际上是依照表达式四则运算过程来进行语法分析。 所谓算符优先分析，就是预先规定运算符(确切地说是终结符)之间的优先关系和结合性质，借助于这种优先关系来比较相邻运算符的优先级，以确定句型的可归约串并进行归约。 注意：算符优先分析不是规范归约。3.4.2 算符优先分析法第11页，共108页，2022年，5月20日，20点34分，星期二 1. 算符优先文法 算符文法: 若一个文法的任一产生式的 右部都不含两个相继的非终结符， 即不含QR这样的右部，则称 该文法为算符文法。 算符优先文法: 算

7、符优先文法首先应是算符文法, 其次还要定义任意两个可能相继 出现的终结符的优先关系。 具体定义如下:第12页，共108页，2022年，5月20日，20点34分，星期二假定G是一个不含产生式的算符文法, 对任一对终结符a,b, 定义(1) a=b当且仅当文法G中含有形如 Pab 或 PaQb的产生式;(2) ab当且仅当G中含有形如 PRb的产生式， 而R a 或 R aQ。+第13页，共108页，2022年，5月20日，20点34分，星期二若一个算符文法G中任一终结符对(a,b) 至多满足下述三种关系之一 : a=b，ab则称文法G是一个算符优先文法。例3.10 试说明下述文法G是算符文法，

8、但不是算符优先文法。 EE+EE*E(E)i解: 由于文法G的任一产生式右部都不 含两个相邻的非终结符， 故文法G是算符文法。第14页，共108页，2022年，5月20日，20点34分，星期二 (1)由于存在EE+E，而E+E中第二 个E可推出E*E，故有+* 可见, 运算符+和*之间同时存在两种不同的优先关系，故文法G不是算符优先文法。第15页，共108页，2022年，5月20日，20点34分，星期二2. 算符优先关系表的构造 通过检查文法的每个产生式的各个侯选式,可找出所有满足a=b的终结符对。 为找出所有满足关系 “”的终结符对,需先对文法的每个非终结符P构造两个集合FIRSTVT(P)

9、和LASTVT(P): FIRSTVT(P)=a | P a或 P Qa, aVT而QVN LASTVT(P)=a | P a或 P aQ, aVT而QVN+第16页，共108页，2022年，5月20日，20点34分，星期二FIRSTVT集的构造方法：(1)若有产生式Pa或PQa， 则aFIRSTVT(P)；(2)若有产生式PQ,且aFIRSTVT(Q), 则aFIRSTVT(P)。第17页，共108页，2022年，5月20日，20点34分，星期二例如 试构造文法GE的FIRSTVT集。 GE: EE+TT TT*FF F(E)i解: 根据规则(1)知： 由EE+得, FIRSTVT(E)=+

10、； 由TT*得, FIRSTVT(T)=*； 由F(和Fi得,FIRSTVT(F)=(,i 根据规则(2)知： 由TF和FIRSTVT(F)=(,i得, FIRSTVT(T)=*, (, i； 由ET和FIRSTVT(T)得, FIRSTVT(E)=+, *, (, i第18页，共108页，2022年，5月20日，20点34分，星期二LASTVT集构造方法：(1)若有产生式Pa或PaQ， 则aLASTVT(P)；(2)若有产生式PQ,且 aLASTVT(Q), 则aLASTVT(P)。第19页，共108页，2022年，5月20日，20点34分，星期二例如 试构造文法GE的LASTVT集。 GE

11、: EE+TT TT*FF F(E)i解: 根据规则(1)知： 由E+T得, LASTVT(E)=+ 由T*F得, LASTVT(T)=* 由F)和Fi得,LASTVT(F)=),i 根据规则(2)知： 由TF和LASTVT(F)得, LASTVT(T)=*, ), i; 由ET和LASTVT(T)得, LASTVT(E)=+, *, ), i。第20页，共108页，2022年，5月20日，20点34分，星期二构造优先关系表的方法：(1) 对形如Pab或PaQb的 产生式, 有a=b；(2) 对形如PaR的产生式, 若 bFIRSTVT(R), 则ab。(4) 对于语句括号#,有 # = #

12、# #第21页，共108页，2022年，5月20日，20点34分，星期二例3.11 构造文法GE的算符优先关系表。 GE: EE+TT TT*FF F(E)i解: 构造FIRSTVT集 根据规则(1)知： 由EE+得, FIRSTVT(E)=+； 由TT*得, FIRSTVT(T)=*； 由F(和Fi得,FIRSTVT(F)=(,i 根据规则(2)知： 由TF和FIRSTVT(F)=(,i得, FIRSTVT(T)=*, (, i； 由ET和FIRSTVT(T)得, FIRSTVT(E)=+, *, (, i第22页，共108页，2022年，5月20日，20点34分，星期二构造LASTVT集根

13、据规则(1)知： 由E+T得, LASTVT(E)=+； 由T*F得, LASTVT(T)=*； 由F)和Fi得,LASTVT(F)=),i。根据规则(2)知： 由TF和LASTVT(F)得, LASTVT(T)=*, ), i; 由ET和LASTVT(T)得, LASTVT(E)=+, *, ), i。第23页，共108页，2022年，5月20日，20点34分，星期二构造优先关系表根据规则(1), 由“(E)”知, (=)。根据规则(2), 由E+T知, + FIRSTVT(T), 即 + *, + (, + i 由T*F知, * FIRSTVT(F), 即* (, * i 由F(E知, (

14、FIRSTVT(E), 即( +, ( *, ( (, ( +， 即+ +，* +，) +，i + 由TT*知, LASTVT(T)*， 即* *，) *，i * 由FE)知, LASTVT(E)， 即+ )，* )，) )，i )由#E#知, # = #； #FIRSTVT(E), 即#+,#*,#(,#, 即+#,*#,)#,i#第25页，共108页，2022年，5月20日，20点34分，星期二故算术表达式文法的优先关系表如下:+*i()#+*i(#=第26页，共108页，2022年，5月20日，20点34分，星期二3. 算符优先分析算法的设计 由于算符优先分析法仅在终结符之间定义了优先关

15、系而未对非终结符定义优先关系，这就无法使用优先关系表去识别由单个非终结符组成的可归约串，因此算符优先分析法不是用句柄而是用最左素短语来刻画“可归约串” 。 所谓句型的素短语是指这样一种短语,它至少包含一个终结符且除自身外不再包含其它更小的素短语。最左素短语是处于句型最左边的那个素短语。第27页，共108页，2022年，5月20日，20点34分，星期二如何让计算机寻找最左素短语？算符优先文法的句型的一般形式为 # N1a1N2a2NnanNn+1# 其中, ai是终结符, Ni是可有可无的 非终结符。算符优先文法任一句型的最左素短语是满足下述条件的最左子串: NjajNj+1aj+1 Niai

16、Ni+1 aj-1ai+1第28页，共108页，2022年，5月20日，20点34分，星期二查找最左素短语的方法：(1) 最左子串法 先找出句型中终结符由左至右满足aj-1ai+1的最左子串。 再检查文法的每个候选式,看其是否满足:所有终结符由左至右的排列恰为ajaj+1ai, 即终结符对应相等而非终结符仅对应位置相同。若存在这样的候选式, 则用该候选式进行归约。第29页，共108页，2022年，5月20日，20点34分，星期二 (2) 语法树法 先画出句型的语法树, 再找语法树中所有相邻终结符间的优先关系。 确定相邻终结符间优先关系的原则: 语法树中同层的优先关系为“= ”; 不同层时, 层

17、次在下的优先级高, 层次在上的优先级低; 在句型两侧加上语句括号“#”, 则有#。 最后按最左素短语必须具备的条件 确定最左素短语。第30页，共108页，2022年，5月20日，20点34分，星期二例3.12 文法GE: EE+T | T TT*F | F F(E) | i 试确定F+T*i的最左素短语。 解:画句型F+T*i的语法树, 根据语法树确定相邻终 结符间优先关系如图, 故最左素短语为i。 注意:最左直接短语为FEEE*TFTiF#*i#第31页，共108页，2022年，5月20日，20点34分，星期二算符优先分析算法: k=1; Sk=#; /k代表栈S的使用深度 doa=下一个输

18、入符; if (SkVT) j=k;else j=k1; /j指栈顶终结符 while (Sja) /找最左Sja doQ=Sj; /j从最左素短语末逐步移向首 if (Sj1VT) j=j1; else j=j2; while (Sj=Q); 把Sj+1Sk归约为某个N; k=j+1; Sk=N; /把N置于原Sj+1位置 if (Sja) | (Sj=a) k=k+1; Sk=a; else error( ); /若栈顶Sja或=a则将a压栈 while (a!=#);第32页，共108页，2022年，5月20日，20点34分，星期二 上述算法工作过程中, 若出现j减1后其值小于等于0,

19、则意味着输入串有错。正确情况下, 算法工作完毕时符号栈将呈现#S#。例3.13 文法GE及其优先关系如例3.12 所示, 试给出输入串i+i*i的算符优先 分析过程。解: 输入串i+i*i的算符优先分析过程如下:第33页，共108页，2022年，5月20日，20点34分，星期二符号栈输入串 动 作#i+i*i#i#i+i*i#+, 用Fi归约#F+i*i#+#F+i*i#+i#F+i*i#+*, 用Fi归约#F+F*i#+*#F+F*i#+*i#F+F*i#*#, 用Fi归约#F+F*F#+#, 用TT*F归约#F+T#, 用EE+T归约#E#E# 结束第34页，共108页，2022年，5月2

20、0日，20点34分，星期二 算符优先分析的归约只关心句型中由左至右终结符序列的优先关系,不涉及非终结符。再以i+i为例, 给出其算符优先分析过程和规范归约过程。 算符优先分析比规范归约要快得多。这既是算符优先分析的优点,也是它的缺点,因为这可能把本来不成句子的输入串误认为是句子,这种缺点易于弥补。 第35页，共108页，2022年，5月20日，20点34分，星期二例3.14 试设计下述文法的算符优先分析表: GS: SiBtSiBtAeSa AiBtAeSa Bb解: 首先构造FIRSTVT集和LASTVT集 FIRSTVT(S)=i,a; FIRSTVT(A)=i,a; FIRSTVT(B)

21、=b; LASTVT(S)=t,e,a; LASTVT(A)=e,a; LASTVT(B)=b; 由AS知, LASTVT(S)LASTVT(A) 即 LASTVT(A)=t,e,a第36页，共108页，2022年，5月20日，20点34分，星期二然后构造优先关系表:(1)由产生式SiBtAeS和SiBtS可知: 由SiB得, it； 由StA得, te； 由SeS得, eFIRSTVT(S)； 由SiBt得, i=t； 由StAe得, t=e； 由StS得, te和t=e, 由iBtAeS知, 此时应 将iBtAeS同时归约为S或A,即取t=e。第37页，共108页，2022年，5月20日，

22、20点34分，星期二最后得到优先关系表如下:iteabiteb=第38页，共108页，2022年，5月20日，20点34分，星期二4. 优先函数 用优先关系表表示终结符间的优先关系时,存储量大,查找费时。若给终结符赋一个值,值的大小反映其优先关系,则终结符间的优先关系比较就转为值的比较。 一个终结符在栈中与在输入串中的优先值不同,例如,既存在+),又存在)+。因此,对一个终结符a而言,它应该有一个左优先数f(a)和一个右优先数g(a)。 第39页，共108页，2022年，5月20日，20点34分，星期二 若根据一个文法的算符优先关系表,使得文法中每个终结符a和b满足下述条件: (1)若存在a=

23、b，则有f(a)=g(b)； (2)若存在ab，则有f(a)g(b)； (3)若存在ab=第41页，共108页，2022年，5月20日，20点34分，星期二 根据优先关系表构造优先函数f和g的方法有两种: 关系图法、直接构造法 (1)用关系图法构造优先函数的步骤 对每个终结符a(包括“#”),令其对应两个符号fa和ga, 画一张以所有fa和ga为结点的方向图： 若ab或a=b,画一条从fa到gb的有向边; 若ab而f(a)g(b), 则令f(a)=g(b)+1； 若a*i(#=第45页，共108页，2022年，5月20日，20点34分，星期二解: (1)用关系图法构造的优先关系图如下:ff*f

24、if)gg*gig(g)f(第46页，共108页，2022年，5月20日，20点34分，星期二+ * i ( )f4 6 6 2 6g3 5 7 7 2由上图求得优先函数如下:第47页，共108页，2022年，5月20日，20点34分，星期二迭代函数函数+*i()0(初值)f11111g111111f24414g235512f35515g246613f35515g24661(2)由定义直接计算优先函数的过程如下:第48页，共108页，2022年，5月20日，20点34分，星期二3.5 LR分 析 法 LR分析法是一种自下而上进行规范归约的语法分析方法, L指自左向右扫描输入串, R指最右推导(

25、规范归约)。 LR分析法比递归下降分析法、LL(1)分析法对文法的限制要少得多, 大多数无二义性CFG语言都可用LR分析器识别, 且速度快, 并能准确、指出输入串的语法错误及出错位置。 LR分析法的主要缺点: 手工构造工作量相当大, 必须求助自动产生工具。第49页，共108页，2022年，5月20日，20点34分，星期二3.5.1 LR分析器的工作原理 规范归约(最右推导逆过程)的关键是寻找句柄。LR分析法的基本思想:在规范归约过程中,一方面记住已移进和归约出的符号串,即记住“历史”; 另一方面根据所用产生式推测未来可能遇到的输入符,即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈栈顶

26、时,希望能根据所记载的“历史”、“展望”及“现实”材料来确定栈顶符号是否构成句柄。 第50页，共108页，2022年，5月20日，20点34分，星期二 LR分析器的结构示意如下所示,它由分析栈、分析表和总控程序三部分组成:a1a2aian#LR分析表总控程序输入串：栈顶#x1xm输出s0s1sm分析栈第51页，共108页，2022年，5月20日，20点34分，星期二 LR分析器实质上是一个带先进后出栈的DFA。“历史”和“展望”材料被抽象成某些“状态”,而分析栈用来存放这些状态,栈里的每个状态概括了从分析开始直到某一归约阶段的全部“历史”和“展望”资料。任何时候,栈顶的状态都代表了整个“历史”

27、和已推测出的“展望”。第52页，共108页，2022年，5月20日，20点34分，星期二 LR分析器的每一步工作都由栈顶状态和现行输入符唯一决定。为了易于归约,把已归约出的文法符号也放在栈中。栈的每一项内容包括状态s和文法符号X两部分。(s0,#)为分析开始前预先放入栈里的初始状态和句子括号。栈顶状态为sm,符号串X1X2Xm是已移进归约出的文法符号串。第53页，共108页，2022年，5月20日，20点34分，星期二 LR分析表是LR分析器的核心, 它包括两部分: 动作表(ACTION表) (二维数组) 状态转换表(GOTO表)(二维数组) ACTIONs,a规定了状态s面临输入符a时应采取

28、的动作。GOTOs,X规定了状态s面对文法符号X(终结符或非终结符)时的下一状态。显然, GOTOs,X定义了一个以文法符号为字母表的DFA。第54页，共108页，2022年，5月20日，20点34分，星期二ACTIONs,a的动作:(1)移进: 使(s,a)的下一状态s=GOTOs,a和 输入符a进栈,下一输入符变现行输入符。 注:对终结符a,下一状态s的值GOTOs,a 实际上放在ACTIONs,a中(2)归约: 用某一产生式A进行归约。 若的长度为,则归约动作是去掉栈顶 的个项,使状态sm-变成栈顶状态,然后 使(sm-,A)的下一状态s=GOTOsm-,A 和文法符号A进栈。 归约不改

29、变现行输入符。执行归约意味 着栈顶符号串Xm-+1Xm是句柄。 第55页，共108页，2022年，5月20日，20点34分，星期二(3)接受: 宣布分析成功,分析器停止工作。(4)报错: 报告发现源程序有错,调用出错处 理程序。LR分析器总控程序的工作十分简单,它的任一步只需按分析栈栈顶状态s和现行输入符a执行ACTIONs,a所规定的动作。LR分析器的工作过程可看成是栈中状态序列、已归约串和输入串构成的三元式的变化过程。第56页，共108页，2022年，5月20日，20点34分，星期二例如, 算术表达式文法GE如下: GE: (1) EE+T (2) ET (3) TT*F (4) TF (

30、5) F(E) (6) Fi文法GE的LR分析表见表3.13, 试给出语句i+i*i的LR分析过程。第57页，共108页，2022年，5月20日，20点34分，星期二表3.13 算术表达式文法的LR分析表状态ACTIONGOTOi+*()#ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5第58页，共108页，2022年，5月20日，20点34分，星期二步骤状态栈符号栈输入串动 作 说 明10#i+i*i#ACTION0,i=s5,状态5入栈2

31、0 5# i+i*i#r6:Fi归约,GOTO(0,F)=3入栈30 3# F+i*i#r4:TF归约,GOTO(0,T)=2入栈40 2# T+i*i#r2:ET归约,GOTO(0,E)=1入栈50 1# E+i*i#ACTION1,+=s6,状态6入栈60 1 6# E+i*i#ACTION6,i=s5,状态5入栈表3.14 i+i*i的LR分析过程第59页，共108页，2022年，5月20日，20点34分，星期二70 1 6 5# E+i*i#r6:Fi归约,GOTO(6,F)=3入栈80 1 6 3# E+F*i#r4:TF归约,GOTO(6,T)=9入栈90 1 6 9# E+T*i

32、#ACTION9,*=s7, 状态7入栈100 1 6 9 7#E+T*i#ACTION7,i=s5,状态5入栈110 1 6 9 7 5# E+T*i#r6:Fi归约,GOTO(7,F)=10入栈12016 9 7 10# E+T*F#r3:TT*F归,GOTO(6,T)=9入栈130 1 6 9# E+T#r1:EE+T,GOTO(0,E)=1入栈140 1# E#Acc: 分析成功第60页，共108页，2022年，5月20日，20点34分，星期二如何由文法构造LR分析表? LR文法: 对于一个文法, 如果能够构造一张LR分析表使得它的每个入口均是唯一确定的, 则称该文法为LR文法。 对于

33、LR文法, 当分析器对输入串进行自左至右扫描时, 一旦句柄呈现于栈顶, 能及时对它实行归约。 有些情况下LR分析器需“展望”和实际检查未来的k个输入符才能决定应采取什么样的“移进-归约”决策。第61页，共108页，2022年，5月20日，20点34分，星期二 LR(k)文法: 一个文法如果能用一个每步最多向前检查k个输入符的LR分析器进行分析, 则称该文法为LR(k)文法。 若一个文法的任何“移进-归约”分析器都存在下述情况: 尽管栈的内容和下一输入符都已了解, 但仍无法确定是“移进”还是“归约”, 或无法从几种可能的归约中确定其一, 则该文法为非LR(1)文法。 注意: (1) LR文法肯定

34、是无二义的, 一个二义文法不会是LR文法。(2) LR分析技术可适当修改以适于一定的二义文法。第62页，共108页，2022年，5月20日，20点34分，星期二四种LR分析表的构造方法: (1) LR(0)表的构造方法: 该法局限性很大, 但它是建立一般LR分析表的基础。 (2)SLR(1)表(简单LR表)的构造方法: 该法较易实现又极有使用价值。 (3)LR(1)表(规范LR表)的构造方法: 该法适用于大多数CFG文法,但分析表 体积庞大。 (4)LALR表(向前LR表)的构造方法: 该法介于SLR(1)和LR(1)之间。第63页，共108页，2022年，5月20日，20点34分，星期二3.

35、5.2 LR(0)分析表的构造 希望仅由一种只概括“历史”资料而不包含推测性“展望”材料的简单状态就能识别呈现在栈顶的某些句柄，LR(0)项目集就是这样一种简单状态。 讨论LR分析法时,需要定义一个重要概念,这就是文法规范句型的活前缀。字的前缀是指该字的任意首部,例如,字abc的前缀有、a、ab或abc。 所谓活前缀是指规范句型的一个前缀, 这种前缀不含句柄之后的任何符号。第64页，共108页，2022年，5月20日，20点34分，星期二 在LR分析过程中的任何时候，栈里的文法符号X1X2Xm应构成活前缀。把输入串的剩余部分匹配于其后应成为规范句型(如果整个输入串确为一个句子的话)。因此，只要

36、输入串的已扫描部分保持可归约成一个活前缀，就意味着所扫描的部分没有错误。第65页，共108页，2022年，5月20日，20点34分，星期二 对于文法GS,首先要构造一个NFA,它能识别GS的所有活前缀,这个NFA的每个状态称为一个项目。 项目:文法GS中每一产生式的右部添加一个圆点,称为文法GS的一个LR(0)项目, 简称项目。 例如,产生式AXYZ对应四个项目： AX Y Z A XY Z A X YZ A X Y Z注意,产生式A只对应一个项目A第66页，共108页，2022年，5月20日，20点34分，星期二 一个项目指明了在分析过程的某个时刻看到产生式的多大一部分。 通过使用文法的项目

37、可构造一个NFA来识别文法的所有活前缀，再用子集法把识别活前缀的NFA确定化，使之成为一个以项目集合为状态的DFA，这个DFA就是建立LR分析算法的基础。第67页，共108页，2022年，5月20日，20点34分，星期二 识别一个文法活前缀的DFA的项目集的全体称为这个文法的LR(0)项目集规范族。这个规范族提供了建立一类LR(0)和SLR(1)分析器的基础。 圆点在最右端的项目, 如A, 称为一个归约项目; 对文法的开始符号S的归约项目, 如S ,称为接受项目; 形如Aa的项目(a为终结符),称为移进项目; 形如AB的项目(B为非终结符)，称为待约项目。第68页，共108页，2022年，5月

38、20日，20点34分，星期二1. LR(0)项目集规范族的构造 可用_CLOSURE构造一个文法的LR(0)项目集规范族。 首先构造文法GS的拓广文法GS，它包含整个GS并引进一个不出现在GS中的非终结符S，同时加进了一个新产生式SS。这样，仅含项目SS的状态是唯一的接受状态。第69页，共108页，2022年，5月20日，20点34分，星期二 假定I是文法GS的任一项目集, 定义和构造CLOSURE(I)的方法: (1)I的任何项目都属于CLOSURE(I)； (2)若AB属于CLOSURE(I)， 则对任何关于B的产生式B, 其项目B属于CLOSURE(I)。 (3)重复(1)(2)直至CL

39、OSURE(I)不再 增大为止。第70页，共108页，2022年，5月20日，20点34分，星期二 假定I是文法GS的任一项目集,X是一个文法符号(终结符或非终结符),则状态转换函数GO(I,X)的定义为 GO(I,X)=CLOSURE(J) 其中J=任何形如AX的项目 | AX属于I。 若I是对某个活前缀有效的项目集(状态), 则GO(I,X)是对X有效的项目集(状态)。第71页，共108页，2022年，5月20日，20点34分，星期二 通过CLOSURE(I)和GO(I,X)构造拓广文法GS的LR(0)项目集规范族的方法: (1)求出I的闭包CLOSURE(I) (2)先用GO(I,X)求

40、出J, 再对J求其闭包CLOSURE(J)。 以此类推, 最终可构造出拓广文法GS的LR(0)项目集规范族。第72页，共108页，2022年，5月20日，20点34分，星期二2. LR(0)分析表的构造 若文法GS的拓广文法GS的活前缀识别自动机中的每个状态(项目集)不存在下述情况：既含移进项目又含归约项目或含有多个归约项目,则GS是一个LR(0)文法。换言之,LR(0)文法的项目集规范族中任一项目集均不包含冲突项。 对于LR(0)文法, 可直接从它的项目集规范族C和状态转换函数GO(I,X)构造出其LR(0)分析表。第73页，共108页，2022年，5月20日，20点34分，星期二 假定C=

41、I0,I1,In, 令每个项目集Ik的下标k作为分析器的状态, 并令包含项目SS的集合Ik的下标k为分析器的初态, 则LR(0)分析表的构造算法如下: (1)若项目Aa属于Ik且 GO(Ik,a)=Ij, a为终结符, 则置ACTIONk,a为“将(j,a)移进 栈”, 简记为sj。第74页，共108页，2022年，5月20日，20点34分，星期二 (2)若项目A属于Ik, 则对任何终结符a或#,置 ACTIONk,a为“用A归约”, 简记为rj(其中j是第j个产生式。 (3)若项目SS属于Ik, 则置ACTIONk,#为接受,简记acc。 (4)若GO(Ik,A)=Ij, A为非终结符,则置

42、 GOTOk,A=j。 (5)分析表中凡不能用规则(1)(4)填 入的空白格均置为“出错标志”。第75页，共108页，2022年，5月20日，20点34分，星期二例3.16 试构造文法GS的LR(0)分析表: GS: SBB BaBb 解: 将文法GS拓广为文法GS： GS: (0) SS (1) SBB (2) BaB (3) Bb第76页，共108页，2022年，5月20日，20点34分，星期二该文法的LR(0)项目集规范族为: I0: SS SBB BaB Bb I1: SS I2: SBB BaB Bb I3: BaB BaB Bb I4: Bb I5: SBB I6: BaB 第77

43、页，共108页，2022年，5月20日，20点34分，星期二S I0:SSSBB BaB Bb I1:SSS I2:SBBBaBBb I5:SBBB I4:B bbb I3:BaBBaBBbab I6:B aBBaa识别该文法活前缀的DFA为:第78页，共108页，2022年，5月20日，20点34分，星期二该文法的LR(0)分析表为:状态ACTIONGOTOab#SB0s3s4121acc2s3s453s3s464r3r3r35r1r1r16r2r2r2第79页，共108页，2022年，5月20日，20点34分，星期二3.5.3 SLR(1)分析表的构造 LR(0)文法是一类非常简单的文法,

44、其特点是该文法的活前缀识别自动机的每一状态都不含冲突项。但即使是算术表达式文法也不是LR(0)的,因此需要研究一种简单“展望”材料的LR分析法,即SLR(1)法。 实际上,许多冲突性的动作都可以通过考察有关非终结符的FOLLOW集而获得解决。第80页，共108页，2022年，5月20日，20点34分，星期二SLR(1)冲突解决办法如下：假定LR(0)规范族的任一项目集I中含有m个移进项目: A1a11, A2a22, Amamm 同时含有n个归约项目: B1, B2, , Bn 若集合a1,am, FOLLOW(B1), FOLLOW(Bn)两两不相交, 则隐含在I中的动作冲突可通过检查 现行

45、输入符a属于上述n+1个集合中 的哪个集合而获得解决, 即: 第81页，共108页，2022年，5月20日，20点34分，星期二 (1)若a是某个ai, i=1,2,m,则移进; (2)若aFOLLOW(Bi), i=1,2,n, 则用产生式Bi进行归约; (3)对(1)(2)以外的情况, 报错。 冲突性动作的这种解决办法叫做 SLR(1)冲突解决办法。第82页，共108页，2022年，5月20日，20点34分，星期二文法GS的SLR(1)分析表的构造方法: 先把GS拓广为GS，对GS构造LR(0)项目集规范族C和活前缀识别自动机的状态转换函数GO，然后再使用C和GO按下面的算法构造GS的SL

46、R(1)分析表: 假定C=I0,I1,In, 令每个项目集Ik的下标k为分析器的一个状态, 并令含项目SS的Ik的下标k为初态, 则SLR(1)分析表可按如下方法构造:第83页，共108页，2022年，5月20日，20点34分，星期二(1)若项目Aa属于Ik且GO(Ik,a)=Ij, a为终结符, 则置ACTIONk,a为“将状 态j和符号a移进栈”, 即sj。(2)若项目A属于Ik, 则对任何输入符a, aFOLLOW(A), 置ACTIONk,a为“用产生式A进 行归约”, 即rj。 (3)若项目SS属于Ik, 则置ACTIONk,#为接受, 即acc。(4)若GO(Ik,A)=Ij, A

47、为非终结符, 则置GOTOk,A=j。第84页，共108页，2022年，5月20日，20点34分，星期二 (5) 凡不能用规则(1)(4)填入信息的空 白格均置“出错标志”。 若按上法构造的ACTION表和GOTO表不含多重入口,则称它为文法GS的SLR(1)表。具有SLR(1)表的文法称为一个SLR(1)文法。使用SLR(1)表的分析器叫做SLR(1)分析器。 若按上述算法构造的分析表存在多重入口, 则不能用上述算法构造分析器。第85页，共108页，2022年，5月20日，20点34分，星期二例3.18 构造例3.16文法SLR(1)分析表。解: 先拓广文法, 再求文法的LR(0)项目集 规

48、范族及DFA, 求所有形如A 的 项目的FOLLOW(A), 即 对SBB,BaB,Bb求FOLLOW集: 由FOLLOW集的构造方法得： FOLLOW(S)=#； FIRST(B)FOLLOW(B), 即 FOLLOW(B)=a,b； 由SS, FOLLOW(S)FOLLOW(S), 即FOLLOW(S)=#； 由SBB,FOLLOW(S)FOLLOW(B), 即FOLLOW(B)=a,b,#。第86页，共108页，2022年，5月20日，20点34分，星期二最后求GS的SLR(1)分析表如下: 状 态ACTIONGOTOab#SB0s3s4121acc2s3s453s3s464r3r3r3

49、5r16r2r2r2第87页，共108页，2022年，5月20日，20点34分，星期二*3.5.4 LR(1)分析表的构造 在SLR(1)方法中，若项目集Ik含有A，那么在状态k时，只要当前输入符aFOLLOW(A)，就采取“用A归约”的动作。但在某种情况下，当状态k呈现于栈顶时，栈里的符号串所构成的活前缀未必允许把归约为A，因为可能没有一个规范句型含有前缀Aa。因此，在这种情况下，用A进行归约未必有效。第88页，共108页，2022年，5月20日，20点34分，星期二 可设想让每个状态含有更多的展望信息,这些信息将有助于克服动作冲突和排除无效归约,必要时对状态进行分裂,使得LR分析器的每个状

50、态能确切指出当后跟哪些终结符时才允许把归约为A。 为此,需重新定义项目,使得每个项目都附带有k个终结符。现在每个项目的一般形式为 A, a1a2ak 此处, A是一个LR(0)项目,ai是终结符, 这种项目称为LR(k)项目,其中, a1a2ak称为向前搜索串(或展望串)。第89页，共108页，2022年，5月20日，20点34分，星期二 向前搜索串仅对归约项目A, a1a2ak有意义, 对移进或待约项目不起作用。归约项目A,a1a2ak意味着当它所属状态呈现在栈顶且后续的k个输入符为a1a2ak时,才把栈顶的归约为A。这里只对k1的情形感兴趣。 构造有效的LR(1)项目集族的方法和构造LR(

51、0)项目集规范族的方法本质上一样,也需两个函数:CLOSURE(I)和GO(I,X)。第90页，共108页，2022年，5月20日，20点34分，星期二项目集I的闭包可按如下方式构造： (1) I的任何项目都属于CLOSURE(I)。 (2)若项目AB, a 属于CLOSURE(I), B是 一产生式, 则对于FIRST(a)中的每个终结符b, 若B, b原来不在CLOSURE(I)中,把它加进去。 (3)重复(2)直到CLOSURE(I)不再增大。函数GO(I, X)定义为: GO(I, X) =CLOSURE(J) 其中J=形如AX, a的项目 | AX, a属于I第91页，共108页，2

52、022年，5月20日，20点34分，星期二构造LR(1)分析表的算法: 假定C=I0,I1,In,令每个Ik的下标k为分析表的状态,令含有SS, #的Ik的k为分析器的初态。LR(1)分析表可按如下方法构造： (1)若项目Aa, b属于Ik且GO(Ik,a)=Ij, a为终结符,则置ACTIONk,a为“将状态j和符号a移进栈”,简记为sj；第92页，共108页，2022年，5月20日，20点34分，星期二 (2)若项目A, a属于Ik, 则置ACTIONk,a为“用产生式A归约”,简记为rj, 其中j是产生式的编号; (3)若项目SS,#属于Ik, 则置ACTIONk,#为接受, 简记为ac

53、c; (4)若GO(Ik, A)=Ij, A为非终结符, 则置GOTO(Ik, A)=j; (5)分析表中凡不能用规则(1)(4)填入信息的空白栏均填“出错标志”。第93页，共108页，2022年，5月20日，20点34分，星期二 对于LR(1), 有些状态(项目集)除向前搜索符不同外,其核心部分都相同,即LR(1)比SLR(1)和LR(0)存在更多的状态。因此, LR(1)的构造比LR(0)和SLR(1)更复杂, 占用的存储空间也更多。第94页，共108页，2022年，5月20日，20点34分，星期二3.5.5 LALR分析表的构造 自学 对LR(1)来说,存在着某些状态(项目集),这些状态

54、除向前搜索符不同外,其核心部分都相同,能否将核心部分相同的诸状态合并为一个状态,这种合并是否会产生冲突?下面将对此进行讨论。 两个LR(1)项目集具有相同的心是指除去搜索符之后这两个集合是相同的。如果把所有同心的LR(1)项目集合并为一, 将看到这个心就是一个LR(0)项目集,这种LR分析法称为LALR方法。第95页，共108页，2022年，5月20日，20点34分，星期二 对于同一个文法, LALR分析表和LR(0)以及SLR分析表永远具有相同数目的状态。LALR方法本质上是一种折中方法，LALR分析表比LR(1)分析表要小得多，能力也差一点，但它却能对付一些SLR(1)所不能对付的情况。第

55、96页，共108页，2022年，5月20日，20点34分，星期二 由于GO(I,X)的心仅仅依赖于I的心，因此LR(1)项目集合并之后的转换函数GO可通过GO(I,X)自身的合并而得到，因而在合并项目集时无需考虑修改转换函数问题(假定I1与I2的心相同，即项目集相同，则GO(I1,X) =GO(I2,X)，但这里的项目集是不包括搜索符的)。但是，动作ACTION必须进行修改，使之能够反映被合并的集合的既定动作。第97页，共108页，2022年，5月20日，20点34分，星期二 假定有一个LR(1)文法,它的LR(1)项目集不存在动作冲突,但如果把同心集合并为一,就可能导致产生冲突。这种冲突不会

56、是移进/归约的冲突,因为若存在这种冲突,则意味着面对当前的输入符号a,有一个项目A,a要求采取归约动作,而同时有另一项目Ba,b要求把a移进;这两个项目同处于(合并前的)某一个集合中,则意味着合并前必有某个c使得A,a和Ba,c同处于(合并前的)某一集合,这意味着原来的LR(1)项目集已存在移进/归约冲突。第98页，共108页，2022年，5月20日，20点34分，星期二 因此, 同心集的合并不会产生新的移进/归约冲突(因是同心合并,故只改变搜索符,不改变移进或归约操作,故不可能存在移进/归约冲突)。同时说明,若原LR(1)存在着移进/归约冲突, 则LALR必定有移进/归约冲突。 但是同心集的合并可能产生新的归约/归约冲突。例如, 假定对活前缀ac有效的项目集为Ac,d,Bc,e,对bc有效的项目集Ac,e,Bc,d,这两集合不含冲突且同心,但合并后变成Ac,d/e,Bc,d/e,含归/归冲突。第99页，共108页，2022年，5月20日，20点34分，星期二构造LALR分析表的算法: 基本思想: 首先构