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

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

（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

typedef struct {

char R; char r; int flag; }array;

typedef struct {

char E; char e; }charLode;

typedef struct {

charLode *base; int top; }charstack;

char str[80][80],arr[80][80],brr[80][80]; array F[20];

int m,kk,p,ppp,FF=1; char r[10];

int crr[20][20],FLAG=0;

char ccrr1[1][20],ccrr2[20][1];

void Initstack(charstack &s)//定义栈

{

s.base=new charLode[20]; s.top=-1; }

void push(charstack &s,charLode w) //入栈 {

s.top++;

s.base[s.top].E=w.E; s.base[s.top].e=w.e; }

void pop(charstack &s,charLode &w) //出栈 {

w.E=s.base[s.top].E; w.e=s.base[s.top].e; s.top--; }

int IsEmpty(charstack s) //判断是否到栈顶

{

if(s.top==-1) return 1; else

return 0; }

int IsLetter(char ch) //判断是不是大写字母（非终结符）

{

if(ch>='A'&&ch<='Z') return 1; else

return 0; }

//judge1是判断是否是算符文法：若产生式中含有两个相继的非终结符则不是算符文法 int judge1(int n) {

int j=3,flag=0;

for(int i=0;i<=n;i++) while(str[i][j]!='\\0') {

char a=str[i][j]; char b=str[i][j+1];

if(IsLetter(a)&&IsLetter(b)) //两个非终结符相连，不是算符文法 {

flag=1; break; } else j++; }

if(flag==1) //根据flag设定返回值

return 0; else

return 1; }

//judge2是判断文法G是否为算符优先文法：若不是算符文法或若文法中含空字或终结符的优先级不唯一则不是算符优先文法

void judge2(int n) {

for(int i=0;i<=n;i++)

if(str[i][3]=='~'||FLAG==1)//'~'代表空 {

cout<<\文法G不是算符优先文法!\ FF=0; break; }

if(i>n)

cout<<\文法G是算符优先文法!\

}

//search1是查看存放终结符的数组r中是否含有重复的终结符

