SLR分析器设计实验报告.doc

SLR分析器设计实验报告

装

订

线

编译原理实验报告

题目： SLR(1)分析器的设计

学 院 计算机科学及技术
专 业 xxxxxxxxxxxxxxxxx
学 号 xxxxxxxxxxxxx
姓 名 宁剑
指导教师 xx

20xx年xx月xx日
SLR(1)分析器的设计

一、实验目的 
     构造LR(1)分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。 
二、实验原理 
       对下列文法，用LR（1）分析法对任意输入的符号串进行分析：  
S->E
E->E+T
E->T
T->T*F
T->F
F->(E)
F->i
三、实验步骤
1.总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。 
2.分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表将不同，分析表又可以分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。 
3.分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。 
分析器的动作就是由栈顶状态和当前输入符号所决定。
LR分析器由三个部分组成：其中:SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。 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#

四、实验环境 
计算机 DEV C++软件
五、实验程序  
#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]={'\0'};
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("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]='\0';
break;
}
if(singleChar=='\n')
{
Grammar[i][j]='\0';
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]='\0';
i++;
j=1;
continue;
}
Grammar[i][j]=singleChar;
if(singleChar>='A'&&singleChar<='Z')
{
count=0;
while(VN[count]!=singleChar&&VN[count]!='\0')
{
count++;
}
if(VN[count]=='\0')
{
vnNum=count+1;
if(singleChar=='S')
{
j++;
continue;
}
VN[count]=singleChar;
vnNum=count+1;
}
}else{
count=0;
while(VT[count]!=singleChar&&VT[count]!='\0')
{
count++;
}
if(VT[count]=='\0')
{
VT[count]=singleChar;
vtNum=count+1;
}
}
j++;
}
printf("输入的文法：\n");
for(k=0;k<=i;k++){
j=0;
while(Grammar[k][j]!='\0')
{
if(j==1)
{
printf("->");
}
printf("%c",Grammar[k][j]);
j++;
}
printf("\n");
}
count=0;
printf("VT:");
while(VT[count]!='\0')
{
printf("%3c",VT[count]);
count++;
}
VT[count]='#';
vtNum=count+1;
printf("%3c",VT[count]);
printf("\nVN:");
count=0;
while(VN[count]!='\0')
{
printf("%3c",VN[count]);
count++;
}
printf("\n");
//?printf("\n%d?%d\n",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]!='\0')
{
j++;
}
VNum[i]=j;
//??printf("%3d",VNum[i]);
}
printf("\n");
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][j];
}
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\t",count);
while(p!=state.top+1)
{
stateNum=*p;
printf("%d",stateNum);
p++;
}
printf("\t");
while(q!=symbol.top+1)
{
symbolNum=*q;
printf("%c",symbolNum);
q++;
}
printf("\t");
j=i;
jj=0;
while(jj<j)
{
printf("?");
jj++;
}
while(Input[j]!='\0')
{
printf("%c",Input[j]);
j++;
}
printf("\t");
if(sign==1)
{
printf("\tS%d\t%d\n",action,gt);
}
if(sign==2)
{
printf("\tr%d\t%d\n",action,gt);
}
if(sign==3)
{
printf("\tacc\t%d\n",gt);
}
if(sign==0)
printf("\t0\t0\n");
return 0;
}
int Pop(int action) {
int *p,stateNum,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]!='\0')
{
if(Input[i]>='A'&&Input[i]<='Z')
{
printf("输入的不是有效的表达式！");
return 0;
}
i++;
}
i=0;
printf("步骤\t状态栈\t符号栈\t输入串\t\tACTION\tGOTO\n");
while(Input[i]!='\0')
{
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();
system("pause");
return 0;
}

【运行结果】

【程序如图】

21 / 21