fsm.c (14777B)
1 #include <stdio.h> 2 #include <string.h> 3 #include<stdlib.h> 4 5 //////////////////// GLOBALS ///////////////////////////// 6 7 #define MAXSTATE 130 8 #define MAXLINE 1010 9 10 const int EOFCHAR=128, ALLCHAR=129, NOINPUT=0; 11 12 // Comments_1: 13 // eksigeiste ti simainoun ta diafora fields tou struct state 14 typedef struct { 15 char * name; 16 int number; 17 int accepting; 18 int nextstate[MAXSTATE]; 19 } state ; 20 21 int numstates=0, statesize=0, trace=0, tracein=0; 22 state ** states; 23 24 typedef struct entry { 25 struct entry *next; 26 state * contents; 27 } tableEntry; 28 29 tableEntry * table = NULL; //Comments_2: Se ti xrisimeuei auto? 30 31 char line[MAXLINE]; 32 char filename[300]; 33 int pos=0, linenum=0; 34 char symbol[110]; 35 FILE *fin; 36 37 //////////////////// LOOKUP ////////////////////////////// 38 // Comments_3: Ti apotelesma exei auti i sunartisi? 39 state *lookup(char *name) { 40 41 //Comments_4: Ti akribws kanei auto to loop? 42 if (table != NULL) { 43 tableEntry *runner = table; 44 while (runner != NULL) { 45 if (strcmp(runner->contents->name, name) == 0) 46 return runner->contents; 47 runner = runner->next; 48 } 49 } 50 51 52 // Comments_5: Pote ekteleitai o parakatw kwdikas (mexri to telos tis sunartisis) 53 // kai ti apotelesmata/synepeies exei? 54 state *p= (state*) malloc(1*sizeof(state)); 55 p->name=strdup(name); 56 numstates+=1; 57 58 int i; // Comments_6: Giati einai aparaitito auto to if-statement? 59 if (numstates>=statesize) { 60 int newsz=statesize*2; 61 state ** newst=(state **) malloc(newsz*sizeof(state *)); 62 for (i=0; i<numstates; i+=1) 63 newst[i]=states[i]; 64 free(states); 65 states=newst; 66 statesize=newsz; 67 } 68 69 states[numstates]=p; 70 p->number=numstates; 71 p->accepting=0; 72 for (i=0; i<MAXSTATE; i+=1) { 73 p->nextstate[i]=0; 74 } 75 tableEntry * newEntry = (tableEntry *) malloc (1*sizeof( tableEntry)); 76 newEntry->contents = p; 77 newEntry->next = table; 78 table = newEntry; 79 return p; 80 } 81 82 83 /////////////////// LOWER /////////////////////////////// 84 85 // Comments_7: Perigrapste ti apotelesma exei i ektelesi autis tis sunartisis 86 87 void lower(char *s) { 88 int i; 89 for (i=0; 1; i+=1) { 90 char c=s[i]; 91 if (c==0) 92 break; 93 if (c>='A' && c<='Z') 94 s[i]=c+'a'-'A'; 95 } 96 } 97 98 //////////////////// DECODE /////////////////////////////// 99 100 int decode(char *s) { 101 if (s[0]=='\\') 102 return s[1]; 103 if (s[0]=='*' && s[1]==0) 104 return ALLCHAR; 105 if (strcasecmp(s, "EOF")==0) 106 return EOFCHAR; 107 if (s[1]==0) 108 return s[0]; 109 fprintf(stderr, "fsm: Line %d of %s: '%s' is not a valid character representation\n", linenum, filename, s); 110 exit(1); 111 return 0; 112 } 113 114 //////////////////// CHARSTRING /////////////////////////// 115 116 char *charstring(int c) { 117 static char s[10]; 118 if (c==ALLCHAR) return "ALL"; 119 if (c==EOFCHAR) return "EOF"; 120 if (c==NOINPUT) return "NONE"; 121 if (c=='\t') return "\\t"; 122 if (c=='\n') return "\\n"; 123 if (c==' ') return "\\s"; 124 if (c>' ' && c<127) { 125 s[0]=c; 126 s[1]=0; 127 return s; 128 } 129 sprintf(s, "\\%03o", c); 130 return s; 131 } 132 133 ///////////////////// VALIDSTATE /////////////////////////// 134 135 // Comments_8: Ti apotelesma exei auti i sunartisi? 136 137 int validstate(char *s) { 138 int i; 139 for (i=0; 1; i+=1) { 140 char c=s[i]; 141 if (c==0) 142 return 1; 143 if (c>='a' && c<='z' || c>='A' && c<='Z' || c>='0' && c<='9') 144 continue; 145 if (c=='$' || c=='_' || c=='.') 146 continue; 147 return 0; 148 } 149 } 150 151 /////////////////////// SNEAKCH //////////////////////////// 152 153 // Comments_9: Poios einai o skopos autis tis sunartisis. Ti epistrefei? 154 155 char sneakch() { 156 char c=line[pos]; 157 pos+=1; 158 while (c>0 && c<=' ' && c!='\n') { 159 c=line[pos]; 160 pos+=1; 161 } 162 pos-=1; 163 return c; 164 } 165 166 /////////////////////// GETSYM ////////////////////////////// 167 // Comments_10: Poios einai o skopos autis tis sunartisis. 168 169 void getsym() { 170 int len=0; 171 char c=line[pos]; 172 pos+=1; 173 while (c>0 && c<=' ' && c!='\n') { 174 c=line[pos]; 175 pos+=1; 176 } 177 symbol[0]=c; 178 symbol[1]=0; 179 switch (c) { 180 case 0: { 181 pos-=1; 182 fprintf(stderr, "fsm: Line %d of %s: Line Too Long\n", linenum, filename); 183 exit(1); 184 } 185 case '\n': pos-=1; 186 return; 187 case 'a': case 'h': case 'o': case 'v': case 'C': case 'J': case 'Q': case 'X': case '4': case '_': 188 case 'b': case 'i': case 'p': case 'w': case 'D': case 'K': case 'R': case 'Y': case '5': case '.': 189 case 'c': case 'j': case 'q': case 'x': case 'E': case 'L': case 'S': case 'Z': case '6': 190 case 'd': case 'k': case 'r': case 'y': case 'F': case 'M': case 'T': case '0': case '7': 191 case 'e': case 'l': case 's': case 'z': case 'G': case 'N': case 'U': case '1': case '8': 192 case 'f': case 'm': case 't': case 'A': case 'H': case 'O': case 'V': case '2': case '9': 193 case 'g': case 'n': case 'u': case 'B': case 'I': case 'P': case 'W': case '3': case '$': 194 { 195 while (c>='a' && c<='z' || c>='A' && c<='Z' || c>='0' && c<='9' || c=='$' || c=='_' || c=='.') { 196 symbol[len]=c; 197 len+=1; 198 if (len>100) { 199 symbol[10]=0; 200 fprintf(stderr, "fsm: Line %d of %s: Symbol '%s...' too long\n", linenum, filename, symbol); 201 exit(1); 202 } 203 c=line[pos]; 204 pos+=1; 205 } 206 pos-=1; 207 symbol[len]=0; 208 return; 209 } 210 case '-': { 211 if (line[pos]=='>') { 212 pos+=1; 213 symbol[1]='>'; 214 symbol[2]=0; 215 } 216 return; 217 } 218 case '/': { 219 if (line[pos]=='/') { 220 pos-=1; 221 line[pos]='\n'; 222 line[pos+1]=0; 223 symbol[0]='\n'; 224 } 225 return; 226 } 227 case '\\': { 228 if (line[pos]>' ' && line[pos]<127) { 229 c=line[pos]; 230 pos+=1; 231 if (c=='n') 232 c='\n'; 233 else if (c=='t') 234 c='\t'; 235 else if (c=='s') 236 c=' '; 237 else if (c>='0' && c<='7') { 238 int n=0; 239 while (c>='0' && c<='7') { 240 n=n*8+c-'0'; 241 c=line[pos]; 242 pos+=1; 243 } 244 pos-=1; 245 c=n; 246 } 247 symbol[1]=c; 248 symbol[2]=0; 249 } 250 } 251 } 252 } 253 254 //////////////////// PARSEARGS ////////////////////////////////// 255 256 // Comments_11: Poios einai o skopos autis tis sunartisis? 257 258 void parseargs(int argc, char *argv[]) { 259 filename[0]=0; 260 int i; 261 for (i=1; i<argc; i+=1) 262 if (argv[i][0]!='-') 263 strcpy(filename, argv[i]); 264 else if (strcasecmp(argv[i], "-trace")==0) 265 trace=1; 266 else if (strcasecmp(argv[i], "-list")==0) 267 tracein=1; 268 269 if (filename[0]!=0 && strstr(filename, ".")==NULL) 270 strcat(filename, ".fsm"); 271 272 fin=stdin; 273 274 if (filename[0]!=0) { 275 fin=fopen(filename, "r"); 276 if (fin==NULL) { 277 fprintf(stderr, "fsm: can not open input file '%s'\n", filename); 278 exit(1); 279 } 280 } 281 else 282 strcpy(filename, "<stdin>"); 283 } 284 285 //////////////////// MAIN /////////////////////////////////// 286 287 int main (int argc, char *argv[]) { 288 289 int i, len; 290 char c; 291 int startstate=-1, anyaccepting=0; 292 parseargs(argc, argv); 293 294 numstates=0; 295 states=(state **) malloc(2*sizeof(state *)); 296 statesize=2; 297 state * currstate=NULL; 298 state *s0=(state *) malloc(1*sizeof(state)); 299 s0->name="<DEAD>"; 300 s0->accepting=0; 301 s0->number=0; 302 303 for (i=0; i<MAXSTATE; i+=1) { 304 s0->nextstate[i]=0; 305 } 306 states[0]=s0; 307 308 // Comments_12: Perigrapste se 2-3 grammes to skopo autou tou while loop. 309 while (1) { 310 char *s=fgets(line, MAXLINE, fin); 311 pos=0; 312 if (s==NULL) 313 break; 314 linenum+=1; 315 getsym(); 316 if (symbol[0]=='\n') 317 continue; 318 len=strlen(symbol); 319 c=sneakch(); 320 if (c==':') { // Comments_13: Perigrapste to skopo autou tou if (c==':') 321 lower(symbol); 322 if (!validstate(symbol)) { 323 fprintf(stderr, "fsm: Line %d of %s, '%s' is not a valid state name\n", linenum, filename, symbol); 324 exit(1); 325 } 326 currstate=lookup(symbol); 327 getsym(); 328 getsym(); 329 if (symbol[0]=='\n') 330 continue; 331 } 332 else if (c=='=') { // Comments_14: Perigrapste to skopo autou tou else if (c=='=') 333 if (strcasecmp(symbol, "START")==0) { 334 getsym(); 335 getsym(); 336 lower(symbol); 337 if (!validstate(symbol)) { 338 fprintf(stderr, "fsm: Line %d of %s, '%s' is not a valid state name\n", linenum, filename, symbol); 339 exit(1); 340 } 341 if (startstate!=-1) { 342 fprintf(stderr, "fsm: Line %d of %s, Start state specified twice\n", linenum, filename); 343 exit(1); 344 } 345 state *s=lookup(symbol); 346 startstate=s->number; 347 if (tracein) printf("START STATE IS '%s'\n", symbol); 348 getsym(); 349 if (symbol[0]!='\n') { 350 fprintf(stderr, "fsm: Line %d of %s, Line too long, '%s' is out of place\n", linenum, filename, symbol); 351 exit(1); 352 } 353 continue; 354 } 355 fprintf(stderr, "fsm: Line %d of %s, '%s=...' is not permitted\n", linenum, filename, symbol); 356 exit(1); 357 } 358 else if (c=='(') { // Comments_15: Perigrapste to skopo autou tou else if (c=='(') 359 getsym(); 360 getsym(); 361 int ok=strcasecmp(symbol, "OK")==0; 362 if (ok) { 363 getsym(); 364 ok=symbol[0]==')'; 365 } 366 if (ok) { 367 getsym(); 368 ok=symbol[0]==':'; 369 } 370 pos=0; 371 getsym(); 372 if (ok) { 373 lower(symbol); 374 if (!validstate(symbol)) { 375 fprintf(stderr, "fsm: Line %d of %s, '%s' is not a valid state name\n", linenum, filename, symbol); 376 exit(1); 377 } 378 currstate=lookup(symbol); 379 getsym(); 380 getsym(); 381 getsym(); 382 getsym(); 383 getsym(); 384 anyaccepting=1; 385 currstate->accepting=1; 386 if (tracein) printf("STATE '%s' IS AN ACCEPTING STATE\n", currstate->name); 387 if (symbol[0]=='\n') 388 continue; 389 } 390 } 391 if (currstate==NULL) { 392 fprintf(stderr, "fsm: Line %d of %s, no current state specified\n", linenum, filename); 393 exit(1); 394 } 395 if (tracein) 396 printf("STATE '%s' ", currstate->name); 397 int nins=0; 398 int said[MAXSTATE]; 399 for (i=0; i<MAXSTATE; i+=1) 400 said[i]=0; 401 if (strcasecmp(symbol, "none")==0) { 402 nins=1; 403 said[NOINPUT]=1; 404 if (tracein) 405 printf("CONSUME NO INPUT: "); 406 getsym(); 407 if (strcmp(symbol, "->")!=0) { 408 fprintf(stderr, "fsm: Line %d of %s, no inputs allowed after stating NONE\n", linenum, filename); 409 exit(1); 410 } 411 } // Comments_16: Perigrapste se 2-3 grammes to skopo autou tou while loop. 412 while (strcmp(symbol, "->")!=0 && symbol[0]!='\n') { 413 char in1[300], in2[300]; 414 strcpy(in1, symbol); 415 in2[0]=0; 416 nins+=1; 417 getsym(); 418 if (strcmp(symbol, "-")==0) { 419 if (in1[1]!=0 || in1[0]=='*') { 420 fprintf(stderr, "fsm: Line %d of %s, symbol '%s' not allowed in a range\n", linenum, filename, in1); 421 exit(1); 422 } 423 getsym(); 424 if (strcmp(symbol, "-")==0 || strcmp(symbol, "->")==0) { 425 fprintf(stderr, "fsm: Line %d of %s, symbol '%s' not allowed after symbol '-'\n", linenum, filename, symbol); 426 exit(1); 427 } 428 if (symbol[0]=='\n') { 429 fprintf(stderr, "fsm: Line %d of %s, Line incomplete\n", linenum, filename, symbol); 430 exit(1); 431 } 432 strcpy(in2, symbol); 433 if (in2[1]!=0 || in2[0]=='*') { 434 fprintf(stderr, "fsm: Line %d of %s, symbol '%s' not allowed in a range\n", linenum, filename, in2); 435 exit(1); 436 } 437 getsym(); 438 } 439 int c1=decode(in1); 440 if (in2[0]!=0) { 441 int c2=decode(in2); 442 if (c1>c2) { 443 char x1[10]; 444 strcpy(x1, charstring(c1)); 445 fprintf(stderr, "fsm: Line %d of %s, range %s - %s is empty or out of order\n", linenum, filename, x1, charstring(c2)); 446 exit(1); 447 } 448 for (i=c1; i<=c2; i+=1) 449 said[i]=1; 450 if (tracein) 451 printf("INPUTS %s ", charstring(c1)); 452 if (tracein) 453 printf("TO %s: ", charstring(c2)); 454 } 455 else if (c1==-1) { 456 said[EOFCHAR]=1; 457 if (tracein) 458 printf("AT EOF: "); 459 } 460 else if (c1==-2) { 461 said[ALLCHAR]=1; 462 if (tracein) 463 printf("ALL OTHER INPUTS: "); 464 } 465 else { 466 said[c1]=1; 467 if (tracein) 468 printf("INPUT %s ", charstring(c1)); 469 } 470 } 471 if (symbol[0]=='\n') { 472 fprintf(stderr, "fsm: Line %d of %s, line incomplete, no '->'\n", linenum, filename); 473 exit(1); 474 } 475 if (nins==0) { 476 fprintf(stderr, "fsm: Line %d of %s, line incomplete, no inputs specified\n", linenum, filename); 477 exit(1); 478 } 479 getsym(); 480 if (symbol[0]=='\n') { 481 fprintf(stderr, "fsm: Line %d of %s, line incomplete, no new state\n", linenum, filename); 482 exit(1); 483 } 484 lower(symbol); 485 if (!validstate(symbol)) { 486 fprintf(stderr, "fsm: Line %d of %s, '%s' is not a valid state name\n", linenum, filename, symbol); 487 exit(1); 488 } 489 state *newst=lookup(symbol); 490 if (tracein) 491 printf("NEW STATE '%s'", symbol); 492 char out[300]; 493 out[0]=0; 494 getsym(); 495 if (strcasecmp(symbol, "none")==0) { 496 getsym(); 497 if (symbol[0]!='\n') { 498 fprintf(stderr, "fsm: Line %d of %s, line too long, '%s' out of place\n", linenum, filename, symbol); 499 exit(1); 500 } 501 } 502 for (i=0; i<MAXSTATE; i+=1) 503 if (said[i]) { 504 if (currstate->nextstate[i]!=0) { 505 fprintf(stderr, "fsm: Line %d of %s, Non-Deterministic: state='%s', input='%s'\n", linenum, filename, currstate->name, charstring(i)); 506 exit(1); 507 } 508 currstate->nextstate[i]=newst->number; 509 } 510 if (tracein) 511 printf("\n"); 512 if (symbol[0]!='\n') { 513 fprintf(stderr, "fsm: Line %d of %s, line too long, '%s' out of place\n", linenum, filename, symbol); 514 exit(1); 515 } 516 } 517 for (i=1; i<=numstates; i+=1) { 518 state *s=states[i]; 519 int none=s->nextstate[NOINPUT], alls=s->nextstate[ALLCHAR]; 520 int j; 521 for (j=0; j<MAXSTATE; j+=1) { 522 if (j!=NOINPUT) { 523 if (s->nextstate[j]==0) { 524 s->nextstate[j]=alls; 525 } 526 else if (none) { 527 fprintf(stderr, "fsm: in %s, Non-Deterministic, state='%s', no input and input='%s'\n", filename, s->name, charstring(j)); 528 exit(1); 529 } 530 } 531 } 532 } 533 534 fclose(fin); 535 536 if (startstate==-1) 537 startstate=1; 538 if (startstate>numstates) { 539 fprintf(stderr, "fsm: in %s, no start state\n", filename); 540 exit(1); 541 } 542 543 while (1) { 544 currstate=states[startstate]; // start at the start state 545 int inc=0; 546 // Comments_17: Perigrapste se 3-4 grammes ti leitourgia autou tou loop. 547 while (1) { 548 int nsn=currstate->nextstate[NOINPUT]; 549 if (nsn!=0) { 550 if (trace) 551 printf("%s () -> ", currstate->name); 552 currstate=states[nsn]; 553 if (trace) 554 printf("%s ", currstate->name); 555 if (trace) 556 printf("\n"); 557 continue; 558 } 559 if (inc==EOFCHAR) 560 break; 561 562 inc=getchar(); 563 if (inc==EOF) 564 inc=EOFCHAR; 565 nsn=currstate->nextstate[inc]; 566 if (nsn==0) { 567 if (inc!=EOFCHAR) { 568 anyaccepting=0; 569 fprintf(stderr, "fsm: in %s, state '%s' input %s not accepted\n", filename, currstate->name, charstring(inc)); 570 exit(2); 571 } 572 break; 573 } 574 if (trace) 575 printf("%s %s -> ", currstate->name, charstring(inc)); 576 currstate=states[nsn]; 577 if (trace) 578 printf("%s ", currstate->name); 579 if (trace) 580 printf("\n"); 581 } 582 if (anyaccepting) { 583 if (currstate->accepting) 584 printf("YES\n"); 585 else 586 printf("NO\n"); 587 } 588 break; 589 } 590 if (tracein) 591 printf("Done\n"); 592 return 0; 593 } 594