.
实验名称：
实验任务：
对下述描述算符表达式的算符优先文法G[E],给出算符优先分析的实验结果。
实验内容：
有上下无关文法如下：
E->E+T|E-T|T
T->T*F|T/F|F
F->(E)|i
说明： 优先关系矩阵的构造过程： （1） = 关系 由产生式 F->(E) 知FIRSTVT集 及LASTVT集
FIRSTVT(E)={ +,-,*,/,(,i }
FIRSTVT(F)={ (,i }
.
（’=‘）’
‘.
FIRSTVT(T)={ *,/,(,i }
LASTVT(E)={ +,-,*,/,),i }
LASTVT(F)={ ),i }
LASTVT(T)={ *,/,),i }
(2) < 关系
+T 则有：+ < FIRSTVT(T)
-T 则有：- < FIRSTVT(T)
*F 则有：* < FIRSTVT(F)
/F 则有：/ < FIRSTVT(F)
(E 则有：( < FIRSTVT(E)
(3) > 关系
E+ 则有： LASTVT(E) > +
E- 则有： LASTVT(E) > -
.
.
T* 则有： LASTVT(T) > *
T/ 则有： LASTVT(T) > /
E) 则有： LASTVT(E) > )
(4)请大家画出优先关系矩阵
终结符之间的优先关系是唯一的，所以该文法是算符优先文法。 程序的功能描述： 程序由文件读入字符串（以#结束），然后进行算符优先分析，分析过程中如有错误，则终止程序并报告错误位置，最终向屏幕输出移近——规约过程。
(5)依据文法和求出的相应FirstVT和 LastVT 集生成算符优先分析表。 算法描述如下：
for 每个形如 P->X1X2…Xn的产生式
do
for i =1 to n-1 do
begin
if Xi和Xi+1都是终结符 then
Xi = Xi+1
.
.
if i<= n-2, Xi和Xi+2 是终结符, 但Xi+1 为非终结符
then
Xi = Xi+2
if Xi为终结符, Xi+1为非终结符 then
for FirstVT 中的每个元素 a do
Xi < a
if Xi为非终结符, Xi+1为终结符 then
for LastVT 中的每个元素 a do
a > Xi+1
end
(6)构造总控程序
算法描述如下：
stack S; k = 1; //符号栈S的使用深度
.
.
S[k] = ‘#’
REPEAT
把下一个输入符号读进a中；
If S[k] VT then
j = k
else
j = k-1;
While S[j] > a do
Begin
Repeat
Q = S[j];
if S[j-1] VT then
j = j-1
.
.
else
j = j-2
until S[j] < Q;
把S[j+1]…S[k]归约为某个N，并输出归约为哪个符号；S[k] = N;
end of while
if S[j] < a or S[j] = a then
begin k = k+1; S[k] = a end
else error //调用出错诊察程序
until a = ‘#’
(7)代码如下：
#include \"stdio.h\"
#include \"stdlib.h\"
.
K = j+1;
.
#include \"iostream.h\"
char data[20][20]; //算符优先关系
char s[100]; //模拟符号栈s
char lable[20]; char input[100]; char string[20][10]; int k; char a;
int j; char q; int r; int r1; char st[10][30]; .
//文法终极符集
//文法输入符号串
//用于输入串的分析
//文法规则个数
//转化后文法规则个数 //用来存储文法规则
.
char first[10][10]; //文法非终结符FIRSTVT集
char last[10][10]; //文法非终结符LASTVT集
int fflag[10]={0}; //标志第i个非终结符的FIRSTVT集是否已求出
int lflag[10]={0}; 出
int deal(); int zhongjie(char c); int xiabiao(char c); void out(int j,int k,char *s); void firstvt(char c); void lastvt(char c); void table(); void main()
.
//标志第i个非终结符的LASTVT集是否已求 //对输入串的分析
//判断字符c是否是终极符
//求字符c在算符优先关系表中的下标
//打印s栈
//求非终结符c的FIRSTVT集
//求非终结符c的LASTVT集
//创建文法优先关系表
.
{
int i,j,k=0;
printf(\"请输入文法规则数：\");
scanf(\"%d\
printf(\"请输入文法规则：\\n\");
for(i=0;i{scanf(\"%s\ //存储文法规则，初始化FIRSTVT集和LASTVT集*/
first[i][0]=0; /*first[i][0]和last[i][0]分别表示st[i][0]非终极
符的FIRSTVT集和LASTVT集中元素的个数*/
last[i][0]=0;
}
for(i=0;i..
{
for(j=0;st[i][j]!='\\0';j++)
{
if(st[i][0]<'A'||st[i][0]>'Z')
{
printf(\"不是算符文法!\\n\");
exit(-1);
}
if(st[i][j]>='A'&&st[i][j]<='Z')
{
if(st[i][j+1]>='A'&&st[i][j+1]<='Z')
{
printf(\"不是算符文法!\\n\");
.
.
exit(-1);
}
}
}
}
for(i=0;i{for(j=0;st[i][j]!='\\0';j++)
{
if((st[i][j]<'A'||st[i][j]>'Z')&&st[i][j]!='-'&&st[i][j]!='>'&&st[i][j]!='|')
lable[k++]=st[i][j];
}
}
.
.
lable[k]='#';
lable[k+1]='\\0';
table();
printf(\"每个非终结符的FIRSTVT集为：\\n\"); for(i=0;i{printf(\"%c: \
for(j=0;j{printf(\"%c \
}
printf(\"\\n\");
}
.
//输出每个非终结符的FIRSTVT集
.
printf(\"每个非终结符的LASTVT集为：\\n\"); //输出每个非终结符的LASTVT集
for(i=0;i{printf(\"%c: \
for(j=0;j{printf(\"%c \j+1]);
}
printf(\"\\n\");
}
printf(\"算符优先分析表如下:\\n\");
for(i=0;lable[i]!='\\0';i++)
printf(\"\%c\
.
.
printf(\"\\n\");
for(i=0;i{printf(\"%c\\
for(j=0;j{printf(\"%c\\j]);
}
printf(\"\\n\");
}
printf(\"请输入文法输入符号串以#结束:\");
scanf(\"%s\
deal();
.
.
}
void table()
{
char text[20][10];
int i,j,k,t,l,x=0,y=0;
int m,n;
x=0;
for(i=0;i{firstvt(st[i][0]);
lastvt(st[i][0]);
}
for(i=0;i..
{
text[x][y]=st[i][0];
y++;
for(j=1;st[i][j]!='\\0';j++)
{
if(st[i][j]=='|')
{
text[x][y]='\\0';
x++;
y=0;
text[x][y]=st[i][0];
y++;
text[x][y++]='-';
.
.
text[x][y++]='>';
}
else
{
text[x][y]=st[i][j];
y++;
}
}
text[x][y]='\\0';
x++;
y=0;
}
r1=x;
.
.
printf(\"转化后的文法为:\\n\");
for(i=0;i{printf(\"%s\\n\
}
for(i=0;i{string[i][0]=text[i][0];
for(j=3,l=1;text[i][j]!='\\0';j++,l++)
string[i][l]=text[i][j];
string[i][l]='\\0';
}
.
/*求每个终结符的推导结果(去掉\"->\"
.
for(i=0;i{for(j=1;text[i][j+1]!='\\0';j++)
{
if(zhongjie(text[i][j])&&zhongjie(text[i][j+1]))
{
m=xiabiao(text[i][j]);
n=xiabiao(text[i][j+1]);
data[m][n]='=';
}
if(text[i][j+2]!='\\0'&&zhongjie(text[i][j])&&zhongjie(text[i][j+2])&&!zhongjie(text[i][j+1]))
{
m=xiabiao(text[i][j]);
.
.
n=xiabiao(text[i][j+2]);
data[m][n]='=';
}
if(zhongjie(text[i][j])&&!zhongjie(text[i][j+1]))
{
for(k=0;k{if(st[k][0]==text[i][j+1])
break;
}
m=xiabiao(text[i][j]);
for(t=0;t{.
.
n=xiabiao(first[k][t+1]);
data[m][n]='<';
}
}
if(!zhongjie(text[i][j])&&zhongjie(text[i][j+1]))
{
for(k=0;k{if(st[k][0]==text[i][j])
break;
}
n=xiabiao(text[i][j+1]);
for(t=0;t..
{
m=xiabiao(last[k][t+1]);
data[m][n]='>';
}
}
}
}
m=xiabiao('#');
for(t=0;t{n=xiabiao(first[0][t+1]);
data[m][n]='<';
}
.
.
n=xiabiao('#');
for(t=0;t{m=xiabiao(last[0][t+1]);
data[m][n]='>';
}
data[n][n]='=';
}
void firstvt(char c) {
int i,j,k,m,n;
for(i=0;i{.
//求FIRSTVT集
.
if(st[i][0]==c)
break;
}
if(fflag[i]==0)
{
n=first[i][0]+1;
m=0;
do
{
if(m==2||st[i][m]=='|')
{
if(zhongjie(st[i][m+1]))
{
.
.
first[i][n]=st[i][m+1];
n++;
}
else
{
if(zhongjie(st[i][m+2]))
{
first[i][n]=st[i][m+2];
n++;
}
if(st[i][m+1]!=c)
{
firstvt(st[i][m+1]);
.
.
for(j=0;j{if(st[j][0]==st[i][m+1])
break;
}
for(k=0;k{int t;
for(t=0;t{if(first[i][t]==first[j][k+1])
break;
}
.
.
if(t==n)
{
first[i][n]=first[j][k+1];
n++;
}
}
}
}
}
m++;
}while(st[i][m]!='\\0');
first[i][n]='\\0';
first[i][0]=--n;
.
.
fflag[i]=1;
}
}
void lastvt(char c) {
int i,j,k,m,n;
for(i=0;i{if(st[i][0]==c)
break;
}
if(lflag[i]==0)
{
.
//求LASTVT集
.
n=last[i][0]+1;
m=0;
do
{
if(st[i][m+1]=='\\0'||st[i][m+1]=='|')
{
if(zhongjie(st[i][m]))
{
last[i][n]=st[i][m];
n++;
}
else
{
.
.
if(zhongjie(st[i][m-1]))
{
last[i][n]=st[i][m-1];
n++;
}
if(st[i][m]!=c)
{
lastvt(st[i][m]);
for(j=0;j{if(st[j][0]==st[i][m])
break;
}
.
.
for(k=0;k{int t;
for(t=0;t{if(last[i][t]==last[j][k+1])
break;
}
if(t==n)
{
last[i][n]=last[j][k+1];
n++;
}
.
.
}
}
}
}
m++;
}while(st[i][m]!='\\0');
last[i][n]='\\0';
last[i][0]=--n;
lflag[i]=1;
}
}
int deal()
{
.
.
int i,j;
int x,y;
int z; //输入串的长度
k=1;
s[k]='#'; for(i=0;input[i]!='\\0';i++); z=i--;
i=0;
while((a=input[i])!='\\0')
{
if(zhongjie(s[k]))
j=k;
else
.
//栈置初值
//计算输入串的长度
.
j=k-1;
x=xiabiao(s[j]);
y=xiabiao(a);
if(data[x][y]=='>')
{
out(1,k,s);
printf(\"%c\
out(i+1,z,input);
printf(\"规约\\n\");
do
{
q=s[j];
if(zhongjie(s[j-1]))
.
.
j=j-1;
else j=j-2;
x=xiabiao(s[j]);
y=xiabiao(q);
}while(data[x][y]!='<');
int m,n,N;
for(m=j+1;m<=k;m++)
{
for(N=0;Nfor(n=1;string[N][n]!='\\0';n++){
if(!zhongjie(s[m])&&!zhongjie(string[N][n]))
{
.
.
if(zhongjie(s[m+1])&&zhongjie(string[N][n+1])
&&s[m+1]==string[N][n+1])
{
s[j+1]=string[N][0];
break;
}
}
else
if(zhongjie(s[m]))
if(s[m]==string[N][n])
{
s[j+1]=string[N][0];
break;
.
.
}
}
}
k=j+1;
if(k==2&&a=='#')
{
out(1,k,s);
printf(\"%c\
out(i+1,z,input);
printf(\"结束\\n\");
printf(\"输入串符合文法的定义！\\n\");
return 1; }
.
//输入串符合文法的定义
.
}
else
if(data[x][y]=='<'||data[x][y]=='=')
{ out(1,k,s);
printf(\"%c\
out(i+1,z,input);
printf(\"移进\\n\");
k++;
s[k]=a;
i++;
}
else
.
//移进
.
{
printf(\"\\nflase\");
return 0;
}
}
printf(\"\\nflase\");
return 0;
}
void out(int j,int k,char *s)
{
int n=0;
int i;
for(i=j;i<=k;i++)
.
.
{
printf(\"%c\
n++;
}
for(;n<15;n++)
{
printf(\" \");
}
}
int xiabiao(char c) 下标
{
int i;
for(i=0;lable[i]!='\\0';i++)
.
//求字符c在算符优先关系表中的 .
{
if(c==lable[i])
return i;
}
return -1;
}
int zhongjie(char c) {
int i;
for(i=0;lable[i]!='\\0';i++)
{
if(c==lable[i])
return 1;
.
//判断字符c是否是终极符
.
}
return 0;
}
实验结果：
.
