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分析法分析的文法可以称为LR分析法。LR文法（ Knuth ，1963）是最大的、可以构造出相应移入- 归约语法分析器的文法类。

LR(k)分析，需要向前查看k个输入符号的LR分析，k=0 和 k=1 这两种情况具有实践意义，当省略(k)时，表示k=1。而在LR(k)这样的名称中，k代表的是分析时所需前瞻符号（lookahead symbol）的数量，也就是除了当前处理到的输入符号之外，还得再向右引用几个符号之意；省略 （k）时即视为LR(1)，而非LR(0)。

作为对比这里列出LL(1)文法的含义：

问：自底向上分析的关键问题是什么？

答：如何正确地识别句柄，句柄是逐步形成的，用“状态”表示句柄识别的进展程度。例如在 自底向上分析概述 中所提及到句柄识别错误的例子，通过状态跟下一个输入符号就可以判断出应该做出哪一个动作，而状态相当于一种记忆功能记录当前句柄识别到什么程度。

与移入分析器不同的是LR分析器多了一个与符号栈平行的状态栈。

之后的分析过程与上图类似，直至到如下状态，分析成功。可见分析时进行什么动作是由栈状态栈栈顶的状态和下一个输入符号决定。

输入：串w和LR语法分析表，该表描述了文法G的ACTION函数和GOTO函数。

输出：如果w在L(G)中，则输出w的自底向上语法分析过程中的归约步骤；否则给出一个错误指示。

方法：初始时，语法分析器栈中的内容为初始状态s0 ，输入缓冲区中的内容为w$。然后，语法分析器执行下面的程序：

先了解LR(0)项目和增广文法这两个概念

右部某位置标有圆点的产生式称为相应文法的一个LR(0)项目（简称为项目）：A → α1·α2

文法开始符号S表示的是语言中的最大成分。如下图当b出现时可以将它移入到分析栈中。b移进栈后我们期待归约出B。当归约出B时我们还期待再归约一个B。

如果G是一个以S为开始符号的文法，则G的增广文法G'就是在G中加上新开始符号S'和产生式S'→S而得到的文法

引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态。

项目可以分为以下几类：

上图中S'对应的第一个项目称为初始项目，而S'对应的最后一个项目称之为接收项目在此状态下文法的开始符号已经被归约出来，因此可以接收了故称为接收项目。红色方框中的项目则被称为归约项目。

项目集闭包(Closure of Item Sets)

可以把等价的项目组成一个项目集(I)，称为项目集闭包，每个项目集闭包对应着自动机的一个状态。

先了解CLOSURE和GOTO这两个函数

项目集I的闭包的数学定义：

返回项目集I对应于文法符号X的后继项目集闭包

规范LR(0)项集族(Canonical LR(0) Collection)

说明： 该自动机的初始状态就是文法的初始项目的项目集闭包，其终止状态集合只有一个状态就是文法的接收项目的项目集闭包。

如果LR(0)分析表中没有语法分析动作冲突，那么给定的文法就称为LR(0)。不是所有CFG都能用LR(0)方法进行分析，也就是说，CFG不总是LR(0)文法。

为了解决移进/归约冲突和归约/归约冲突需要使用到 SLR分析法 和 LR(1)分析法 。

问: 为什么没有移进/移进冲突？

答: 首先只有在移进状态和待约状态下的项目才会有使用到移进 *** 作。在0状态时所有项目都是移进状态根据LL文法显然不会产生移进/移进 *** 作，因为每个产生式左部的SELECT集是没有交集的。而在其他具有待约状态项目的状态中，所有集合都是等价的。假若在某状态下输入终结符y时发生移进/移进冲突，即存在两个这样的项目A0→α0·yβ0，A1→α1·yβ1，但显然这两个项目是不等价的显然与同一状态下所有项目等价相矛盾，因此这种移进/移进冲突是不存在的。假若在某状态下输入非终结符X时发生移进/移进冲突，即存在两个这样的项目A0→α0·Xβ0，A1→α1·Xβ1，而A0与A1在同一状态下是等价的则两项目要么是A0→α0·Xβ0与X→.Xβ1(原项目A1变为X，α1变为ε)要么是A1→α1·Xβ1与X→.Xβ0(原项目A0变为X，α0变为ε)。显然X→Xβ0|Xβ1（左递归）是不符合LL文法的因此这种情况也是不可能出现。

综上移进/移进冲突在LR分析下是不存在的。

这个是精简的语法分析程序，如果符合的话，hi我

给你实验报告

#include <stdio.h>

#include<dos.h>

#include<stdlib.h>

#include<string.h>

char a[50] ,b[50]

char ch

int n1,i1=0,n=5

int E()int T()int E1()int T1()int F()

void main() /*递归分析*/

{

int f,j=0

printf("请输入字符串(长度<50,以#号结束）\n")

do{

scanf("%c",&ch)

a[j]=ch

j++

}while(ch!='#')

n1=j

ch=b[0]=a[0]

f=E()

if (f==0) return

if (ch=='#') printf("accept\n")

else printf("error\n")

}

int E() // E→TE'

{ int f,t

f=T()

if (f==0) return(0)

t=E1()

if (t==0) return(0)

else return(1)

}

int T() // T→FT'

{ int f,t

f=F()

if (f==0) return(0)

t=T1()

if (t==0) return(0)

else return(1)

}

int E1()/*E’*/ // E'→+TE'

{ int f

if(ch=='+') {

b[i1]=ch

ch=a[++i1]

f=T()

if (f==0) return(0)

E1()

return(1)

}

return(1)

}

int T1()/*T’*/ // T'→*FT'

{

int f,t

if(ch=='*') {

b[i1]=ch

ch=a[++i1]

f=F()

if (f==0) return(0)

t=T1()

if (t==0) return(0)

else return(1)}

a[i1]=ch

return(1)

}

int F() // F→(E)

{ int f

if(ch=='(') {

b[i1]=ch

ch=a[++i1]

f=E()

if (f==0) return(0)

if(ch==')') {

b[i1]=ch

ch=a[++i1]

}

else {

printf("error\n")

return(0)

}

}

else if(ch=='i') {

b[i1]=ch

ch=a[++i1]

}

else {printf("error\n")return(0)}

return(1)

}

---