LR分析器工作过程算法描述:一个LR分析器的工作过程可看成是栈里的状态序列,已规约串和输入串所构成的三元式的变化过程。
分析开始时的初始三元式为(s0,#,a1a2……an#)其中,s0为分析器的初态;
#为句子的左括号;
a1a2……an为输入串;
其后的#为结束符(句子右括号)。
分析过程每步的结果可表示为(s0s1……sm,#X1X2……Xmai,ai+1……an#)分析器的下一步动作是由栈顶状态sm和现行输入符号ai所唯一决定的。
即,执行ACTION(sm,ai)所规定的动作。
经执行每种可能的动作之后,三元式的变化情形是:(1)若ACTION(sm,ai)为移进,且s=GOTO(sm,ai),则三元式变成:(s0s1……sms,#X1X2……Xmai,ai+1……an#)(2)若ACTION(sm,ai)={A→β},则按照产生式A→β进行规约。
此时三元式变为(s0s1……sms,#X1X2……XmA,aiai+1……an#)此处s=GOTO(Sm-r,A),r为β的长度,β=Xm-r+1……Xm。
(3)若ACTION(sm,ai)为“接受”,则三元式不再变化,变化过程终止,宣布分析成功。
(4)若ACTION(sm,ai)为“报错”,则三元式的变化过程终止,报告错误。
一个LR分析器的工作过程就是一步一步的变换三元式,直至执行“接受”或“报错”为止。
1