程序分析器 Time Limit:2s Memory Limit:2000k Total Submit:26 Accepted:4 -------------------------------------------------------------------------------- Problem Tiny Basm语言(简称为TB语言)的巴科斯-瑙尔范式(BNF)为： <程序> ::= <语句> ¿ { <语句> ¿ } <语句> ::= <行号> ÿ <语句体> <语句体> ::= <累加语句> | <输出语句> | <转移语句> | <条件语句> | <结束语句> <累加语句> ::= <变量> + <整数> <输出语句> ::= <变量> ? <转移语句> ::= GO ÿ <行号> <条件语句> ::= IF ÿ <变量> = <整数> ÿ <转移语句> <结束语句> ::= END <变量> ::= <字母> <行号> ::= <整数> <整数> ::= <数字> { <数字> } <字母> ::= A|B|C|D|E|F|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U|V|W|X|Y|Z <数字> ::= 0|1|2|3|4|5|6|7|8|9 注：其中“::=”表示定义为，“|”表示或，{}内的项可以重复任意多次或不出现，“ÿ”表示空格(一个字符，ASCII码为32)，“¿”表示回车/换行(两个字符，ASCII码分别为13和10)。 错误语句示例(在输入文件中不会出现任何错误语句)： 10ÿA+1.5 （不符合累加语句的定义，所加的不是整数） 20ÿAÿ? （不符合输出语句的定义，多加了一个空格） 30ÿIFÿA=BÿGOÿ10 （不符合条件语句的定义，不应变量=变量） TB程序的执行： l 程序从行号最小的一条语句开始执行，在未遇到条件语句时按行号由小至大顺序执行。 l 所有变量在程序执行前被自动初始化为0。 l 累加语句将语句中变量的值加上语句中的整数送回该变量。 l 输出语句将语句中变量的值在监视器上显示出来。 l 执行条件语句时，当且仅当该语句中的变量与紧跟在等号后面的整数值相等，后面的转移语句才被执行。该语句中的所有整数值至多为4位。 l 转移语句被执行后，程序将转去执行GO后面指定的行号的语句。 l 当程序执行结束语句后，结束整个程序的执行。 l 假设该系统能处理任意大小的整数，而不会发生溢出。 请编程，对于给定的TB语言程序P，求该程序所执行的语句数(执行条件语句不论是否成功转移，仅记为执行一条语句)。 Input l 输入为一个TB语言程序P，语句数不超过100行。 l P中每条语句的长度不超过20个字符。 l P中转移语句里GO后面的行号一定有对应的语句。 l P中可能有多个不同行号的结束语句。 l P中行号最大的语句一定是结束语句。 l P中的行号都不大于3000。 输入文件不一定是按行号递增顺序给出P的。 当一行只有一个数-1时，表示一组数据输入结束 Output 输出文件有且仅有一行： 如果程序能够正常结束，输出该程序所执行的语句数； 如果程序不能正常结束，输出-1 Sample Input 10 A+1 20 IF A=5 GO 60 60 END 30 A+2 40 A? 50 GO 20 -1 Sample Output 11 Source NOI2000 #include<iostream.h> #include<stdio.h> enum opn{add,compare,end,print,go}; struct stc { int line; opn tag; int op[3]; stc *next; }; class clspgm { public: clspgm(); ~clspgm(); void display(); void run(); protected: stc *head,*pc; int v[26]; }; int getline(char *str) { char c; while(1) { c=getc(stdin); if(c==EOF)return 0; if(c=='\n')break; *str++=c; } *str='\0'; return 1; } clspgm::clspgm() { char str[20]; stc *p,*sp,*prep; head=pc=NULL; int t,i; for(i=0;i<26;++i)v[i]=0; while(1) { getline(str); if(str[0]=='-')break; p=new stc; for(t=0,i=0;str[i]!=' ';++i)t=t*10+str[i]-'0'; p->line=t;//line number ++i; if(str[i]=='I') { p->tag=compare; i+=3; p->op[0]=str[i]-'A'; for(t=0,i+=2;str[i]!=' ';++i)t=t*10+str[i]-'0'; p->op[1]=t; for(t=0,i+=4;str[i]!='\0';++i)t=t*10+str[i]-'0'; p->op[2]=t; } else if(str[i]=='E') { p->tag=end; } else if(str[i]=='G') { p->tag=go; for(t=0,i+=3;str[i]!='\0';++i)t=t*10+str[i]-'0'; p->op[0]=t; } else if(str[i+1]=='+') { p->tag=add; p->op[0]=str[i]-'A'; for(t=0,i+=2;str[i]!='\0';++i)t=t*10+str[i]-'0'; p->op[1]=t; } else { p->tag=print; p->op[0]=str[i]-'A'; } if(head==NULL) { p->next=NULL; head=p; } else { for(prep=NULL,sp=head;sp&&sp->line<p->line;prep=sp,sp=sp->next); if(prep==NULL) { p->next=head; head=p; } else { p->next=sp; prep->next=p; } } } } clspgm::~clspgm() { stc *p,*prep; for(prep=head,p=head->next;!p;prep=p,p=p->next)delete prep; delete prep; } void clspgm::display() { stc *p=head; while(p) { cout<<p->line<<":"; switch(p->tag) { case add:cout<<"Add "<<(char)('A'+p->op[0])<<" "<<p->op[1]<<endl;break; case compare:cout<<"If "<<(char)('A'+p->op[0])<<"="<<p->op[1]<<" Go "<<p->op[2]<<endl;break; case end:cout<<"End."<<endl;break; case print:cout<<"Print "<<(char)('A'+p->op[0])<<endl;break; case go:cout<<"Go "<<p->op[0]<<endl;break; } p=p->next; } } void clspgm::run() { stc *p; int count=1; pc=head; while(pc->tag!=end) { switch(pc->tag) { case add:v[pc->op[0]]+=pc->op[1];pc=pc->next;break; case go:for(p=head;p->line!=pc->op[0];p=p->next);pc=p;break; case compare: if(v[pc->op[0]]==pc->op[1]) { for(p=head;p->line!=pc->op[2];p=p->next);pc=p; } else pc=pc->next; break; default:pc=pc->next; } if(++count>30000) { cout<<(-1)<<endl; return; } } cout<<count<<endl; } int main() { clspgm program; program.display(); program.run(); return 0; }
评论