int search1(char r[],int kk,char a) {

for(int i=0;i

return 1; }

//createF函数是用F数组存放每个终结符与非终结符和组合，并且值每队的标志位为0;F数组是一个结构体

void createF(int n) {

int k=0,i=1;char g;

char t[10];//t数组用来存放非终结符 t[0]=str[0][0]; while(i<=n) {

if(t[k]!=str[i][0]) {

k++;

t[k]=str[i][0]; g=t[k]; i++; }

else i++; }

kk=0; char c;

for(i=0;i<=n;i++) {

int j=3;

while(str[i][j]!='\\0') {

c=str[i][j];

if(IsLetter(c)==0) {

if(!search1(r,kk,c))

r[kk]=c;

kk++;//r数组用来存放终结符

} j++; } }

m=0;

for(i=0;i

for(int j=0;j

F[m].R=t[i]; F[m].r=r[j]; F[m].flag=0; m++; } }

//search函数是将在F数组中寻找到的终结符与非终结符对的标志位值为1 void search(charLode w) {

for(int i=0;i

if(F[i].R==w.E&&F[i].r==w.e) {

F[i].flag=1;break; } }

void FirstVT(int n)//求FirstVT

{

charstack sta; charLode w; int i=0;

Initstack(sta); while(i<=n) {

int k=3;

w.E=str[i][0]; char a=str[i][k]; char b=str[i][k+1];

if(!IsLetter(a)) //产生式的后选式的第一个字符就是终结符的情况 {

w.e=a;

push(sta,w); search(w);

i++; }

else if(IsLetter(a)&&b!='\\0'&&!IsLetter(b)) //产生式的后选式的第一个字符是非终结符的情况

{

w.e=b;

push(sta,w); search(w); i++; }

else i++; }

charLode ww;

while(!IsEmpty(sta)) {

pop(sta,ww);

for(i=0;i<=n;i++) {

w.E=str[i][0];

if(str[i][3]==ww.E&&str[i][4]=='\\0') {

w.e=ww.e; push(sta,w); search(w); break; } } }

p=0;int k=1;i=1; while(i

if(F[i-1].flag==1) {

arr[p][0]=F[i-1].R; arr[p][k]=F[i-1].r; }

while(F[i].flag==0&&i

if(F[i].flag==1) {

if(F[i].R==arr[p][0]) k++;

else {arr[p][k+1]='\\0';p++;k=1;} i++;

} } }

void LastVT(int n)//求LastVT

{

charstack sta; charLode w;

for(int i=0;i

Initstack(sta); while(i<=n) {

int k=strlen(str[i]); w.E=str[i][0];

char a=str[i][k-1]; char b=str[i][k-2]; if(!IsLetter(a)) {

w.e=a;

push(sta,w); search(w); i++; }

else if(IsLetter(a)&&!IsLetter(b)) {

w.e=b;

push(sta,w); search(w); i++; }

else i++; }

charLode ee;

while(!IsEmpty(sta)) {

pop(sta,ee);

for(i=0;i<=n;i++) {

w.E=str[i][0];

if(str[i][3]==ee.E&&str[i][4]=='\\0') {

w.e=ee.e;

push(sta,w); search(w); } } }

int k=1;i=1; ppp=0; while(i

if(F[i-1].flag==1) {

brr[ppp][0]=F[i-1].R; brr[ppp][k]=F[i-1].r; }

while(F[i].flag==0&&i

if(F[i].flag==1) {

if(F[i].R==arr[ppp][0]) k++;

else {brr[ppp][k+1]='\\0';ppp++;k=1;} i++; } } }

void createYXB(int n)//构造优先表

{

int i,j;

for(j=1;j<=kk;j++) ccrr1[0][j]=r[j-1]; for( i=1;i<=kk;i++) ccrr2[i][0]=r[i-1]; for(i=1;i<=kk;i++) for(j=1;j<=kk;j++) crr[i][j]=0; int I=0,J=3; while(I<=n) {

if(str[I][J+1]=='\\0') //扫描右部 {

I++; J=3; }

else {

while(str[I][J+1]!='\\0') {

char aa=str[I][J]; char bb=str[I][J+1];

if(!IsLetter(aa)&&!IsLetter(bb))//优先及等于的情况，用1值表示等于 {

for(i=1;i<=kk;i++) {

if(ccrr2[i][0]==aa) break; }

for(j=1;j<=kk;j++) {

if(ccrr1[0][j]==bb) break; }

if(crr[i][j]==0) crr[i][j]=1; else {

FLAG=1; I=n+1; } J++; }

if(!IsLetter(aa)&&IsLetter(bb)&&str[I][J+2]!='\\0'&&!IsLetter(str[I][J+2]))//优先及等于的情况

{

for(i=1;i<=kk;i++) {

if(ccrr2[i][0]==aa) break; }

for(int j=1;j<=kk;j++) {

if(ccrr1[0][j]==str[I][J+2]) break; }

if(crr[i][j]==0) crr[i][j]=1; else {

FLAG=1;

I=n+1; } }

if(!IsLetter(aa)&&IsLetter(bb))//优先及小于的情况，用2值表示小于 {

for(i=1;i<=kk;i++) {

if(aa==ccrr2[i][0]) break; }

for(j=0;j<=p;j++) {

if(bb==arr[j][0]) break; }

for(int mm=1;arr[j][mm]!='\\0';mm++) {

for(int pp=1;pp<=kk;pp++) {

if(ccrr1[0][pp]==arr[j][mm]) break; }

if(crr[i][pp]==0) crr[i][pp]=2; else {

FLAG=1;I=n+1; } } J++; }

if(IsLetter(aa)&&!IsLetter(bb))//优先及大于的情况，用3值表示大于 {

for(i=1;i<=kk;i++) {

if(ccrr1[0][i]==bb) break; }

for(j=0;j<=ppp;j++) {

if(aa==brr[j][0]) break; }

for(int mm=1;brr[j][mm]!='\\0';mm++) {

for(int pp=1;pp<=kk;pp++) {

if(ccrr2[pp][0]==brr[j][mm]) break; }

if(crr[pp][i]==0) crr[pp][i]=3;

else {FLAG=1;I=n+1;} } J++; } } } } }

