LR分析器LR(k)概述

1、LR分析器LR(k)概述 3.5 LR分析器 nLR(k)：L表示从左至右扫描输入串，R表示构造一个最 右推导的逆过程，k指的是在决定语法分析动作时需要 向前看的符号个数。 nLR分析法的缺点：手工实现工作量大 n构造LR分析表的方法 n简单LR方法（SLR） n规范的LR方法 n向前搜索的LR文法（LALR） n描述能力：规范LRLALRSLR n实现代价：规范LRLALRSLR LR分析器LR(k)概述 LRLR分析分析 程程 序序 action gotoaction goto LR LR分析表分析表 a a1 1a a2 2a ai ia an n$ $输入串输入串 输出输出 LR分析器

2、模型 Sm Xm Sm-1 Xm-1 . . S1 X1 S0 栈 LR分析器LR(k)概述 语法分析表 n分析表构成：动作表(action)和转向表(goto) n注：Si表示状态， ai表示终结符，Ai表示非终 结符。 a1 a2 an a1 a2 an A1Am s 0 sk action goto LR分析器LR(k)概述 nactions,a规定了状态s面临输入符号a时应该采 取什么动作： n移进：把(s,a)的下一状态s=gotos,a和输入符号a推 进栈，下一输入符号变成现行输入符号； n归约：指用某一产生式A进行归约。 n接受：宣布分析成功，停止分析器的工作； n报错：报告发现

3、错误，调用出错处理程序扫描输 入串就可以发现错误位置。 LR分析器LR(k)概述 ngotos,X则指出状态s面对文法符号X（终结符 或非终结符）时下一状态是什么。 ngotos,X：若X VT ，表示在当前状态下，读 入X应转向什么状态；若X VN ，表示当前栈 顶句柄归约成X后，应转向什么状态。 LR分析器LR(k)概述 ( so X1 s1 . Xm sm, ai ai+1 . an $ ) n分析器根据action(sm , ai)确定下一步动作 1. 若action(sm , ai)为移进，且s=gotosm,ai，则二元式格局变 为: (s0 X1 s1 Xm sm ai s, a

4、i+1 an $) 2. 若action(sm , ai)为按A归约，二元式变为: (s0 X1 s1 Xm-rsm-r A s, aiai+1 an $) 此处, s=goto(sm-r, A), r为的长度, = Xm-r+1 Xm 3. 若action(sm , ai)为接受，则二元式不再变化，变化过程终 止，宣布分析成功。 4. 若action(sm , ai)为报错，则二元式变化过程终止，报告错误。 LR分析器LR(k)概述 算法3.3 LR分析算法 令a指向$的第一个符号; while(1) 令s是栈顶的状态; if (actions,a=移进t ) 把a和t依次压入栈顶; a指向

5、下一个输入符号; else if (actions,a=按文法产生式A归约 ) 从栈顶弹出2*|个符号; 令t是现在的栈顶状态; 把A和gotot,A依次压入栈顶; 输出产生式A; else if (actions,a=接受) break; /*分析完成*/ else error(); LR分析器LR(k)概述 n例：文法G(E)： (1) EET (2) ET (3) TT*F (4) TF (5) F(E) (6) Fid 分析id*id+id的识别过程。 LR分析器LR(k)概述 ACTIO NG O TO 状状 态态i+*()#ETF 0s5s4123 1s6acc 2r2s7r2r2

6、 3r4r4r4r4 4s5s4823 5r6r6r6r6 6s5s493 7s5s410 8s6s11 9r1s7r1r1 10r3r3r3r3 11r5r5r5r5 其LR分析表为: nsi表示把当前符号和状态i压入栈 nrj表示按第j个产生式归约 nacc表示接受 n空白表示出错 LR分析器LR(k)概述 栈栈 输入输入 动作动作输出输出 0id*id+id$s5 0id5*id+id$用 Fid归约 Fid 0F3*id+id$用 TF归约 TF 0T2*id+id$s7 0T2*7id+id$s5 0T2*7id5 +id$用 Fid归约 Fid 0T2*7F10+id$ 用 TT*

7、F归约 TT*F 0T2+id$用 ET归约 ET 0E1+id$s6 0E1+6id$s5 0E1+6id5 $用 Fid归约 Fid 0E1+6F3 $用TF归约 TF 0E1+6T9 $用 EE+T归约 EE+T 0E1$接受 LR分析器LR(k)概述 n对于给定文法G，如果能为G构造出LR语法分 析表，则称G是LR文法。 nLR语法分析器不需要扫描整个栈就可以知道什 么时候句柄出现在栈顶，栈顶的状态符号包含 了所需要的一切信息。 ngotos,X定义了一个以文法符号为字母表的 DFA。 LR分析器LR(k)概述 n每步需要向前看k个符号的LR语法分析器所分 析的文法称为LR(k)文法

8、n一般k=0或k=1 LR分析器LR(k)概述 nLR分析方法的特点 n栈中的文法符号总是形成一个活前缀 n分析表的转移函数本质上是识别活前缀的DFA n栈顶的状态符号包含了确定句柄所需要的一切信息 n是已知的最一般的无回溯的移进归约方法 n能分析的文法类是预测分析法能分析的文法类的真 超集 nLR分析法的缺点：手工实现工作量大 LR分析器LR(k)概述 n构造分析表的基本策略： n构造文法G的一个有限自动机，它能识别文法中的 所有活前缀。 n字的前缀是指该字的任意首部。 n例如：字ABC的前缀有，A,AB,ABC。 n活前缀(Viable Prefix)是指规范句型的一个前缀， 这种前缀不含

