实验三算符优先分析算法的设计与实现.doc

实验三算符优先分析算法的设计与实现
（8学时）
一、实验目的
根据算符优先分析法，对表达式进行语法分析，使其能够判断一个表达式是否正确。通过算符优先分析方法的实现，加深对自下而上语法分析方法的理解。
二、实验要求
1、输入文法。可以是如下算术表达式的文法（你可以根据需要适当改变）：
E→E+T|E-T|T
T→T*F|T/F|F
F→（E）|i
2、对给定表达式进行分析，输出表达式正确与否的判断。
程序输入/输出示例：
输入：1+2;
输出：正确
输入：(1+2)/3+4-(5+6/7);
输出：正确
输入：((1-2)/3+4
输出：错误
输入：1+2-3+(*4/5)
输出：错误
三、实验步骤
1、参考数据结构
char*VN=0,*VT=0;//非终结符和终结符数组
charfirstvt[N][N],lastvt[N][N],table[N][N];
typedefstruct//符号对(P,a)
{
charVn;
charVt;
}VN_VT;
typedefstruct//栈
{
VN_VT*top;
VN_VT*bollow;
intsize;
}stack;

2、根据文法求FIRSTVT集和LASTVT集
给定一个上下文无关文法，根据算法设计一个程序，求文法中每个非终结符的FirstVT集和LastVT集。
算符描述如下：
/*求FirstVT集的算法*/
PROCEDUREinsert(P,a);
IFnotF[P,a]then
begin
F[P,a]=true;//(P,a)进栈
end;
ProcedureFirstVT;
Begin
for对每个非终结符P和终结符ado
F[P,a]=false
for对每个形如P a…或P→Qa…的产生式do
Insert(P,a)
whilestack非空
begin
栈顶项出栈，记为(Q,a)
for对每条形如P→Q…的产生式do
insert(P,a)
end;
end.
同理，可构造计算LASTVT的算法。
3、构造算符优先分析表
依据文法和求出的相应FirstVT和LastVT集生成算符优先分析表。
算法描述如下：
for每个形如P->X1X2…Xn的产生式do
fori=1ton-1do
begin
ifXi和Xi+1都是终结符then
Xi=Xi+1
ifi<=n-2,Xi和Xi+2是终结符,但Xi+1为非终结符then
Xi=Xi+2
ifXi为终结符,Xi+1为非终结符then
forFirstVT中的每个元素ado
Xi<a;
ifXi为非终结符,Xi+1为终结符then
forLastVT中的每个元素ado
a>Xi+1;
end
4、构造总控程序
算法描述如下：
stackS;
k=1;//符号栈S的使用深度
S[k]=‘#’
REPEAT
把下一个输入符号读进a中；
IfS[k]VTthenj=kelsej=k-1;
WhileS[j]>ado
Begin
Repeat
Q=S[j];
ifS[j-1]VTthenj=j-1elsej=j-2
untilS[j]<Q;
把S[j+1]…S[k]归约为某个N，并输出归约为哪个符号；
K=j+1;
S[k]=N;
endofwhile
ifS[j]<aorS[j]=athen
begink=k+1;S[k]=aend
elseerror//调用出错诊察程序
untila=‘#’
5、对给定的表达式，给出准确与否的分析过程
6、给出表达式的计算结果。（本步骤可选作）

四、实验报告要求
1.写出编程思路、源代码（或流程图）；
2.写出上机调试时发现的问题，以及解决的过程；
3.写出你所使用的测试数据及结果；
4.谈谈你的体会。
5.上机8小时，完成实验报告2小时。
五、源代码
#include<iostream.h>#include<string.h>#include<stdio.h>typedefstruct{charR;charr;intflag;}array;typedefstruct{charE;chare;}charLode;typedefstruct{charLode*base;inttop;}charstack;charstr[80][80],arr[80][80],brr[80][80];arrayF[20];intm,kk,p,ppp,FF=1;charr[10];intcrr[20][20],FLAG=0;charccrr1[1][20],ccrr2[20][1];voidInitstack(charstack&s)//定义栈{s.base=newcharLode[20];s.top=-1;}voidpush(charstack&s,charLodew)//入栈