第四章语法分析.ppt

4.2.4 LR分析法 迄今为止我们所学的分析方法对文法都有一定的要求,即有局限性; 1965年D.Knuth提出了分析效率极高的LR(k)分析技术; LR分析: 自左至右扫描的自底向上的分析; 在分析的每一步,只须根据分析栈中的已移进的和已归约出的符号,并至多向前扫描k个字符就能确定应采取什么分析动作(移进、归约、接受、报错); LR分析对文法要求很少,效率极高,且能及时发现错误,是目前最广泛使用的方法;一般用CFG描述的语言均可用LR分析法 LR分析综述 计算机理论研究已证明了如下结论: LR(k)文法是无二义性文法; LR(k)文法与LR(1)文法等价. 由于常见的程序设计语言均能由LR(1)文法产生,因此我们只讨论k=0,1两种情况; 本节中,我们将先介绍LR分析器的逻辑结构及工作原理,再分别介绍几种LR分析器(即LR(0),SLR(1))的构造; LR(0)简单,能力低; SLR(1)能力强于LR(0); LR分析表的优缺点 优点： 比其他“移进-归约”分析法，如算符优先分析法使用更加广泛，识别效率高 能用LL(1)分析法分析的所有文法都能使用LR方法来进行分析。 LR分析法在自左至右扫描输入串的过程中就能发现其中的任何错误，并能准确地指出出错位置。 缺点： 手工构造分析表工作量太大。必须使用自动生成器。 自底向上分析法的关键问题是如何确定句柄。LR分析法与算符优先方法一样，LR方法也是通过求句柄逐步归约来进行语法分析。 在算符优先分析中，通过算符的优先关系得到句柄，LR方法中句柄是通过求活前缀而求得。 根据栈顶状态Sm和输入符号ai查action表, 根据表中的内容不同完成不同的动作，若action[Sm, ai]为： 移进：当前输入符号ai进符号栈，下一输入符号变成当前输入符号，将action表中指出的状态S进状态栈。三元式变为： (S0S1…SmS, # X1X2…Xmai, ai+1…an#) 归约：按某个产生式A→β进行归约，若产生式的右端长度为r，则两个栈顶的r个元素同时出栈。将归约后的符号A进符号栈; 根据新栈顶状态Sm-r和归约符号A查GOTO表，S=goto[Sm-r, A]进状态栈。三元式变为： (S0S1 … Sm-r S, # X1X2…Xm-rA, aiai+1…an #) 接受：分析成功，终止分析。三元式不再变化。 出错：报告出错信息。三元式的变化过程终止。 文法： S’ →E E → aA | bB A → cA | d B → cB | d LR(0)项目集规范族：构成识别一个文法活前缀的DFA的项目集的全体。 一个项目集I的闭包CLOSURE(I)的计算： I中的任何项目i?I都有i?CLOSURE(I) (2) 若A ? ?·B??CLOSURE(I), 且B ? VN则对任何关于B的产生式：B?γ的B?·γ?CLOSURE(I)，γ为任意符号串 (3) 重复(2)直到CLOSURE(I)不再增加为止。 定义状态转换函数GO(I,X)： GO(I,X)=CLOSURE(J)=Ij I是一个项目集，X是一个文法符号 其中J={A??X·?的项目|A??·X??I} GO函数实际就是检查I中的每一个后随符号为X的项目，将这个圆点向后移动一个位置，得到项目集J，再对项目集J求闭包。 1. 拓广文法：若原文法G的开始符号为S，则增加一个非终结符S’和一个产生式S’→S，这样是为了得到唯一的接受状态S’ →S · (原因是当存在这样的产生式s →aA|A时如果不引进s’那么就存在两个接受状态aA.和A.) 设项目集规范族C只包含第一个状态{S’ →●S}的闭包，即C = Closure({S’ →●S}) 然后利用GO函数对C中的每个项目集和每个符号X计算其下一状态，并将下一状态GO(I,X)加入到C中，直到C中状态数不再增加 C即为文法G’的LR(0) 项目集规范族 若一个项目集中既含有移进项目，又含有归约项目，出现了冲突。 解决冲突的办法是：分析所有含A、B的句型，根据后继符号即FOLLOW(A)和FOLLOW(B)来判断。当在状态I时面临某输入符号为a时： 当a = b，则b应移进； 当a ∈follow(A)，则用产生式A → α进行归约； 当a ∈follow(B)，则用产生式B → α进行归约. Follow(E)={#,),+} 所以如果当前输入符号为#, ), +时，就使用E → T进行归约；如果当前输入符号为*时，就移进；当面临其他输入符号时，出错。 SLR(1)分析表的构造 设有文法G，则SLR(1)分析表的构造方法为： ? 对于A ??·X??Ik，GOTO(Ik,X)=Ij 若X ?Vt，则置a