编译原理SLR1语法分析实验报告.doc
《编译原理SLR1语法分析实验报告.doc》由会员分享，可在线阅读，更多相关《编译原理SLR1语法分析实验报告.doc（8页珍藏版）》请在冰点文库上搜索。
学号E10714103专业计算机科学与技术姓名万学进
实验日期2010-6-8教师签字成绩
实验报告
【实验名称】SLR
（1）语法分析
【实验目的】
构造LR
（1）分析程序，利用它进行语法分析，判断给出的符号串是否为该文法识别的句子，了解LR（K）分析方法是严格的从左向右扫描，和自底向上的语法分析方法。
【实验内容】
对下列文法，用LR
（1）分析法对任意输入的符号串进行分析：
7
（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）分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。
分析器的动作就是由栈顶状态和当前输入符号所决定。
uLR分析器由三个部分组成：
u其中:
SP为栈指针，S[i]为状态栈，X[i]为文法符号栈。
状态转换表用GOTO[i，X]=j表示，规定当栈顶状态为i，遇到当前文法符号为X时应转向状态j，X为终结符或非终结符。
uACTION[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#）：
在此位置输入符号串
输出过程如下：
步骤状态栈符号栈剩余输入串动作
10#i+i*i#移进
【流程图】
【源代码】
#include
#include
intAction[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};
intGoto[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
};
charGrammar[20][10]={'\0'};
charVT[10],VN[10];
charAVT[6]={'i','+','*','（','）','#'};
charGVN[3]={'E','T','F'};
intvnNum,vtNum,stateNum=12;
intVNum[10];
intgrammarNum;
typedefstruct{
char*base;
char*top;
}SymbolStack;
typedefstruct{
int*base;
int*top;
}StateStack;
StateStackstate;
SymbolStacksymbol;
intScanGrammar（）
{
FILE*fp=fopen（"SLR文法.txt","r"）;
FILE*tp;
charsingleChar,nextChar;
inti=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;
returni;
}
intvNumCount（）
{
inti,j;
for（i=0;i {
j=1;
while（Grammar[i][j]!
='\0'）
{
j++;
}
VNum[i]=j;
// printf（"%3d",VNum[i]）;
}
printf（"\n"）;
return0;
}
voidInitStack（）
{
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='#';
}
intJudge（intstateTop,charinputChar）
{
inti,j;
for（i=0;i {
if（stateTop==i）break;
}
for（j=0;j {
if（inputChar==AVT[j]）break;
}
returnAction[i][j];
}
intGetGoto（intstateTop,charinputChar）
{
inti,j;
for（i=0;i {
if（stateTop==i）break;
}
for（j=0;j {
if（inputChar==GVN[j]）break;
}
returnGoto[i][j];
}
intprint（intcount,inti,charInput[],intaction,intgt,intsign）
{
int*p=state.base,stateNum;
intj,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 {
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"）;
return0;
}
intPop（intaction）
{
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）returnssValue;
state.top++;
*state.top=ssValue;
returnssValue;
}
intReduction（）
{
charInput[20];
inti=0,count=1;
intssValue,action;
intstateTop,gt;
intsign=-1;//移进1，规约2，接受3
scanf（"%s",&Input）;
while（Input[i]!
='\0'）
{
if（Input[i]>='A'&&Input[i]<='Z'）
{
printf（"输入的不是有效的表达式！
"）;
return0;
}
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（"规约出错！
"）;
return0;
}
continue;
}
if（ssValue==-1）
{
sign=3;
print（count,i,Input,ssValue,0,sign）;
count++;
return1;
}
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++;
}
}
return0;
}
intmain（）
{
ScanGrammar（）;
vNumCount（）;
InitStack（）;
Reduction（）;
return0;
}
【运行结果】
升级会员 