//judge3是用来返回在归约过程中两个非终结符相比较的值

int judge3(char s,char a) {

int i=1,j=1;

while(ccrr2[i][0]!=s) i++;

while(ccrr1[0][j]!=a) j++;

if(crr[i][j]==3) return 3; else

if(crr[i][j]==2) return 2; else

if(crr[i][j]==1) return 1; else

return 0; }

void print(char s[],char STR[][20],int q,int u,int ii,int k)//打印归约的过程 {

cout<

for(i=q;i<=ii;i++) cout<

void process(char STR[][20],int ii)//对输入的字符串进行归约的过程

{

cout<<\步骤\符号栈\输入串\\动作\

int k=0,q=0,u=0,b,i,j; char s[40],a; s[k]='#';

print(s,STR,q,u,ii,k); cout<<\预备\ k++; u++;

s[k]=STR[0][q]; q++;

print(s,STR,q,u,ii,k); cout<<\移进\

while(q<=ii) {

a=STR[0][q];

if(!IsLetter(s[k])) j=k; else j=k-1;

b=judge3(s[j],a);

if(b==3)//大于的情况进行归约 {

while(IsLetter(s[j-1])) j--;

for(i=j;i<=k;i++) s[i]='\\0'; k=j;

s[k]='N'; u++;

print(s,STR,q,u,ii,k); cout<<\归约\

}

else if(b==2||b==1)//小于或等于的情况移进 {

k++; s[k]=a; u++; q++;

print(s,STR,q,u,ii,k);

if(s[0]=='#'&&s[1]=='N'&&s[2]=='#') cout<<\接受\ else cout<<\移进\ } else {

cout<<\出错\

break; } }

if(s[0]=='#'&&s[1]=='N'&&s[2]=='#') cout<<\归约成功\ else cout<<\归约失败\

}

void main() {

int n,i,j;

cout<<\请输入你要定义的文法G的产生式的个数n:\ cin>>n;

cout<<\请输入文法产生式：\ for(i=0;i

gets(str[i]); j=strlen(str[i]); str[i][j]='\\0'; }

str[i][0]='Q'; //最末行添加扩展 str[i][1]='-'; str[i][2]='>'; str[i][3]='#';

str[i][4]=str[0][0]; str[i][5]='#';

cout<<\你定义的产生式如下:\

str[i][6]='\\0';

for(i=0;i<=n;i++)

cout<

if(judge1(n)==0) //判断文法G是否为算符文法 cout<<\文法G不是算符文法!\

if(judge1(n)==1) {

cout<<\文法G是算符文法!\

}

createF(n); FirstVT(n); LastVT(n); createYXB(n);

for(i=0;i<=p;i++)//打印FirstVT

{

cout<<\ for(int l=1;arr[i][l+1]!='\\0';l++) cout<

cout<

cout<<\ for(i=0;i<=ppp;i++)//打印LastVT {

cout<<\ for(int l=1;brr[i][l+1]!='\\0';l++) cout<

cout<

cout<<\ cout<<\优先表如下:\

for(i=1;i

cout<<\\

cout<

cout<

for(i=1;i

cout<

if(crr[i][j]==0) cout<<\

else if(crr[i][j]==1) cout<<\

else if(crr[i][j]==2) cout<<\

else if(crr[i][j]==3) cout<<\

cout<<\\ }

cout<

judge2(n);//判断文法G是否为算符优先文法

if(FF==1) {

char STR[1][20];

cout<<\请输入要规约的字符串:\ gets(STR[0]);

int ii=strlen(STR[0]); STR[0][ii]='#';

cout<<\下面是规约的过程:\ process(STR,ii); } }

本文来源：https://www.bwwdw.com/article/9e0v.html