程序分析器
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;
}
正文
[TOJ]1203程序分析器2005-06-07 18:50:00
【评论】 【打印】 【字体：大 中 小】 本文链接：http://blog.pfan.cn/rickone/1545.html
阅读(7248) | 评论(0)
版权声明：编程爱好者网站为此博客服务提供商，如本文牵涉到版权问题，编程爱好者网站不承担相关责任，如有版权问题请直接与本文作者联系解决。谢谢！
评论