コンパイル原理TEST言語文法分析+出力文法ツリーC/C++
文法の木は進め方ですが、木の形については考えてみると、あまり書きにくいです.
バージョン1は関数呼び出し時に直接出力され、バージョン2は木が建てられています.先生の言うことはよく闻こえませんでした.
語法分析は頭ファイルとして使われた.
setで未宣言と重複宣言を処理した.他はまだ書いてない
(両バージョンとも隠れたバグがあるので、先生が調べられないことを願っていますhhh)
バージョン1:関数呼び出しとシンボル出力時に各ノードを順次出力
#include
#include"DSJ_ .h"
using namespace std;
char token[20],token1[40];
char yufa_in[300];//
char yufa_out[300];
FILE *fin,*fout;
setse;
int program(int p);
int declaration_list(int p);
int declaration_stat(int p);
int statement_list(int p);
int statement(int p);
int if_stat(int p);
int while_stat(int p);
int for_stat(int p);
int read_stat(int p);
int write_stat(int p);
int compound_stat(int p);
int expression_stat(int p);
int expression(int p);
int bool_expr(int p);
int additive_expr(int p);
int term(int p);
int factor(int p);
int fun_declaration(int p);//
int fun_body(int p);//
int main_declaration(int p);//
int call_stat(int p);//
void shift(int p){
for(int i=0;i
");
int es=0;
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,"function")&&strcmp(token,"main")){
return es=11;
}
while(strcmp(token,"function")==0){
es=fun_declaration(p+1);
if(es>0) return es;
}
if(strcmp(token,"main")){
return es=9;
}
es=main_declaration(p+1);
if(es>0) return es;
return es;
}
int fun_declaration(int p){
shift(p);
fprintf(fout,"
");
out(p);
int es=0;
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,"ID")) return es=3;
out(p);
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,"(")) return es=5;
out(p);
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,")")) return es=5;
out(p);
es=fun_body(p+1);
if(es>0) return es;
return es;
}
int main_declaration(int p){
shift(p);
fprintf(fout,"
");
out(p);
int es=0;
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,"(")) return es=5;
out(p);
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,")")) return es=6;
out(p);
es=fun_body(p+1);
if(es>0) return es;
fscanf(fin,"%s %s
",token,token1);
return es;
}
int fun_body(int p){
shift(p);
fprintf(fout,"
");
int es=0;
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,"{")) return es=1;
out(p);
fscanf(fin,"%s %s
",token,token1);
es=declaration_list(p+1);
if(es>0) return es;
es=statement_list(p+1);
if(es>0) return es;
if(strcmp(token,"}")) return es=2;
out(p);
fscanf(fin,"%s %s
",token,token1);
se.clear();//
return es;
}
int declaration_list(int p){
shift(p);
fprintf(fout,"
");
int es=0;
while(strcmp(token,"int")==0){
es=declaration_stat(p+1);
if(es>0) return es;
}
return es;
}
int declaration_stat(int p){
shift(p);
fprintf(fout,"
");
int es=0;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
if(strcmp(token,"ID")) return es=3;
if(se.count(token1)) return es=8;
se.insert(token1);
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
if(strcmp(token,";")) return es=4;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
return es;
}
int statement_list(int p){
shift(p);
fprintf(fout,"
");
int es=0;
while(strcmp(token,"}")){
es=statement(p+1);
if(es>0) return es;
}
return es;
}
int statement(int p){
shift(p);
fprintf(fout,"
");
int es=0;
if(es==0&&strcmp(token,"if")==0) es=if_stat(p+1);
if(es==0&&strcmp(token,"while")==0) es=while_stat(p+1);
if(es==0&&strcmp(token,"for")==0) es=for_stat(p+1);
if(es==0&&strcmp(token,"read")==0) es=read_stat(p+1);
if(es==0&&strcmp(token,"write")==0) es=write_stat(p+1);
if(es==0&&strcmp(token,"{")==0) es=compound_stat(p+1);
if(es==0&&strcmp(token,"call")==0) es=call_stat(p+1);
if(es==0&&(strcmp(token,"ID")==0||strcmp(token,"NUM")==0||strcmp(token,"(")==0)) es=expression_stat(p+1);
return es;
}
int if_stat(int p){
shift(p);
fprintf(fout,"
");
int es=0;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
if(strcmp(token,"(")) return es=5;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p+1);
if(es>0) return es;
if(strcmp(token,")")) return es=6;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=statement(p+1);
if(es>0) return es;
if(strcmp(token,"else")==0){
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=statement(p+1);
return es;
}
return es;
}
int while_stat(int p){
shift(p);
fprintf(fout,"
");
int es=0;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
out(p);
if(strcmp(token,"(")) return es=5;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p+1);
if(es>0) return es;
out(p);
if(strcmp(token,")")) return es=6;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=statement(p+1);
return es;
}
int for_stat(int p){
shift(p);
fprintf(fout,"
");
out(p);
int es=0;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
out(p);
if(strcmp(token,"(")) return es=5;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p+1);
if(es>0) return es;
if(strcmp(token,";")) return es=4;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p+1);
if(es>0) return es;
if(strcmp(token,";")) return es=4;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p+1);
if(es>0) return es;
if(strcmp(token,")")) return es=6;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=statement(p+1);
return es;
}
int write_stat(int p){
shift(p);
fprintf(fout,"
");
out(p);
int es=0;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p+1);
if(es>0) return es;
if(strcmp(token,";")) return es=4;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
return es;
}
int read_stat(int p){
shift(p);
fprintf(fout,"
");
out(p);
int es=0;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
if(strcmp(token,"ID")) return es=3;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
if(strcmp(token,";")) return es=4;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
return es;
}
int compound_stat(int p){
shift(p);
fprintf(fout,"
");
out(p);
int es=0;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=statement_list(p+1);
return es;
}
int expression_stat(int p){
shift(p);
fprintf(fout,"
");
out(p);
int es=0;
if(strcmp(token,";")==0){
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
return es;
}
es=expression(p+1);
if(es>0) return es;
if(es==0&&strcmp(token,";")==0){
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
return es;
}
else{
return es=4;
}
}
int call_stat(int p){
shift(p);
fprintf(fout,"
");
int es=0;
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,"ID")) return es=3;
out(p);
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,"(")) return es=5;
out(p);
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,")")) return es=6;
out(p);
fscanf(fin,"%s %s
",token,token1);
return es;
}
int expression(int p){
shift(p);
fprintf(fout,"
");
int es=0,fileadd;
char token2[20],token3[40];
if(strcmp(token,"ID")==0){
if(!se.count(token1)) return es=12;
fileadd=ftell(fin);
fscanf(fin,"%s %s
",token2,token3);
// printf("%s %s
",token2,token3);...
if(strcmp(token2,"=")==0){
out(p);
shift(p+1);
fprintf(fout,"%s
",token2);
// printf("%s %s
",token2,token3);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=bool_expr(p+1);
if(es>0) return es;
}
else{
fseek(fin,fileadd,0);
// printf("%s %s
",token,token1);...
es=bool_expr(p+1);
if(es>0) return es;
}
}
else es=bool_expr(p+1);
return es;
}
int bool_expr(int p){
shift(p);
fprintf(fout,"
");
int es=0;
es=additive_expr(p+1);
if(es>0) return es;
if(strcmp(token,">")==0||strcmp(token,">=")==0||strcmp(token,"0) return es;
}
return es;
}
int additive_expr(int p){
shift(p);
fprintf(fout,"
");
int es=0;
es=term(p+1);
if(es>0) return es;
while(strcmp(token,"+")==0||strcmp(token,"-")==0){
out(p);
fscanf(fin,"%s %s",token,token1);
// printf("%s %s
",token,token1);
es=term(p+1);
if(es>0) return es;
}
return es;
}
int term(int p){
shift(p);
fprintf(fout,"
");
int es=0;
es=factor(p+1);
if(es>0) return es;
while(strcmp(token,"*")==0||strcmp(token,"/")==0){
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=factor(p+1);
if(es>0) return es;
}
return es;
}
int factor(int p){
shift(p);
fprintf(fout,"
");
int es=0;
if(strcmp(token,"(")==0){
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p+1);
if(es>0) return es;
if(strcmp(token,")")) return es=6;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
}
else{
if(strcmp(token,"ID")==0||strcmp(token,"NUM")==0){
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
return es;
}
else{
es=7;
return es;
}
}
return es;
}
int main()
{
if(!init()){cout<
バージョン2:後で先生がデータ構造を聞いたと聞いて、私は木を建てました.
#include
#include"DSJ_ .h"
using namespace std;
char token[20],token1[40];
char yufa_in[300];//
char yufa_out[300];
FILE *fin,*fout;
setse;
struct node{
string st;
vectorson;
node* addSon(string s){
node* Son=new node();
Son->st=s;
son.push_back(Son);
return Son;
}
} *Root;
int program();
int declaration_list(node* fa);
int declaration_stat(node* fa);
int statement_list(node* fa);
int statement(node* fa);
int if_stat(node* fa);
int while_stat(node* fa);
int for_stat(node* fa);
int read_stat(node* fa);
int write_stat(node* fa);
int compound_stat(node* fa);
int expression_stat(node* fa);
int expression(node* fa);
int bool_expr(node* fa);
int additive_expr(node* fa);
int term(node* fa);
int factor(node* fa);
int fun_declaration(node* fa);//
int fun_body(node* fa);//
int main_declaration(node* fa);//
int call_stat(node* fa);//
void out(node* p){
p->addSon(token1);
}
void shift(int x){
for(int i=0;ist;
fprintf(fout,"%s
",p->st.c_str());
int nc=p->son.size();
if(nc==0) return;
for(int i=0;ison[i],x+1);
}
return ;
}
int TESTparse(){
int es=0;
// scanf("%s",fileName);
// fileName="out.txt";
strcpy(yufa_in,cifa_out);
if((fin=fopen(yufa_in,"r"))==NULL){
printf(" %s
",yufa_in);
es=10;
}
strcpy(yufa_out,"out_yufa_");
strcat(yufa_out,cifa_in);
if((fout=fopen(yufa_out,"w"))==NULL){
printf(" yufa_out
");
es=10;
}
if(es==0) es=program();
printf("===== :======
");
switch(es){
case 0:printf("
");break;
case 10:cout<st="";
// shift(p);
// fprintf(fout,"
");
int es=0;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
if(strcmp(token,"function")&&strcmp(token,"main")){
return es=11;
}
while(strcmp(token,"function")==0){
es=fun_declaration(Root);
if(es>0) return es;
}
if(strcmp(token,"main")){
return es=9;
}
es=main_declaration(Root);
if(es>0) return es;
return es;
}
int fun_declaration(node* fa){
node* p=fa->addSon("");
out(p);
// cur->addSon(token1);
int es=0;
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,"ID")) return es=3;
out(p);
// cur->addSon(token1);
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,"(")) return es=5;
out(p);
// cur->addSon(token1);
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,")")) return es=5;
out(p);
// cur->addSon(token1);
es=fun_body(p);
if(es>0) return es;
return es;
}
int main_declaration(node* fa){
node* p=fa->addSon("");
out(p);
// cur->addSon(token1);
int es=0;
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,"(")) return es=5;
out(p);
// cur->addSon(token1);
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,")")) return es=6;
out(p);
// cur->addSon(token1);
es=fun_body(p);
if(es>0) return es;
fscanf(fin,"%s %s
",token,token1);
return es;
}
int fun_body(node* fa){
node* p=fa->addSon("fun_body");
int es=0;
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,"{")) return es=1;
out(p);
fscanf(fin,"%s %s
",token,token1);
es=declaration_list(p);
if(es>0) return es;
es=statement_list(p);
if(es>0) return es;
if(strcmp(token,"}")) return es=2;
out(p);
fscanf(fin,"%s %s
",token,token1);
se.clear();//
return es;
}
int declaration_list(node* fa){
node* p=fa->addSon("declaration_list");
int es=0;
while(strcmp(token,"int")==0){
es=declaration_stat(p);
if(es>0) return es;
}
return es;
}
int declaration_stat(node* fa){
node* p=fa->addSon("");
int es=0;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
if(strcmp(token,"ID")) return es=3;
if(se.count(token1)) return es=8;
se.insert(token1);
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
if(strcmp(token,";")) return es=4;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
return es;
}
int statement_list(node* fa){
node* p=fa->addSon("");
int es=0;
while(strcmp(token,"}")){
es=statement(p);
if(es>0) return es;
}
return es;
}
int statement(node* fa){
node* p=fa->addSon("");
int es=0;
if(es==0&&strcmp(token,"if")==0) es=if_stat(p);
if(es==0&&strcmp(token,"while")==0) es=while_stat(p);
if(es==0&&strcmp(token,"for")==0) es=for_stat(p);
if(es==0&&strcmp(token,"read")==0) es=read_stat(p);
if(es==0&&strcmp(token,"write")==0) es=write_stat(p);
if(es==0&&strcmp(token,"{")==0) es=compound_stat(p);
if(es==0&&strcmp(token,"call")==0) es=call_stat(p);
if(es==0&&(strcmp(token,"ID")==0||strcmp(token,"NUM")==0||strcmp(token,"(")==0)) es=expression_stat(p);
return es;
}
int if_stat(node* fa){
node* p=fa->addSon("");
int es=0;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
if(strcmp(token,"(")) return es=5;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p);
if(es>0) return es;
if(strcmp(token,")")) return es=6;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=statement(p);
if(es>0) return es;
if(strcmp(token,"else")==0){
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=statement(p);
return es;
}
return es;
}
int while_stat(node* fa){
node* p=fa->addSon("");
int es=0;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
out(p);
if(strcmp(token,"(")) return es=5;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p);
if(es>0) return es;
out(p);
if(strcmp(token,")")) return es=6;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=statement(p);
return es;
}
int for_stat(node* fa){
node* p=fa->addSon("");
out(p);
int es=0;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
out(p);
if(strcmp(token,"(")) return es=5;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p);
if(es>0) return es;
if(strcmp(token,";")) return es=4;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p);
if(es>0) return es;
if(strcmp(token,";")) return es=4;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p);
if(es>0) return es;
if(strcmp(token,")")) return es=6;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=statement(p);
return es;
}
int write_stat(node* fa){
node* p=fa->addSon("");
out(p);
int es=0;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p);
if(es>0) return es;
if(strcmp(token,";")) return es=4;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
return es;
}
int read_stat(node* fa){
node* p=fa->addSon("");
out(p);
int es=0;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
if(strcmp(token,"ID")) return es=3;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
if(strcmp(token,";")) return es=4;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
return es;
}
int compound_stat(node* fa){
node* p=fa->addSon("");
out(p);
int es=0;
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=statement_list(p);
return es;
}
int expression_stat(node* fa){
node* p=fa->addSon("");
out(p);
int es=0;
if(strcmp(token,";")==0){
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
return es;
}
es=expression(p);
if(es>0) return es;
if(es==0&&strcmp(token,";")==0){
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
return es;
}
else{
return es=4;
}
}
int call_stat(node* fa){
node* p=fa->addSon("");
int es=0;
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,"ID")) return es=3;
out(p);
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,"(")) return es=5;
out(p);
fscanf(fin,"%s %s
",token,token1);
if(strcmp(token,")")) return es=6;
out(p);
fscanf(fin,"%s %s
",token,token1);
return es;
}
int expression(node* fa){
node* p=fa->addSon("");
int es=0,fileadd;
char token2[20],token3[40];
if(strcmp(token,"ID")==0){
if(!se.count(token1)) return es=12;
fileadd=ftell(fin);
fscanf(fin,"%s %s
",token2,token3);
// printf("%s %s
",token2,token3);...
if(strcmp(token2,"=")==0){
out(p);
// shift(p+1);
// fprintf(fout,"%s
",token2);
p->addSon(token2);
fscanf(fin,"%s %s
",token,token1);
es=bool_expr(p);
if(es>0) return es;
}
else{
fseek(fin,fileadd,0);
es=bool_expr(p);
if(es>0) return es;
}
}
else es=bool_expr(p+1);
return es;
}
int bool_expr(node* fa){
node* p=fa->addSon("");
int es=0;
es=additive_expr(p);
if(es>0) return es;
if(strcmp(token,">")==0||strcmp(token,">=")==0||strcmp(token,"0) return es;
}
return es;
}
int additive_expr(node* fa){
node* p=fa->addSon("");
int es=0;
es=term(p);
if(es>0) return es;
while(strcmp(token,"+")==0||strcmp(token,"-")==0){
out(p);
fscanf(fin,"%s %s",token,token1);
// printf("%s %s
",token,token1);
es=term(p);
if(es>0) return es;
}
return es;
}
int term(node*fa){
node* p=fa->addSon("");
int es=0;
es=factor(p);
if(es>0) return es;
while(strcmp(token,"*")==0||strcmp(token,"/")==0){
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=factor(p);
if(es>0) return es;
}
return es;
}
int factor(node* fa){
node* p=fa->addSon("");
int es=0;
if(strcmp(token,"(")==0){
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
es=expression(p);
if(es>0) return es;
if(strcmp(token,")")) return es=6;
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
}
else{
if(strcmp(token,"ID")==0||strcmp(token,"NUM")==0){
out(p);
fscanf(fin,"%s %s
",token,token1);
// printf("%s %s
",token,token1);
return es;
}
else{
es=7;
return es;
}
}
return es;
}
int main()
{
if(!init()){cout<