[NOI2000]程序分析器

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，求该程序所执行的语句数(执行条件语句不论是否成功转移，仅记为执行一条语句)。

为一个TB语言程序P，语句数不超过100行。

P中每条语句的长度不超过20个字符。

P中转移语句里GO后面的行号一定有对应的语句。

P中可能有多个不同行号的结束语句。

P中行号最大的语句一定是结束语句。

P中的行号都不大于3000。

输入文件不一定是按行号递增顺序给出P的。

10 $\rightarrow$ 20 $\rightarrow$ 30 $\rightarrow$ 40 $\rightarrow$ 50 $\rightarrow$ 20 $\rightarrow$ 30 $\rightarrow$ 40 $\rightarrow$ 50 $\rightarrow$ 20 $\rightarrow$ 60

#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> const int MAXS=101,MAXL=3001,PLUS=0,PRINT=1,GO=2,IFGO=3,END=4; using namespace std; struct statement { statement *next; int line,var,value,goline,type; }L[MAXS]; statement *Skip[MAXL]; int N,l,cnt=1; int Vars[30]; inline int cmp(const void *a,const void *b) { return ((statement *)a)->line-((statement *)b)->line; } void init() { int l,i;char C[MAXL]; while (scanf("%d",&l)!=EOF) { L[++N].line=l; l=getchar(); scanf("%s",C); if (C[1]=='?') //print { L[N].var=C[0]-'A'; L[N].type=PRINT; } else if (C[1]=='+') //plus { L[N].var=C[0]-'A'; L[N].type=PLUS; sscanf(C+2,"%d",&l); L[N].value=l; } else if (C[1]=='O') //GO { L[N].type=GO; scanf("%d",&l); L[N].goline=l; } else if (C[1]=='F') //IF { l=getchar();l=getchar(); L[N].type=IFGO; L[N].var=l-'A'; l=getchar(); scanf("%d",&l); L[N].value=l; l=getchar();l=getchar();l=getchar();l=getchar(); //<S>GO<S> scanf("%d",&l); L[N].goline=l; } else L[N].type=END; } qsort(L+1,N,sizeof(L[0]),cmp); for (i=1;i<N;i++) { L[i].next=&L[i+1]; Skip[L[i].line]=&L[i]; } Skip[L[i].line]=&L[i]; } bool execute() { for (statement *p=&L[1];p;cnt++) { if (cnt>10000000) return false; if (p->type==PLUS) Vars[p->var]+=p->value; else if (p->type==END) return true; else if (p->type==GO) { p=Skip[p->goline]; continue; } else if (p->type==IFGO && Vars[p->var]==p->value) { p=Skip[p->goline]; continue; } p=p->next; } return false; } int main() { init(); if (!execute())cnt=-1; printf("%d",cnt); return 0; }

详情