实验4算符优先分析法

实验名称：

实验任务：

对下述描述算符表达式的算符优先文法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;

}

实验结果：

.