00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012 #include <stdio.h>
00013 #include <stdarg.h>
00014 #include <string.h>
00015 #include <ctype.h>
00016 #include <stdlib.h>
00017
00018 #ifndef __WIN32__
00019 # if defined(_WIN32) || defined(WIN32)
00020 # define __WIN32__
00021 # endif
00022 #endif
00023
00024 #ifndef __WIN32__
00025 # include <unistd.h>
00026 #endif
00027
00028
00029 #define PRIVATE
00030
00031 #ifdef TEST
00032 #define MAXRHS 5
00033 #else
00034 #define MAXRHS 1000
00035 #endif
00036
00037 char *msort();
00038
00039
00040
00041 struct action *Action_new();
00042 struct action *Action_sort();
00043
00044
00045 void myassert();
00046 #ifndef NDEBUG
00047 # define assert(X) if(!(X))myassert(__FILE__,__LINE__)
00048 #else
00049 # define assert(X)
00050 #endif
00051
00052
00053 void FindRulePrecedences();
00054 void FindFirstSets();
00055 void FindStates();
00056 void FindLinks();
00057 void FindFollowSets();
00058 void FindActions();
00059
00060
00061 void Configlist_init();
00062 struct config *Configlist_add();
00063 struct config *Configlist_addbasis();
00064 void Configlist_closure();
00065 void Configlist_sort();
00066 void Configlist_sortbasis();
00067 struct config *Configlist_return();
00068 struct config *Configlist_basis();
00069 void Configlist_eat();
00070 void Configlist_reset();
00071
00072
00073 void ErrorMsg(const char *, int,const char *, ...);
00074
00075
00076 struct s_options {
00077 enum { OPT_FLAG=1, OPT_INT, OPT_DBL, OPT_STR,
00078 OPT_FFLAG, OPT_FINT, OPT_FDBL, OPT_FSTR} type;
00079 char *label;
00080 void *arg;
00081 void(*func)();
00082
00083 char *message;
00084 };
00085 int OptInit();
00086 int OptNArgs();
00087 char *OptArg();
00088 void OptErr();
00089 void OptPrint();
00090
00091
00092 void Parse();
00093
00094
00095 struct plink *Plink_new();
00096 void Plink_add();
00097 void Plink_copy();
00098 void Plink_delete();
00099
00100
00101 void Reprint();
00102 void ReportOutput();
00103 void ReportTable();
00104 void ReportHeader();
00105 void CompressTables();
00106
00107
00108 void SetSize();
00109 char *SetNew();
00110 void SetFree();
00111
00112 int SetAdd();
00113 int SetUnion();
00114
00115 #define SetFind(X,Y) (X[Y])
00116
00117
00118
00119
00120
00121
00122 typedef enum {B_FALSE=0, B_TRUE} Boolean;
00123
00124
00125
00126 struct symbol {
00127 char *name;
00128 int index;
00129 enum {
00130 TERMINAL,
00131 NONTERMINAL
00132 } type;
00133 struct rule *rule;
00134 struct symbol *fallback;
00135 int prec;
00136 enum e_assoc {
00137 LEFT,
00138 RIGHT,
00139 NONE,
00140 UNK
00141 } assoc;
00142 char *firstset;
00143 Boolean lambda;
00144 char *destructor;
00145
00146 int destructorln;
00147 char *datatype;
00148
00149 int dtnum;
00150
00151
00152 };
00153
00154
00155
00156 struct rule {
00157 struct symbol *lhs;
00158 char *lhsalias;
00159 int ruleline;
00160 int nrhs;
00161 struct symbol **rhs;
00162 char **rhsalias;
00163 int line;
00164 char *code;
00165 struct symbol *precsym;
00166 int index;
00167 Boolean canReduce;
00168 struct rule *nextlhs;
00169 struct rule *next;
00170 };
00171
00172
00173
00174
00175
00176
00177 struct config {
00178 struct rule *rp;
00179 int dot;
00180 char *fws;
00181 struct plink *fplp;
00182 struct plink *bplp;
00183 struct state *stp;
00184 enum {
00185 COMPLETE,
00186 INCOMPLETE
00187 } status;
00188 struct config *next;
00189 struct config *bp;
00190 };
00191
00192
00193 struct action {
00194 struct symbol *sp;
00195 enum e_action {
00196 SHIFT,
00197 ACCEPT,
00198 REDUCE,
00199 ERROR,
00200 CONFLICT,
00201 SH_RESOLVED,
00202 RD_RESOLVED,
00203 NOT_USED
00204 } type;
00205 union {
00206 struct state *stp;
00207 struct rule *rp;
00208 } x;
00209 struct action *next;
00210 struct action *collide;
00211 };
00212
00213
00214
00215 struct state {
00216 struct config *bp;
00217 struct config *cfp;
00218 int index;
00219 struct action *ap;
00220 int nTknAct, nNtAct;
00221 int iTknOfst, iNtOfst;
00222 int iDflt;
00223 };
00224 #define NO_OFFSET (-2147483647)
00225
00226
00227
00228
00229 struct plink {
00230 struct config *cfp;
00231 struct plink *next;
00232 };
00233
00234
00235
00236
00237
00238 struct lemon {
00239 struct state **sorted;
00240 struct rule *rule;
00241 int nstate;
00242 int nrule;
00243 int nsymbol;
00244 int nterminal;
00245 struct symbol **symbols;
00246 int errorcnt;
00247 struct symbol *errsym;
00248 char *name;
00249 char *arg;
00250 char *tokentype;
00251 char *vartype;
00252 char *start;
00253 char *stacksize;
00254 char *include;
00255 int includeln;
00256 char *error;
00257 int errorln;
00258 char *overflow;
00259 int overflowln;
00260 char *failure;
00261 int failureln;
00262 char *accept;
00263 int acceptln;
00264 char *extracode;
00265 int extracodeln;
00266 char *tokendest;
00267 int tokendestln;
00268 char *vardest;
00269 int vardestln;
00270 char *filename;
00271 char *outname;
00272 char *tokenprefix;
00273 int nconflict;
00274 int tablesize;
00275 int basisflag;
00276 int has_fallback;
00277 char *argv0;
00278 };
00279
00280 #define MemoryCheck(X) if((X)==0){ \
00281 extern void memory_error(); \
00282 memory_error(); \
00283 }
00284
00285
00286
00287
00288
00289
00290
00291
00292
00293
00294
00295
00296
00297
00298
00299
00300 char *Strsafe();
00301
00302 void Strsafe_init();
00303 int Strsafe_insert();
00304 char *Strsafe_find();
00305
00306
00307
00308 struct symbol *Symbol_new();
00309 int Symbolcmpp(const void *void_a, const void *void_b);
00310 void Symbol_init();
00311 int Symbol_insert();
00312 struct symbol *Symbol_find();
00313 struct symbol *Symbol_Nth();
00314 int Symbol_count();
00315 struct symbol **Symbol_arrayof();
00316
00317
00318
00319 int Configcmp();
00320 struct state *State_new();
00321 void State_init();
00322 int State_insert();
00323 struct state *State_find();
00324 struct state **State_arrayof();
00325
00326
00327
00328 void Configtable_init();
00329 int Configtable_insert();
00330 struct config *Configtable_find();
00331 void Configtable_clear();
00332
00333
00334
00335
00336
00337
00338 struct action *Action_new(){
00339 static struct action *freelist = 0;
00340 struct action *new;
00341
00342 if( freelist==0 ){
00343 int i;
00344 int amt = 100;
00345 freelist = (struct action *)malloc( sizeof(struct action)*amt );
00346 if( freelist==0 ){
00347 fprintf(stderr,"Unable to allocate memory for a new parser action.");
00348 exit(1);
00349 }
00350 for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
00351 freelist[amt-1].next = 0;
00352 }
00353 new = freelist;
00354 freelist = freelist->next;
00355 return new;
00356 }
00357
00358
00359 static int actioncmp(ap1,ap2)
00360 struct action *ap1;
00361 struct action *ap2;
00362 {
00363 int rc;
00364 rc = ap1->sp->index - ap2->sp->index;
00365 if( rc==0 ) rc = (int)ap1->type - (int)ap2->type;
00366 if( rc==0 ){
00367 assert( ap1->type==REDUCE || ap1->type==RD_RESOLVED || ap1->type==CONFLICT);
00368 assert( ap2->type==REDUCE || ap2->type==RD_RESOLVED || ap2->type==CONFLICT);
00369 rc = ap1->x.rp->index - ap2->x.rp->index;
00370 }
00371 return rc;
00372 }
00373
00374
00375 struct action *Action_sort(ap)
00376 struct action *ap;
00377 {
00378
00379 ap = (struct action *)msort((char *)ap,(char **)(void *)&ap->next,actioncmp);
00380 return ap;
00381 }
00382
00383 void Action_add(app,type,sp,arg)
00384 struct action **app;
00385 enum e_action type;
00386 struct symbol *sp;
00387 char *arg;
00388 {
00389 struct action *new;
00390 new = Action_new();
00391 new->next = *app;
00392 *app = new;
00393 new->type = type;
00394 new->sp = sp;
00395 if( type==SHIFT ){
00396 new->x.stp = (struct state *)arg;
00397 }else{
00398 new->x.rp = (struct rule *)arg;
00399 }
00400 }
00401
00402
00403
00404
00405
00406
00407
00408
00409
00410 typedef struct acttab acttab;
00411 struct acttab {
00412 int nAction;
00413 int nActionAlloc;
00414 struct {
00415 int lookahead;
00416 int action;
00417 } *aAction,
00418 *aLookahead;
00419 int mnLookahead;
00420 int mnAction;
00421 int mxLookahead;
00422 int nLookahead;
00423 int nLookaheadAlloc;
00424 };
00425
00426
00427 #define acttab_size(X) ((X)->nAction)
00428
00429
00430 #define acttab_yyaction(X,N) ((X)->aAction[N].action)
00431
00432
00433 #define acttab_yylookahead(X,N) ((X)->aAction[N].lookahead)
00434
00435
00436 void acttab_free(acttab *p){
00437 free( p->aAction );
00438 free( p->aLookahead );
00439 free( p );
00440 }
00441
00442
00443 acttab *acttab_alloc(void){
00444 acttab *p = malloc( sizeof(*p) );
00445 if( p==0 ){
00446 fprintf(stderr,"Unable to allocate memory for a new acttab.");
00447 exit(1);
00448 }
00449 memset(p, 0, sizeof(*p));
00450 return p;
00451 }
00452
00453
00454
00455 void acttab_action(acttab *p, int lookahead, int action){
00456 if( p->nLookahead>=p->nLookaheadAlloc ){
00457 p->nLookaheadAlloc += 25;
00458 p->aLookahead = realloc( p->aLookahead,
00459 sizeof(p->aLookahead[0])*p->nLookaheadAlloc );
00460 if( p->aLookahead==0 ){
00461 fprintf(stderr,"malloc failed\n");
00462 exit(1);
00463 }
00464 }
00465 if( p->nLookahead==0 ){
00466 p->mxLookahead = lookahead;
00467 p->mnLookahead = lookahead;
00468 p->mnAction = action;
00469 }else{
00470 if( p->mxLookahead<lookahead ) p->mxLookahead = lookahead;
00471 if( p->mnLookahead>lookahead ){
00472 p->mnLookahead = lookahead;
00473 p->mnAction = action;
00474 }
00475 }
00476 p->aLookahead[p->nLookahead].lookahead = lookahead;
00477 p->aLookahead[p->nLookahead].action = action;
00478 p->nLookahead++;
00479 }
00480
00481
00482
00483
00484
00485
00486
00487
00488 int acttab_insert(acttab *p){
00489 int i, j, k, n;
00490 assert( p->nLookahead>0 );
00491
00492
00493
00494
00495
00496 n = p->mxLookahead + 1;
00497 if( p->nAction + n >= p->nActionAlloc ){
00498 int oldAlloc = p->nActionAlloc;
00499 p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
00500 p->aAction = realloc( p->aAction,
00501 sizeof(p->aAction[0])*p->nActionAlloc);
00502 if( p->aAction==0 ){
00503 fprintf(stderr,"malloc failed\n");
00504 exit(1);
00505 }
00506 for(i=oldAlloc; i<p->nActionAlloc; i++){
00507 p->aAction[i].lookahead = -1;
00508 p->aAction[i].action = -1;
00509 }
00510 }
00511
00512
00513
00514
00515
00516
00517
00518
00519 for(i=0; i<p->nAction+p->mnLookahead; i++){
00520 if( p->aAction[i].lookahead<0 ){
00521 for(j=0; j<p->nLookahead; j++){
00522 k = p->aLookahead[j].lookahead - p->mnLookahead + i;
00523 if( k<0 ) break;
00524 if( p->aAction[k].lookahead>=0 ) break;
00525 }
00526 if( j<p->nLookahead ) continue;
00527 for(j=0; j<p->nAction; j++){
00528 if( p->aAction[j].lookahead==j+p->mnLookahead-i ) break;
00529 }
00530 if( j==p->nAction ){
00531 break;
00532 }
00533 }else if( p->aAction[i].lookahead==p->mnLookahead ){
00534 if( p->aAction[i].action!=p->mnAction ) continue;
00535 for(j=0; j<p->nLookahead; j++){
00536 k = p->aLookahead[j].lookahead - p->mnLookahead + i;
00537 if( k<0 || k>=p->nAction ) break;
00538 if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
00539 if( p->aLookahead[j].action!=p->aAction[k].action ) break;
00540 }
00541 if( j<p->nLookahead ) continue;
00542 n = 0;
00543 for(j=0; j<p->nAction; j++){
00544 if( p->aAction[j].lookahead<0 ) continue;
00545 if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;
00546 }
00547 if( n==p->nLookahead ){
00548 break;
00549 }
00550 }
00551 }
00552
00553 for(j=0; j<p->nLookahead; j++){
00554 k = p->aLookahead[j].lookahead - p->mnLookahead + i;
00555 p->aAction[k] = p->aLookahead[j];
00556 if( k>=p->nAction ) p->nAction = k+1;
00557 }
00558 p->nLookahead = 0;
00559
00560
00561
00562 return i - p->mnLookahead;
00563 }
00564
00565
00566
00567
00568
00569 void myassert(file,line)
00570 char *file;
00571 int line;
00572 {
00573 fprintf(stderr,"Assertion failed on line %d of file \"%s\"\n",line,file);
00574 exit(1);
00575 }
00576
00577
00578
00579
00580
00581
00582
00583
00584
00585
00586
00587
00588
00589
00590
00591 void FindRulePrecedences(xp)
00592 struct lemon *xp;
00593 {
00594 struct rule *rp;
00595 for(rp=xp->rule; rp; rp=rp->next){
00596 if( rp->precsym==0 ){
00597 int i;
00598 for(i=0; i<rp->nrhs; i++){
00599 if( rp->rhs[i]->prec>=0 ){
00600 rp->precsym = rp->rhs[i];
00601 break;
00602 }
00603 }
00604 }
00605 }
00606 return;
00607 }
00608
00609
00610
00611
00612
00613
00614 void FindFirstSets(lemp)
00615 struct lemon *lemp;
00616 {
00617 int i;
00618 struct rule *rp;
00619 int progress;
00620
00621 for(i=0; i<lemp->nsymbol; i++){
00622 lemp->symbols[i]->lambda = B_FALSE;
00623 }
00624 for(i=lemp->nterminal; i<lemp->nsymbol; i++){
00625 lemp->symbols[i]->firstset = SetNew();
00626 }
00627
00628
00629 do{
00630 progress = 0;
00631 for(rp=lemp->rule; rp; rp=rp->next){
00632 if( rp->lhs->lambda ) continue;
00633 for(i=0; i<rp->nrhs; i++){
00634 if( rp->rhs[i]->lambda==B_FALSE ) break;
00635 }
00636 if( i==rp->nrhs ){
00637 rp->lhs->lambda = B_TRUE;
00638 progress = 1;
00639 }
00640 }
00641 }while( progress );
00642
00643
00644 do{
00645 struct symbol *s1, *s2;
00646 progress = 0;
00647 for(rp=lemp->rule; rp; rp=rp->next){
00648 s1 = rp->lhs;
00649 for(i=0; i<rp->nrhs; i++){
00650 s2 = rp->rhs[i];
00651 if( s2->type==TERMINAL ){
00652 progress += SetAdd(s1->firstset,s2->index);
00653 break;
00654 }else if( s1==s2 ){
00655 if( s1->lambda==B_FALSE ) break;
00656 }else{
00657 progress += SetUnion(s1->firstset,s2->firstset);
00658 if( s2->lambda==B_FALSE ) break;
00659 }
00660 }
00661 }
00662 }while( progress );
00663 return;
00664 }
00665
00666
00667
00668
00669
00670 PRIVATE struct state *getstate();
00671 void FindStates(lemp)
00672 struct lemon *lemp;
00673 {
00674 struct symbol *sp;
00675 struct rule *rp;
00676
00677 Configlist_init();
00678
00679
00680 if( lemp->start ){
00681 sp = Symbol_find(lemp->start);
00682 if( sp==0 ){
00683 ErrorMsg(lemp->filename,0,
00684 "The specified start symbol \"%s\" is not "
00685 "in a nonterminal of the grammar. \"%s\" will be used as the start "
00686 "symbol instead.",lemp->start,lemp->rule->lhs->name);
00687 lemp->errorcnt++;
00688 sp = lemp->rule->lhs;
00689 }
00690 }else{
00691 sp = lemp->rule->lhs;
00692 }
00693
00694
00695
00696
00697 for(rp=lemp->rule; rp; rp=rp->next){
00698 int i;
00699 for(i=0; i<rp->nrhs; i++){
00700 if( rp->rhs[i]==sp ){
00701 ErrorMsg(lemp->filename,0,
00702 "The start symbol \"%s\" occurs on the "
00703 "right-hand side of a rule. This will result in a parser which "
00704 "does not work properly.",sp->name);
00705 lemp->errorcnt++;
00706 }
00707 }
00708 }
00709
00710
00711
00712
00713 for(rp=sp->rule; rp; rp=rp->nextlhs){
00714 struct config *newcfp;
00715 newcfp = Configlist_addbasis(rp,0);
00716 SetAdd(newcfp->fws,0);
00717 }
00718
00719
00720
00721
00722 (void)getstate(lemp);
00723 return;
00724 }
00725
00726
00727
00728
00729 PRIVATE void buildshifts();
00730 PRIVATE struct state *getstate(lemp)
00731 struct lemon *lemp;
00732 {
00733 struct config *cfp, *bp;
00734 struct state *stp;
00735
00736
00737
00738 Configlist_sortbasis();
00739 bp = Configlist_basis();
00740
00741
00742 stp = State_find(bp);
00743 if( stp ){
00744
00745
00746
00747 struct config *x, *y;
00748 for(x=bp, y=stp->bp; x && y; x=x->bp, y=y->bp){
00749 Plink_copy(&y->bplp,x->bplp);
00750 Plink_delete(x->fplp);
00751 x->fplp = x->bplp = 0;
00752 }
00753 cfp = Configlist_return();
00754 Configlist_eat(cfp);
00755 }else{
00756
00757 Configlist_closure(lemp);
00758 Configlist_sort();
00759 cfp = Configlist_return();
00760 stp = State_new();
00761 MemoryCheck(stp);
00762 stp->bp = bp;
00763 stp->cfp = cfp;
00764 stp->index = lemp->nstate++;
00765 stp->ap = 0;
00766 State_insert(stp,stp->bp);
00767 buildshifts(lemp,stp);
00768 }
00769 return stp;
00770 }
00771
00772
00773
00774
00775 PRIVATE void buildshifts(lemp,stp)
00776 struct lemon *lemp;
00777 struct state *stp;
00778 {
00779 struct config *cfp;
00780 struct config *bcfp;
00781 struct config *new;
00782 struct symbol *sp;
00783 struct symbol *bsp;
00784 struct state *newstp;
00785
00786
00787
00788 for(cfp=stp->cfp; cfp; cfp=cfp->next) cfp->status = INCOMPLETE;
00789
00790
00791 for(cfp=stp->cfp; cfp; cfp=cfp->next){
00792 if( cfp->status==COMPLETE ) continue;
00793 if( cfp->dot>=cfp->rp->nrhs ) continue;
00794 Configlist_reset();
00795 sp = cfp->rp->rhs[cfp->dot];
00796
00797
00798
00799
00800 for(bcfp=cfp; bcfp; bcfp=bcfp->next){
00801 if( bcfp->status==COMPLETE ) continue;
00802 if( bcfp->dot>=bcfp->rp->nrhs ) continue;
00803 bsp = bcfp->rp->rhs[bcfp->dot];
00804 if( bsp!=sp ) continue;
00805 bcfp->status = COMPLETE;
00806 new = Configlist_addbasis(bcfp->rp,bcfp->dot+1);
00807 Plink_add(&new->bplp,bcfp);
00808 }
00809
00810
00811
00812 newstp = getstate(lemp);
00813
00814
00815
00816 Action_add(&stp->ap,SHIFT,sp,(char *)newstp);
00817 }
00818 }
00819
00820
00821
00822
00823 void FindLinks(lemp)
00824 struct lemon *lemp;
00825 {
00826 int i;
00827 struct config *cfp, *other;
00828 struct state *stp;
00829 struct plink *plp;
00830
00831
00832
00833
00834 for(i=0; i<lemp->nstate; i++){
00835 stp = lemp->sorted[i];
00836 for(cfp=stp->cfp; cfp; cfp=cfp->next){
00837 cfp->stp = stp;
00838 }
00839 }
00840
00841
00842
00843 for(i=0; i<lemp->nstate; i++){
00844 stp = lemp->sorted[i];
00845 for(cfp=stp->cfp; cfp; cfp=cfp->next){
00846 for(plp=cfp->bplp; plp; plp=plp->next){
00847 other = plp->cfp;
00848 Plink_add(&other->fplp,cfp);
00849 }
00850 }
00851 }
00852 }
00853
00854
00855
00856
00857
00858
00859 void FindFollowSets(lemp)
00860 struct lemon *lemp;
00861 {
00862 int i;
00863 struct config *cfp;
00864 struct plink *plp;
00865 int progress;
00866 int change;
00867
00868 for(i=0; i<lemp->nstate; i++){
00869 for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
00870 cfp->status = INCOMPLETE;
00871 }
00872 }
00873
00874 do{
00875 progress = 0;
00876 for(i=0; i<lemp->nstate; i++){
00877 for(cfp=lemp->sorted[i]->cfp; cfp; cfp=cfp->next){
00878 if( cfp->status==COMPLETE ) continue;
00879 for(plp=cfp->fplp; plp; plp=plp->next){
00880 change = SetUnion(plp->cfp->fws,cfp->fws);
00881 if( change ){
00882 plp->cfp->status = INCOMPLETE;
00883 progress = 1;
00884 }
00885 }
00886 cfp->status = COMPLETE;
00887 }
00888 }
00889 }while( progress );
00890 }
00891
00892 static int resolve_conflict();
00893
00894
00895
00896 void FindActions(lemp)
00897 struct lemon *lemp;
00898 {
00899 int i,j;
00900 struct config *cfp;
00901 struct state *stp;
00902 struct symbol *sp;
00903 struct rule *rp;
00904
00905
00906
00907
00908
00909 for(i=0; i<lemp->nstate; i++){
00910 stp = lemp->sorted[i];
00911 for(cfp=stp->cfp; cfp; cfp=cfp->next){
00912 if( cfp->rp->nrhs==cfp->dot ){
00913 for(j=0; j<lemp->nterminal; j++){
00914 if( SetFind(cfp->fws,j) ){
00915
00916
00917 Action_add(&stp->ap,REDUCE,lemp->symbols[j],(char *)cfp->rp);
00918 }
00919 }
00920 }
00921 }
00922 }
00923
00924
00925 if( lemp->start ){
00926 sp = Symbol_find(lemp->start);
00927 if( sp==0 ) sp = lemp->rule->lhs;
00928 }else{
00929 sp = lemp->rule->lhs;
00930 }
00931
00932
00933
00934 Action_add(&lemp->sorted[0]->ap,ACCEPT,sp,0);
00935
00936
00937 for(i=0; i<lemp->nstate; i++){
00938 struct action *ap, *nap;
00939 struct state *stp;
00940 stp = lemp->sorted[i];
00941 assert( stp->ap );
00942 stp->ap = Action_sort(stp->ap);
00943 for(ap=stp->ap; ap && ap->next; ap=ap->next){
00944 for(nap=ap->next; nap && nap->sp==ap->sp; nap=nap->next){
00945
00946
00947 lemp->nconflict += resolve_conflict(ap,nap);
00948 }
00949 }
00950 }
00951
00952
00953 for(rp=lemp->rule; rp; rp=rp->next) rp->canReduce = B_FALSE;
00954 for(i=0; i<lemp->nstate; i++){
00955 struct action *ap;
00956 for(ap=lemp->sorted[i]->ap; ap; ap=ap->next){
00957 if( ap->type==REDUCE ) ap->x.rp->canReduce = B_TRUE;
00958 }
00959 }
00960 for(rp=lemp->rule; rp; rp=rp->next){
00961 if( rp->canReduce ) continue;
00962 ErrorMsg(lemp->filename,rp->ruleline,"This rule can not be reduced.\n");
00963 lemp->errorcnt++;
00964 }
00965 }
00966
00967
00968
00969
00970
00971
00972
00973
00974
00975
00976
00977
00978
00979
00980 static int resolve_conflict(apx,apy)
00981 struct action *apx;
00982 struct action *apy;
00983 {
00984 struct symbol *spx, *spy;
00985 int errcnt = 0;
00986 assert( apx->sp==apy->sp );
00987 if( apx->type==SHIFT && apy->type==REDUCE ){
00988 spx = apx->sp;
00989 spy = apy->x.rp->precsym;
00990 if( spy==0 || spx->prec<0 || spy->prec<0 ){
00991
00992 apy->type = CONFLICT;
00993 errcnt++;
00994 }else if( spx->prec>spy->prec ){
00995 apy->type = RD_RESOLVED;
00996 }else if( spx->prec<spy->prec ){
00997 apx->type = SH_RESOLVED;
00998 }else if( spx->prec==spy->prec && spx->assoc==RIGHT ){
00999 apy->type = RD_RESOLVED;
01000 }else if( spx->prec==spy->prec && spx->assoc==LEFT ){
01001 apx->type = SH_RESOLVED;
01002 }else{
01003 assert( spx->prec==spy->prec && spx->assoc==NONE );
01004 apy->type = CONFLICT;
01005 errcnt++;
01006 }
01007 }else if( apx->type==REDUCE && apy->type==REDUCE ){
01008 spx = apx->x.rp->precsym;
01009 spy = apy->x.rp->precsym;
01010 if( spx==0 || spy==0 || spx->prec<0 ||
01011 spy->prec<0 || spx->prec==spy->prec ){
01012 apy->type = CONFLICT;
01013 errcnt++;
01014 }else if( spx->prec>spy->prec ){
01015 apy->type = RD_RESOLVED;
01016 }else if( spx->prec<spy->prec ){
01017 apx->type = RD_RESOLVED;
01018 }
01019 }else{
01020 assert(
01021 apx->type==SH_RESOLVED ||
01022 apx->type==RD_RESOLVED ||
01023 apx->type==CONFLICT ||
01024 apy->type==SH_RESOLVED ||
01025 apy->type==RD_RESOLVED ||
01026 apy->type==CONFLICT
01027 );
01028
01029
01030
01031 }
01032 return errcnt;
01033 }
01034
01035
01036
01037
01038
01039
01040 static struct config *freelist = 0;
01041 static struct config *current = 0;
01042 static struct config **currentend = 0;
01043 static struct config *basis = 0;
01044 static struct config **basisend = 0;
01045
01046
01047 PRIVATE struct config *newconfig(){
01048 struct config *new;
01049 if( freelist==0 ){
01050 int i;
01051 int amt = 3;
01052 freelist = (struct config *)malloc( sizeof(struct config)*amt );
01053 if( freelist==0 ){
01054 fprintf(stderr,"Unable to allocate memory for a new configuration.");
01055 exit(1);
01056 }
01057 for(i=0; i<amt-1; i++) freelist[i].next = &freelist[i+1];
01058 freelist[amt-1].next = 0;
01059 }
01060 new = freelist;
01061 freelist = freelist->next;
01062 return new;
01063 }
01064
01065
01066 PRIVATE void deleteconfig(old)
01067 struct config *old;
01068 {
01069 old->next = freelist;
01070 freelist = old;
01071 }
01072
01073
01074 void Configlist_init(){
01075 current = 0;
01076 currentend = ¤t;
01077 basis = 0;
01078 basisend = &basis;
01079 Configtable_init();
01080 return;
01081 }
01082
01083
01084 void Configlist_reset(){
01085 current = 0;
01086 currentend = ¤t;
01087 basis = 0;
01088 basisend = &basis;
01089 Configtable_clear(0);
01090 return;
01091 }
01092
01093
01094 struct config *Configlist_add(rp,dot)
01095 struct rule *rp;
01096 int dot;
01097 {
01098 struct config *cfp, model;
01099
01100 assert( currentend!=0 );
01101 model.rp = rp;
01102 model.dot = dot;
01103 cfp = Configtable_find(&model);
01104 if( cfp==0 ){
01105 cfp = newconfig();
01106 cfp->rp = rp;
01107 cfp->dot = dot;
01108 cfp->fws = SetNew();
01109 cfp->stp = 0;
01110 cfp->fplp = cfp->bplp = 0;
01111 cfp->next = 0;
01112 cfp->bp = 0;
01113 *currentend = cfp;
01114 currentend = &cfp->next;
01115 Configtable_insert(cfp);
01116 }
01117 return cfp;
01118 }
01119
01120
01121 struct config *Configlist_addbasis(rp,dot)
01122 struct rule *rp;
01123 int dot;
01124 {
01125 struct config *cfp, model;
01126
01127 assert( basisend!=0 );
01128 assert( currentend!=0 );
01129 model.rp = rp;
01130 model.dot = dot;
01131 cfp = Configtable_find(&model);
01132 if( cfp==0 ){
01133 cfp = newconfig();
01134 cfp->rp = rp;
01135 cfp->dot = dot;
01136 cfp->fws = SetNew();
01137 cfp->stp = 0;
01138 cfp->fplp = cfp->bplp = 0;
01139 cfp->next = 0;
01140 cfp->bp = 0;
01141 *currentend = cfp;
01142 currentend = &cfp->next;
01143 *basisend = cfp;
01144 basisend = &cfp->bp;
01145 Configtable_insert(cfp);
01146 }
01147 return cfp;
01148 }
01149
01150
01151 void Configlist_closure(lemp)
01152 struct lemon *lemp;
01153 {
01154 struct config *cfp, *newcfp;
01155 struct rule *rp, *newrp;
01156 struct symbol *sp, *xsp;
01157 int i, dot;
01158
01159 assert( currentend!=0 );
01160 for(cfp=current; cfp; cfp=cfp->next){
01161 rp = cfp->rp;
01162 dot = cfp->dot;
01163 if( dot>=rp->nrhs ) continue;
01164 sp = rp->rhs[dot];
01165 if( sp->type==NONTERMINAL ){
01166 if( sp->rule==0 && sp!=lemp->errsym ){
01167 ErrorMsg(lemp->filename,rp->line,"Nonterminal \"%s\" has no rules.",
01168 sp->name);
01169 lemp->errorcnt++;
01170 }
01171 for(newrp=sp->rule; newrp; newrp=newrp->nextlhs){
01172 newcfp = Configlist_add(newrp,0);
01173 for(i=dot+1; i<rp->nrhs; i++){
01174 xsp = rp->rhs[i];
01175 if( xsp->type==TERMINAL ){
01176 SetAdd(newcfp->fws,xsp->index);
01177 break;
01178 }else{
01179 SetUnion(newcfp->fws,xsp->firstset);
01180 if( xsp->lambda==B_FALSE ) break;
01181 }
01182 }
01183 if( i==rp->nrhs ) Plink_add(&cfp->fplp,newcfp);
01184 }
01185 }
01186 }
01187 return;
01188 }
01189
01190
01191 void Configlist_sort(){
01192
01193 current = (struct config *)msort((char *)current,(char **)(void *)&(current->next),Configcmp);
01194 currentend = 0;
01195 return;
01196 }
01197
01198
01199 void Configlist_sortbasis(){
01200
01201 basis = (struct config *)msort((char *)current,(char **)(void *)&(current->bp),Configcmp);
01202 basisend = 0;
01203 return;
01204 }
01205
01206
01207
01208 struct config *Configlist_return(){
01209 struct config *old;
01210 old = current;
01211 current = 0;
01212 currentend = 0;
01213 return old;
01214 }
01215
01216
01217
01218 struct config *Configlist_basis(){
01219 struct config *old;
01220 old = basis;
01221 basis = 0;
01222 basisend = 0;
01223 return old;
01224 }
01225
01226
01227 void Configlist_eat(cfp)
01228 struct config *cfp;
01229 {
01230 struct config *nextcfp;
01231 for(; cfp; cfp=nextcfp){
01232 nextcfp = cfp->next;
01233 assert( cfp->fplp==0 );
01234 assert( cfp->bplp==0 );
01235 if( cfp->fws ) SetFree(cfp->fws);
01236 deleteconfig(cfp);
01237 }
01238 return;
01239 }
01240
01241
01242
01243
01244
01245
01246
01247
01248 static int findbreak(msg,min,max)
01249 char *msg;
01250 int min;
01251 int max;
01252 {
01253 int i,spot;
01254 char c;
01255 for(i=spot=min; i<=max; i++){
01256 c = msg[i];
01257 if( c=='\t' ) msg[i] = ' ';
01258 if( c=='\n' ){ msg[i] = ' '; spot = i; break; }
01259 if( c==0 ){ spot = i; break; }
01260 if( c=='-' && i<max-1 ) spot = i+1;
01261 if( c==' ' ) spot = i;
01262 }
01263 return spot;
01264 }
01265
01266
01267
01268
01269
01270
01271 #define ERRMSGSIZE 10000
01272 #define LINEWIDTH 79
01273 #define PREFIXLIMIT 60
01274 void ErrorMsg(const char *filename, int lineno, const char *format, ...){
01275 char errmsg[ERRMSGSIZE];
01276 char prefix[PREFIXLIMIT+10];
01277 int errmsgsize;
01278 int prefixsize;
01279 int availablewidth;
01280 va_list ap;
01281 int end, restart, base;
01282
01283 va_start(ap, format);
01284
01285 if( lineno>0 ){
01286 sprintf(prefix,"%.*s:%d: ",PREFIXLIMIT-10,filename,lineno);
01287 }else{
01288 sprintf(prefix,"%.*s: ",PREFIXLIMIT-10,filename);
01289 }
01290 prefixsize = strlen(prefix);
01291 availablewidth = LINEWIDTH - prefixsize;
01292
01293
01294 vsprintf(errmsg,format,ap);
01295 va_end(ap);
01296 errmsgsize = strlen(errmsg);
01297
01298 while( errmsgsize>0 && errmsg[errmsgsize-1]=='\n' ){
01299 errmsg[--errmsgsize] = 0;
01300 }
01301
01302
01303 base = 0;
01304 while( errmsg[base]!=0 ){
01305 end = restart = findbreak(&errmsg[base],0,availablewidth);
01306 restart += base;
01307 while( errmsg[restart]==' ' ) restart++;
01308 fprintf(stdout,"%s%.*s\n",prefix,end,&errmsg[base]);
01309 base = restart;
01310 }
01311 }
01312
01313
01314
01315
01316
01317
01318
01319
01320 void memory_error(){
01321 fprintf(stderr,"Out of memory. Aborting...\n");
01322 exit(1);
01323 }
01324
01325 static int nDefine = 0;
01326 static char **azDefine = 0;
01327
01328
01329
01330
01331 static void handle_D_option(char *z){
01332 char **paz;
01333 nDefine++;
01334 azDefine = realloc(azDefine, sizeof(azDefine[0])*nDefine);
01335 if( azDefine==0 ){
01336 fprintf(stderr,"out of memory\n");
01337 exit(1);
01338 }
01339 paz = &azDefine[nDefine-1];
01340 *paz = malloc( strlen(z)+1 );
01341 if( *paz==0 ){
01342 fprintf(stderr,"out of memory\n");
01343 exit(1);
01344 }
01345 strcpy(*paz, z);
01346 for(z=*paz; *z && *z!='='; z++){}
01347 *z = 0;
01348 }
01349
01350 static char *output_filename = 0;
01351
01352
01353
01354 static void handle_o_option(char *z){
01355 output_filename = malloc( strlen(z)+1 );
01356 if( output_filename==0 ){
01357 fprintf(stderr,"out of memory\n");
01358 exit(1);
01359 }
01360 strcpy(output_filename, z);
01361 }
01362
01363 static char *output_header_filename = 0;
01364
01365
01366
01367 static void handle_h_option(char *z){
01368 output_header_filename = malloc( strlen(z)+1 );
01369 if( output_header_filename==0 ){
01370 fprintf(stderr,"out of memory\n");
01371 exit(1);
01372 }
01373 strcpy(output_header_filename, z);
01374 }
01375
01376
01377
01378 int main(argc,argv)
01379 int argc;
01380 char **argv;
01381 {
01382 static int version = 0;
01383 static int rpflag = 0;
01384 static int basisflag = 0;
01385 static int compress = 0;
01386 static int quiet = 0;
01387 static int statistics = 0;
01388 static int mhflag = 0;
01389 static struct s_options options[] = {
01390 {OPT_FLAG, "b", (void*)&basisflag, 0, "Print only the basis in report."},
01391 {OPT_FLAG, "c", (void*)&compress, 0, "Don't compress the action table."},
01392 {OPT_FSTR, "D", 0, handle_D_option, "Define an %ifdef macro."},
01393 {OPT_FLAG, "g", (void*)&rpflag, 0, "Print grammar without actions."},
01394 {OPT_FLAG, "m", (void*)&mhflag, 0, "Output a makeheaders compatible file"},
01395 {OPT_FLAG, "q", (void*)&quiet, 0, "(Quiet) Don't print the report file."},
01396 {OPT_FLAG, "s", (void*)&statistics, 0,
01397 "Print parser stats to standard output."},
01398 {OPT_FLAG, "x", (void*)&version, 0, "Print the version number."},
01399 {OPT_FSTR, "o", 0, handle_o_option, "Specify output filename."},
01400 {OPT_FSTR, "h", 0, handle_h_option, "Specify output header filename."},
01401 {OPT_FLAG,0,0,0,0}
01402 };
01403 int i;
01404 struct lemon lem;
01405
01406 (void)argc;
01407 OptInit(argv,options,stderr);
01408 if( version ){
01409 printf("Lemon version 1.0 (patched for Xapian)\n");
01410 exit(0);
01411 }
01412 if( OptNArgs()!=1 ){
01413 fprintf(stderr,"Exactly one filename argument is required.\n");
01414 exit(1);
01415 }
01416 lem.errorcnt = 0;
01417
01418
01419 Strsafe_init();
01420 Symbol_init();
01421 State_init();
01422 lem.argv0 = argv[0];
01423 lem.filename = OptArg(0);
01424 lem.basisflag = basisflag;
01425 lem.has_fallback = 0;
01426 lem.nconflict = 0;
01427 lem.name = lem.include = lem.arg = lem.tokentype = lem.start = 0;
01428 lem.vartype = 0;
01429 lem.stacksize = 0;
01430 lem.error = lem.overflow = lem.failure = lem.accept = lem.tokendest =
01431 lem.tokenprefix = lem.outname = lem.extracode = 0;
01432 lem.vardest = 0;
01433 lem.tablesize = 0;
01434 Symbol_new("$");
01435 lem.errsym = Symbol_new("error");
01436
01437
01438 Parse(&lem);
01439 if( lem.errorcnt ) exit(lem.errorcnt);
01440 if( lem.rule==0 ){
01441 fprintf(stderr,"Empty grammar.\n");
01442 exit(1);
01443 }
01444
01445
01446 lem.nsymbol = Symbol_count();
01447 Symbol_new("{default}");
01448 lem.symbols = Symbol_arrayof();
01449 for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
01450 qsort(lem.symbols,lem.nsymbol+1,sizeof(struct symbol*),
01451 Symbolcmpp);
01452 for(i=0; i<=lem.nsymbol; i++) lem.symbols[i]->index = i;
01453 for(i=1; isupper(lem.symbols[i]->name[0]); i++);
01454 lem.nterminal = i;
01455
01456
01457 if( rpflag ){
01458 Reprint(&lem);
01459 }else{
01460
01461 SetSize(lem.nterminal);
01462
01463
01464 FindRulePrecedences(&lem);
01465
01466
01467
01468 FindFirstSets(&lem);
01469
01470
01471
01472 lem.nstate = 0;
01473 FindStates(&lem);
01474 lem.sorted = State_arrayof();
01475
01476
01477 FindLinks(&lem);
01478
01479
01480 FindFollowSets(&lem);
01481
01482
01483 FindActions(&lem);
01484
01485
01486 if( compress==0 ) CompressTables(&lem);
01487
01488
01489 if( !quiet ) ReportOutput(&lem);
01490
01491
01492 ReportTable(&lem, mhflag);
01493
01494
01495
01496
01497 if( !mhflag ) ReportHeader(&lem);
01498 }
01499 if( statistics ){
01500 printf("Parser statistics: %d terminals, %d nonterminals, %d rules\n",
01501 lem.nterminal, lem.nsymbol - lem.nterminal, lem.nrule);
01502 printf(" %d states, %d parser table entries, %d conflicts\n",
01503 lem.nstate, lem.tablesize, lem.nconflict);
01504 }
01505 if( lem.nconflict ){
01506 fprintf(stderr,"%d parsing conflicts.\n",lem.nconflict);
01507 }
01508 exit(lem.errorcnt + lem.nconflict);
01509 return (lem.errorcnt + lem.nconflict);
01510 }
01511
01512
01513
01514
01515
01516
01517
01518
01519
01520
01521
01522
01523
01524
01525
01526
01527
01528
01529
01530
01531
01532
01533
01534
01535
01536
01537
01538 #define NEXT(A) (*(char**)(((unsigned long)A)+offset))
01539
01540
01541
01542
01543
01544
01545
01546
01547
01548
01549
01550
01551
01552
01553
01554
01555 static char *merge(a,b,cmp,offset)
01556 char *a;
01557 char *b;
01558 int (*cmp)();
01559 int offset;
01560 {
01561 char *ptr, *head;
01562
01563 if( a==0 ){
01564 head = b;
01565 }else if( b==0 ){
01566 head = a;
01567 }else{
01568 if( (*cmp)(a,b)<0 ){
01569 ptr = a;
01570 a = NEXT(a);
01571 }else{
01572 ptr = b;
01573 b = NEXT(b);
01574 }
01575 head = ptr;
01576 while( a && b ){
01577 if( (*cmp)(a,b)<0 ){
01578 NEXT(ptr) = a;
01579 ptr = a;
01580 a = NEXT(a);
01581 }else{
01582 NEXT(ptr) = b;
01583 ptr = b;
01584 b = NEXT(b);
01585 }
01586 }
01587 if( a ) NEXT(ptr) = a;
01588 else NEXT(ptr) = b;
01589 }
01590 return head;
01591 }
01592
01593
01594
01595
01596
01597
01598
01599
01600
01601
01602
01603
01604
01605
01606 #define LISTSIZE 30
01607 char *msort(list,next,cmp)
01608 char *list;
01609 char **next;
01610 int (*cmp)();
01611 {
01612 unsigned long offset;
01613 char *ep;
01614 char *set[LISTSIZE];
01615 int i;
01616 offset = (unsigned long)next - (unsigned long)list;
01617 for(i=0; i<LISTSIZE; i++) set[i] = 0;
01618 while( list ){
01619 ep = list;
01620 list = NEXT(list);
01621 NEXT(ep) = 0;
01622 for(i=0; i<LISTSIZE-1 && set[i]!=0; i++){
01623 ep = merge(ep,set[i],cmp,offset);
01624 set[i] = 0;
01625 }
01626 set[i] = ep;
01627 }
01628 ep = 0;
01629 for(i=0; i<LISTSIZE; i++) if( set[i] ) ep = merge(ep,set[i],cmp,offset);
01630 return ep;
01631 }
01632
01633 static char **argv;
01634 static struct s_options *op;
01635 static FILE *errstream;
01636
01637 #define ISOPT(X) ((X)[0]=='-'||(X)[0]=='+'||strchr((X),'=')!=0)
01638
01639
01640
01641
01642
01643 static void errline(n,k,err)
01644 int n;
01645 int k;
01646 FILE *err;
01647 {
01648 int spcnt, i;
01649 spcnt = 0;
01650 if( argv[0] ) fprintf(err,"%s",argv[0]);
01651 spcnt = strlen(argv[0]) + 1;
01652 for(i=1; i<n && argv[i]; i++){
01653 fprintf(err," %s",argv[i]);
01654 spcnt += strlen(argv[i]+1);
01655 }
01656 spcnt += k;
01657 for(; argv[i]; i++) fprintf(err," %s",argv[i]);
01658 if( spcnt<20 ){
01659 fprintf(err,"\n%*s^-- here\n",spcnt,"");
01660 }else{
01661 fprintf(err,"\n%*shere --^\n",spcnt-7,"");
01662 }
01663 }
01664
01665
01666
01667
01668
01669 static int argindex(n)
01670 int n;
01671 {
01672 int i;
01673 int dashdash = 0;
01674 if( argv!=0 && *argv!=0 ){
01675 for(i=1; argv[i]; i++){
01676 if( dashdash || !ISOPT(argv[i]) ){
01677 if( n==0 ) return i;
01678 n--;
01679 }
01680 if( strcmp(argv[i],"--")==0 ) dashdash = 1;
01681 }
01682 }
01683 return -1;
01684 }
01685
01686 static char emsg[] = "Command line syntax error: ";
01687
01688
01689
01690
01691 static int handleflags(i,err)
01692 int i;
01693 FILE *err;
01694 {
01695 int v;
01696 int errcnt = 0;
01697 int j;
01698 for(j=0; op[j].label; j++){
01699 if( strncmp(&argv[i][1],op[j].label,strlen(op[j].label))==0 ) break;
01700 }
01701 v = argv[i][0]=='-' ? 1 : 0;
01702 if( op[j].label==0 ){
01703 if( err ){
01704 fprintf(err,"%sundefined option.\n",emsg);
01705 errline(i,1,err);
01706 }
01707 errcnt++;
01708 }else if( op[j].type==OPT_FLAG ){
01709 *((int*)op[j].arg) = v;
01710 }else if( op[j].type==OPT_FFLAG ){
01711 (op[j].func)(v);
01712 }else if( op[j].type==OPT_FSTR ){
01713 (op[j].func)(&argv[i][2]);
01714 }else{
01715 if( err ){
01716 fprintf(err,"%smissing argument on switch.\n",emsg);
01717 errline(i,1,err);
01718 }
01719 errcnt++;
01720 }
01721 return errcnt;
01722 }
01723
01724
01725
01726
01727 static int handleswitch(i,err)
01728 int i;
01729 FILE *err;
01730 {
01731 int lv = 0;
01732 double dv = 0.0;
01733 char *sv = 0, *end;
01734 char *cp;
01735 int j;
01736 int errcnt = 0;
01737 cp = strchr(argv[i],'=');
01738 *cp = 0;
01739 for(j=0; op[j].label; j++){
01740 if( strcmp(argv[i],op[j].label)==0 ) break;
01741 }
01742 *cp = '=';
01743 if( op[j].label==0 ){
01744 if( err ){
01745 fprintf(err,"%sundefined option.\n",emsg);
01746 errline(i,0,err);
01747 }
01748 errcnt++;
01749 }else{
01750 cp++;
01751 switch( op[j].type ){
01752 case OPT_FLAG:
01753 case OPT_FFLAG:
01754 if( err ){
01755 fprintf(err,"%soption requires an argument.\n",emsg);
01756 errline(i,0,err);
01757 }
01758 errcnt++;
01759 break;
01760 case OPT_DBL:
01761 case OPT_FDBL:
01762 dv = strtod(cp,&end);
01763 if( *end ){
01764 if( err ){
01765 fprintf(err,"%sillegal character in floating-point argument.\n",emsg);
01766 errline(i,((unsigned long)end)-(unsigned long)argv[i],err);
01767 }
01768 errcnt++;
01769 }
01770 break;
01771 case OPT_INT:
01772 case OPT_FINT:
01773 lv = strtol(cp,&end,0);
01774 if( *end ){
01775 if( err ){
01776 fprintf(err,"%sillegal character in integer argument.\n",emsg);
01777 errline(i,((unsigned long)end)-(unsigned long)argv[i],err);
01778 }
01779 errcnt++;
01780 }
01781 break;
01782 case OPT_STR:
01783 case OPT_FSTR:
01784 sv = cp;
01785 break;
01786 }
01787 switch( op[j].type ){
01788 case OPT_FLAG:
01789 case OPT_FFLAG:
01790 break;
01791 case OPT_DBL:
01792 *(double*)(op[j].arg) = dv;
01793 break;
01794 case OPT_FDBL:
01795 (op[j].func)(dv);
01796 break;
01797 case OPT_INT:
01798 *(int*)(op[j].arg) = lv;
01799 break;
01800 case OPT_FINT:
01801 (op[j].func)((int)lv);
01802 break;
01803 case OPT_STR:
01804 *(char**)(op[j].arg) = sv;
01805 break;
01806 case OPT_FSTR:
01807 (op[j].func)(sv);
01808 break;
01809 }
01810 }
01811 return errcnt;
01812 }
01813
01814 int OptInit(a,o,err)
01815 char **a;
01816 struct s_options *o;
01817 FILE *err;
01818 {
01819 int errcnt = 0;
01820 argv = a;
01821 op = o;
01822 errstream = err;
01823 if( argv && *argv && op ){
01824 int i;
01825 for(i=1; argv[i]; i++){
01826 if( argv[i][0]=='+' || argv[i][0]=='-' ){
01827 errcnt += handleflags(i,err);
01828 }else if( strchr(argv[i],'=') ){
01829 errcnt += handleswitch(i,err);
01830 }
01831 }
01832 }
01833 if( errcnt>0 ){
01834 fprintf(err,"Valid command line options for \"%s\" are:\n",*a);
01835 OptPrint();
01836 exit(1);
01837 }
01838 return 0;
01839 }
01840
01841 int OptNArgs(){
01842 int cnt = 0;
01843 int dashdash = 0;
01844 int i;
01845 if( argv!=0 && argv[0]!=0 ){
01846 for(i=1; argv[i]; i++){
01847 if( dashdash || !ISOPT(argv[i]) ) cnt++;
01848 if( strcmp(argv[i],"--")==0 ) dashdash = 1;
01849 }
01850 }
01851 return cnt;
01852 }
01853
01854 char *OptArg(n)
01855 int n;
01856 {
01857 int i;
01858 i = argindex(n);
01859 return i>=0 ? argv[i] : 0;
01860 }
01861
01862 void OptErr(n)
01863 int n;
01864 {
01865 int i;
01866 i = argindex(n);
01867 if( i>=0 ) errline(i,0,errstream);
01868 }
01869
01870 void OptPrint(){
01871 int i;
01872 int max, len;
01873 max = 0;
01874 for(i=0; op[i].label; i++){
01875 len = strlen(op[i].label) + 1;
01876 switch( op[i].type ){
01877 case OPT_FLAG:
01878 case OPT_FFLAG:
01879 break;
01880 case OPT_INT:
01881 case OPT_FINT:
01882 len += 9;
01883 break;
01884 case OPT_DBL:
01885 case OPT_FDBL:
01886 len += 6;
01887 break;
01888 case OPT_STR:
01889 case OPT_FSTR:
01890 len += 8;
01891 break;
01892 }
01893 if( len>max ) max = len;
01894 }
01895 for(i=0; op[i].label; i++){
01896 switch( op[i].type ){
01897 case OPT_FLAG:
01898 case OPT_FFLAG:
01899 fprintf(errstream," -%-*s %s\n",max,op[i].label,op[i].message);
01900 break;
01901 case OPT_INT:
01902 case OPT_FINT:
01903 fprintf(errstream," %s=<integer>%*s %s\n",op[i].label,
01904 (int)(max-strlen(op[i].label)-9),"",op[i].message);
01905 break;
01906 case OPT_DBL:
01907 case OPT_FDBL:
01908 fprintf(errstream," %s=<real>%*s %s\n",op[i].label,
01909 (int)(max-strlen(op[i].label)-6),"",op[i].message);
01910 break;
01911 case OPT_STR:
01912 case OPT_FSTR:
01913 fprintf(errstream," %s=<string>%*s %s\n",op[i].label,
01914 (int)(max-strlen(op[i].label)-8),"",op[i].message);
01915 break;
01916 }
01917 }
01918 }
01919
01920
01921
01922
01923
01924
01925 struct pstate {
01926 char *filename;
01927 int tokenlineno;
01928 int errorcnt;
01929 char *tokenstart;
01930 struct lemon *gp;
01931 enum e_state {
01932 INITIALIZE,
01933 WAITING_FOR_DECL_OR_RULE,
01934 WAITING_FOR_DECL_KEYWORD,
01935 WAITING_FOR_DECL_ARG,
01936 WAITING_FOR_PRECEDENCE_SYMBOL,
01937 WAITING_FOR_ARROW,
01938 IN_RHS,
01939 LHS_ALIAS_1,
01940 LHS_ALIAS_2,
01941 LHS_ALIAS_3,
01942 RHS_ALIAS_1,
01943 RHS_ALIAS_2,
01944 PRECEDENCE_MARK_1,
01945 PRECEDENCE_MARK_2,
01946 RESYNC_AFTER_RULE_ERROR,
01947 RESYNC_AFTER_DECL_ERROR,
01948 WAITING_FOR_DESTRUCTOR_SYMBOL,
01949 WAITING_FOR_DATATYPE_SYMBOL,
01950 WAITING_FOR_FALLBACK_ID
01951 } state;
01952 struct symbol *fallback;
01953 struct symbol *lhs;
01954 char *lhsalias;
01955 int nrhs;
01956 struct symbol *rhs[MAXRHS];
01957 char *alias[MAXRHS];
01958 struct rule *prevrule;
01959 char *declkeyword;
01960 char **declargslot;
01961 int *decllnslot;
01962 enum e_assoc declassoc;
01963 int preccounter;
01964 struct rule *firstrule;
01965 struct rule *lastrule;
01966 };
01967
01968
01969 static void parseonetoken(psp)
01970 struct pstate *psp;
01971 {
01972 char *x;
01973 x = Strsafe(psp->tokenstart);
01974 #if 0
01975 printf("%s:%d: Token=[%s] state=%d\n",psp->filename,psp->tokenlineno,
01976 x,psp->state);
01977 #endif
01978 switch( psp->state ){
01979 case INITIALIZE:
01980 psp->prevrule = 0;
01981 psp->preccounter = 0;
01982 psp->firstrule = psp->lastrule = 0;
01983 psp->gp->nrule = 0;
01984
01985 case WAITING_FOR_DECL_OR_RULE:
01986 if( x[0]=='%' ){
01987 psp->state = WAITING_FOR_DECL_KEYWORD;
01988 }else if( islower(x[0]) ){
01989 psp->lhs = Symbol_new(x);
01990 psp->nrhs = 0;
01991 psp->lhsalias = 0;
01992 psp->state = WAITING_FOR_ARROW;
01993 }else if( x[0]=='{' ){
01994 if( psp->prevrule==0 ){
01995 ErrorMsg(psp->filename,psp->tokenlineno,
01996 "There is not prior rule opon which to attach the code "
01997 "fragment which begins on this line.");
01998 psp->errorcnt++;
01999 }else if( psp->prevrule->code!=0 ){
02000 ErrorMsg(psp->filename,psp->tokenlineno,
02001 "Code fragment beginning on this line is not the first "
02002 "to follow the previous rule.");
02003 psp->errorcnt++;
02004 }else{
02005 psp->prevrule->line = psp->tokenlineno;
02006 psp->prevrule->code = &x[1];
02007 }
02008 }else if( x[0]=='[' ){
02009 psp->state = PRECEDENCE_MARK_1;
02010 }else{
02011 ErrorMsg(psp->filename,psp->tokenlineno,
02012 "Token \"%s\" should be either \"%%\" or a nonterminal name.",
02013 x);
02014 psp->errorcnt++;
02015 }
02016 break;
02017 case PRECEDENCE_MARK_1:
02018 if( !isupper(x[0]) ){
02019 ErrorMsg(psp->filename,psp->tokenlineno,
02020 "The precedence symbol must be a terminal.");
02021 psp->errorcnt++;
02022 }else if( psp->prevrule==0 ){
02023 ErrorMsg(psp->filename,psp->tokenlineno,
02024 "There is no prior rule to assign precedence \"[%s]\".",x);
02025 psp->errorcnt++;
02026 }else if( psp->prevrule->precsym!=0 ){
02027 ErrorMsg(psp->filename,psp->tokenlineno,
02028 "Precedence mark on this line is not the first "
02029 "to follow the previous rule.");
02030 psp->errorcnt++;
02031 }else{
02032 psp->prevrule->precsym = Symbol_new(x);
02033 }
02034 psp->state = PRECEDENCE_MARK_2;
02035 break;
02036 case PRECEDENCE_MARK_2:
02037 if( x[0]!=']' ){
02038 ErrorMsg(psp->filename,psp->tokenlineno,
02039 "Missing \"]\" on precedence mark.");
02040 psp->errorcnt++;
02041 }
02042 psp->state = WAITING_FOR_DECL_OR_RULE;
02043 break;
02044 case WAITING_FOR_ARROW:
02045 if( x[0]==':' && x[1]==':' && x[2]=='=' ){
02046 psp->state = IN_RHS;
02047 }else if( x[0]=='(' ){
02048 psp->state = LHS_ALIAS_1;
02049 }else{
02050 ErrorMsg(psp->filename,psp->tokenlineno,
02051 "Expected to see a \":\" following the LHS symbol \"%s\".",
02052 psp->lhs->name);
02053 psp->errorcnt++;
02054 psp->state = RESYNC_AFTER_RULE_ERROR;
02055 }
02056 break;
02057 case LHS_ALIAS_1:
02058 if( isalpha(x[0]) ){
02059 psp->lhsalias = x;
02060 psp->state = LHS_ALIAS_2;
02061 }else{
02062 ErrorMsg(psp->filename,psp->tokenlineno,
02063 "\"%s\" is not a valid alias for the LHS \"%s\"\n",
02064 x,psp->lhs->name);
02065 psp->errorcnt++;
02066 psp->state = RESYNC_AFTER_RULE_ERROR;
02067 }
02068 break;
02069 case LHS_ALIAS_2:
02070 if( x[0]==')' ){
02071 psp->state = LHS_ALIAS_3;
02072 }else{
02073 ErrorMsg(psp->filename,psp->tokenlineno,
02074 "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);
02075 psp->errorcnt++;
02076 psp->state = RESYNC_AFTER_RULE_ERROR;
02077 }
02078 break;
02079 case LHS_ALIAS_3:
02080 if( x[0]==':' && x[1]==':' && x[2]=='=' ){
02081 psp->state = IN_RHS;
02082 }else{
02083 ErrorMsg(psp->filename,psp->tokenlineno,
02084 "Missing \"->\" following: \"%s(%s)\".",
02085 psp->lhs->name,psp->lhsalias);
02086 psp->errorcnt++;
02087 psp->state = RESYNC_AFTER_RULE_ERROR;
02088 }
02089 break;
02090 case IN_RHS:
02091 if( x[0]=='.' ){
02092 struct rule *rp;
02093 rp = (struct rule *)malloc( sizeof(struct rule) +
02094 sizeof(struct symbol*)*psp->nrhs + sizeof(char*)*psp->nrhs );
02095 if( rp==0 ){
02096 ErrorMsg(psp->filename,psp->tokenlineno,
02097 "Can't allocate enough memory for this rule.");
02098 psp->errorcnt++;
02099 psp->prevrule = 0;
02100 }else{
02101 int i;
02102 rp->ruleline = psp->tokenlineno;
02103 rp->rhs = (struct symbol**)&rp[1];
02104 rp->rhsalias = (char**)&(rp->rhs[psp->nrhs]);
02105 for(i=0; i<psp->nrhs; i++){
02106 rp->rhs[i] = psp->rhs[i];
02107 rp->rhsalias[i] = psp->alias[i];
02108 }
02109 rp->lhs = psp->lhs;
02110 rp->lhsalias = psp->lhsalias;
02111 rp->nrhs = psp->nrhs;
02112 rp->code = 0;
02113 rp->precsym = 0;
02114 rp->index = psp->gp->nrule++;
02115 rp->nextlhs = rp->lhs->rule;
02116 rp->lhs->rule = rp;
02117 rp->next = 0;
02118 if( psp->firstrule==0 ){
02119 psp->firstrule = psp->lastrule = rp;
02120 }else{
02121 psp->lastrule->next = rp;
02122 psp->lastrule = rp;
02123 }
02124 psp->prevrule = rp;
02125 }
02126 psp->state = WAITING_FOR_DECL_OR_RULE;
02127 }else if( isalpha(x[0]) ){
02128 if( psp->nrhs>=MAXRHS ){
02129 ErrorMsg(psp->filename,psp->tokenlineno,
02130 "Too many symbol on RHS or rule beginning at \"%s\".",
02131 x);
02132 psp->errorcnt++;
02133 psp->state = RESYNC_AFTER_RULE_ERROR;
02134 }else{
02135 psp->rhs[psp->nrhs] = Symbol_new(x);
02136 psp->alias[psp->nrhs] = 0;
02137 psp->nrhs++;
02138 }
02139 }else if( x[0]=='(' && psp->nrhs>0 ){
02140 psp->state = RHS_ALIAS_1;
02141 }else{
02142 ErrorMsg(psp->filename,psp->tokenlineno,
02143 "Illegal character on RHS of rule: \"%s\".",x);
02144 psp->errorcnt++;
02145 psp->state = RESYNC_AFTER_RULE_ERROR;
02146 }
02147 break;
02148 case RHS_ALIAS_1:
02149 if( isalpha(x[0]) ){
02150 psp->alias[psp->nrhs-1] = x;
02151 psp->state = RHS_ALIAS_2;
02152 }else{
02153 ErrorMsg(psp->filename,psp->tokenlineno,
02154 "\"%s\" is not a valid alias for the RHS symbol \"%s\"\n",
02155 x,psp->rhs[psp->nrhs-1]->name);
02156 psp->errorcnt++;
02157 psp->state = RESYNC_AFTER_RULE_ERROR;
02158 }
02159 break;
02160 case RHS_ALIAS_2:
02161 if( x[0]==')' ){
02162 psp->state = IN_RHS;
02163 }else{
02164 ErrorMsg(psp->filename,psp->tokenlineno,
02165 "Missing \")\" following LHS alias name \"%s\".",psp->lhsalias);
02166 psp->errorcnt++;
02167 psp->state = RESYNC_AFTER_RULE_ERROR;
02168 }
02169 break;
02170 case WAITING_FOR_DECL_KEYWORD:
02171 if( isalpha(x[0]) ){
02172 psp->declkeyword = x;
02173 psp->declargslot = 0;
02174 psp->decllnslot = 0;
02175 psp->state = WAITING_FOR_DECL_ARG;
02176 if( strcmp(x,"name")==0 ){
02177 psp->declargslot = &(psp->gp->name);
02178 }else if( strcmp(x,"include")==0 ){
02179 psp->declargslot = &(psp->gp->include);
02180 psp->decllnslot = &psp->gp->includeln;
02181 }else if( strcmp(x,"code")==0 ){
02182 psp->declargslot = &(psp->gp->extracode);
02183 psp->decllnslot = &psp->gp->extracodeln;
02184 }else if( strcmp(x,"token_destructor")==0 ){
02185 psp->declargslot = &psp->gp->tokendest;
02186 psp->decllnslot = &psp->gp->tokendestln;
02187 }else if( strcmp(x,"default_destructor")==0 ){
02188 psp->declargslot = &psp->gp->vardest;
02189 psp->decllnslot = &psp->gp->vardestln;
02190 }else if( strcmp(x,"token_prefix")==0 ){
02191 psp->declargslot = &psp->gp->tokenprefix;
02192 }else if( strcmp(x,"syntax_error")==0 ){
02193 psp->declargslot = &(psp->gp->error);
02194 psp->decllnslot = &psp->gp->errorln;
02195 }else if( strcmp(x,"parse_accept")==0 ){
02196 psp->declargslot = &(psp->gp->accept);
02197 psp->decllnslot = &psp->gp->acceptln;
02198 }else if( strcmp(x,"parse_failure")==0 ){
02199 psp->declargslot = &(psp->gp->failure);
02200 psp->decllnslot = &psp->gp->failureln;
02201 }else if( strcmp(x,"stack_overflow")==0 ){
02202 psp->declargslot = &(psp->gp->overflow);
02203 psp->decllnslot = &psp->gp->overflowln;
02204 }else if( strcmp(x,"extra_argument")==0 ){
02205 psp->declargslot = &(psp->gp->arg);
02206 }else if( strcmp(x,"token_type")==0 ){
02207 psp->declargslot = &(psp->gp->tokentype);
02208 }else if( strcmp(x,"default_type")==0 ){
02209 psp->declargslot = &(psp->gp->vartype);
02210 }else if( strcmp(x,"stack_size")==0 ){
02211 psp->declargslot = &(psp->gp->stacksize);
02212 }else if( strcmp(x,"start_symbol")==0 ){
02213 psp->declargslot = &(psp->gp->start);
02214 }else if( strcmp(x,"left")==0 ){
02215 psp->preccounter++;
02216 psp->declassoc = LEFT;
02217 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
02218 }else if( strcmp(x,"right")==0 ){
02219 psp->preccounter++;
02220 psp->declassoc = RIGHT;
02221 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
02222 }else if( strcmp(x,"nonassoc")==0 ){
02223 psp->preccounter++;
02224 psp->declassoc = NONE;
02225 psp->state = WAITING_FOR_PRECEDENCE_SYMBOL;
02226 }else if( strcmp(x,"destructor")==0 ){
02227 psp->state = WAITING_FOR_DESTRUCTOR_SYMBOL;
02228 }else if( strcmp(x,"type")==0 ){
02229 psp->state = WAITING_FOR_DATATYPE_SYMBOL;
02230 }else if( strcmp(x,"fallback")==0 ){
02231 psp->fallback = 0;
02232 psp->state = WAITING_FOR_FALLBACK_ID;
02233 }else{
02234 ErrorMsg(psp->filename,psp->tokenlineno,
02235 "Unknown declaration keyword: \"%%%s\".",x);
02236 psp->errorcnt++;
02237 psp->state = RESYNC_AFTER_DECL_ERROR;
02238 }
02239 }else{
02240 ErrorMsg(psp->filename,psp->tokenlineno,
02241 "Illegal declaration keyword: \"%s\".",x);
02242 psp->errorcnt++;
02243 psp->state = RESYNC_AFTER_DECL_ERROR;
02244 }
02245 break;
02246 case WAITING_FOR_DESTRUCTOR_SYMBOL:
02247 if( !isalpha(x[0]) ){
02248 ErrorMsg(psp->filename,psp->tokenlineno,
02249 "Symbol name missing after %destructor keyword");
02250 psp->errorcnt++;
02251 psp->state = RESYNC_AFTER_DECL_ERROR;
02252 }else{
02253 struct symbol *sp = Symbol_new(x);
02254 psp->declargslot = &sp->destructor;
02255 psp->decllnslot = &sp->destructorln;
02256 psp->state = WAITING_FOR_DECL_ARG;
02257 }
02258 break;
02259 case WAITING_FOR_DATATYPE_SYMBOL:
02260 if( !isalpha(x[0]) ){
02261 ErrorMsg(psp->filename,psp->tokenlineno,
02262 "Symbol name missing after %destructor keyword");
02263 psp->errorcnt++;
02264 psp->state = RESYNC_AFTER_DECL_ERROR;
02265 }else{
02266 struct symbol *sp = Symbol_new(x);
02267 psp->declargslot = &sp->datatype;
02268 psp->decllnslot = 0;
02269 psp->state = WAITING_FOR_DECL_ARG;
02270 }
02271 break;
02272 case WAITING_FOR_PRECEDENCE_SYMBOL:
02273 if( x[0]=='.' ){
02274 psp->state = WAITING_FOR_DECL_OR_RULE;
02275 }else if( isupper(x[0]) ){
02276 struct symbol *sp;
02277 sp = Symbol_new(x);
02278 if( sp->prec>=0 ){
02279 ErrorMsg(psp->filename,psp->tokenlineno,
02280 "Symbol \"%s\" has already be given a precedence.",x);
02281 psp->errorcnt++;
02282 }else{
02283 sp->prec = psp->preccounter;
02284 sp->assoc = psp->declassoc;
02285 }
02286 }else{
02287 ErrorMsg(psp->filename,psp->tokenlineno,
02288 "Can't assign a precedence to \"%s\".",x);
02289 psp->errorcnt++;
02290 }
02291 break;
02292 case WAITING_FOR_DECL_ARG:
02293 if( (x[0]=='{' || x[0]=='\"' || isalnum(x[0])) ){
02294 if( *(psp->declargslot)!=0 ){
02295 ErrorMsg(psp->filename,psp->tokenlineno,
02296 "The argument \"%s\" to declaration \"%%%s\" is not the first.",
02297 x[0]=='\"' ? &x[1] : x,psp->declkeyword);
02298 psp->errorcnt++;
02299 psp->state = RESYNC_AFTER_DECL_ERROR;
02300 }else{
02301 *(psp->declargslot) = (x[0]=='\"' || x[0]=='{') ? &x[1] : x;
02302 if( psp->decllnslot ) *psp->decllnslot = psp->tokenlineno;
02303 psp->state = WAITING_FOR_DECL_OR_RULE;
02304 }
02305 }else{
02306 ErrorMsg(psp->filename,psp->tokenlineno,
02307 "Illegal argument to %%%s: %s",psp->declkeyword,x);
02308 psp->errorcnt++;
02309 psp->state = RESYNC_AFTER_DECL_ERROR;
02310 }
02311 break;
02312 case WAITING_FOR_FALLBACK_ID:
02313 if( x[0]=='.' ){
02314 psp->state = WAITING_FOR_DECL_OR_RULE;
02315 }else if( !isupper(x[0]) ){
02316 ErrorMsg(psp->filename, psp->tokenlineno,
02317 "%%fallback argument \"%s\" should be a token", x);
02318 psp->errorcnt++;
02319 }else{
02320 struct symbol *sp = Symbol_new(x);
02321 if( psp->fallback==0 ){
02322 psp->fallback = sp;
02323 }else if( sp->fallback ){
02324 ErrorMsg(psp->filename, psp->tokenlineno,
02325 "More than one fallback assigned to token %s", x);
02326 psp->errorcnt++;
02327 }else{
02328 sp->fallback = psp->fallback;
02329 psp->gp->has_fallback = 1;
02330 }
02331 }
02332 break;
02333 case RESYNC_AFTER_RULE_ERROR:
02334
02335
02336 case RESYNC_AFTER_DECL_ERROR:
02337 if( x[0]=='.' ) psp->state = WAITING_FOR_DECL_OR_RULE;
02338 if( x[0]=='%' ) psp->state = WAITING_FOR_DECL_KEYWORD;
02339 break;
02340 }
02341 }
02342
02343
02344
02345
02346
02347
02348 static void preprocess_input(char *z){
02349 int i, j, k, n;
02350 int exclude = 0;
02351 int start = -1;
02352 int lineno = 1;
02353 int start_lineno = -1;
02354 for(i=0; z[i]; i++){
02355 if( z[i]=='\n' ) lineno++;
02356 if( z[i]!='%' || (i>0 && z[i-1]!='\n') ) continue;
02357 if( strncmp(&z[i],"%endif",6)==0 && isspace(z[i+6]) ){
02358 if( exclude ){
02359 exclude--;
02360 if( exclude==0 ){
02361 for(j=start; j<i; j++) if( z[j]!='\n' ) z[j] = ' ';
02362 }
02363 }
02364 for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';
02365 }else if( (strncmp(&z[i],"%ifdef",6)==0 && isspace(z[i+6]))
02366 || (strncmp(&z[i],"%ifndef",7)==0 && isspace(z[i+7])) ){
02367 if( exclude ){
02368 exclude++;
02369 }else{
02370 for(j=i+7; isspace(z[j]); j++){}
02371 for(n=0; z[j+n] && !isspace(z[j+n]); n++){}
02372 exclude = 1;
02373 for(k=0; k<nDefine; k++){
02374 if( strncmp(azDefine[k],&z[j],n)==0 && (int)strlen(azDefine[k])==n ){
02375 exclude = 0;
02376 break;
02377 }
02378 }
02379 if( z[i+3]=='n' ) exclude = !exclude;
02380 if( exclude ){
02381 start = i;
02382 start_lineno = lineno;
02383 }
02384 }
02385 for(j=i; z[j] && z[j]!='\n'; j++) z[j] = ' ';
02386 }
02387 }
02388 if( exclude ){
02389 fprintf(stderr,"unterminated %%ifdef starting on line %d\n", start_lineno);
02390 exit(1);
02391 }
02392 }
02393
02394
02395
02396
02397
02398
02399 void Parse(gp)
02400 struct lemon *gp;
02401 {
02402 struct pstate ps;
02403 FILE *fp;
02404 char *filebuf;
02405 int filesize;
02406 int lineno;
02407 int c;
02408 char *cp, *nextcp;
02409 int startline = 0;
02410
02411 memset(&ps, 0, sizeof(struct pstate));
02412 ps.gp = gp;
02413 ps.filename = gp->filename;
02414 ps.errorcnt = 0;
02415 ps.state = INITIALIZE;
02416
02417
02418 fp = fopen(ps.filename,"rb");
02419 if( fp==0 ){
02420 ErrorMsg(ps.filename,0,"Can't open this file for reading.");
02421 gp->errorcnt++;
02422 return;
02423 }
02424 fseek(fp,0,2);
02425 filesize = ftell(fp);
02426 if( filesize==-1 ){
02427 ErrorMsg(ps.filename,0,"Couldn't read size of this file.");
02428 gp->errorcnt++;
02429 return;
02430 }
02431 rewind(fp);
02432 filebuf = (char *)malloc( filesize+1 );
02433 if( filebuf==0 ){
02434 ErrorMsg(ps.filename,0,"Can't allocate %d of memory to hold this file.",
02435 filesize+1);
02436 gp->errorcnt++;
02437 return;
02438 }
02439 if( fread(filebuf,1,filesize,fp)!=(size_t)filesize ){
02440 ErrorMsg(ps.filename,0,"Can't read in all %d bytes of this file.",
02441 filesize);
02442 free(filebuf);
02443 gp->errorcnt++;
02444 return;
02445 }
02446 fclose(fp);
02447 filebuf[filesize] = 0;
02448
02449
02450 preprocess_input(filebuf);
02451
02452
02453 lineno = 1;
02454 for(cp=filebuf; (c= *cp)!=0; ){
02455 if( c=='\n' ) lineno++;
02456 if( isspace(c) ){ cp++; continue; }
02457 if( c=='/' && cp[1]=='/' ){
02458 cp+=2;
02459 while( (c= *cp)!=0 && c!='\n' ) cp++;
02460 continue;
02461 }
02462 if( c=='/' && cp[1]=='*' ){
02463 cp+=2;
02464 while( (c= *cp)!=0 && (c!='/' || cp[-1]!='*') ){
02465 if( c=='\n' ) lineno++;
02466 cp++;
02467 }
02468 if( c ) cp++;
02469 continue;
02470 }
02471 ps.tokenstart = cp;
02472 ps.tokenlineno = lineno;
02473 if( c=='\"' ){
02474 cp++;
02475 while( (c= *cp)!=0 && c!='\"' ){
02476 if( c=='\n' ) lineno++;
02477 cp++;
02478 }
02479 if( c==0 ){
02480 ErrorMsg(ps.filename,startline,
02481 "String starting on this line is not terminated before the end of the file.");
02482 ps.errorcnt++;
02483 nextcp = cp;
02484 }else{
02485 nextcp = cp+1;
02486 }
02487 }else if( c=='{' ){
02488 int level;
02489 cp++;
02490 for(level=1; (c= *cp)!=0 && (level>1 || c!='}'); cp++){
02491 if( c=='\n' ) lineno++;
02492 else if( c=='{' ) level++;
02493 else if( c=='}' ) level--;
02494 else if( c=='/' && cp[1]=='*' ){
02495 int prevc;
02496 cp = &cp[2];
02497 prevc = 0;
02498 while( (c= *cp)!=0 && (c!='/' || prevc!='*') ){
02499 if( c=='\n' ) lineno++;
02500 prevc = c;
02501 cp++;
02502 }
02503 }else if( c=='/' && cp[1]=='/' ){
02504 cp = &cp[2];
02505 while( (c= *cp)!=0 && c!='\n' ) cp++;
02506 if( c ) lineno++;
02507 }else if( c=='\'' || c=='\"' ){
02508 int startchar, prevc;
02509 startchar = c;
02510 prevc = 0;
02511 for(cp++; (c= *cp)!=0 && (c!=startchar || prevc=='\\'); cp++){
02512 if( c=='\n' ) lineno++;
02513 if( prevc=='\\' ) prevc = 0;
02514 else prevc = c;
02515 }
02516 }
02517 }
02518 if( c==0 ){
02519 ErrorMsg(ps.filename,ps.tokenlineno,
02520 "C code starting on this line is not terminated before the end of the file.");
02521 ps.errorcnt++;
02522 nextcp = cp;
02523 }else{
02524 nextcp = cp+1;
02525 }
02526 }else if( isalnum(c) ){
02527 while( (c= *cp)!=0 && (isalnum(c) || c=='_') ) cp++;
02528 nextcp = cp;
02529 }else if( c==':' && cp[1]==':' && cp[2]=='=' ){
02530 cp += 3;
02531 nextcp = cp;
02532 }else{
02533 cp++;
02534 nextcp = cp;
02535 }
02536 c = *cp;
02537 *cp = 0;
02538 parseonetoken(&ps);
02539 *cp = c;
02540 cp = nextcp;
02541 }
02542 free(filebuf);
02543 gp->rule = ps.firstrule;
02544 gp->errorcnt = ps.errorcnt;
02545 }
02546
02547
02548
02549
02550
02551 static struct plink *plink_freelist = 0;
02552
02553
02554 struct plink *Plink_new(){
02555 struct plink *new;
02556
02557 if( plink_freelist==0 ){
02558 int i;
02559 int amt = 100;
02560 plink_freelist = (struct plink *)malloc( sizeof(struct plink)*amt );
02561 if( plink_freelist==0 ){
02562 fprintf(stderr,
02563 "Unable to allocate memory for a new follow-set propagation link.\n");
02564 exit(1);
02565 }
02566 for(i=0; i<amt-1; i++) plink_freelist[i].next = &plink_freelist[i+1];
02567 plink_freelist[amt-1].next = 0;
02568 }
02569 new = plink_freelist;
02570 plink_freelist = plink_freelist->next;
02571 return new;
02572 }
02573
02574
02575 void Plink_add(plpp,cfp)
02576 struct plink **plpp;
02577 struct config *cfp;
02578 {
02579 struct plink *new;
02580 new = Plink_new();
02581 new->next = *plpp;
02582 *plpp = new;
02583 new->cfp = cfp;
02584 }
02585
02586
02587 void Plink_copy(to,from)
02588 struct plink **to;
02589 struct plink *from;
02590 {
02591 struct plink *nextpl;
02592 while( from ){
02593 nextpl = from->next;
02594 from->next = *to;
02595 *to = from;
02596 from = nextpl;
02597 }
02598 }
02599
02600
02601 void Plink_delete(plp)
02602 struct plink *plp;
02603 {
02604 struct plink *nextpl;
02605
02606 while( plp ){
02607 nextpl = plp->next;
02608 plp->next = plink_freelist;
02609 plink_freelist = plp;
02610 plp = nextpl;
02611 }
02612 }
02613
02614
02615
02616
02617
02618
02619
02620
02621
02622 PRIVATE char *file_makename(lemp,suffix)
02623 struct lemon *lemp;
02624 char *suffix;
02625 {
02626 char *name;
02627 char *cp;
02628 name = malloc( strlen(lemp->filename) + strlen(suffix) + 5 );
02629 if( name==0 ){
02630 fprintf(stderr,"Can't allocate space for a filename.\n");
02631 exit(1);
02632 }
02633 strcpy(name,lemp->filename);
02634 cp = strrchr(name,'.');
02635 if( cp ) *cp = 0;
02636 strcat(name,suffix);
02637 return name;
02638 }
02639
02640
02641
02642
02643 PRIVATE FILE *file_open(lemp,suffix,mode)
02644 struct lemon *lemp;
02645 char *suffix;
02646 char *mode;
02647 {
02648 FILE *fp;
02649
02650 if( lemp->outname ) free(lemp->outname);
02651 lemp->outname = file_makename(lemp, suffix);
02652 fp = fopen(lemp->outname,mode);
02653 if( fp==0 && *mode=='w' ){
02654 fprintf(stderr,"Can't open file \"%s\".\n",lemp->outname);
02655 lemp->errorcnt++;
02656 return 0;
02657 }
02658 return fp;
02659 }
02660
02661
02662
02663 void Reprint(lemp)
02664 struct lemon *lemp;
02665 {
02666 struct rule *rp;
02667 struct symbol *sp;
02668 int i, j, maxlen, len, ncolumns, skip;
02669 printf("// Reprint of input file \"%s\".\n// Symbols:\n",lemp->filename);
02670 maxlen = 10;
02671 for(i=0; i<lemp->nsymbol; i++){
02672 sp = lemp->symbols[i];
02673 len = strlen(sp->name);
02674 if( len>maxlen ) maxlen = len;
02675 }
02676 ncolumns = 76/(maxlen+5);
02677 if( ncolumns<1 ) ncolumns = 1;
02678 skip = (lemp->nsymbol + ncolumns - 1)/ncolumns;
02679 for(i=0; i<skip; i++){
02680 printf("//");
02681 for(j=i; j<lemp->nsymbol; j+=skip){
02682 sp = lemp->symbols[j];
02683 assert( sp->index==j );
02684 printf(" %3d %-*.*s",j,maxlen,maxlen,sp->name);
02685 }
02686 printf("\n");
02687 }
02688 for(rp=lemp->rule; rp; rp=rp->next){
02689 printf("%s",rp->lhs->name);
02690
02691 printf(" ::=");
02692 for(i=0; i<rp->nrhs; i++){
02693 printf(" %s",rp->rhs[i]->name);
02694
02695 }
02696 printf(".");
02697 if( rp->precsym ) printf(" [%s]",rp->precsym->name);
02698
02699 printf("\n");
02700 }
02701 }
02702
02703 void ConfigPrint(fp,cfp)
02704 FILE *fp;
02705 struct config *cfp;
02706 {
02707 struct rule *rp;
02708 int i;
02709 rp = cfp->rp;
02710 fprintf(fp,"%s ::=",rp->lhs->name);
02711 for(i=0; i<=rp->nrhs; i++){
02712 if( i==cfp->dot ) fprintf(fp," *");
02713 if( i==rp->nrhs ) break;
02714 fprintf(fp," %s",rp->rhs[i]->name);
02715 }
02716 }
02717
02718
02719 #ifdef TEST
02720
02721 PRIVATE void SetPrint(out,set,lemp)
02722 FILE *out;
02723 char *set;
02724 struct lemon *lemp;
02725 {
02726 int i;
02727 char *spacer;
02728 spacer = "";
02729 fprintf(out,"%12s[","");
02730 for(i=0; i<lemp->nterminal; i++){
02731 if( SetFind(set,i) ){
02732 fprintf(out,"%s%s",spacer,lemp->symbols[i]->name);
02733 spacer = " ";
02734 }
02735 }
02736 fprintf(out,"]\n");
02737 }
02738
02739
02740 PRIVATE void PlinkPrint(out,plp,tag)
02741 FILE *out;
02742 struct plink *plp;
02743 char *tag;
02744 {
02745 while( plp ){
02746 fprintf(out,"%12s%s (state %2d) ","",tag,plp->cfp->stp->index);
02747 ConfigPrint(out,plp->cfp);
02748 fprintf(out,"\n");
02749 plp = plp->next;
02750 }
02751 }
02752 #endif
02753
02754
02755
02756
02757 int PrintAction(struct action *ap, FILE *fp, int indent){
02758 int result = 1;
02759 switch( ap->type ){
02760 case SHIFT:
02761 fprintf(fp,"%*s shift %d",indent,ap->sp->name,ap->x.stp->index);
02762 break;
02763 case REDUCE:
02764 fprintf(fp,"%*s reduce %d",indent,ap->sp->name,ap->x.rp->index);
02765 break;
02766 case ACCEPT:
02767 fprintf(fp,"%*s accept",indent,ap->sp->name);
02768 break;
02769 case ERROR:
02770 fprintf(fp,"%*s error",indent,ap->sp->name);
02771 break;
02772 case CONFLICT:
02773 fprintf(fp,"%*s reduce %-3d ** Parsing conflict **",
02774 indent,ap->sp->name,ap->x.rp->index);
02775 break;
02776 case SH_RESOLVED:
02777 case RD_RESOLVED:
02778 case NOT_USED:
02779 result = 0;
02780 break;
02781 }
02782 return result;
02783 }
02784
02785
02786 void ReportOutput(lemp)
02787 struct lemon *lemp;
02788 {
02789 int i;
02790 struct state *stp;
02791 struct config *cfp;
02792 struct action *ap;
02793 FILE *fp;
02794
02795 fp = file_open(lemp,".out","wb");
02796 if( fp==0 ) return;
02797 fprintf(fp," \b");
02798 for(i=0; i<lemp->nstate; i++){
02799 stp = lemp->sorted[i];
02800 fprintf(fp,"State %d:\n",stp->index);
02801 if( lemp->basisflag ) cfp=stp->bp;
02802 else cfp=stp->cfp;
02803 while( cfp ){
02804 char buf[20];
02805 if( cfp->dot==cfp->rp->nrhs ){
02806 sprintf(buf,"(%d)",cfp->rp->index);
02807 fprintf(fp," %5s ",buf);
02808 }else{
02809 fprintf(fp," ");
02810 }
02811 ConfigPrint(fp,cfp);
02812 fprintf(fp,"\n");
02813 #ifdef TEST
02814 SetPrint(fp,cfp->fws,lemp);
02815 PlinkPrint(fp,cfp->fplp,"To ");
02816 PlinkPrint(fp,cfp->bplp,"From");
02817 #endif
02818 if( lemp->basisflag ) cfp=cfp->bp;
02819 else cfp=cfp->next;
02820 }
02821 fprintf(fp,"\n");
02822 for(ap=stp->ap; ap; ap=ap->next){
02823 if( PrintAction(ap,fp,30) ) fprintf(fp,"\n");
02824 }
02825 fprintf(fp,"\n");
02826 }
02827 fclose(fp);
02828 return;
02829 }
02830
02831
02832
02833 PRIVATE char *pathsearch(argv0,name,modemask)
02834 char *argv0;
02835 char *name;
02836 int modemask;
02837 {
02838 char *pathlist;
02839 char *path,*cp;
02840 char c;
02841 extern int access();
02842
02843 #ifdef __WIN32__
02844 cp = strrchr(argv0,'\\');
02845 #else
02846 cp = strrchr(argv0,'/');
02847 #endif
02848 if( cp ){
02849 c = *cp;
02850 *cp = 0;
02851 path = (char *)malloc( strlen(argv0) + strlen(name) + 2 );
02852 if( path ) sprintf(path,"%s/%s",argv0,name);
02853 *cp = c;
02854 }else{
02855 extern char *getenv();
02856 pathlist = getenv("PATH");
02857 if( pathlist==0 ) pathlist = ".:/bin:/usr/bin";
02858 path = (char *)malloc( strlen(pathlist)+strlen(name)+2 );
02859 if( path!=0 ){
02860 while( *pathlist ){
02861 cp = strchr(pathlist,':');
02862 if( cp==0 ) cp = &pathlist[strlen(pathlist)];
02863 c = *cp;
02864 *cp = 0;
02865 sprintf(path,"%s/%s",pathlist,name);
02866 *cp = c;
02867 if( c==0 ) pathlist = "";
02868 else pathlist = &cp[1];
02869 if( access(path,modemask)==0 ) break;
02870 }
02871 }
02872 }
02873 return path;
02874 }
02875
02876
02877
02878
02879
02880 PRIVATE int compute_action(lemp,ap)
02881 struct lemon *lemp;
02882 struct action *ap;
02883 {
02884 int act;
02885 switch( ap->type ){
02886 case SHIFT: act = ap->x.stp->index; break;
02887 case REDUCE: act = ap->x.rp->index + lemp->nstate; break;
02888 case ERROR: act = lemp->nstate + lemp->nrule; break;
02889 case ACCEPT: act = lemp->nstate + lemp->nrule + 1; break;
02890 default: act = -1; break;
02891 }
02892 return act;
02893 }
02894
02895 #define LINESIZE 1000
02896
02897
02898
02899
02900
02901
02902
02903
02904
02905 PRIVATE void tplt_xfer(name,in,out,lineno)
02906 char *name;
02907 FILE *in;
02908 FILE *out;
02909 int *lineno;
02910 {
02911 int i, iStart;
02912 char line[LINESIZE];
02913 while( fgets(line,LINESIZE,in) && (line[0]!='%' || line[1]!='%') ){
02914 (*lineno)++;
02915 iStart = 0;
02916 if( name ){
02917 for(i=0; line[i]; i++){
02918 if( line[i]=='P' && strncmp(&line[i],"Parse",5)==0
02919 && (i==0 || !isalpha(line[i-1]))
02920 ){
02921 if( i>iStart ) fprintf(out,"%.*s",i-iStart,&line[iStart]);
02922 fprintf(out,"%s",name);
02923 i += 4;
02924 iStart = i+1;
02925 }
02926 }
02927 }
02928 fprintf(out,"%s",&line[iStart]);
02929 }
02930 }
02931
02932
02933
02934 PRIVATE FILE *tplt_open(lemp)
02935 struct lemon *lemp;
02936 {
02937 static char templatename[] = "lempar.c";
02938 char buf[1000];
02939 FILE *in;
02940 char *tpltname;
02941 char *cp;
02942
02943 cp = strrchr(lemp->filename,'.');
02944 if( cp ){
02945 sprintf(buf,"%.*s.lt",(int)(cp-lemp->filename),lemp->filename);
02946 }else{
02947 sprintf(buf,"%s.lt",lemp->filename);
02948 }
02949 if( access(buf,004)==0 ){
02950 tpltname = buf;
02951 }else if( access(templatename,004)==0 ){
02952 tpltname = templatename;
02953 }else{
02954 tpltname = pathsearch(lemp->argv0,templatename,0);
02955 }
02956 if( tpltname==0 ){
02957 fprintf(stderr,"Can't find the parser driver template file \"%s\".\n",
02958 templatename);
02959 lemp->errorcnt++;
02960 return 0;
02961 }
02962 in = fopen(tpltname,"rb");
02963 if( in==0 ){
02964 fprintf(stderr,"Can't open the template file \"%s\".\n",templatename);
02965 lemp->errorcnt++;
02966 return 0;
02967 }
02968 return in;
02969 }
02970
02971
02972 PRIVATE void tplt_linedir(out,lineno,filename)
02973 FILE *out;
02974 int lineno;
02975 char *filename;
02976 {
02977 fprintf(out,"#line %d \"",lineno);
02978 while( *filename ){
02979 if( *filename == '\\' ) putc('\\',out);
02980 putc(*filename,out);
02981 filename++;
02982 }
02983 fprintf(out,"\"\n");
02984 }
02985
02986
02987 PRIVATE void tplt_print(out,lemp,str,strln,lineno)
02988 FILE *out;
02989 struct lemon *lemp;
02990 char *str;
02991 int strln;
02992 int *lineno;
02993 {
02994 if( str==0 ) return;
02995 tplt_linedir(out,strln,lemp->filename);
02996 (*lineno)++;
02997 while( *str ){
02998 if( *str=='\n' ) (*lineno)++;
02999 putc(*str,out);
03000 str++;
03001 }
03002 if( str[-1]!='\n' ){
03003 putc('\n',out);
03004 (*lineno)++;
03005 }
03006 tplt_linedir(out,*lineno+2,lemp->outname);
03007 (*lineno)+=2;
03008 return;
03009 }
03010
03011
03012
03013
03014
03015 void emit_destructor_code(out,sp,lemp,lineno)
03016 FILE *out;
03017 struct symbol *sp;
03018 struct lemon *lemp;
03019 int *lineno;
03020 {
03021 char *cp = 0;
03022
03023 int linecnt = 0;
03024 if( sp->type==TERMINAL ){
03025 cp = lemp->tokendest;
03026 if( cp==0 ) return;
03027 tplt_linedir(out,lemp->tokendestln,lemp->filename);
03028 fprintf(out,"{");
03029 }else if( sp->destructor ){
03030 cp = sp->destructor;
03031 tplt_linedir(out,sp->destructorln,lemp->filename);
03032 fprintf(out,"{");
03033 }else if( lemp->vardest ){
03034 cp = lemp->vardest;
03035 if( cp==0 ) return;
03036 tplt_linedir(out,lemp->vardestln,lemp->filename);
03037 fprintf(out,"{");
03038 }else{
03039 assert( 0 );
03040 }
03041 for(; *cp; cp++){
03042 if( *cp=='$' && cp[1]=='$' ){
03043 fprintf(out,"(yypminor->yy%d)",sp->dtnum);
03044 cp++;
03045 continue;
03046 }
03047 if( *cp=='\n' ) linecnt++;
03048 fputc(*cp,out);
03049 }
03050 (*lineno) += 3 + linecnt;
03051 fprintf(out,"}\n");
03052 tplt_linedir(out,*lineno,lemp->outname);
03053 return;
03054 }
03055
03056
03057
03058
03059 int has_destructor(sp, lemp)
03060 struct symbol *sp;
03061 struct lemon *lemp;
03062 {
03063 int ret;
03064 if( sp->type==TERMINAL ){
03065 ret = lemp->tokendest!=0;
03066 }else{
03067 ret = lemp->vardest!=0 || sp->destructor!=0;
03068 }
03069 return ret;
03070 }
03071
03072
03073
03074
03075
03076
03077
03078
03079
03080
03081
03082
03083
03084 PRIVATE char *append_str(char *zText, int n, int p1, int p2){
03085 static char *z = 0;
03086 static int alloced = 0;
03087 static int used = 0;
03088 int c;
03089 char zInt[40];
03090
03091 if( zText==0 ){
03092 used = 0;
03093 return z;
03094 }
03095 if( n<=0 ){
03096 if( n<0 ){
03097 used += n;
03098 assert( used>=0 );
03099 }
03100 n = strlen(zText);
03101 }
03102 if( n+sizeof(zInt)*2+used >= (size_t)alloced ){
03103 alloced = n + sizeof(zInt)*2 + used + 200;
03104 z = realloc(z, alloced);
03105 }
03106 if( z==0 ) return "";
03107 while( n-- > 0 ){
03108 c = *(zText++);
03109 if( c=='%' && zText[0]=='d' ){
03110 sprintf(zInt, "%d", p1);
03111 p1 = p2;
03112 strcpy(&z[used], zInt);
03113 used += strlen(&z[used]);
03114 zText++;
03115 n--;
03116 }else{
03117 z[used++] = c;
03118 }
03119 }
03120 z[used] = 0;
03121 return z;
03122 }
03123
03124
03125
03126
03127
03128
03129 PRIVATE void translate_code(struct lemon *lemp, struct rule *rp){
03130 char *cp, *xp;
03131 int i;
03132 char lhsused = 0;
03133 char used[MAXRHS];
03134
03135 for(i=0; i<rp->nrhs; i++) used[i] = 0;
03136 lhsused = 0;
03137
03138 append_str(0,0,0,0);
03139 for(cp=rp->code; *cp; cp++){
03140 if( isalpha(*cp) && (cp==rp->code || (!isalnum(cp[-1]) && cp[-1]!='_')) ){
03141 char saved;
03142 for(xp= &cp[1]; isalnum(*xp) || *xp=='_'; xp++);
03143 saved = *xp;
03144 *xp = 0;
03145 if( rp->lhsalias && strcmp(cp,rp->lhsalias)==0 ){
03146 append_str("yygotominor.yy%d",0,rp->lhs->dtnum,0);
03147 cp = xp;
03148 lhsused = 1;
03149 }else{
03150 for(i=0; i<rp->nrhs; i++){
03151 if( rp->rhsalias[i] && strcmp(cp,rp->rhsalias[i])==0 ){
03152 if( cp!=rp->code && cp[-1]=='@' ){
03153
03154
03155 append_str("yymsp[%d].major",-1,i-rp->nrhs+1,0);
03156 }else{
03157 append_str("yymsp[%d].minor.yy%d",0,
03158 i-rp->nrhs+1,rp->rhs[i]->dtnum);
03159 }
03160 cp = xp;
03161 used[i] = 1;
03162 break;
03163 }
03164 }
03165 }
03166 *xp = saved;
03167 }
03168 append_str(cp, 1, 0, 0);
03169 }
03170
03171
03172 if( rp->lhsalias && !lhsused ){
03173 ErrorMsg(lemp->filename,rp->ruleline,
03174 "Label \"%s\" for \"%s(%s)\" is never used.",
03175 rp->lhsalias,rp->lhs->name,rp->lhsalias);
03176 lemp->errorcnt++;
03177 }
03178
03179
03180
03181 for(i=0; i<rp->nrhs; i++){
03182 if( rp->rhsalias[i] && !used[i] ){
03183 ErrorMsg(lemp->filename,rp->ruleline,
03184 "Label %s for \"%s(%s)\" is never used.",
03185 rp->rhsalias[i],rp->rhs[i]->name,rp->rhsalias[i]);
03186 lemp->errorcnt++;
03187 }else if( rp->rhsalias[i]==0 ){
03188 if( has_destructor(rp->rhs[i],lemp) ){
03189 append_str(" yy_destructor(%d,&yymsp[%d].minor);\n", 0,
03190 rp->rhs[i]->index,i-rp->nrhs+1);
03191 }else{
03192
03193 }
03194 }
03195 }
03196 cp = append_str(0,0,0,0);
03197 rp->code = Strsafe(cp);
03198 }
03199
03200
03201
03202
03203
03204 PRIVATE void emit_code(out,rp,lemp,lineno)
03205 FILE *out;
03206 struct rule *rp;
03207 struct lemon *lemp;
03208 int *lineno;
03209 {
03210 char *cp;
03211 int linecnt = 0;
03212
03213
03214 if( rp->code ){
03215 tplt_linedir(out,rp->line,lemp->filename);
03216 fprintf(out,"{%s",rp->code);
03217 for(cp=rp->code; *cp; cp++){
03218 if( *cp=='\n' ) linecnt++;
03219 }
03220 (*lineno) += 3 + linecnt;
03221 fprintf(out,"}\n");
03222 tplt_linedir(out,*lineno,lemp->outname);
03223 }
03224
03225 return;
03226 }
03227
03228
03229
03230
03231
03232
03233
03234
03235 void print_stack_union(out,lemp,plineno,mhflag)
03236 FILE *out;
03237 struct lemon *lemp;
03238 int *plineno;
03239 int mhflag;
03240 {
03241 int lineno = *plineno;
03242 char **types;
03243 int arraysize;
03244 int maxdtlength;
03245 char *stddt;
03246 int i,j;
03247 int hash;
03248 char *name;
03249
03250
03251 arraysize = lemp->nsymbol * 2;
03252 types = (char**)malloc( arraysize * sizeof(char*) );
03253 for(i=0; i<arraysize; i++) types[i] = 0;
03254 maxdtlength = 0;
03255 if( lemp->vartype ){
03256 maxdtlength = strlen(lemp->vartype);
03257 }
03258 for(i=0; i<lemp->nsymbol; i++){
03259 int len;
03260 struct symbol *sp = lemp->symbols[i];
03261 if( sp->datatype==0 ) continue;
03262 len = strlen(sp->datatype);
03263 if( len>maxdtlength ) maxdtlength = len;
03264 }
03265 stddt = (char*)malloc( maxdtlength*2 + 1 );
03266 if( types==0 || stddt==0 ){
03267 fprintf(stderr,"Out of memory.\n");
03268 exit(1);
03269 }
03270
03271
03272
03273
03274
03275
03276
03277 for(i=0; i<lemp->nsymbol; i++){
03278 struct symbol *sp = lemp->symbols[i];
03279 char *cp;
03280 if( sp==lemp->errsym ){
03281 sp->dtnum = arraysize+1;
03282 continue;
03283 }
03284 if( sp->type!=NONTERMINAL || (sp->datatype==0 && lemp->vartype==0) ){
03285 sp->dtnum = 0;
03286 continue;
03287 }
03288 cp = sp->datatype;
03289 if( cp==0 ) cp = lemp->vartype;
03290 j = 0;
03291 while( isspace(*cp) ) cp++;
03292 while( *cp ) stddt[j++] = *cp++;
03293 while( j>0 && isspace(stddt[j-1]) ) j--;
03294 stddt[j] = 0;
03295 hash = 0;
03296 for(j=0; stddt[j]; j++){
03297 hash = hash*53 + stddt[j];
03298 }
03299 hash = (hash & 0x7fffffff)%arraysize;
03300 while( types[hash] ){
03301 if( strcmp(types[hash],stddt)==0 ){
03302 sp->dtnum = hash + 1;
03303 break;
03304 }
03305 hash++;
03306 if( hash>=arraysize ) hash = 0;
03307 }
03308 if( types[hash]==0 ){
03309 sp->dtnum = hash + 1;
03310 types[hash] = (char*)malloc( strlen(stddt)+1 );
03311 if( types[hash]==0 ){
03312 fprintf(stderr,"Out of memory.\n");
03313 exit(1);
03314 }
03315 strcpy(types[hash],stddt);
03316 }
03317 }
03318
03319
03320 name = lemp->name ? lemp->name : "Parse";
03321 lineno = *plineno;
03322 if( mhflag ){ fprintf(out,"#if INTERFACE\n"); lineno++; }
03323 fprintf(out,"#define %sTOKENTYPE %s\n",name,
03324 lemp->tokentype?lemp->tokentype:"void*"); lineno++;
03325 if( mhflag ){ fprintf(out,"#endif\n"); lineno++; }
03326 fprintf(out,"typedef union {\n"); lineno++;
03327 fprintf(out," %sTOKENTYPE yy0;\n",name); lineno++;
03328 for(i=0; i<arraysize; i++){
03329 if( types[i]==0 ) continue;
03330 fprintf(out," %s yy%d;\n",types[i],i+1); lineno++;
03331 free(types[i]);
03332 }
03333 fprintf(out," int yy%d;\n",lemp->errsym->dtnum); lineno++;
03334 free(stddt);
03335 free(types);
03336 fprintf(out,"} YYMINORTYPE;\n"); lineno++;
03337 *plineno = lineno;
03338 }
03339
03340
03341
03342
03343
03344 static const char *minimum_size_type(int lwr, int upr){
03345 if( lwr>=0 ){
03346 if( upr<=255 ){
03347 return "unsigned char";
03348 }else if( upr<65535 ){
03349 return "unsigned short int";
03350 }else{
03351 return "unsigned int";
03352 }
03353 }else if( lwr>=-127 && upr<=127 ){
03354 return "signed char";
03355 }else if( lwr>=-32767 && upr<32767 ){
03356 return "short";
03357 }else{
03358 return "int";
03359 }
03360 }
03361
03362
03363
03364
03365
03366
03367
03368 struct axset {
03369 struct state *stp;
03370 int isTkn;
03371 int nAction;
03372 };
03373
03374
03375
03376
03377 static int axset_compare(const void *a, const void *b){
03378 struct axset *p1 = (struct axset*)a;
03379 struct axset *p2 = (struct axset*)b;
03380 return p2->nAction - p1->nAction;
03381 }
03382
03383
03384 void ReportTable(lemp, mhflag)
03385 struct lemon *lemp;
03386 int mhflag;
03387 {
03388 FILE *out, *in;
03389 char line[LINESIZE];
03390 int lineno;
03391 struct state *stp;
03392 struct action *ap;
03393 struct rule *rp;
03394 struct acttab *pActtab;
03395 int i, j, n;
03396 char *name;
03397 int mnTknOfst, mxTknOfst;
03398 int mnNtOfst, mxNtOfst;
03399 struct axset *ax;
03400
03401 in = tplt_open(lemp);
03402 if( in==0 ) return;
03403 if( output_filename!=0 ){
03404 char *tmp = lemp->filename;
03405 char *ext = strrchr(output_filename, '.');
03406 if( ext==0 ) ext = ".c";
03407 lemp->filename = output_filename;
03408 out = file_open(lemp,ext,"wb");
03409 lemp->filename = tmp;
03410 }else{
03411 out = file_open(lemp,".c","wb");
03412 }
03413 if( out==0 ){
03414 fclose(in);
03415 return;
03416 }
03417 lineno = 1;
03418 tplt_xfer(lemp->name,in,out,&lineno);
03419
03420
03421 tplt_print(out,lemp,lemp->include,lemp->includeln,&lineno);
03422 if( mhflag ){
03423 char *name = file_makename(lemp, ".h");
03424 fprintf(out,"#include \"%s\"\n", name); lineno++;
03425 free(name);
03426 }
03427 tplt_xfer(lemp->name,in,out,&lineno);
03428
03429
03430 if( mhflag ){
03431 char *prefix;
03432 fprintf(out,"#if INTERFACE\n"); lineno++;
03433 if( lemp->tokenprefix ) prefix = lemp->tokenprefix;
03434 else prefix = "";
03435 for(i=1; i<lemp->nterminal; i++){
03436 fprintf(out,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
03437 lineno++;
03438 }
03439 fprintf(out,"#endif\n"); lineno++;
03440 }
03441 tplt_xfer(lemp->name,in,out,&lineno);
03442
03443
03444 fprintf(out,"#define YYCODETYPE %s\n",
03445 minimum_size_type(0, lemp->nsymbol+5)); lineno++;
03446 fprintf(out,"#define YYNOCODE %d\n",lemp->nsymbol+1); lineno++;
03447 fprintf(out,"#define YYACTIONTYPE %s\n",
03448 minimum_size_type(0, lemp->nstate+lemp->nrule+5)); lineno++;
03449 print_stack_union(out,lemp,&lineno,mhflag);
03450 if( lemp->stacksize ){
03451 if( atoi(lemp->stacksize)<=0 ){
03452 ErrorMsg(lemp->filename,0,
03453 "Illegal stack size: [%s]. The stack size should be an integer constant.",
03454 lemp->stacksize);
03455 lemp->errorcnt++;
03456 lemp->stacksize = "100";
03457 }
03458 fprintf(out,"#define YYSTACKDEPTH %s\n",lemp->stacksize); lineno++;
03459 }else{
03460 fprintf(out,"#define YYSTACKDEPTH 100\n"); lineno++;
03461 }
03462 if( mhflag ){
03463 fprintf(out,"#if INTERFACE\n"); lineno++;
03464 }
03465 name = lemp->name ? lemp->name : "Parse";
03466 if( lemp->arg && lemp->arg[0] ){
03467 int i;
03468 i = strlen(lemp->arg);
03469 while( i>=1 && isspace(lemp->arg[i-1]) ) i--;
03470 while( i>=1 && (isalnum(lemp->arg[i-1]) || lemp->arg[i-1]=='_') ) i--;
03471 fprintf(out,"#define %sARG_SDECL %s;\n",name,lemp->arg); lineno++;
03472 fprintf(out,"#define %sARG_PDECL ,%s\n",name,lemp->arg); lineno++;
03473 fprintf(out,"#define %sARG_FETCH %s = yypParser->%s\n",
03474 name,lemp->arg,&lemp->arg[i]); lineno++;
03475 fprintf(out,"#define %sARG_STORE yypParser->%s = %s\n",
03476 name,&lemp->arg[i],&lemp->arg[i]); lineno++;
03477 }else{
03478 fprintf(out,"#define %sARG_SDECL\n",name); lineno++;
03479 fprintf(out,"#define %sARG_PDECL\n",name); lineno++;
03480 fprintf(out,"#define %sARG_FETCH\n",name); lineno++;
03481 fprintf(out,"#define %sARG_STORE\n",name); lineno++;
03482 }
03483 if( mhflag ){
03484 fprintf(out,"#endif\n"); lineno++;
03485 }
03486 fprintf(out,"#define YYNSTATE %d\n",lemp->nstate); lineno++;
03487 fprintf(out,"#define YYNRULE %d\n",lemp->nrule); lineno++;
03488 fprintf(out,"#define YYERRORSYMBOL %d\n",lemp->errsym->index); lineno++;
03489 fprintf(out,"#define YYERRSYMDT yy%d\n",lemp->errsym->dtnum); lineno++;
03490 if( lemp->has_fallback ){
03491 fprintf(out,"#define YYFALLBACK 1\n"); lineno++;
03492 }
03493 tplt_xfer(lemp->name,in,out,&lineno);
03494
03495
03496
03497
03498
03499
03500
03501
03502
03503
03504
03505
03506
03507
03508 ax = malloc( sizeof(ax[0])*lemp->nstate*2 );
03509 if( ax==0 ){
03510 fprintf(stderr,"malloc failed\n");
03511 exit(1);
03512 }
03513 for(i=0; i<lemp->nstate; i++){
03514 stp = lemp->sorted[i];
03515 stp->nTknAct = stp->nNtAct = 0;
03516 stp->iDflt = lemp->nstate + lemp->nrule;
03517 stp->iTknOfst = NO_OFFSET;
03518 stp->iNtOfst = NO_OFFSET;
03519 for(ap=stp->ap; ap; ap=ap->next){
03520 if( compute_action(lemp,ap)>=0 ){
03521 if( ap->sp->index<lemp->nterminal ){
03522 stp->nTknAct++;
03523 }else if( ap->sp->index<lemp->nsymbol ){
03524 stp->nNtAct++;
03525 }else{
03526 stp->iDflt = compute_action(lemp, ap);
03527 }
03528 }
03529 }
03530 ax[i*2].stp = stp;
03531 ax[i*2].isTkn = 1;
03532 ax[i*2].nAction = stp->nTknAct;
03533 ax[i*2+1].stp = stp;
03534 ax[i*2+1].isTkn = 0;
03535 ax[i*2+1].nAction = stp->nNtAct;
03536 }
03537 mxTknOfst = mnTknOfst = 0;
03538 mxNtOfst = mnNtOfst = 0;
03539
03540
03541
03542
03543
03544 qsort(ax, lemp->nstate*2, sizeof(ax[0]), axset_compare);
03545 pActtab = acttab_alloc();
03546 for(i=0; i<lemp->nstate*2 && ax[i].nAction>0; i++){
03547 stp = ax[i].stp;
03548 if( ax[i].isTkn ){
03549 for(ap=stp->ap; ap; ap=ap->next){
03550 int action;
03551 if( ap->sp->index>=lemp->nterminal ) continue;
03552 action = compute_action(lemp, ap);
03553 if( action<0 ) continue;
03554 acttab_action(pActtab, ap->sp->index, action);
03555 }
03556 stp->iTknOfst = acttab_insert(pActtab);
03557 if( stp->iTknOfst<mnTknOfst ) mnTknOfst = stp->iTknOfst;
03558 if( stp->iTknOfst>mxTknOfst ) mxTknOfst = stp->iTknOfst;
03559 }else{
03560 for(ap=stp->ap; ap; ap=ap->next){
03561 int action;
03562 if( ap->sp->index<lemp->nterminal ) continue;
03563 if( ap->sp->index==lemp->nsymbol ) continue;
03564 action = compute_action(lemp, ap);
03565 if( action<0 ) continue;
03566 acttab_action(pActtab, ap->sp->index, action);
03567 }
03568 stp->iNtOfst = acttab_insert(pActtab);
03569 if( stp->iNtOfst<mnNtOfst ) mnNtOfst = stp->iNtOfst;
03570 if( stp->iNtOfst>mxNtOfst ) mxNtOfst = stp->iNtOfst;
03571 }
03572 }
03573 free(ax);
03574
03575
03576 fprintf(out,"static const YYACTIONTYPE yy_action[] = {\n"); lineno++;
03577 n = acttab_size(pActtab);
03578 for(i=j=0; i<n; i++){
03579 int action = acttab_yyaction(pActtab, i);
03580 if( action<0 ) action = lemp->nsymbol + lemp->nrule + 2;
03581 if( j==0 ) fprintf(out," /* %5d */ ", i);
03582 fprintf(out, " %4d,", action);
03583 if( j==9 || i==n-1 ){
03584 fprintf(out, "\n"); lineno++;
03585 j = 0;
03586 }else{
03587 j++;
03588 }
03589 }
03590 fprintf(out, "};\n"); lineno++;
03591
03592
03593 fprintf(out,"static const YYCODETYPE yy_lookahead[] = {\n"); lineno++;
03594 for(i=j=0; i<n; i++){
03595 int la = acttab_yylookahead(pActtab, i);
03596 if( la<0 ) la = lemp->nsymbol;
03597 if( j==0 ) fprintf(out," /* %5d */ ", i);
03598 fprintf(out, " %4d,", la);
03599 if( j==9 || i==n-1 ){
03600 fprintf(out, "\n"); lineno++;
03601 j = 0;
03602 }else{
03603 j++;
03604 }
03605 }
03606 fprintf(out, "};\n"); lineno++;
03607
03608
03609 fprintf(out, "#define YY_SHIFT_USE_DFLT (%d)\n", mnTknOfst-1); lineno++;
03610 fprintf(out, "static const %s yy_shift_ofst[] = {\n",
03611 minimum_size_type(mnTknOfst-1, mxTknOfst)); lineno++;
03612 n = lemp->nstate;
03613 for(i=j=0; i<n; i++){
03614 int ofst;
03615 stp = lemp->sorted[i];
03616 ofst = stp->iTknOfst;
03617 if( ofst==NO_OFFSET ) ofst = mnTknOfst - 1;
03618 if( j==0 ) fprintf(out," /* %5d */ ", i);
03619 fprintf(out, " %4d,", ofst);
03620 if( j==9 || i==n-1 ){
03621 fprintf(out, "\n"); lineno++;
03622 j = 0;
03623 }else{
03624 j++;
03625 }
03626 }
03627 fprintf(out, "};\n"); lineno++;
03628
03629
03630 fprintf(out, "#define YY_REDUCE_USE_DFLT (%d)\n", mnNtOfst-1); lineno++;
03631 fprintf(out, "static const %s yy_reduce_ofst[] = {\n",
03632 minimum_size_type(mnNtOfst-1, mxNtOfst)); lineno++;
03633 n = lemp->nstate;
03634 for(i=j=0; i<n; i++){
03635 int ofst;
03636 stp = lemp->sorted[i];
03637 ofst = stp->iNtOfst;
03638 if( ofst==NO_OFFSET ) ofst = mnNtOfst - 1;
03639 if( j==0 ) fprintf(out," /* %5d */ ", i);
03640 fprintf(out, " %4d,", ofst);
03641 if( j==9 || i==n-1 ){
03642 fprintf(out, "\n"); lineno++;
03643 j = 0;
03644 }else{
03645 j++;
03646 }
03647 }
03648 fprintf(out, "};\n"); lineno++;
03649
03650
03651 fprintf(out, "static const YYACTIONTYPE yy_default[] = {\n"); lineno++;
03652 n = lemp->nstate;
03653 for(i=j=0; i<n; i++){
03654 stp = lemp->sorted[i];
03655 if( j==0 ) fprintf(out," /* %5d */ ", i);
03656 fprintf(out, " %4d,", stp->iDflt);
03657 if( j==9 || i==n-1 ){
03658 fprintf(out, "\n"); lineno++;
03659 j = 0;
03660 }else{
03661 j++;
03662 }
03663 }
03664 fprintf(out, "};\n"); lineno++;
03665 tplt_xfer(lemp->name,in,out,&lineno);
03666
03667
03668
03669 if( lemp->has_fallback ){
03670 for(i=0; i<lemp->nterminal; i++){
03671 struct symbol *p = lemp->symbols[i];
03672 if( p->fallback==0 ){
03673 fprintf(out, " 0, /* %10s => nothing */\n", p->name);
03674 }else{
03675 fprintf(out, " %3d, /* %10s => %s */\n", p->fallback->index,
03676 p->name, p->fallback->name);
03677 }
03678 lineno++;
03679 }
03680 }
03681 tplt_xfer(lemp->name, in, out, &lineno);
03682
03683
03684
03685 for(i=0; i<lemp->nsymbol; i++){
03686 sprintf(line,"\"%s\",",lemp->symbols[i]->name);
03687 fprintf(out," %-15s",line);
03688 if( (i&3)==3 ){ fprintf(out,"\n"); lineno++; }
03689 }
03690 if( (i&3)!=0 ){ fprintf(out,"\n"); lineno++; }
03691 tplt_xfer(lemp->name,in,out,&lineno);
03692
03693
03694
03695
03696
03697 for(i=0, rp=lemp->rule; rp; rp=rp->next, i++){
03698 assert( rp->index==i );
03699 fprintf(out," /* %3d */ \"%s ::=", i, rp->lhs->name);
03700 for(j=0; j<rp->nrhs; j++) fprintf(out," %s",rp->rhs[j]->name);
03701 fprintf(out,"\",\n"); lineno++;
03702 }
03703 tplt_xfer(lemp->name,in,out,&lineno);
03704
03705
03706
03707
03708
03709 if( lemp->tokendest ){
03710 for(i=0; i<lemp->nsymbol; i++){
03711 struct symbol *sp = lemp->symbols[i];
03712 if( sp==0 || sp->type!=TERMINAL ) continue;
03713 fprintf(out," case %d:\n",sp->index); lineno++;
03714 }
03715 for(i=0; i<lemp->nsymbol && lemp->symbols[i]->type!=TERMINAL; i++);
03716 if( i<lemp->nsymbol ){
03717 emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
03718 fprintf(out," break;\n"); lineno++;
03719 }
03720 }
03721 for(i=0; i<lemp->nsymbol; i++){
03722 struct symbol *sp = lemp->symbols[i];
03723 if( sp==0 || sp->type==TERMINAL || sp->destructor==0 ) continue;
03724 fprintf(out," case %d:\n",sp->index); lineno++;
03725
03726
03727 for(j=i+1; j<lemp->nsymbol; j++){
03728 struct symbol *sp2 = lemp->symbols[j];
03729 if( sp2 && sp2->type!=TERMINAL && sp2->destructor
03730 && sp2->dtnum==sp->dtnum
03731 && strcmp(sp->destructor,sp2->destructor)==0 ){
03732 fprintf(out," case %d:\n",sp2->index); lineno++;
03733 sp2->destructor = 0;
03734 }
03735 }
03736
03737 emit_destructor_code(out,lemp->symbols[i],lemp,&lineno);
03738 fprintf(out," break;\n"); lineno++;
03739 }
03740 if( lemp->vardest ){
03741 struct symbol *dflt_sp = 0;
03742 for(i=0; i<lemp->nsymbol; i++){
03743 struct symbol *sp = lemp->symbols[i];
03744 if( sp==0 || sp->type==TERMINAL ||
03745 sp->index<=0 || sp->destructor!=0 ) continue;
03746 fprintf(out," case %d:\n",sp->index); lineno++;
03747 dflt_sp = sp;
03748 }
03749 if( dflt_sp!=0 ){
03750 emit_destructor_code(out,dflt_sp,lemp,&lineno);
03751 fprintf(out," break;\n"); lineno++;
03752 }
03753 }
03754 tplt_xfer(lemp->name,in,out,&lineno);
03755
03756
03757 tplt_print(out,lemp,lemp->overflow,lemp->overflowln,&lineno);
03758 tplt_xfer(lemp->name,in,out,&lineno);
03759
03760
03761
03762
03763
03764
03765 for(rp=lemp->rule; rp; rp=rp->next){
03766 fprintf(out," { %d, %d },\n",rp->lhs->index,rp->nrhs); lineno++;
03767 }
03768 tplt_xfer(lemp->name,in,out,&lineno);
03769
03770
03771 for(rp=lemp->rule; rp; rp=rp->next){
03772 if( rp->code ) translate_code(lemp, rp);
03773 }
03774 for(rp=lemp->rule; rp; rp=rp->next){
03775 struct rule *rp2;
03776 if( rp->code==0 ) continue;
03777 fprintf(out," case %d:\n",rp->index); lineno++;
03778 for(rp2=rp->next; rp2; rp2=rp2->next){
03779 if( rp2->code==rp->code ){
03780 fprintf(out," case %d:\n",rp2->index); lineno++;
03781 rp2->code = 0;
03782 }
03783 }
03784 emit_code(out,rp,lemp,&lineno);
03785 fprintf(out," break;\n"); lineno++;
03786 }
03787 tplt_xfer(lemp->name,in,out,&lineno);
03788
03789
03790 tplt_print(out,lemp,lemp->failure,lemp->failureln,&lineno);
03791 tplt_xfer(lemp->name,in,out,&lineno);
03792
03793
03794 tplt_print(out,lemp,lemp->error,lemp->errorln,&lineno);
03795 tplt_xfer(lemp->name,in,out,&lineno);
03796
03797
03798 tplt_print(out,lemp,lemp->accept,lemp->acceptln,&lineno);
03799 tplt_xfer(lemp->name,in,out,&lineno);
03800
03801
03802 tplt_print(out,lemp,lemp->extracode,lemp->extracodeln,&lineno);
03803
03804 fclose(in);
03805 fclose(out);
03806 return;
03807 }
03808
03809
03810 void ReportHeader(lemp)
03811 struct lemon *lemp;
03812 {
03813 FILE *out, *in;
03814 char *prefix;
03815 char line[LINESIZE];
03816 char pattern[LINESIZE];
03817 int i;
03818
03819 if( lemp->tokenprefix ) prefix = lemp->tokenprefix;
03820 else prefix = "";
03821 if( output_header_filename!=0 ){
03822 char *tmp = lemp->filename;
03823 char *ext = strrchr(output_header_filename, '.');
03824 if( ext==0 ) ext = ".h";
03825 lemp->filename = output_header_filename;
03826 in = file_open(lemp,ext,"rb");
03827 lemp->filename = tmp;
03828 }else{
03829 in = file_open(lemp,".h","rb");
03830 }
03831 if( in ){
03832 for(i=1; i<lemp->nterminal && fgets(line,LINESIZE,in); i++){
03833 sprintf(pattern,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
03834 if( strcmp(line,pattern) ) break;
03835 }
03836 fclose(in);
03837 if( i==lemp->nterminal ){
03838
03839 return;
03840 }
03841 }
03842 if( output_header_filename!=0 ){
03843 char *tmp = lemp->filename;
03844 char *ext = strrchr(output_header_filename, '.');
03845 if( ext==0 ) ext = ".h";
03846 lemp->filename = output_header_filename;
03847 out = file_open(lemp,ext,"wb");
03848 lemp->filename = tmp;
03849 }else{
03850 out = file_open(lemp,".h","wb");
03851 }
03852 if( out ){
03853 for(i=1; i<lemp->nterminal; i++){
03854 fprintf(out,"#define %s%-30s %2d\n",prefix,lemp->symbols[i]->name,i);
03855 }
03856 fclose(out);
03857 }
03858 return;
03859 }
03860
03861
03862
03863
03864
03865
03866
03867 void CompressTables(lemp)
03868 struct lemon *lemp;
03869 {
03870 struct state *stp;
03871 struct action *ap, *ap2;
03872 struct rule *rp, *rp2, *rbest;
03873 int nbest, n;
03874 int i;
03875
03876 for(i=0; i<lemp->nstate; i++){
03877 stp = lemp->sorted[i];
03878 nbest = 0;
03879 rbest = 0;
03880
03881 for(ap=stp->ap; ap; ap=ap->next){
03882 if( ap->type!=REDUCE ) continue;
03883 rp = ap->x.rp;
03884 if( rp==rbest ) continue;
03885 n = 1;
03886 for(ap2=ap->next; ap2; ap2=ap2->next){
03887 if( ap2->type!=REDUCE ) continue;
03888 rp2 = ap2->x.rp;
03889 if( rp2==rbest ) continue;
03890 if( rp2==rp ) n++;
03891 }
03892 if( n>nbest ){
03893 nbest = n;
03894 rbest = rp;
03895 }
03896 }
03897
03898
03899
03900 if( nbest<2 ) continue;
03901
03902
03903
03904 for(ap=stp->ap; ap; ap=ap->next){
03905 if( ap->type==REDUCE && ap->x.rp==rbest ) break;
03906 }
03907 assert( ap );
03908 ap->sp = Symbol_new("{default}");
03909 for(ap=ap->next; ap; ap=ap->next){
03910 if( ap->type==REDUCE && ap->x.rp==rbest ) ap->type = NOT_USED;
03911 }
03912 stp->ap = Action_sort(stp->ap);
03913 }
03914 }
03915
03916
03917
03918
03919
03920
03921 static int size = 0;
03922
03923
03924 void SetSize(n)
03925 int n;
03926 {
03927 size = n+1;
03928 }
03929
03930
03931 char *SetNew(){
03932 char *s;
03933 int i;
03934 s = (char*)malloc( size );
03935 if( s==0 ){
03936 extern void memory_error();
03937 memory_error();
03938 }
03939 for(i=0; i<size; i++) s[i] = 0;
03940 return s;
03941 }
03942
03943
03944 void SetFree(s)
03945 char *s;
03946 {
03947 free(s);
03948 }
03949
03950
03951
03952 int SetAdd(s,e)
03953 char *s;
03954 int e;
03955 {
03956 int rv;
03957 rv = s[e];
03958 s[e] = 1;
03959 return !rv;
03960 }
03961
03962
03963 int SetUnion(s1,s2)
03964 char *s1;
03965 char *s2;
03966 {
03967 int i, progress;
03968 progress = 0;
03969 for(i=0; i<size; i++){
03970 if( s2[i]==0 ) continue;
03971 if( s1[i]==0 ){
03972 progress = 1;
03973 s1[i] = 1;
03974 }
03975 }
03976 return progress;
03977 }
03978
03979
03980
03981
03982
03983
03984
03985
03986
03987
03988
03989
03990
03991 PRIVATE int strhash(x)
03992 char *x;
03993 {
03994 int h = 0;
03995 while( *x) h = h*13 + *(x++);
03996 return h;
03997 }
03998
03999
04000
04001
04002
04003 char *Strsafe(y)
04004 char *y;
04005 {
04006 char *z;
04007
04008 z = Strsafe_find(y);
04009 if( z==0 && (z=malloc( strlen(y)+1 ))!=0 ){
04010 strcpy(z,y);
04011 Strsafe_insert(z);
04012 }
04013 MemoryCheck(z);
04014 return z;
04015 }
04016
04017
04018
04019
04020 struct s_x1 {
04021 int size;
04022
04023
04024 int count;
04025 struct s_x1node *tbl;
04026 struct s_x1node **ht;
04027 };
04028
04029
04030
04031
04032 typedef struct s_x1node {
04033 char *data;
04034 struct s_x1node *next;
04035 struct s_x1node **from;
04036 } x1node;
04037
04038
04039 static struct s_x1 *x1a;
04040
04041
04042 void Strsafe_init(){
04043 if( x1a ) return;
04044 x1a = (struct s_x1*)malloc( sizeof(struct s_x1) );
04045 if( x1a ){
04046 x1a->size = 1024;
04047 x1a->count = 0;
04048 x1a->tbl = (x1node*)malloc(
04049 (sizeof(x1node) + sizeof(x1node*))*1024 );
04050 if( x1a->tbl==0 ){
04051 free(x1a);
04052 x1a = 0;
04053 }else{
04054 int i;
04055 x1a->ht = (x1node**)&(x1a->tbl[1024]);
04056 for(i=0; i<1024; i++) x1a->ht[i] = 0;
04057 }
04058 }
04059 }
04060
04061
04062 int Strsafe_insert(data)
04063 char *data;
04064 {
04065 x1node *np;
04066 int h;
04067 int ph;
04068
04069 if( x1a==0 ) return 0;
04070 ph = strhash(data);
04071 h = ph & (x1a->size-1);
04072 np = x1a->ht[h];
04073 while( np ){
04074 if( strcmp(np->data,data)==0 ){
04075
04076
04077 return 0;
04078 }
04079 np = np->next;
04080 }
04081 if( x1a->count>=x1a->size ){
04082
04083 int i,size;
04084 struct s_x1 array;
04085 array.size = size = x1a->size*2;
04086 array.count = x1a->count;
04087 array.tbl = (x1node*)malloc(
04088 (sizeof(x1node) + sizeof(x1node*))*size );
04089 if( array.tbl==0 ) return 0;
04090 array.ht = (x1node**)&(array.tbl[size]);
04091 for(i=0; i<size; i++) array.ht[i] = 0;
04092 for(i=0; i<x1a->count; i++){
04093 x1node *oldnp, *newnp;
04094 oldnp = &(x1a->tbl[i]);
04095 h = strhash(oldnp->data) & (size-1);
04096 newnp = &(array.tbl[i]);
04097 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
04098 newnp->next = array.ht[h];
04099 newnp->data = oldnp->data;
04100 newnp->from = &(array.ht[h]);
04101 array.ht[h] = newnp;
04102 }
04103 free(x1a->tbl);
04104 *x1a = array;
04105 }
04106
04107 h = ph & (x1a->size-1);
04108 np = &(x1a->tbl[x1a->count++]);
04109 np->data = data;
04110 if( x1a->ht[h] ) x1a->ht[h]->from = &(np->next);
04111 np->next = x1a->ht[h];
04112 x1a->ht[h] = np;
04113 np->from = &(x1a->ht[h]);
04114 return 1;
04115 }
04116
04117
04118
04119 char *Strsafe_find(key)
04120 char *key;
04121 {
04122 int h;
04123 x1node *np;
04124
04125 if( x1a==0 ) return 0;
04126 h = strhash(key) & (x1a->size-1);
04127 np = x1a->ht[h];
04128 while( np ){
04129 if( strcmp(np->data,key)==0 ) break;
04130 np = np->next;
04131 }
04132 return np ? np->data : 0;
04133 }
04134
04135
04136
04137
04138 struct symbol *Symbol_new(x)
04139 char *x;
04140 {
04141 struct symbol *sp;
04142
04143 sp = Symbol_find(x);
04144 if( sp==0 ){
04145 sp = (struct symbol *)malloc( sizeof(struct symbol) );
04146 MemoryCheck(sp);
04147 sp->name = Strsafe(x);
04148 sp->type = isupper(*x) ? TERMINAL : NONTERMINAL;
04149 sp->rule = 0;
04150 sp->fallback = 0;
04151 sp->prec = -1;
04152 sp->assoc = UNK;
04153 sp->firstset = 0;
04154 sp->lambda = B_FALSE;
04155 sp->destructor = 0;
04156 sp->datatype = 0;
04157 Symbol_insert(sp,sp->name);
04158 }
04159 return sp;
04160 }
04161
04162
04163
04164
04165
04166
04167
04168
04169
04170
04171
04172 int Symbolcmpp(const void *void_a, const void *void_b){
04173 struct symbol *a = *(struct symbol **)void_a;
04174 struct symbol *b = *(struct symbol **)void_b;
04175 int i1 = a->index + 10000000*(a->name[0]>'Z');
04176 int i2 = b->index + 10000000*(b->name[0]>'Z');
04177 return i1-i2;
04178 }
04179
04180
04181
04182
04183 struct s_x2 {
04184 int size;
04185
04186
04187 int count;
04188 struct s_x2node *tbl;
04189 struct s_x2node **ht;
04190 };
04191
04192
04193
04194
04195 typedef struct s_x2node {
04196 struct symbol *data;
04197 char *key;
04198 struct s_x2node *next;
04199 struct s_x2node **from;
04200 } x2node;
04201
04202
04203 static struct s_x2 *x2a;
04204
04205
04206 void Symbol_init(){
04207 if( x2a ) return;
04208 x2a = (struct s_x2*)malloc( sizeof(struct s_x2) );
04209 if( x2a ){
04210 x2a->size = 128;
04211 x2a->count = 0;
04212 x2a->tbl = (x2node*)malloc(
04213 (sizeof(x2node) + sizeof(x2node*))*128 );
04214 if( x2a->tbl==0 ){
04215 free(x2a);
04216 x2a = 0;
04217 }else{
04218 int i;
04219 x2a->ht = (x2node**)&(x2a->tbl[128]);
04220 for(i=0; i<128; i++) x2a->ht[i] = 0;
04221 }
04222 }
04223 }
04224
04225
04226 int Symbol_insert(data,key)
04227 struct symbol *data;
04228 char *key;
04229 {
04230 x2node *np;
04231 int h;
04232 int ph;
04233
04234 if( x2a==0 ) return 0;
04235 ph = strhash(key);
04236 h = ph & (x2a->size-1);
04237 np = x2a->ht[h];
04238 while( np ){
04239 if( strcmp(np->key,key)==0 ){
04240
04241
04242 return 0;
04243 }
04244 np = np->next;
04245 }
04246 if( x2a->count>=x2a->size ){
04247
04248 int i,size;
04249 struct s_x2 array;
04250 array.size = size = x2a->size*2;
04251 array.count = x2a->count;
04252 array.tbl = (x2node*)malloc(
04253 (sizeof(x2node) + sizeof(x2node*))*size );
04254 if( array.tbl==0 ) return 0;
04255 array.ht = (x2node**)&(array.tbl[size]);
04256 for(i=0; i<size; i++) array.ht[i] = 0;
04257 for(i=0; i<x2a->count; i++){
04258 x2node *oldnp, *newnp;
04259 oldnp = &(x2a->tbl[i]);
04260 h = strhash(oldnp->key) & (size-1);
04261 newnp = &(array.tbl[i]);
04262 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
04263 newnp->next = array.ht[h];
04264 newnp->key = oldnp->key;
04265 newnp->data = oldnp->data;
04266 newnp->from = &(array.ht[h]);
04267 array.ht[h] = newnp;
04268 }
04269 free(x2a->tbl);
04270 *x2a = array;
04271 }
04272
04273 h = ph & (x2a->size-1);
04274 np = &(x2a->tbl[x2a->count++]);
04275 np->key = key;
04276 np->data = data;
04277 if( x2a->ht[h] ) x2a->ht[h]->from = &(np->next);
04278 np->next = x2a->ht[h];
04279 x2a->ht[h] = np;
04280 np->from = &(x2a->ht[h]);
04281 return 1;
04282 }
04283
04284
04285
04286 struct symbol *Symbol_find(key)
04287 char *key;
04288 {
04289 int h;
04290 x2node *np;
04291
04292 if( x2a==0 ) return 0;
04293 h = strhash(key) & (x2a->size-1);
04294 np = x2a->ht[h];
04295 while( np ){
04296 if( strcmp(np->key,key)==0 ) break;
04297 np = np->next;
04298 }
04299 return np ? np->data : 0;
04300 }
04301
04302
04303 struct symbol *Symbol_Nth(n)
04304 int n;
04305 {
04306 struct symbol *data;
04307 if( x2a && n>0 && n<=x2a->count ){
04308 data = x2a->tbl[n-1].data;
04309 }else{
04310 data = 0;
04311 }
04312 return data;
04313 }
04314
04315
04316 int Symbol_count()
04317 {
04318 return x2a ? x2a->count : 0;
04319 }
04320
04321
04322
04323
04324 struct symbol **Symbol_arrayof()
04325 {
04326 struct symbol **array;
04327 int i,size;
04328 if( x2a==0 ) return 0;
04329 size = x2a->count;
04330 array = (struct symbol **)malloc( sizeof(struct symbol *)*size );
04331 if( array ){
04332 for(i=0; i<size; i++) array[i] = x2a->tbl[i].data;
04333 }
04334 return array;
04335 }
04336
04337
04338 int Configcmp(a,b)
04339 struct config *a;
04340 struct config *b;
04341 {
04342 int x;
04343 x = a->rp->index - b->rp->index;
04344 if( x==0 ) x = a->dot - b->dot;
04345 return x;
04346 }
04347
04348
04349 PRIVATE int statecmp(a,b)
04350 struct config *a;
04351 struct config *b;
04352 {
04353 int rc;
04354 for(rc=0; rc==0 && a && b; a=a->bp, b=b->bp){
04355 rc = a->rp->index - b->rp->index;
04356 if( rc==0 ) rc = a->dot - b->dot;
04357 }
04358 if( rc==0 ){
04359 if( a ) rc = 1;
04360 if( b ) rc = -1;
04361 }
04362 return rc;
04363 }
04364
04365
04366 PRIVATE int statehash(a)
04367 struct config *a;
04368 {
04369 int h=0;
04370 while( a ){
04371 h = h*571 + a->rp->index*37 + a->dot;
04372 a = a->bp;
04373 }
04374 return h;
04375 }
04376
04377
04378 struct state *State_new()
04379 {
04380 struct state *new;
04381 new = (struct state *)malloc( sizeof(struct state) );
04382 MemoryCheck(new);
04383 return new;
04384 }
04385
04386
04387
04388
04389 struct s_x3 {
04390 int size;
04391
04392
04393 int count;
04394 struct s_x3node *tbl;
04395 struct s_x3node **ht;
04396 };
04397
04398
04399
04400
04401 typedef struct s_x3node {
04402 struct state *data;
04403 struct config *key;
04404 struct s_x3node *next;
04405 struct s_x3node **from;
04406 } x3node;
04407
04408
04409 static struct s_x3 *x3a;
04410
04411
04412 void State_init(){
04413 if( x3a ) return;
04414 x3a = (struct s_x3*)malloc( sizeof(struct s_x3) );
04415 if( x3a ){
04416 x3a->size = 128;
04417 x3a->count = 0;
04418 x3a->tbl = (x3node*)malloc(
04419 (sizeof(x3node) + sizeof(x3node*))*128 );
04420 if( x3a->tbl==0 ){
04421 free(x3a);
04422 x3a = 0;
04423 }else{
04424 int i;
04425 x3a->ht = (x3node**)&(x3a->tbl[128]);
04426 for(i=0; i<128; i++) x3a->ht[i] = 0;
04427 }
04428 }
04429 }
04430
04431
04432 int State_insert(data,key)
04433 struct state *data;
04434 struct config *key;
04435 {
04436 x3node *np;
04437 int h;
04438 int ph;
04439
04440 if( x3a==0 ) return 0;
04441 ph = statehash(key);
04442 h = ph & (x3a->size-1);
04443 np = x3a->ht[h];
04444 while( np ){
04445 if( statecmp(np->key,key)==0 ){
04446
04447
04448 return 0;
04449 }
04450 np = np->next;
04451 }
04452 if( x3a->count>=x3a->size ){
04453
04454 int i,size;
04455 struct s_x3 array;
04456 array.size = size = x3a->size*2;
04457 array.count = x3a->count;
04458 array.tbl = (x3node*)malloc(
04459 (sizeof(x3node) + sizeof(x3node*))*size );
04460 if( array.tbl==0 ) return 0;
04461 array.ht = (x3node**)&(array.tbl[size]);
04462 for(i=0; i<size; i++) array.ht[i] = 0;
04463 for(i=0; i<x3a->count; i++){
04464 x3node *oldnp, *newnp;
04465 oldnp = &(x3a->tbl[i]);
04466 h = statehash(oldnp->key) & (size-1);
04467 newnp = &(array.tbl[i]);
04468 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
04469 newnp->next = array.ht[h];
04470 newnp->key = oldnp->key;
04471 newnp->data = oldnp->data;
04472 newnp->from = &(array.ht[h]);
04473 array.ht[h] = newnp;
04474 }
04475 free(x3a->tbl);
04476 *x3a = array;
04477 }
04478
04479 h = ph & (x3a->size-1);
04480 np = &(x3a->tbl[x3a->count++]);
04481 np->key = key;
04482 np->data = data;
04483 if( x3a->ht[h] ) x3a->ht[h]->from = &(np->next);
04484 np->next = x3a->ht[h];
04485 x3a->ht[h] = np;
04486 np->from = &(x3a->ht[h]);
04487 return 1;
04488 }
04489
04490
04491
04492 struct state *State_find(key)
04493 struct config *key;
04494 {
04495 int h;
04496 x3node *np;
04497
04498 if( x3a==0 ) return 0;
04499 h = statehash(key) & (x3a->size-1);
04500 np = x3a->ht[h];
04501 while( np ){
04502 if( statecmp(np->key,key)==0 ) break;
04503 np = np->next;
04504 }
04505 return np ? np->data : 0;
04506 }
04507
04508
04509
04510
04511 struct state **State_arrayof()
04512 {
04513 struct state **array;
04514 int i,size;
04515 if( x3a==0 ) return 0;
04516 size = x3a->count;
04517 array = (struct state **)malloc( sizeof(struct state *)*size );
04518 if( array ){
04519 for(i=0; i<size; i++) array[i] = x3a->tbl[i].data;
04520 }
04521 return array;
04522 }
04523
04524
04525 PRIVATE int confighash(a)
04526 struct config *a;
04527 {
04528 int h=0;
04529 h = h*571 + a->rp->index*37 + a->dot;
04530 return h;
04531 }
04532
04533
04534
04535
04536 struct s_x4 {
04537 int size;
04538
04539
04540 int count;
04541 struct s_x4node *tbl;
04542 struct s_x4node **ht;
04543 };
04544
04545
04546
04547
04548 typedef struct s_x4node {
04549 struct config *data;
04550 struct s_x4node *next;
04551 struct s_x4node **from;
04552 } x4node;
04553
04554
04555 static struct s_x4 *x4a;
04556
04557
04558 void Configtable_init(){
04559 if( x4a ) return;
04560 x4a = (struct s_x4*)malloc( sizeof(struct s_x4) );
04561 if( x4a ){
04562 x4a->size = 64;
04563 x4a->count = 0;
04564 x4a->tbl = (x4node*)malloc(
04565 (sizeof(x4node) + sizeof(x4node*))*64 );
04566 if( x4a->tbl==0 ){
04567 free(x4a);
04568 x4a = 0;
04569 }else{
04570 int i;
04571 x4a->ht = (x4node**)&(x4a->tbl[64]);
04572 for(i=0; i<64; i++) x4a->ht[i] = 0;
04573 }
04574 }
04575 }
04576
04577
04578 int Configtable_insert(data)
04579 struct config *data;
04580 {
04581 x4node *np;
04582 int h;
04583 int ph;
04584
04585 if( x4a==0 ) return 0;
04586 ph = confighash(data);
04587 h = ph & (x4a->size-1);
04588 np = x4a->ht[h];
04589 while( np ){
04590 if( Configcmp(np->data,data)==0 ){
04591
04592
04593 return 0;
04594 }
04595 np = np->next;
04596 }
04597 if( x4a->count>=x4a->size ){
04598
04599 int i,size;
04600 struct s_x4 array;
04601 array.size = size = x4a->size*2;
04602 array.count = x4a->count;
04603 array.tbl = (x4node*)malloc(
04604 (sizeof(x4node) + sizeof(x4node*))*size );
04605 if( array.tbl==0 ) return 0;
04606 array.ht = (x4node**)&(array.tbl[size]);
04607 for(i=0; i<size; i++) array.ht[i] = 0;
04608 for(i=0; i<x4a->count; i++){
04609 x4node *oldnp, *newnp;
04610 oldnp = &(x4a->tbl[i]);
04611 h = confighash(oldnp->data) & (size-1);
04612 newnp = &(array.tbl[i]);
04613 if( array.ht[h] ) array.ht[h]->from = &(newnp->next);
04614 newnp->next = array.ht[h];
04615 newnp->data = oldnp->data;
04616 newnp->from = &(array.ht[h]);
04617 array.ht[h] = newnp;
04618 }
04619 free(x4a->tbl);
04620 *x4a = array;
04621 }
04622
04623 h = ph & (x4a->size-1);
04624 np = &(x4a->tbl[x4a->count++]);
04625 np->data = data;
04626 if( x4a->ht[h] ) x4a->ht[h]->from = &(np->next);
04627 np->next = x4a->ht[h];
04628 x4a->ht[h] = np;
04629 np->from = &(x4a->ht[h]);
04630 return 1;
04631 }
04632
04633
04634
04635 struct config *Configtable_find(key)
04636 struct config *key;
04637 {
04638 int h;
04639 x4node *np;
04640
04641 if( x4a==0 ) return 0;
04642 h = confighash(key) & (x4a->size-1);
04643 np = x4a->ht[h];
04644 while( np ){
04645 if( Configcmp(np->data,key)==0 ) break;
04646 np = np->next;
04647 }
04648 return np ? np->data : 0;
04649 }
04650
04651
04652
04653 void Configtable_clear(f)
04654 int(*f)();
04655 {
04656 int i;
04657 if( x4a==0 || x4a->count==0 ) return;
04658 if( f ) for(i=0; i<x4a->count; i++) (*f)(x4a->tbl[i].data);
04659 for(i=0; i<x4a->size; i++) x4a->ht[i] = 0;
04660 x4a->count = 0;
04661 return;
04662 }