home *** CD-ROM | disk | FTP | other *** search
/ Otherware / Otherware_1_SB_Development.iso / mac / developm / source / suntar1.cpt / gc / par.c < prev   
Encoding:
C/C++ Source or Header  |  1992-06-13  |  13.9 KB  |  539 lines
  1. /************************\
  2. *                        *
  3. *         Parser         *    
  4. *                        *
  5. \************************/
  6.  
  7. /* One pass optimizing compiler for typeless expressions
  8. written by Gabriele Speranza on a Sinclair QL (summer 1990),
  9. adapted to C language expressions and modified gen.c (november 1990)
  10. quickly ported to the Macintosh (jan-feb 1991)
  11. added comments & dynamic choice between the two calling protocols (june 92)
  12. Algorithms used:
  13. lexical analyzer: table lookup
  14. expression parser: left corner parsing
  15. optimizer: lazy evaluation & strength reduction
  16. */
  17.  
  18.  
  19. /* the QL screen is small, and the QL keyboard is rather awkward
  20. to use, hence a rather strange graphical appearence of the listing
  21. and almost no original comments. Now that I'm writing on a Mac I tried
  22. to add more comments, but more than one year has passed since I wrote
  23. the program and these comments are necessarily imprecise */
  24.  
  25. #include <stdio.h>
  26. #include <ctype.h>
  27. #include <setjmp.h>
  28.  
  29. #include "gc.h"
  30.  
  31. /* #define hidden static*/
  32. #define hidden
  33. /* i prossimi dovrebbero stare in ctype.h ma evidentemente qui non ci sono... */
  34. #define iscsym(c) (isalnum(c)||(c)=='_')
  35. #define iscsymf(c) (isalpha(c)||(c)=='_')
  36.  
  37.  
  38. struct t token;
  39. FILE *out;
  40. localmem currentExpr;
  41.  
  42. static char buffer[160], *textPointer;
  43. static jmp_buf mainProgram;
  44.  
  45. #define sTsize 64
  46. #define predefined 6
  47.  
  48. /* table of predefined symbols:the code generator
  49. supports constant values and dynamic variables, but
  50. all new symbols are considered absolute (the C static
  51. variables), hence to try the capabilities of the program
  52. I have 3 predefined constants and 3 predefined dynamic
  53. variables */
  54.  
  55.  
  56. tabel *lastEntry,symbolTable[sTsize]={
  57. {dyn,"x",0},{dyn,"y",0},{dyn,"z",0},
  58. {const,"u",1},{const,"v",2},
  59. {const,"w",0}};
  60.  
  61.  
  62. /* the lexical analyzer is table driven, and here are the tables: */
  63.  
  64.  
  65. static char tabBichar[][2]={
  66.    '-','>','<','<','>','>','+','+',
  67.    '-','-','=','=','!','=','&','&',
  68.    '|','|','<','=','>','='};
  69. static byte valBichar[][2]={
  70.    'P',255,0,4,1,4,0,255,1,255,EQ,1,
  71.    NE,1,0,2,1,2,LE,1,GE,1};
  72. static word prioBichar[]={
  73.    0,0100135,0100135,060161,060161,
  74.    0115,0115,055,045,0125,0125};
  75. static char tabMono[]={
  76.    '+','-','&','|','*','/','%','!',
  77.    '~','<','>','^','?',',','=' };
  78. static byte valMono[]={
  79.    3,3,3,3,4,4,4,0,0,1,1,3,6,0,10};
  80. static word prioMono[]={
  81.    0100145,0140145,0140105,0100065,
  82.    0140155,0100155,0100155,0162,0162,
  83.    0125,0125,0100075,034,017,020027};
  84.  
  85. /* coding of the priority:
  86. least significant 3 bits (l.s. octal digit) the associativity: see the #define's
  87. for (unary) prefix, (unary) postfix, leftass, rightass...;
  88. next 9 bits (three more octal digits) are the priority: 0 is reserved, hence
  89. up to 511 levels of precedence are possible. Only about 20 are really used for
  90. C expressions.
  91. The remaining 4 bits will be shifted to the "features" bytes, containing some
  92. attributes of the operator (lval1op,lval2op,unaryToo,asgnOpToo)
  93. The input parameter of E_parser has this same coding, but the upper four bit
  94. have a different meaning (bits 12 to 14 are always cleared, bit 15 means "this
  95. sub-expression is not nested within a parenthesis" and is not used currently,
  96. but it was used in the summer 90 version which used a Pascal-like syntax rather
  97. than a C-like one)
  98.  
  99. Since it's the lexical analyzer which determines priority and associativity of
  100. operators, it would be extremely easy to dynamically insert and delete 
  101. user-defined operators (e.g. using identifiers or sequences of chars which, by 
  102. some simple rule, are guaranteed not to create ambiguities to the lexical analyzer).
  103. Question: why do Ada and C++ allow to redefine existing operators, but not to define
  104.     new ones ?
  105. Answer: Ichbiah and Stroustrup never heard about left-corner parsing (the one
  106.     used here). Probably they knew that C-Prolog allows to redefine operators,
  107.     but Prolog means AI and AI algorithms are horribly slow and memory hungry
  108.     (the left corner expression parser should be slightly faster and should
  109.     use less memory than any other expression parsing algorithm)
  110. */
  111.  
  112.  
  113.  
  114. #define UNARYPRIO 0162
  115. #define ASSIGNPRIO 027
  116. #define ASSIGNOPFEA 022
  117.  
  118.  
  119. void  lexanal(),E_parser(),
  120.    gestioneSel(),Statement();
  121.  
  122. void main()
  123. {
  124. /*static word w2[4]={206,200,284,8};
  125. static word w1[4]={260,200,22,8};*/
  126. int width,heigth;
  127. FILE*fopen_win();
  128. lastEntry= &symbolTable[predefined];
  129.  
  130. InitConsole();
  131. screen_size(&width,&heigth);
  132. if(width>=640){
  133.     config_console(44,4,"\pinput",-1,25,40,0,0,0);
  134.     printf("\f");
  135.     out=fopen_win(44,320,"\poutput",0,25,40,0,0);
  136.     }
  137. else{
  138.     config_console(44,4,"\pinput",-1,25,40,0,0,0);
  139.     printf("\f");
  140.     out=fopen_win(44,256,"\poutput",0,25,40,0,0);
  141.     }
  142.  
  143. /*printf("Programma di esempio\n");
  144. printf("Parsing espressioni e\n");
  145. printf("generazione di codice\n\n");
  146. */
  147. printf("\nDemo code generator\nby Gabriele Speranza November 1990\n");
  148. printf("Type expressions in C, for example\"2+2\",\n\"t=(a[x]-b.u)^f(y,3+s); b= y*8+1\"\n");
  149. printf("or \"a=b?(!!c||d):(foo+=j),g(h|r)\"\n\n");
  150.  
  151. if(setjmp(mainProgram)<0)
  152.    {
  153.    /*printf("Riprova !!\n");*/
  154.    printf("Try again !\n");
  155.    fflush(out); }
  156. for(;;){
  157.    printf("Expr: ");
  158.    /*getline(&buffer,sizeof(buffer));*/
  159.    fgets(buffer,sizeof(buffer),stdin);
  160.    if(buffer[1]=='\0'){
  161.       fclose(out);
  162.       return;
  163.    }
  164.    fprintf(out,"\f");
  165.    textPointer= &buffer[0];
  166.    Statement();
  167.    fflush(out);
  168.    printf("\n");
  169. }}
  170. /*********************/
  171. void Statement()
  172. {
  173. /* it does NOT parse C-like statements, only sequences of expressions separated
  174. by ';', but above the "expression" level it's typical to find something
  175. named "statement" */
  176.  
  177.  
  178.  
  179. static char *classes[]={
  180. "immediate","*immediate","simplevar",
  181. "*simplevar","relocatable","based",
  182. "generated","flags"};
  183. do{
  184.    lexanal();
  185.    if(token.asc!='Z'){
  186.       E_parser(Normal|externalCall);
  187. /*      printf("class=%s\nlval=%d CExpr=%d\n",
  188.          classes[currentExpr.class],
  189.          currentExpr.lval,currentExpr.isCExpr);
  190. */
  191.       if(currentExpr.class==flags){
  192.          ForceJump(¤tExpr,0);
  193.          Emit("...");
  194.          }
  195.       else
  196.          ForceA(¤tExpr);
  197.       }
  198.    }
  199. while(token.asc==';');
  200. Emit("END");
  201. if(token.asc!='Z')errore("extra chars");
  202. }
  203. /**********************/
  204.  
  205. /* parameter parsing must be done in a different way according
  206. to how parameters are passed (on the Mac, the two methods are 
  207. called C and Pascal), since the "parse tree" must be built in
  208. two different ways (this programs builds no parse tree, but 
  209. conceptually it exists, simply it's destroyed during the same pass
  210. which should construct it). This parser has both methods, with a global
  211. variable choosing
  212.  
  213. /* hidden */void FunParameters()
  214. {localmem first;
  215. lexanal();
  216. first.op='(';first.opfea=0;
  217. InitSecOp(&first,8);
  218. while(token.asc!=')'){
  219.    E_parser(commaIsNotOp);
  220.    BinaryOp(&first,7);
  221.    if(token.asc==',')lexanal();
  222.    else if(token.asc!=')')errore(") expected");
  223. }
  224. first.op=')';first.opfea=32;
  225. BinaryOp(&first,8); lexanal();
  226. }
  227. /**********************/
  228. hidden void restOfPars()
  229. {localmem first;
  230. first.op=')';first.opfea=0;
  231. E_parser(commaIsNotOp);
  232. InitSecOp(&first,11);
  233. if(token.asc==','){
  234.    lexanal();
  235.    restOfPars();
  236.    }
  237. else if(token.asc!=')')
  238.    errore(") expected");
  239. first.opfea=32;
  240. BinaryOp(&first,11);
  241. }
  242. /**********************/
  243. hidden void FunParsInv()
  244. {localmem first;
  245. first.op='(';first.opfea=0;
  246. lexanal();InitSecOp(&first,12);
  247. if(token.asc!=')')
  248.    restOfPars();
  249. first.opfea=32;
  250. BinaryOp(&first,12);lexanal();
  251. }
  252. /**********************/
  253. hidden void RecordOffset()
  254. {localmem first;
  255. first.op='.';first.opfea=lval1op;
  256. InitSecOp(&first,9);
  257. lexanal();
  258. if(token.asc!='I'||
  259.    token.symTable->name[0]=='\0'||
  260.    token.symTable->typ!=const)
  261.       errore("field name expected");
  262. primary(token.symTable);
  263. BinaryOp(&first,9);
  264. lexanal();
  265. }
  266. /*****************/
  267. hidden void ArrayIndex()
  268. {localmem first;
  269. static localmem aux={
  270.    '*',0,0,{0,immediate /* e il resto 0 */}};
  271. first.op='[';first.opfea=32;
  272. /* for(;;){ solo per indici multipli
  273. uncomment for Pascal, which allows a[x,y]
  274. */
  275.    InitSecOp(&first,9);
  276.    lexanal(); E_parser(Normal);
  277. /* solo per limite inf != 0
  278.   uncomment for Pascal, where the lower limit is not 0
  279.  
  280.    aux.eval= - limite inferiore ;
  281.    aux.op='+';
  282.    BinaryOp(&aux,3);
  283.    aux.op='*';
  284. */
  285.    aux.eval=4; /* size dell'entit
  286.  puntata */
  287.    BinaryOp(&aux,4);
  288. /* solo per indici multipli
  289. uncomment for Pascal, which allows a[x,y]
  290.    if(token.asc==',')
  291.       BinaryOp(&first,9);
  292.    else
  293.       break;
  294.    }
  295. */
  296. match(']');
  297. BinaryOp(&first,9);
  298.  
  299. }
  300. /**********************/
  301. hidden void gestioneSel()
  302. {
  303. extern word parsInverted;
  304. for(;;){
  305.    switch(token.asc){
  306.    case 'P' /*'->'*/:
  307.       UnaryPre('*',0);
  308.       /* RecordOffset();
  309.       break; */
  310.    case '.':
  311.       RecordOffset();
  312.       break;
  313.    case '[':
  314.       ArrayIndex();
  315.       break;
  316.    case '(':
  317.       if(!parsInverted)
  318.          FunParameters();
  319.       else
  320.          FunParsInv();
  321.       break;
  322.    default:
  323.       return;
  324.    }}
  325. }
  326. /*********************/
  327. hidden void E_parser(input)
  328. word input;
  329. {
  330.  
  331. /* left-corner expression parser */
  332.  
  333.  
  334. if(token.priority!=0 &&
  335.    (token.features&unaryToo)){
  336.    token.priority=UNARYPRIO;
  337.    if(token.asc=='&')token.features=lval1op;
  338.    }
  339. if(token.asc=='I'){
  340.    primary(token.symTable);
  341.  
  342.    if(token.symTable->name[0]!='\0'){
  343.  /* well, I must use some arbitrary criteria to tell which functions
  344.  have a C interface and which ones have a Pascal interface... */
  345.       parsInverted=((token.symTable->name[0])|0x20)<'m';
  346.       lexanal();
  347.       gestioneSel();
  348.       }
  349.    else
  350.       lexanal();
  351.    }
  352. else if(token.asc=='('){
  353.    lexanal(); E_parser(Normal);
  354.    parsInverted=0;
  355.    match(')');gestioneSel();
  356.    /* converting it to Pascal syntax, remember that somewhere there must be a
  357.    this.lval=false */
  358.    }
  359. else if((token.priority&7)==prefix){
  360.    char c=token.asc,f=token.features;
  361.    lexanal();
  362.    E_parser(UNARYPRIO-prefix);
  363.    /* that's for C, where all unary prefix operators have the same precedence,
  364.    the highest, and right-associate with other operators at the same priority
  365.    (*p++ means *(p++) ).
  366.    Converting to Pascal syntax, where the precedence is not the highest, one
  367.    should remember that a<-b is OK but a*-b is illegal; and since they
  368.    left-associate with other operators at the same priority (-a-b means (-a)-b...)
  369.    you should do this:
  370.    int i=token.priority; lexanal(); E_parser(i+8-prefix);
  371.    */
  372.    UnaryPre(c,f);
  373.    }
  374. else
  375.    errore("missing token");
  376.  
  377. /* MAIN LOOP */
  378.  
  379. {word p,t,minprio=input&0xFFF;
  380. localmem first;
  381.  
  382. /*OK, in theory I should mask out the lowest three bits (associativity)
  383. in both token.priority and minprio. However, not masking them and
  384. cleverly coding the associativity field allowed me to have some
  385. control about what happens when operators of different associativity are
  386. placed at the same priority, and what I obtained seems better than what
  387. happens by the "theoric" law obtained by masking those bits */
  388.  
  389. while(token.priority>=minprio){
  390.  
  391.    t=token.priority&7;
  392.    if(t==prefix)
  393.       errore("missing operator");
  394.    if(t==postfix){
  395.       p=token.asc;lexanal();
  396.       UnaryPost(p,input);
  397.       }
  398.    else {
  399.       int i=token.index;
  400.       p=token.priority;
  401.       first.op=token.asc;
  402.       first.opfea=token.features;
  403.       InitSecOp(&first,i);
  404.       lexanal();
  405.       switch(t){
  406.       case leftass:
  407.          E_parser(p+(8-leftass));break;
  408.       case rightass:
  409.          E_parser(p);break;
  410.       case noass:
  411.          /* OK, I know that C has no no-ass operators, but
  412.          they are supported anyway. And <,>,<= and so on should have been no-ass,
  413.          the C meaning of a<b<c is absolutely silly */
  414.          E_parser(p+(8-noass));
  415.          if(token.priority==p)
  416.             errore("noass !");
  417.          break;
  418.       case ternary:
  419.          E_parser(p);
  420.          if(token.asc!=':')
  421.             errore("misused ternary");
  422.          BinaryOp(&first,5);
  423.          lexanal(); E_parser(p);
  424.          break;
  425.       default:
  426.          errore("???");
  427.       }
  428.       BinaryOp(&first,i);
  429.       }
  430.    }
  431. }
  432. }
  433. /*********************/
  434. hidden void lexanal()
  435. {
  436. /* a very very simple lexical analyzer, containing a very simple
  437. symbol table handling
  438. */
  439.  
  440.  
  441. char *p=textPointer;
  442. static tabel lit={const,{'\0'},0};
  443.  
  444. token.priority=0;
  445. while(*p>0&&isspace(*p)) p++;
  446. if(*p=='\0')
  447.    {token.asc='Z';token.index=255;}
  448. else if(*p<0)
  449.    {token.asc= *p++;token.index=255;}
  450. else if(*p>0&&isdigit(*p)){
  451.    lit.val=0;
  452.    do
  453.        lit.val=lit.val*10+ *p++ -'0';
  454.    while(*p>0&&isdigit(*p));
  455.    token.asc='I';token.index=255;
  456.    token.symTable=&lit;
  457.    }
  458. else if(*p>0&&iscsymf(*p)){ /*car iniziale id */
  459.    char *p1=&(lastEntry->name[0]);
  460.    while(*p>0&&iscsym(*p)) /*car non iniziale id*/
  461.       *p1++ = *p++;
  462.    *p1='\0';
  463.    token.symTable= &symbolTable[0];
  464.    while(strcmp(token.symTable->name,lastEntry->name))
  465.       token.symTable++;
  466.    if(token.symTable==lastEntry)
  467.       {lastEntry->typ=ass;
  468.       if(lastEntry==&symbolTable[sTsize-1])
  469.          errore("sym table full");
  470.       lastEntry++;
  471.       }
  472.    token.asc='I';token.index=255;
  473.    }
  474. else{
  475.    char ricerca[2]; int i=0;
  476.  
  477.    ricerca[0]=*p++;ricerca[1]=*p;
  478.    do
  479.       if(*((word*)&ricerca[0])==*((word*)&tabBichar[i]))
  480.          break;
  481.    while(++i<sizeof(tabBichar)/2);
  482.    if(i<sizeof(tabBichar)/2){
  483.       token.asc=valBichar[i][0];
  484.       token.index=valBichar[i][1];
  485.       token.priority=prioBichar[i];
  486.       p++;
  487.       }
  488.    else{
  489.       token.asc=ricerca[0];
  490.       i=0;
  491.       do
  492.          if(token.asc==tabMono[i])
  493.             break;
  494.       while(++i<sizeof(tabMono));
  495.       if(i<sizeof(tabMono)){
  496.          token.index=valMono[i];
  497.          token.priority=prioMono[i];
  498.          if(token.index==1)
  499.             token.asc=token.asc=='<'?LT:GT;
  500.          }
  501.       else
  502.          token.index=255;
  503.    }
  504.    token.features=0;
  505.    if(token.priority!=0){ /* operatore... */
  506.       token.features=(token.priority>>12)&0xF;
  507.       token.priority&=0xFFF;
  508.       if(*p=='='&&(token.features&asgnOpToo)){
  509.          token.features=ASSIGNOPFEA;
  510.          token.priority=ASSIGNPRIO;
  511.          p++;
  512.          }
  513.       }
  514.  
  515. }
  516. textPointer=p;
  517. }
  518. /*******************/
  519. match(c)
  520. char c;
  521. {
  522. static char p[]="missing  ";
  523. if(token.asc==c)
  524.    lexanal();
  525. else{
  526.    p[sizeof(p)-2]=c;
  527.    errore(p);
  528.    }
  529. }
  530. /*******************/
  531. errore(mesg)
  532. char *mesg;
  533. {
  534. printf("\n%s\n",mesg);
  535. printf("%s\n",textPointer);
  536. longjmp(mainProgram,-1);
  537. exit(0);  /*inutile...*/
  538. }
  539.