883-4.7 LR分析器 序4.7 .1 LR分析器的逻辑结构及工作过程4.7.2 SLR分.ppt

栈中已识别出一个L，此时，a是“=”，不能用“R?L”进行归约，因为不存在“R=”的归范句型。 解决方法：使每个项目中含有更多的展望信息，使得能确切知道何时能进行归约。 一. LR(k) 项目 形式：[A???? , a1a2…ak] ???,移进或待归约项目， a1a2…ak不起作用。对归约项目[A???, a1a2…ak]，仅当前输入符号串开始的前k个符号是a1a2…ak时，才能用A??进行归约。 a1a2…ak称向前有哪些信誉好的足球投注网站符号串。 * * 4.7 LR分析器 序 4.7 .1 LR分析器的逻辑结构及工作过程 4.7.2 SLR分析表的构造 4.7.3 LR（1）分析表的构造 4.7.4 LALR(1)分析表的构造 4.8 LR分析对二义文法的应用 4.9 分析器的生成器yacc 序? ? LR(k)分析技术。这里的“L”是指从左至右扫描输入符号串，“R”是指构造一个最右推导的逆过程，“k”是指为了作出分析决定而向前看的输入符号的个数。 LR分析方法是当前最广义的无回溯的“移进- 归约”方法。根据栈中的符号串和向右顺序查看输入串的k(k?0)个符号，就能唯一确定分析器的动作是移进还是归约，以及用哪个产生式进行归约。 LR(k)分析技术knuth于1965年首先提出 来的。 优点：适用范围广；分析速度快；报错准确。 构造分析器的工作量很大，不大可能手工构造；用软件工具yacc-Yet Another Compiler Compiler,Bell,1974. LR(0) SLR(1) LR(1) LALR(1) 4.7.1 LR分析器的逻辑结构及工作过程? 一个输入、一个输出、一个栈、一个驱动程序和一张分析表 id+id*id$ Sm Xm Sm-1 Xm-1 … S0 LR驱动程序 动作 转移 action goto 输出 分析表： 移进 ai 和s=goto[sm,ai]进栈 action[sm,ai]= 归约 rj : A?Xm-r+1Xm-r+2…Xm 接受 s=goto[sm-r , A] 出错 G[E’]: (0) E’ ?E (1) E ?E +T (2) E ?T (3) T ?T*F (4) T ?F (5) F ?(E) (6) F ?id 表4.11 文法（4.22）的SLR分析表 LR分析器的工作过程 格局：（栈中符号序列，剩余输入符号串） 开始：（s0, a1 a2 ……an$) 中间： （s0x1s1x2s2…xmsm ,aiai+1…an$) x1x2…xmaiai+1…an 是一个右句型。 1. 若action[sm.ai]=si , 则把ai,si=action[sm ,ai]推进栈. 格局：（s0x1s1x2s2…xmsm aisi , ai+1…an$) 2. 若action[sm.ai]=r (A?xm-r+1xm-r+2…xm) ,则 格局：（s0x1s1x2s2…xm-rsm-r As , ai ai+1…an$) 其中，s=goto[sm-r ,A] 3.若action[sm.$]=accep,则分析结束。 4 .若action[sm,ai]=error,则转出错处理程序。 下面，显示id+id*id的LR分析过程： 栈 输入 动作 0 id+id*id$ s5 0id 5 +id*id$ r6 F?id 0F3