LR分析法 1.LR(K)分析法 自底向上的LR分析法是指从左向右扫描 输入串,每次分析由分析栈中符号及向前 搜索K个输入符号以确定作为产生式右部 的短语(句柄)是否已在分析栈的栈顶形成, 从而决定应采取的动作。这种分析方法称 为LR(K)分析法。一般只考虑K的情况
二. LR分析法 1. LR(K) 分析法 自底向上的LR分析法是指从左向右扫描 输入串,每次分析由分析栈中符号及向前 搜索K个输入符号,以确定作为产生式右部 的短语(句柄)是否已在分析栈的栈顶形成, 从而决定应采取的动作。这种分析方法称 为LR(K)分析法。一般只考虑K1的情况
其组成为分析栈控制程序分析表输入串 输入串a1 a1 分析栈 驱动程序 输出 action goto 分析表
其组成为:分析栈,控制程序,分析表,输入串 输入串 分析栈 驱动程序 输出 action goto 分析表 s0 . . . sm-1 sm a1 ... ai ... $
2.分析栈 存放状态初始时置初始状态s栈里的 每一状态概括了从分析开始到某一时刻 已进行的分析工作
2. 分析栈 存放状态;初始时,置初始状态s0 ;栈里的 每一状态概括了从分析开始到某一时刻 已进行的分析工作
3.分析表 由 action[s,a]和 gotos, x]两个子表组成。 (1) action s, a定义了在状态s下,当前输入符号为 a时应采取的分析动作:移进归约接受,出错。 (2)goto表是一个状态及非终结符的二维矩阵, gotolS, X定义了在状态s下,面对文法符号x时的 状态转换
3. 分析表 由action[s,a]和goto[s,x]两个子表组成。 (1)action[s,a]定义了在状态s下, 当前输入符号为 a时应采取的分析动作: 移进, 归约,接受, 出错。 (2)goto表是一个状态及非终结符的二维矩阵, goto[s,x]定义了在状态s下, 面对文法符号x时的 状态转换
例G(E) 1)E→E+T (2)E→T (3)T→TF (4)T→>F (5)F→(E) (6F)i 的LR分析表如后
例 G0 (E) (1)E→E+T (2)E→T (3)T→T*F (4)T→F (5)F→(E) (6)F→i 的LR分析表如后
LR分析表 状态 action goto SETF y4 2 0123456 s6 acc r2 [4 746 S4 246 r4 2 r6 r 6r6 y4 3 s5 10 73 Sr r r 5 5 135 r r5
LR分析表 状态0123456789 10 11 action goto i + * ( ) $ E T F s5 s4 1 2 3 s6 acc r2 s7 r2 r2 r4 r4 r4 r4 s5 s4 8 2 3 r6 r6 r6 r6 s5 s4 9 3 s5 s4 10 s6 s11 r1 s7 r1 r1 r3 r3 r3 r3 r5 r5 r5 r5
4控制程序的工作 据 action s,a进行 (1)若 action[s, a=s,则将状态推入栈顶输入指针指向 下一输入符号; (2)右 action s2a,如 按第j个产生式A→>β归约,设阝t 应在分析栈栈顶上托个状态出栈呈现栈顶的状态设 为s,则根据si及归约后的非终结符A,查goto表, goto[si,A,则将状态j下推入分析栈栈顶。 (3)若 action[s, a=acc,则结束分析输入串被接受。 (4)若 action[s, a或 goto[s, A不是上述情况,转出错处理 程序
4. 控制程序的工作 据action[s,a]进行: (1)若action[s,a]=sj, 则将状态j推入栈顶, 输入指针指向 下一输入符号; (2)若action[s,a]=rj, 则按第j个产生式A→归约, 设||=t, 应在分析栈栈顶上托t个状态出栈, 呈现栈顶的状态设 为si, 则根据si及归约后的非终结符A, 查goto表, goto[si,A]=j, 则将状态j下推入分析栈栈顶。 (3)若action[s,a]=acc, 则结束分析,输入串被接受。 (4)若action[s,a]或goto[s,A]不是上述情况, 转出错处理 程序
例:(+i*)的分析过程 分析栈符号栈输入串动作之 0 (1+i*) 8移进 20,4 $ 计+)s移进 3045 $,(,i +*)$归约 4|043 $,(F +i)$归约 50.4,2 $,(,T +i*1)s归约 60.4.8 $,(,E +i*s移进 7|04:.6 $,(,E, i*$移进 80,4,865 $,(,E,+ )i归约 90.4863 $(,E,+F *i归约
1 2 3 4 5 6 7 8 9 分析栈 符号栈 输入串 动作 $ (i+i*i)$ 移进 $,(,i +i*i)$ 移进 0 0,4 0,4,5 $,( i+i*i)$ 归约 0,4,3 $,(,F +i*i)$ 归约 0,4,2 $,(,T +i*i)$ 归约 0,4,8 $,(,E +i*i)$ 移进 0,4,8,6 $,(,E,+ i*i)$ 移进 0,4,8,6,5 $,(,E,+,i *i)$ 归约 0,4,8,6,3 $,(,E,+,F *i)$ 归约 例: (i+i*i)的分析过程
L(续表) 1004869°s(E+T♂s移进 110.4.697(E,+,T i)$移进 204869,75$(E,+工* )$归约 130486.710$(E+,工*F 归约 140.4.8.69 $,(E,+,T )$归约 150.4.8 $,(,E )$移进 160.4811 $,(,E $归约 170,3 $,F 归约 1802T $归约 $,E $接受
10 11 12 13 14 15 16 17 18 19 0,4,8,6,9 $,(,E,+,T *i)$ 移进 0,4,8,6,9,7 $,(,E,+,T,* i)$ 移进 0,4,8,6,9,7,5 $,(,E,+,T,*,i )$ 归约 0,4,8,6,9,7,10 $,(,E,+,T,*,F )$ 归约 0,4,8,6,9 $,(,E,+,T )$ 归约 0,4,8 $,(,E )$ 移进 0,4,8,11 $,(,E,) $ 归约 0,3 $,F $ 归约 0,2 $,T $ 归约 0,1 $,E $ 接受 (续表)
例:(+i*)的分析过程 分析一符号栈>输入串。动作 0 i+S移进 20,4 计+)s移进 3045 +1归约 4|043 +i)$归约 50.4,2 +i*1)s归约 60.4.8 +i*s移进 7|04:.6 i*$移进 80,4,865 )i归约 90.4863 *i归约
1 2 3 4 5 6 7 8 9 分析栈 符号栈 输入串 动作 (i+i*i)$ 移进 +i*i)$ 移进 0 0,4 0,4,5 i+i*i)$ 归约 0,4,3 +i*i)$ 归约 0,4,2 +i*i)$ 归约 0,4,8 +i*i)$ 移进 0,4,8,6 i*i)$ 移进 0,4,8,6,5 *i)$ 归约 0,4,8,6,3 *i)$ 归约 例: (i+i*i)的分析过程