SLR1分析

【实验目的】

构造LR分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。

【实验内容】

对下列文法，用SLR（1）分析法对任意输入的符号串进行分析：

(1)S->E

(2)E->E+T

(3)E->T

(4)T->T*F

(5)T->F

(6)F->(E)

(7)F->i

【设计思想】

(1)总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。

(2)分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。

(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。

分析器的动作就是由栈顶状态和当前输入符号所决定。

u LR分析器由三个部分组成：

u 其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。

u ACTION[i，a]规定了栈顶状态为i时遇到输入符号a应执行。动作有四种可能：

(1)移进：

action[i，a]= Sj：状态j移入到状态栈，把a移入到文法符号栈，其中i,j表示状态号。

(2)归约：

action[i，a]=rk：当在栈顶形成句柄时，则归约为相应的非终结符A，即文法中有A- B的产生式，若B的长度为R(即|B|=R)，则从状态栈和文法符号栈中自顶向下去掉R个符号，即栈指针SP减去R，并把A移入文法符号栈内，j=GOTO[i,A]移进状态栈，其中i为修改指针后的栈顶状态。

(3)接受acc:

当归约到文法符号栈中只剩文法的开始符号S时，并且输入符号串已结束即当前输入符是'#'，则为分析成功。

(4)报错:

当遇到状态栈顶为某一状态下出现不该遇到的文法符号时，则报错，说明输入端不是该文法能接受的符号串。

【实验要求】

1、编程时注意编程风格：空行的使用、注释的使用、缩进的使用等。

2、如果遇到错误的表达式，应输出错误提示信息。

3、程序输入/输出实例：

输入一以#结束的符号串(包括+—*/（）i#)：在此位置输入符号串

输出过程如下：

步骤状态栈符号栈剩余输入串动作

1 0 # i+i*i# 移进

代码：

 
#include<stdio.h>
 
#include<stdlib.h>
 
int Action[12][6] ={105, 0, 0, 104, 0, 0, 0, 106, 0, 0, 0, -1, 0, 52, 107, 0, 52, 52, 0, 54, 54, 0, 54, 54, 105, 0, 0, 104, 0, 0, 0, 56, 56, 0, 56, 56, 105, 0, 0, 104, 0, 0, 105, 0, 0, 104, 0, 0, 0, 106, 0, 0, 111, 0, 0, 51, 107, 0, 51, 51, 0, 53, 53, 0, 53, 53, 0, 55, 55, 0, 55, 55 };
 
int Goto[12][3] ={1, 2, 3, 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 Grammar[20][10] = { '' };
 
char VT[10], VN[10];
 
char AVT[6] = { 'i', '+', '*', '(', ')', '#' };
 
char GVN[3] = { 'E', 'T', 'F' };
 
int vnNum, vtNum, stateNum = 12;
 
int VNum[10];
 
int grammarNum;
 
typedef struct{
 
char *base;
 
char *top;
 
}SymbolStack;
 
typedef struct{
 
int *base;
 
int *top;
 
}StateStack;
 
StateStack state;
 
SymbolStack symbol;
 
int ScanGrammar()
 
{
 
FILE *fp = fopen("D:SLR文法.txt","r");
 
FILE *tp;
 
char singleChar, nextChar;
 
int i = 0, j = 0, k, count;
 
while (!feof(fp))
 
{
 
fscanf(fp, "%c", &singleChar);
 
if (singleChar == '?')
 
{
 
Grammar[i][j] = '';
 
break;
 
}
 
if (singleChar == '
')
 
{
 
Grammar[i][j] = '';
 
i++;
 
j = 0;
 
continue;
 
}
 
if (singleChar == '_')
 
{
 
tp = fp;
 
fscanf(tp, "%c", &nextChar);
 
if (nextChar == '>')
 
{
 
fp = tp;
 
continue;
 
}
 
}
 
if (singleChar == '|')
 
{
 
Grammar[i + 1][0] = Grammar[i][0];
 
Grammar[i][j] = '';
 
i++;
 
j = 1;
 
continue;
 
}
 
Grammar[i][j] = singleChar;
 
if (singleChar >= 'A'&&singleChar <= 'Z'){
 
count = 0;
 
while (VN[count] != singleChar&&VN[count] != '')
 
{
 
count++;
 
}
 
if (VN[count] == '')
 
{
 
vnNum = count + 1;
 
if (singleChar == 'S')
 
{
 
j++;
 
continue;
 
}
 
VN[count] = singleChar;
 
vnNum = count + 1;
 
}
 
}
 
else
 
{
 
count = 0;
 
while (VT[count] != singleChar&&VT[count] != '')
 
{
 
count++;
 
}
 
if (VT[count] == '')
 
{
 
VT[count] = singleChar;
 
vtNum = count + 1;
 
}
 
}
 
j++;
 
}
 
printf("输入的文法：
");
 
for (k = 0; k <= i; k++)
 
{
 
j = 0;
 
while (Grammar[k][j] != '')
 
{
 
if (j == 1)
 
{
 
printf("_>");
 
}
 
printf("%c", Grammar[k][j]);
 
j++;
 
}
 
printf("
");
 
}
 
count = 0;
 
printf("VT:");
 
while (VT[count] != '')
 
{
 
printf("%3c", VT[count]);
 
count++;
 
}
 
VT[count] = '#';
 
vtNum = count + 1;
 
printf("%3c", VT[count]);
 
printf("
VN:");
 
count = 0;
 
while (VN[count] != '')
 
{
 
printf("%3c", VN[count]);
 
count++;
 
}
 
printf("
");
 
// printf("
%d %d
", vtNum, vnNum);
 
fclose(fp);
 
grammarNum = i + 1;
 
return i;
 
}
 
int vNumCount()
 
{
 
int i,j;
 
for (i = 0; i < grammarNum; i++)
 
{
 
j = 1;
 
while (Grammar[i][j] != '')
 
{
 
j++;
 
}
 
VNum[i]=j;
 
//printf("%3d", VNum[i]);
 
}
 
printf("
");
 
return 0;
 
}
 
void InitStack()
 
{
 
state.base = (int *)malloc(100 * sizeof(int));
 
if (!state.base)exit(1);
 
state.top = state.base;
 
*state.top = 0;
 
symbol.base = (char*)malloc(100 * sizeof(char));
 
if (!symbol.base)exit(1);
 
symbol.top = symbol.base;
 
*symbol.top = '#';
 
}
 
int Judge(int stateTop, char inputChar)
 
{
 
    int i,j;
 
for (i = 0; i < stateNum; i++){
 
if (stateTop == i)break;
 
}
 
for (j = 0; j < vtNum; j++){
 
if (inputChar == AVT[j])break;
 
}
 
    return Action[i][i];
 
}
 
int GetGoto(int stateTop, char inputChar){
 
int i, j;
 
for (i = 0; i < stateNum; i++){
 
if (stateTop == i) break;
 
}
 
for (j = 0; j < vnNum; j++)
 
{
 
if (inputChar == GVN[j]) break;
 
}
 
return Goto[i][j];
 
}
 
int print(int count, int i, char Input[], int action, int gt, int sign)
 
{
 
int *p = state.base, stateNum;
 
int j, jj;
 
char *q = symbol.base, symbolNum;
 
printf("%d	", count);
 
while (p != state.top + 1)
 
{
 
stateNum = *p;
 
printf("%d", stateNum);
 
p++;
 
}
 
printf("	");
 
while (q != symbol.top + 1)
 
{
 
symbolNum = *q;
 
printf("%c", symbolNum);
 
q++;
 
}
 
printf("	");
 
j = i;
 
jj = 0;
 
while (jj < j)
 
{
 
printf(" ");
 
jj++;
 
}
 
while (Input[j] != '')
 
{
 
printf("%c", Input[j]);
 
j++;
 
}
 
printf("	");
 
if (sign == 1)
 
{
 
printf("	S%d	%d
", action, gt);
 
}
 
if (sign == 2)
 
{
 
printf("	r%d	%d
", action, gt);
 
}
 
if (sign == 3)
 
{
 
printf("tacc	%d
", gt);
 
}
 
if (sign == 0) printf("	0	0
");
 
return 0;
 
}
 
int Pop(int action)
 
{
 
int *p, stateNumn, ssValue, i;
 
state.top--;
 
p = state.top;
 
stateNum = *p;
 
i = VNum[action] - 1;
 
while (i != 0)
 
{
 
symbol.top--;
 
i--;
 
}
 
symbol.top++;
 
*symbol.top = Grammar[action][0];
 
ssValue=GetGoto(stateNum,Grammar[action][0]);
 
if (ssValue == 0)return ssValue;
 
state.top++;
 
*state.top = ssValue;
 
return ssValue;
 
}
 
int Reduction()
 
{
 
char Input[20];
 
int i = 0,count = 1;
 
int ssValue, action;
 
int stateTop, gt;
 
int sign = -1; // 彩进1, 规约2, 接受3
 
scanf("%s", &Input);
 
while (Input[i] != '')
 
{
 
if (Input[i] >= 'A'&&Input[i] <= 'Z')
 
{
 
printf("输入的不是有效的表达式!");
 
return 0;
 
}
 
i++;
 
}
 
i = 0;
 
printf("步骤	状态栈	符号栈	输入串		ACTION	GOTO
");
 
while (Input[i] != '')
 
{
 
if (count == 1)
 
{
 
print(count, i, Input, 0, 0, 0);
 
count++;
 
}
 
stateTop = *state.top;
 
ssValue = Judge(stateTop, Input[i]);
 
if (ssValue == 0)
 
{
 
state.top--;
 
if (*symbol.top == '#')
 
{
 
printf("规约出错！");
 
return 0;
 
}
 
continue;
 
}
 
if (ssValue == -1)
 
{
 
sign = 3;
 
print(count, i, Input, ssValue, 0, sign);
 
count++;
 
return 1;
 
}
 
if (ssValue >= 100)
 
{
 
sign = 1;
 
action = ssValue - 100;
 
state.top++;
 
*state.top = action;
 
symbol.top++;
 
*symbol.top = Input[i];
 
i++;
 
print(count, i, Input, action, 0, sign);
 
count++;
 
}
 
if (ssValue >= 50 && ssValue < 100)
 
{
 
sign = 2;
 
action = ssValue - 50;
 
gt = Pop(action);
 
print(count, i, Input, action, gt, sign);
 
count++;
 
}
 
}
 
return 0;
 
}
 
int main()
 
{
 
ScanGrammar();
 
vNumCount();
 
InitStack();
 
Reduction();
 
return 0;
 
}

截图：