编译原理4语法分析new.ppt

S?→?S S→ ?L=R S→ ? R L→ ?*R L→ ? i R→ ?L R→L ? S?→ S ? S→ L ?=R R→ L? S→ R ? L→* ? R R→ ? L L→ ? *R L→ ? i S→ L=R ? S→L= ? R R→ ? L L→ ? *R L→ ? i L→*R ? L→ i ? I0 I1 I2 I3 I4 I5 I6 I9 I7 I8 S L R * i = R * R b i * L i L 一个事实：如果栈里的符号串为$δα，规约后变为$δΑ，当读到的输入符号是a，若文法中不存在以δΑa为前缀的规范句型，那么这种归约无效。 对上例针对句型i=i的SLR（1）分析过程为： S?? S ? L=R ? L=L ? L=i? i=i 状态栈 符号栈 输入串 0 $ i=i$ 05 $i =i$ 02 $L =i$ 03 $R =i$ 当状态2呈现于栈顶且面临的输入符号是=时,由于这个文法不含有以R=为前缀的规范句型,因此用R→L进行的归约是无效归约,也就是说并不是FOLLOW(R)的每个元素在含R的所有句型中都会出现在R的后面.解决这一问题的方法是采用LR(1)分析法. LR(1)分析法的思想是在分析过程中,当试图用某一规则A→α归约栈顶的符号串α时,不仅应该查看栈中符号串δα,还应向前扫视一个输入符号a,只有当δΑa的确构成文法某一规范句型的前缀时,才能用此规则进行归约。为此可以考虑在原来LR（0）项目集中增加更多的展望信息，这些信息有助于克服动作冲突和排除无效归约。也就是需要重新定义称之为LR（1）的项目。 一个LR（1）项目是一个二元组[A→α?β，a]，其中A→α?β是一个LR（0）项目，每个a是终结符且a?Follow(A) ，称为展望符或有哪些信誉好的足球投注网站符。当β≠ε时，有哪些信誉好的足球投注网站符是无意义的；当β=ε时，有哪些信誉好的足球投注网站符a明确指出当[A→α?，a]是栈顶状态的一个LR（1）项目时，仅在输入符号是a时才能用A→α归约，而不是对FOLLOW（A）中的所有符号都用A→α归约。 构造LR（1）项目集族的方法： （1）构造LR（1）项目集I的闭包函数 ①I的任何项目都属于CLOSURE（I） ②若项目[A→α?Bβ，a]，属于CLOSURE（I）， B→r是文法的一条规则，b?FIRST（ βa），则[B→?r，b]也属于CLOSURE（I） ③重复②直到CLOSURE（I）不在增大为止。 （2）构造转换函数 令I是一个LR（1）项目集，X是一个文法符号，函数 GO（ I，X ）= CLOSURE（J） J={[A→αX?β，a]| [A→α?Xβ，a]?I} （3）构造DFA同LR（0）分析法相同（注：构造初态是从基本项目[S?→?S，$]开始的） （4）构造LR（1）分析表的方法与构造LR（0）分析表的方法基本相同，仅对归约项目作如下修改： 若归约项目[A→α?，a]属于Ik，则对有哪些信誉好的足球投注网站符a置ACTION[k，a]= rj，（假定A→α 为文法第j条规则） S?→?S,$ S→ ?L=R, $ S→ ? R, $ L→ ?*R,=/ $ L→ ? i,=/ $ R→ ?L, $ I9 * L→*R ? , $ R→L ?, =/$ S?→ S ?,$ S→ L ?=R,$ R→ L?, $ S→ R ?, $ L→* ? R, =/ $ R→ ? L, =/ $ L→ ? *R ,=/ $ L→ ? i, =/ $ S→ L=R ?,$ S→L= ? R, $ R→ ? L, $ L→ ? *R, $ L→ ? i, $ L→*R ? , =/ $ L→ i ?, =/ $ I0 I1 I2 I3 I4 I5 I6 I7 I8 S L R * i = R * R R i * L i L→ i ?, $ i I12 L→* ? R, $ R→ ? L, $ L→ ? *R , $ L→ ? i, $ R→ L?, $ L I10 I11 I13 L 2.5.5 LALR(1)分析法 LALR（1）分析法是界于SLR（1）和LR（1）分析法之间的一种语法分析方法，这种分析法能解决SLR（1）分析