LR剖析器是一种由下而上（bottom-up）的上下文无关语法剖析器。LR意指由左（Left）至右处理输入字符串，并以最右边优先衍生（Right derivation）的推导顺序（相对于LL剖析器）建构语法树。能以此方式剖析的语法称为LR语法。而在LR(k)这样的名称中，k代表的是剖析时所需前瞻符号（lookahead symbol）的数量，也就是除了目前处理到的输入符号之外，还得再向右参照几个符号之意；省略 （k）时即视为LR(1)，而非LR(0)。
由于LR剖析器尝试由剖析树的叶节点开始，向上一层层透过文法规则的化简，最后推导回到树的根部（起始符号），所以它是一种由下而上的剖析方法。许多程序语言使用LR(1)描述文法，因此许多编译器都使用LR剖析器分析原始码的文法结构。LR剖析的优点如下：
- 众多的程序语言都可以用某种LR剖析器（或其变形）分析文法。（C++是个著名的例外）
- LR剖析器可以很有效率的建置。
- 对所有「由左而右」扫描原始码的剖析器而言，LR剖析器可以在最短的时间内侦测到文法错误（这是指文法无法描述的字符串）。
然而LR剖析器很难以人工的方式设计，一般使用「剖析产生器（parser generator）」或「编译器的编译器（compiler-compiler，产生编译器的工具）」来建构它。LR剖析器可根据剖析表（parsing table）的建构方式，分类为「简单LR剖析器（SLR, Simple LR parser）」、「前瞻LR剖析器（LALR, Look-ahead LR parser）」以及「正统LR剖析器 (Canonical LR parser)」。这些解析器都可以处理大量的文法规则，其中LALR剖析器较SLR剖析器强大，而正统LR剖析器又比LALR剖析器能处理更多的文法。著名的Yacc即是用来产生LALR剖析器的工具。
LR（0）：在分析的每一步，只需根据当前栈顶状态而不必向前查看输入符号就能确定应采取的分析动作。所能分析的LR（0）文法要求文法的每一个LR（0）项目集中都不含冲突项目。
示例文法：
|
0 S’ -> S 1 S -> A 2 S -> B 3 A -> aAb 4 A -> c 5 B -> aBb 6 B -> d |
SLR（1）：通过采用对含有冲突的项目集向前查看一个输入符号的办法来解决冲突的方法。
示例文法：
|
0 E -> E 1 E -> E + T 2 E -> T 3 T -> T*F 4 T -> F 5 F -> (E) 6 F -> id |
一、LR分析器由三个部分组成：
(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。
(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。
(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。
二、分析算法及思路：
①、数据结构： 二维数组action[][]存放ACTION表中的元素，二维数组goto[][]存放GOTO表中元素。字符数组vt[]存放终结符，字符数组vn[]存放非终结符。字符数组LR[]存放产生式。数组a[]实现状态栈，数组b[]实现符号栈。
②、算法：
初始化，初始状态S0在分析栈栈顶，输入串W#的第一个符号读入a中。
while( ACTION[S,a] != acc)
{ if( ACTION[S,a] == Si)
{状态i和输入符号a进栈；将下一个输入符号读入a中；}
else if (ACTION[S,a] == rj)
{ 用第j条规则A –> a 归约；将|a|个状态和|a|个输入符号退栈；当前栈顶状态为S’，将A和GOTO[S’，A] = S’’进栈；
Else if(ACTION[S,a]==ERROR) error();
}
三、程序源代码（SLR（1））
对应文法：
|
0 E -> E 1 E -> E + T 2 E -> T 3 T -> T*F 4 T -> F 5 F -> (E) 6 F -> id |
分析表：
|
状态 |
ACTION |
GOTO |
||||||||
|
id |
+ |
* |
( |
) |
# |
E |
T |
F |
||
|
0 |
S5 |
|
|
S4 |
|
|
1 |
2 |
3 |
|
|
1 |
|
S6 |
|
|
|
acc |
|
|
|
|
|
2 |
|
r2 |
S7 |
|
r2 |
r2 |
|
|
|
|
|
3 |
|
r4 |
r4 |
|
r4 |
r4 |
|
|
|
|
|
4 |
S5 |
|
|
S4 |
|
|
8 |
2 |
3 |
|
|
5 |
|
r6 |
r6 |
|
r6 |
r6 |
|
|
|
|
|
6 |
S5 |
|
|
S4 |
|
|
|
9 |
3 |
|
|
7 |
S5 |
|
|
S4 |
|
|
|
|
10 |
|
|
8 |
|
S6 |
|
|
S11 |
|
|
|
|
|
|
9 |
|
r1 |
S7 |
|
r1 |
r1 |
|
|
|
|
|
10 |
|
r3 |
r3 |
|
r3 |
r3 |
|
|
|
|
|
11 |
|
r5 |
r5 |
|
r5 |
r5 |
|
|
|
|
View Code
#include<stdio.h> #include<string.h> char *action[12][6]={"S5#",NULL,NULL,"S4#",NULL,NULL, /*ACTION表*/ NULL,"S6#",NULL,NULL,NULL,"acc", NULL,"r2#","S7#", NULL,"r2#","r2#", NULL,"r4#","r4#", NULL,"r4#","r4#", "S5#",NULL,NULL, "S4#",NULL,NULL, NULL,"r6#","r6#", NULL,"r6#","r6#", "S5#",NULL,NULL, "S4#",NULL,NULL, "S5#",NULL,NULL, "S4#",NULL,NULL, NULL,"S6#",NULL, NULL,"S11#",NULL, NULL,"r1#","S7#", NULL,"r1#","r1#", NULL,"r3#","r3#", NULL,"r3#","r3#", NULL,"r5#","r5#", NULL,"r5#","r5#"}; int goto1[12][3]={1,2,3, /*QOTO表*/ 0,0,0, 0,0,0, 0,0,0, 8,2,3, 0,0,0, 0,9,3, 0,0,10, 0,0,0, 0,0,0, 0,0,0, 0,0,0}; char vt[6]={'i','+','*','(',')','#'}; /*存放终结符*/ char vn[3]={'E','T','F'}; /*存放非终结符*/ char *LR[7]={"M->E#","E->E+T#","E->T#","T->T*F#","T->F#","F->(E)#","F->i#"};/*存放产生式*/ int a[20];//数组a实现状态栈 char b[20],c[20],c1;//数组b实现符号栈，数组c存放输入的字符串 int top1,top2,top3,top,m,n; void main() { int g,h,i,j,k,l,p,y,z,count; char x,copy[20],copy1[20]; top1=0;top2=0;top3=0;top=0; a[0]=0;y=a[0];b[0]='#'; count=0;z=0; //输入要识别的字符串 printf("请输入表达式/n"); do{ scanf("%c",&c1); c[top3]=c1; //字符数组c[10]存放输入的字符串 top3=top3+1;//最后top3=5 }while(c1!='#'); //输出分析结果 printf("步骤/t状态栈/t/t符号栈/t/t输入串/t/tACTION/tGOTO/n"); do{ y=z;m=0;n=0; /*y,z指向状态栈栈顶*/ g=top;j=0;k=0; x=c[top]; //将输入符号赋给x count++; printf("%d/t",count);//输出步骤序号 while(m<=top1) { /*输出状态栈*/ printf("%d",a[m]); m=m+1; } printf("/t/t"); while(n<=top2) { /*输出符号栈*/ printf("%c",b[n]); n=n+1; } printf("/t/t"); while(g<=top3) { /*输出输入串*/ printf("%c",c[g]); g=g+1; } printf("/t/t"); while(x!=vt[j]&&j<=5) //获取当前x对应j的值 j++; if(j==5&&x!=vt[j])//如果x不是终结符则报错 { printf("error/n"); return; } if(action[y][j]==NULL){//？？？？ printf("error/n"); return; } else strcpy(copy,action[y][j]);// //////////////////////////////////////////////////////// if(copy[0]=='S') { /*处理移进*/ z=copy[1]-'0';//因为状态从0开始 top1=top1+1; top2=top2+1; a[top1]=z;//数组a实现状态栈 b[top2]=x;//数组b实现符号栈 top=top+1;//输入符号串数组c的顶 i=0; while(copy[i]!='#')//例 "S3#" 输出ACTION { printf("%c",copy[i]); i++; } printf("/n"); } //////////////////////////////////////////////////////// if(copy[0]=='r') { /*处理归约*/ i=0; while(copy[i]!='#')//例 "S3#" 输出ACTION { printf("%c",copy[i]); i++; } h=copy[1]-'0';//因为状态从0开始 strcpy(copy1,LR[h]); while(copy1[0]!=vn[k]) //获取当前k值 k++; l=strlen(LR[h])-4;/// top1=top1-l+1; top2=top2-l+1; y=a[top1-1]; p=goto1[y][k]; a[top1]=p; b[top2]=copy1[0]; z=p; printf("/t"); printf("%d/n",p); } }while(action[y][j]!="acc"); printf("acc/n"); }
详细参考:http://zh.wikipedia.org/wiki/LR%E5%89%96%E6%9E%90%E5%99%A8