写在前面：本博客为本人原创，严禁任何形式的转载！本博客只允许放在博客园（.cnblogs.com），如果您在其他网站看到这篇博文，请通过下面这个唯一的合法链接转到原文！
本博客全网唯一合法URL：http://www.cnblogs.com/acm-icpcer/p/9173880.html
基于C++语言实现的PL/0语言的算术表达式的自下而上的语法分析程序。该语言的其他语法实现思想与此一致，故不赘述。
运行此程序前，必须先将代码通过：【编译原理】c++实现词法分析器的词法分析，生成词法表（词法表是txt文件，为了语法分析成功，务必删除文件中最后空着的一行，即文件末尾不可以留空白行）。生成的该词法表为此程序的必要输入。
产生式：
S->X(AX)*|AX(AX)*
X->Y(MY)*
Y->I|N|(S)
A->+|-
M->*|/
C->=|#|<|<=|>|>=
本次的代码主要是在【编译原理】c++实现自下而上语法分析器的基础上，伴随着归约的过程，增加了生成四元式的过程，也就是一边归约一边生成中间代码。
Talk is cheap, show you my source code:
/*
this code was first initiated by TZ,COI,HZAU
contact email:xmb028@163.com
personal website:wnm1503303791.github.io
personal blogs:www.cnblogs.com/acm-icpcer/
this code has been posted on my personal blog,checking url:www.cnblogs.com/acm-icpcer/p/9173880.html
Copyright 2018/6/12 TZ.
All Rights Reserved.
*/ #include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<fstream>
using namespace std; //预处理函数
bool preproccess(char *a,char *b,char *c)
{
int i1=,i2=;//i2为原串指针
memset(b,,'\0');
while(a[i2]!=',')
{
b[i1]=a[i2];
++i1,++i2;
}
b[i1]='\0'; i1=;i2++;
while(a[i2]!=')')
{
c[i1]=a[i2];
++i1,++i2;
}
c[i1]='\0';
//cout<<b<<endl;
return true;
} fstream f2("stack.txt", ios::out);//打开文件，供写
fstream f3("quaternary.txt", ios::out);//打开文件，供写
static int mcount=;//存储打印次数
//当移进或者归约时打印栈内情况，以供分析
bool outf(int head,char data[][],fstream &f)
{
f<<"times("<<mcount<<"),";
f<<"head is:"<<head<<endl;
for(int i=head;i>=;i--)
{
f<<data[i]<<endl;
}
mcount++;
f<<endl;
return true;
}
//四元式写入文件函数1
bool outf2(int top,char dt[][],fstream &f)
{
/*
char arg1[1024],arg2[1024],op[1024];
memset(arg1,sizeof(arg1),'\0');
strcpy(arg1,dt[top]);
memset(op,sizeof(op),'\0');
strcpy(op,dt[top-1]);
memset(arg2,sizeof(arg2),'\0');
strcpy(arg2,dt[top-2]); f<<"("<<op<<","<<arg1<<","<<arg2<<","<<"T"<<")"<<endl;
*/
f<<"("<<dt[top-]<<","<<dt[top]<<","<<dt[top-]<<","<<"T"<<")"<<endl;
return true;
}
//四元式写入文件函数2
bool outf3(int top,char dt[][],fstream &f)
{
f<<"("<<dt[top-]<<","<<dt[top]<<","<<"-"<<","<<"T"<<")"<<endl;
return true;
}
//四元式写入文件函数3
bool outf4(int top,char dt[][],fstream &f,char T)
{
f<<"("<<":="<<","<<dt[top]<<","<<"-"<<","<<T<<")"<<endl;
return true;
} //“策略”设计模式，面向对象方法
class presentation
{
private:
char data[][];//栈
char dt[][];//四元式栈
fstream *infile;//词法分析表
int head,top;//两个栈的栈顶指针
public:
//first initiated the object
presentation(fstream *in_f)
{
this->infile=in_f;
memset(data,sizeof(data),'\0');
memset(dt,sizeof(dt),'\0');
head=top=-;
}
bool push()
{
head++;
top++; infile->getline(data[head],);
char t1[],t2[];//存放字符标志
preproccess(data[head],t1,t2); cout<<data[head]<<","<<t1<<endl; memset(data[head],,'\0');
strcpy(data[head],t1); memset(dt[top],,'\0');
strcpy(dt[top],t2);
cout<<dt[top]<<","<<t2<<endl;
} /*
S->X(AX)*|AX(AX)*
X->Y(MY)*
Y->I|N|(S)
A->+|-
M->*|/
C->=|#|<|<=|>|>=
*/
//归约函数
bool reduce()
{
//S->X(AX)*|AX(AX)*
if( head>=&&
(!strcmp(data[head],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))&&
(!strcmp(data[head-],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))&&
(!strcmp(data[head-],"X"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"S");//归约
/*
stack description:
top-> arg
op
top-2-> arg
op
arg
*/
if(outf2(top,dt,f3)&&outf2(top-,dt,f3))
{
top==-;
memset(dt,sizeof(dt),'\0');
} return true;
} if( head>=&&
(!strcmp(data[head],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))&&
(!strcmp(data[head-],"X"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"S");
if(outf2(top,dt,f3))
{
top==-;
memset(dt,sizeof(dt),'\0');
} return true;
} if( head>=&&/*top>=3*/
(!strcmp(data[head],"plus")||!strcmp(data[head],"minus"))&&
(!strcmp(data[head-],"X"))&&
(!strcmp(data[head-],"plus")||!strcmp(data[head-],"minus"))&&
(!strcmp(data[head-],"X"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"S");
if(outf3(top,dt,f3)&&outf3(top-,dt,f3))
{
top==-;
memset(dt,sizeof(dt),'\0');
} return true;
} if( head>=&&
(!strcmp(data[head],"plus")||!strcmp(data[head],"minus"))&&
(!strcmp(data[head-],"X"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"S");
if(outf3(top,dt,f3))
{
top==-;
memset(dt,sizeof(dt),'\0');
} return true;
} //X->Y(MY)*
if( head>=&&
(!strcmp(data[head],"Y"))&&
(!strcmp(data[head-],"times")||!strcmp(data[head-],"slash"))&&
(!strcmp(data[head-],"Y"))&&
(!strcmp(data[head-],"times")||!strcmp(data[head-],"slash"))&&
(!strcmp(data[head-],"Y"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"X");
/*
current stack description:
top-> arg
op
top-2-> arg
op
arg
*/
if(outf2(top,dt,f3)&&outf2(top-,dt,f3))
{
top==-;
memset(dt,sizeof(dt),'\0');
} return true;
} if( head>=&&
(!strcmp(data[head],"Y"))&&
(!strcmp(data[head-],"times")||!strcmp(data[head-],"slash"))&&
(!strcmp(data[head-],"Y"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"X");
/*
current stack description:
top->arg
op
arg
*/
if(outf2(top,dt,f3))
{
top==-;
memset(dt,sizeof(dt),'\0');
} return true;
} if( head>=&&(!strcmp(data[head],"Y"))
)
{
memset(data[head],,'\0');
head=head-+; strcpy(data[head],"X");
if(outf4(top,dt,f3,'X'))
{
top==-;
memset(dt,sizeof(dt),'\0');
}
return true;
} //Y->I|N|(S)
if( head>=&&(!strcmp(data[head],"ident"))
)
{
memset(data[head],,'\0');
head=head-+; strcpy(data[head],"Y");
if(outf4(top,dt,f3,'Y'))
{
top==-;
memset(dt,sizeof(dt),'\0');
}
return true;
} if( head>=&&(!strcmp(data[head],"number"))
)
{
memset(data[head],,'\0');
head=head-+; strcpy(data[head],"Y");
if(outf4(top,dt,f3,'Y'))
{
top==-;
memset(dt,sizeof(dt),'\0');
}
return true;
} if( head>=&&
(!strcmp(data[head],"rparen"))&&
(!strcmp(data[head-],"S"))&&
(!strcmp(data[head-],"lparen"))
)
{
memset(data[head],,'\0');
memset(data[head-],,'\0');
memset(data[head-],,'\0');
head=head-+; strcpy(data[head],"Y");
return true;
} return false;
}
//遍历栈
bool visit_data()
{
cout<<"current stack:"<<endl;
for(int i=head;i>=;i--)
{
cout<<data[i]<<endl;
}
return true;
}
//主控函数
bool mainf()
{
while(!infile->eof())
{
push();
bool t=reduce();
outf(head,data,f2);
//每当移进结束时就检查一下是否有可规约串
while(t)//防止规约嵌套
{
t=reduce();
outf(head,data,f2);
}
//visit_data();
} visit_data(); bool flag=false;
for(int i=head;i>=;i--)
{
if(!strcmp(data[i],"S"))
{
flag=true;
}
if( strcmp(data[i],"S")&&
strcmp(data[i],"X")&&
strcmp(data[i],"A")&&
strcmp(data[i],"Y")&&
strcmp(data[i],"M")&&
strcmp(data[i],"C")
)
{
return false;
}
} return flag; /*
while(head>0)
{
bool t=reduce();
//每当移进结束时就检查一下是否有可规约串
while(t)//防止规约嵌套
{
t=reduce();
}
//visit_data();
outf(head,data,f2);
}
*/
}
}; int main()
{
fstream f1;
f1.open("lexical.txt", ios::in);//打开词法分析表，供读 presentation* s1=new presentation(&f1);
bool result=s1->mainf(); if(result)
cout<<"ACCEPTED!"<<endl;
else
cout<<"ERROR!"<<endl; f1.close();
f2.close();
return ;
}
运行示例：
(1)合法的语句：
(2)不合法的语句：
tz@COI HZAU
2018/6/12