实验3 算符优先分析算法的设计与实现

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

（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;//非终结符和终结符数组

char firstvt[N][N],lastvt[N][N],table[N][N]; typedef struct //符号对(P,a) {

char Vn; char Vt; } VN_VT;

typedef struct //栈 {

VN_VT *top; VN_VT *bollow; int size;

}stack;

2、根据文法求FIRSTVT集和LASTVT集

给定一个上下文无关文法，根据算法设计一个程序，求文法中每个非终结符的

FirstVT 集和LastVT 集。

算符描述如下：

/*求 FirstVT 集的算法*/ PROCEDURE insert(P,a); IF not F[P,a] then begin

F[P,a] = true; //(P,a)进栈 end;

Procedure FirstVT; Begin

for 对每个非终结符 P和终结符 a do F[P,a] = false for 对每个形如 P Insert(P,a)

while stack 非空 begin

栈顶项出栈，记为(Q,a)

for 对每条形如 P→Q…的产生式 do insert(P,a) end;

end.

同理，可构造计算LASTVT的算法。

3、构造算符优先分析表

依据文法和求出的相应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

4、构造总控程序 算法描述如下： stack S;

k = 1; //符号栈S的使用深度 S[k] = ‘#’ REPEAT

a…或 P→Qa…的产生式 do

把下一个输入符号读进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，并输出归约为哪个符号； K = j+1; 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 = ‘#’

5、对给定的表达式，给出准确与否的分析过程 6、给出表达式的计算结果。（本步骤可选作）

四、实验报告要求

1.写出编程思路、源代码（或流程图）；

2.写出上机调试时发现的问题，以及解决的过程； 3.写出你所使用的测试数据及结果； 4.谈谈你的体会。

5.上机8小时，完成实验报告2小时。

程序代码:

#include #include #include

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}; //标志第i个非终结符的LASTVT集是否已求出

int deal(); //对输入串的分析

int zhongjie(char c); //判断字符c是否是终结符

int xiabiao(char c); //求字符c在算符优先关系表中的下标 void out(int j,int k,char *s); //打印s栈

void firstvt(char c); //求非终结符c的FIRSTVT集 void lastvt(char c); //求非终结符c的LASTVT集 void table(); //创建文法优先关系表 int main() {

int i,j,k=0;

printf(\"请输入文法规则数：\"); scanf(\"%d\

printf(\"请输入文法规则：\\n\"); for(i=0;iscanf(\"%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\"); //输出每个非终结符的FIRSTVT集

for(i=0;i{

printf(\"%c: \ for(j=0;jprintf(\"%c \ }

printf(\"\\n\");

}

printf(\"每个非终结符的LASTVT集为：\\n\"); //输出每个非终结符的LASTVT集 for(i=0;i{

printf(\"%c: \ for(j=0;jprintf(\"%c \ }

printf(\"\\n\");

}

printf(\"算符优先分析表如下:\\n\");

for(i=0;lable[i]!='\\0';i++) printf(\"\%c\

printf(\"\\n\"); for(i=0;iprintf(\"%c\\ for(j=0;j{

printf(\"%c\\ }

printf(\"\\n\"); }

printf(\"请输入文法输入符号串以#结束:\"); scanf(\"%s\

getchar(); deal();system(\"pause\"); }

void table()

{

char text[20][10];

int i,j,k,t,l,x=0,y=0; int m,n; x=0;

for(i=0;ifirstvt(st[i][0]); lastvt(st[i][0]); }

for(i=0;itext[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;iprintf(\"%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;ifor(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;kif(st[k][0]==text[i][j+1]) break;

}

m=xiabiao(text[i][j]); for(t=0;tn=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;tm=xiabiao(last[k][t+1]); data[m][n]='>'; } } }

}

m=xiabiao('#');

for(t=0;tn=xiabiao(first[0][t+1]); data[m][n]='<'; }

n=xiabiao('#');

for(t=0;tm=xiabiao(last[0][t+1]); data[m][n]='>'; }

data[n][n]='=';

}

/*********求FIRSTVT集*************/ void firstvt(char c) {

int i,j,k,m,n; for(i=0;iif(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;kint 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; } }

/*********求LASTVT集*********/ void lastvt(char c) {

int i,j,k,m,n; for(i=0;iif(st[i][0]==c) break; }

if(lflag[i]==0) {

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;kint t;

for(t=0;tif(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 {

return 0; }

}

printf(\"\\nflase\");system(\"pause\"); return 0;

}

void out(int j,int k,char *s) //从栈中输出j到k的元素 {

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++) {

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; }

return 0; }

求字符c在算符优先关系表中判断字符c是否是终结符

运行结果演示: