LR分析法的LR分析器的逻辑结构及工作原理

在逻辑上，一个LR分析器有一个输入符号串，一个下推分析栈，以及一个总控程序和分析表。LR分析器在总控程序的控制下自左至右扫视输入串的各个符号，并根据当前分析栈中所存放之文法符号的状况及正注视的输入符号，按分析表的指示完成相应的分析动作。在分析的每一时刻，分析栈中记录了迄今为止所移进或归约出的全部文法符号，即记录了从分析开始到目前为止的整个历程。因此，为了方便，对于分析过程的每一步，我们可将分析栈中所存放的全部文法符号用一种“状态”来刻画，且将此状态名置于分析栈的栈顶所示。分析刚开始时，栈中仅有一个句子的左界符#，此时分析器处于初始状态S0，它不仅刻画了分析栈中当前仅有一个符号#这一事实，而且还预示着即将扫视的输入符号应当是可作为句子首符号的那些符号。类似地，状态S1刻画了分析栈中已有符号#X1的情况，…，栈顶状态Sm则刻画了分析栈中已存在符号串#X1X2…Xm的情况，等等。此外，根据分析栈的栈顶状态，还可对当前可能遇到的输入符号进行预测。例如，对于前面所述的文法G[E]，设分析栈中已移进和归约出的符号串为#E+T时的栈顶状态为Si，则Si不仅表征了迄今扫描过的输入串部分已被归约成#E+T，而且由Si还可以作这样的预测： 若输入符号串无语法错误，则当前可遇到的输入符号仅能是+,*,)或#。显然，在栈顶状态为上述Si的情况下，若当前所扫视到的符号为*，则应将*移进栈中；当所扫视到的符号为+,)或#时，则应将E+T归约为E；若所扫视到的符号不是上述四种符号之一，则应按语法错误处理。由此可见，知道了栈顶状态Sm和正扫视到的输入符号ai，就知道了当前所需的全部有用信息，从而也就可惟一地确定当前LR分析器所应采取的动作。所以，在具体实现时，并不需要将文法符号记入分析栈中。

LR分析器的核心是一张分析表，它由两个子表组成： 其一是分析动作表；另一个为状态转移表。其中： S1,S2,…,Sn为分析器的各个状态；a1,a2,…,al为文法的全部终结符号和句子界符；X1,X2,…,Xp为文法字汇表中的全部文法符号。分析动作表中的每一个元素ACTION[Sm,ai]指明，当栈顶状态为Sm且正扫视的输入符号为ai时要完成的分析动作。状态转移表中的元素GOTO[Sm,Xi]则指明，当向分析栈中移进一个输入符号或按某一产生式进行归约之后所要转移到的下一状态。

LR分析器的工作在总控程序的控制下进行，其过程如下 (为书写方便，我们将分析栈按顺时针旋转90度)：

1?分析开始时，首先将初始状态S0及句子左界符#推入分析栈。

2?设在分析的某一步，分析栈和余留输入符号串处于如下格局：

S0S1S2…S↓m[]#X1X2…Xma↓iai+1…an#

则用当前栈顶的状态Sm及正扫视的输入符号ai组成符号对(Sm,ai)去查分析动作表，并根据分析表元素ACTION[Sm,ai]的指示采取相应的分析动作，每一分析表元素所指示的仅能是下列四种动作之一：

(1) 若ACTION[Sm,ai]=“移进”，则表明句柄尚未在栈顶部形成，正期待继续移进输入符号以形成句柄，故将当前的输入符号ai推入栈中，即

S0 S1 S2 … S↓m[]# X1 X2 … Xm aia↓i+1ai+2…an#

然后，以符号对(Sm,ai)查状态转移表，设相应的表元素GOTO[Sm,ai]=Sm+1，再将此新的状态Sm+1 (即要转移到的下一状态)推入栈中，则有如下格局：

S0 S1 S2 … Sm S↓m+1[]# X1 X2 … Xm aia↓i+1ai+2…an#

(2) 若ACTION[Sm,ai]=rj，其中rj意指按文法的第j个产生式A→Xm-r+1Xm-r+2…Xm进行归约。这表明栈顶部的符号串Xm-r+1Xm-r+2…Xm已是当前句型 (对非终结符号A)的句柄。按第j个产生式进行归约，也就是将分析栈从顶向下的r个符号 (因为该产生式右部符号串的长度为r)退出，然后再将文法符号A推入栈中，此时分析栈的格局为

S0 S1 S2 … S↓m-r[]# X1 X2 … Xm-r Aa↓iai+1…an#

然后再以(Sm-r,A)查状态转移表，设GOTO[Sm-r,A]=SK，将此新状态推入栈中，则有如下的格局：

S0S1S2…Sm-rS↓K[]#X1X2…Xm-rAa↓iai+1…an#

必须注意的是，当完成归约动作之后，输入串指示器不向前推进，它仍然指向动作前的位置。

(3) 若ACTION[Sm,ai]=“接受”则表明当前的输入串已被成功地分析完毕，应中止分析器的工作。

(4) 若ACTION[Sm,ai]=ERROR，则表明当前的输入串中有语法错误，此时应调用出错处理程序进行处理。

3?重复步骤2的工作，直到在分析的某一步，栈顶出现“接受状态”为止。此时，分析栈的最终格局应为

S0S↓z[]#Z#↓

其中，Z为文法的开始符号，Sz则为使ACTION[Sz,#]=“接受”的惟一状态 (即接受状态)。

上述所列的三个步骤，实质上是对LR分析器总控程序的一个非形式化的描述，它对任何不同的LR分析表都是适用的。顺便提及，LR分析器的输出是在用某个产生式进行归约之后，通过执行相应的语义子程序来实现的，我们将在第5章再讨论这一问题。

LR分析中的同心集指的是一种自下而上进行规范归约的语法分析法，l指从左到右扫描输入符号串，r是指构造最右推导的逆过程。

lr（1）中的1是每次搜索符号需要向前参考一步，对SLR（1）规则稍作分析即可发现，它对某些文法失效的原因，在于当所给的文法出现冲突的分析动作时，SLR（1）规则仅孤立地考察输入符号是否属于与归约项目A→α·相关联的集合FOLLOW（A），以确定是否应按产生式A→α进行归约。

结构及原理

在逻辑上，一个LR分析器有一个输入符号串，一个下推分析栈，以及一个总控程序和分析表。LR分析器在总控程序的控制下自左至右扫视输入串的各个符号，并根据当前分析栈中所存放之文法符号的状况及正注视的输入符号，按分析表的指示完成相应的分析动作。在分析的每一时刻，分析栈中记录了迄今为止所移进或归约出的全部文法符号，即记录了从分析开始到目前为止的整个历程。