LR分析法

LR文法是最大的、可以构造出相应的移入-归约语法分析器的文法类，其中L表示的是对输入进行从左到右的扫描，而R代表的就是反向构造出一个最右的推导序列

LR分析法就是会给出一种能根据当前分析栈中的符号串和向右顺序查看输入串中的k(k>=0)个符号就可以唯一地确定分析器的动作是移入还是归约和用哪个产生式进行归约

LR分析法的归约过程是规范推导的逆过程，所以LR分析过程是一种规范归约过程，在自底向上的分析过程中把最左归约称为规范归约，把最右推导称为规范推导

对于绝大多数的用无二义性上下文无关文法描述的语言都可以用相应的LR分析器进行识别，而且这种方法还具有分析速度快，能准确、即时地指出出错位置的特点，它的缺点在于对于一个实用语言文法的分析器的构造工作量相当大，k越大，构造就越复杂，实现比较困难

所以目前许多实用的编译程序，当采用LR分析器的时候都是借助于美国Bell实验室推出的yacc来实现的。yacc能接受一个用BNF描述的满足LR类中LALR(1)的上下文无关文法并对其自动构造出LALR(1)分析器

LR分析器的工作过程示意图如下所示

一个LR分析器由3部分组成

• 1、总控程序，也可以称为驱动程序。对所有的LR分析器来说，总控程序都是相同的
• 2、分析表或分析函数。不同的文法分析表会不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可以分为动作(ACTION)表和状态转换(GOTO)表两个部分，它们都可用二维数组表示
• 3、分析栈，包括文法符号栈和相应的状态栈，它们都是先进后出栈分析器不需向前查看输入符号

分析器的动作由当前文法符号栈和当前输入符号来决定(LR(0))

下面再看下其的分析的流程

其中Xm代表的就是符号，而Sm代表的是状态，其实就是如果我们需要去对应Action表来说的话，就是如果Sj =Action[Si,a]成立，就把Sj移入到状态栈当中，把a移入到文法符号栈，其中i，j代表的是状态号

下面介绍的就是当进行归约文法符号栈和状态栈怎么变化，以及归约完成之后的非终结符遇到栈顶的状态该怎么变化的流程