9、句柄之后的任何符号。 LR分析器LR(k)概述 n活前缀有两种类型： n1）归态活前缀 活前缀的尾部正好是句柄之尾， 这时可以进行归约。归约之后又成为另一句型的活 前缀。 n2）非归态活前缀 句柄尚未形成，需要继续移进 若干符号之后才能形成句柄。 LR分析器LR(k)概述 n在LR分析过程中的任何时候，栈里的文法符号 （自栈底向上）X1X2Xm应该构成活前缀，把 输入串的剩余部分配上之后即应成为规范句型 （当然，这个输入串必须确实是文法的一个句 子）。反过来说，只要输入串的已扫描部分保 持可归约成一个活前缀，那就意味着扫描过的 部分没有错误。 LR分析器LR(k)概述 n构造出一个FA，它能识

10、别某文法G的所有活前 缀 n可以文法的终结符和非终结符都看成有穷自动机的 输入符号，每次把一个符号进栈看成已识别过了该 符号，同时状态进行转换，当识别到可归前缀时， 相当于在栈中形成句柄，认为达到了识别句柄的终 态。 LR分析器LR(k)概述 项目 n项目（item）：在每个产生式的右部适当位置添加一 个圆点构成项目 n例如：产生式A XYZ对应有4个项目 A XYZ A XYZ A XYZ A XYZ n产生式A只有一个项目A。 n有限自动机的每一个状态由一个项目构成 LR分析器LR(k)概述 n项目圆点的左部表示分析过程的某个时刻用该 产生式归约时句柄已识别的部分，圆点右部表 示待识别的部

11、分。 LR分析器LR(k)概述 拓广文法 n如果文法G的开始符号是S，那么G的拓广文法 G是在文法G的基础上增加一个新的开始符号S 和产生式SS。 n将文法进行拓广，保证文法开始符号不出现在 任何产生式右部，即增加产生式SS ，并令 S S作为初态项目 LR分析器LR(k)概述 闭包运算closure n如果I是文法G的一个项目集，定义和构造I的 闭包closure(I)如下： n1)I的项目都在closure(I)中 n2)若A B 属于closure(I)，则每一形如B 的 项目也属于closure(I) n3)重复2)直到closure(I)不再扩大 LR分析器LR(k)概述 closu

12、re的计算 function closure ( I ) begin J := I; repeat for J 的每个项目 A .B 和G的每个产生式B ，若 B. 不在 J中 do 把 B. 加入 J; until 没有新项目可加入 J; return J end LR分析器LR(k)概述 n例：对于以下文法，计算closure(E E) E E E E+T E T T T*F T F F (E) F id closure(E E) = E E E E+T E T T T*F T F F (E) F id LR分析器LR(k)概述 n核心项目：初始项目和所有圆点不在左端的项 目 n非核心项目

13、：圆点在左端的非初始项目 LR分析器LR(k)概述 goto函数 n定义转换函数如下： goto(I,X)= closure(J) 其中：I为某项目集，X为文法符号 J=任何形如AX 的项目| A X 属 于I n如果I是对某个活前缀 有效的项目集，那么 goto(I,X)是对活前缀 X有效的项目集。 LR分析器LR(k)概述 n例：若I=E E, E E+T，则goto(I,+)为 E E+T T T*F T F F (E) F id LR分析器LR(k)概述 项目集的构造 procedure items(G); begin C:= closure( SS ) ; repeat for C中

14、的每个项目集I和G中的每个符号X DO IF goto(I,X)非空且不属于C THEN 把goto(I,X)放入C中 until C不再增大 end LR分析器LR(k)概述 文法3.11的项目集规范族 I0: E E EE+T ET TT*F TT*F TF F (E) Fi I1: E E EE+T I2: ET TT*F I3: TF I4: F(E) EE+T ET TT*F TF F (E) Fi I5 :Fi I6: EE+T TT*F TF F(E) Fi I7: TT*F F(E) Fi I8: F(E) EE+T I9: EE+T TT*F I10: TT*F I11: F

15、(E) LR分析器LR(k)概述 文法3.11的goto函数 I0 I1 I2 I3 I4 I5 I6 I7 I8 I9 I10 I11 E + T * T T i F ( i ( F E ( F i + F * ( ) LR分析器LR(k)概述 SLR语法分析表 n1.构造G的LR(0)项目集规范族C=I0,I1,.,In n2.从Ii构造状态i，它的分析动作如下： na)若项目Aa属于Ii且GO(Ii,a)=Ij，a为终结符， 则置actioni,a为 “sj”； nb) 若项目A属于Ii，那么，对任何终结符a， aFOLLOW(A)，置actioni,a为 “rj”；其中，假定 A为文法G的第j个产生式； nc) 若项目SS属于Ii，则置ACTIONi,$为“acc”; LR分析器LR(k)概述 n3.对所有非终结符A，若goto(Ii,A)Ij，则置 gotoi,A=j； n4.分析表中凡不能用规则2,3填入信息的空白格 均置上“出错标志”。