parse.c

   1 /*
   2  * Copyright (C) 2012
   3  *      Dale Weiler
   4  *
   5  * Permission is hereby granted, free of charge, to any person obtaining a copy of
   6  * this software and associated documentation files (the "Software"), to deal in
   7  * the Software without restriction, including without limitation the rights to
   8  * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
   9  * of the Software, and to permit persons to whom the Software is furnished to do
  10  * so, subject to the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be included in all
  13  * copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  18  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  19  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  20  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  21  * SOFTWARE.
  22  */
  23 #include <limits.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26 #include "gmqcc.h"
  27
  28 /*
  29  * These are not lexical tokens:  These are parse tree types.  Most people
  30  * perform tokenizing on language punctuation which is wrong.  That stuff
  31  * is technically already tokenized, it just needs to be parsed into a tree
  32  */
  33 #define PARSE_TYPE_DO       0
  34 #define PARSE_TYPE_ELSE     1
  35 #define PARSE_TYPE_IF       2
  36 #define PARSE_TYPE_WHILE    3
  37 #define PARSE_TYPE_BREAK    4
  38 #define PARSE_TYPE_CONTINUE 5
  39 #define PARSE_TYPE_RETURN   6
  40 #define PARSE_TYPE_GOTO     7
  41 #define PARSE_TYPE_FOR      8
  42 #define PARSE_TYPE_VOID     9
  43 #define PARSE_TYPE_STRING   10
  44 #define PARSE_TYPE_FLOAT    11
  45 #define PARSE_TYPE_VECTOR   12
  46 #define PARSE_TYPE_ENTITY   13
  47 #define PARSE_TYPE_LAND     14
  48 #define PARSE_TYPE_LOR      15
  49 #define PARSE_TYPE_LTEQ     16
  50 #define PARSE_TYPE_GTEQ     17
  51 #define PARSE_TYPE_EQEQ     18
  52 #define PARSE_TYPE_LNEQ     19
  53 #define PARSE_TYPE_COMMA    20
  54 #define PARSE_TYPE_LNOT     21
  55 #define PARSE_TYPE_STAR     22
  56 #define PARSE_TYPE_DIVIDE   23
  57 #define PARSE_TYPE_LPARTH   24
  58 #define PARSE_TYPE_RPARTH   25
  59 #define PARSE_TYPE_MINUS    26
  60 #define PARSE_TYPE_ADD      27
  61 #define PARSE_TYPE_EQUAL    28
  62 #define PARSE_TYPE_LBS      29
  63 #define PARSE_TYPE_RBS      30
  64 #define PARSE_TYPE_ELIP     31
  65 #define PARSE_TYPE_DOT      32
  66 #define PARSE_TYPE_LT       33
  67 #define PARSE_TYPE_GT       34
  68 #define PARSE_TYPE_BAND     35
  69 #define PARSE_TYPE_BOR      36
  70 #define PARSE_TYPE_DONE     37
  71 #define PARSE_TYPE_IDENT    38
  72
  73 /*
  74  * Adds a parse type to the parse tree, this is where all the hard
  75  * work actually begins.
  76  */
  77 #define PARSE_TREE_ADD(X)                                        \
  78         do {                                                         \
  79                 parsetree->next       = mem_a(sizeof(struct parsenode)); \
  80                 parsetree->next->next = NULL;                            \
  81                 parsetree->next->type = (X);                             \
  82                 parsetree             = parsetree->next;                 \
  83         } while (0)
  84
  85 /*
  86  * These are all the punctuation handled in the parser, these don't
  87  * need tokens, they're already tokens.
  88  */
  89 #if 0
  90         "&&", "||", "<=", ">=", "==", "!=", ";", ",", "!", "*",
  91         "/" , "(" , ")" , "-" , "+" , "=" , "[" , "]", "{", "}", "...",
  92         "." , "<" , ">" , "&" , "|" ,
  93 #endif
  94
  95 #define STORE(X) {  \
  96         printf(X);      \
  97         break;          \
  98 }
  99
 100 void parse_debug(struct parsenode *tree) {
 101         while (tree) {
 102                 switch (tree->type) {
 103                         case PARSE_TYPE_ADD:       STORE("OPERATOR:  ADD    \n");
 104                         case PARSE_TYPE_BAND:      STORE("OPERATOR:  BITAND \n");
 105                         case PARSE_TYPE_BOR:       STORE("OPERATOR:  BITOR  \n");
 106                         case PARSE_TYPE_COMMA:     STORE("OPERATOR:  SEPERATOR\n");
 107                         case PARSE_TYPE_DOT:       STORE("OPERATOR:  DOT\n");
 108                         case PARSE_TYPE_DIVIDE:    STORE("OPERATOR:  DIVIDE\n");
 109                         case PARSE_TYPE_EQUAL:     STORE("OPERATOR:  ASSIGNMENT\n");
 110
 111                         case PARSE_TYPE_BREAK:     STORE("STATEMENT: BREAK  \n");
 112                         case PARSE_TYPE_CONTINUE:  STORE("STATEMENT: CONTINUE\n");
 113                         case PARSE_TYPE_GOTO:      STORE("STATEMENT: GOTO\n");
 114                         case PARSE_TYPE_RETURN:    STORE("STATEMENT: RETURN\n");
 115                         case PARSE_TYPE_DONE:      STORE("STATEMENT: DONE\n");
 116
 117                         case PARSE_TYPE_VOID:      STORE("DECLTYPE:  VOID\n");
 118                         case PARSE_TYPE_STRING:    STORE("DECLTYPE:  STRING\n");
 119                         case PARSE_TYPE_ELIP:      STORE("DECLTYPE:  VALIST\n");
 120                         case PARSE_TYPE_ENTITY:    STORE("DECLTYPE:  ENTITY\n");
 121                         case PARSE_TYPE_FLOAT:     STORE("DECLTYPE:  FLOAT\n");
 122                         case PARSE_TYPE_VECTOR:    STORE("DECLTYPE:  VECTOR\n");
 123
 124                         case PARSE_TYPE_GT:        STORE("TEST:      GREATER THAN\n");
 125                         case PARSE_TYPE_LT:        STORE("TEST:      LESS THAN\n");
 126                         case PARSE_TYPE_GTEQ:      STORE("TEST:      GREATER THAN OR EQUAL\n");
 127                         case PARSE_TYPE_LTEQ:      STORE("TEST:      LESS THAN OR EQUAL\n");
 128                         case PARSE_TYPE_LNEQ:      STORE("TEST:      NOT EQUAL\n");
 129                         case PARSE_TYPE_EQEQ:      STORE("TEST:      EQUAL-EQUAL\n");
 130
 131                         case PARSE_TYPE_LBS:       STORE("BLOCK:     BEG\n");
 132                         case PARSE_TYPE_RBS:       STORE("BLOCK:     END\n");
 133                         case PARSE_TYPE_ELSE:      STORE("BLOCK:     ELSE\n");
 134                         case PARSE_TYPE_IF:        STORE("BLOCK:     IF\n");
 135
 136                         case PARSE_TYPE_LAND:      STORE("LOGICAL:   AND\n");
 137                         case PARSE_TYPE_LNOT:      STORE("LOGICAL:   NOT\n");
 138                         case PARSE_TYPE_LOR:       STORE("LOGICAL:   OR\n");
 139
 140                         case PARSE_TYPE_LPARTH:    STORE("PARTH:     BEG\n");
 141                         case PARSE_TYPE_RPARTH:    STORE("PARTH:     END\n");
 142
 143                         case PARSE_TYPE_WHILE:     STORE("LOOP:      WHILE\n");
 144                         case PARSE_TYPE_FOR:       STORE("LOOP:      FOR\n");
 145                         case PARSE_TYPE_DO:        STORE("LOOP:      DO\n");
 146
 147                         //case PARSE_TYPE_IDENT:     STORE("IDENT:     ???\n");
 148                 }
 149                 tree = tree->next;
 150         }
 151 }
 152
 153 /*
 154  * This just skips the token and throws it in the parse tree for later
 155  * checking / optimization / codegen, it doesn't do anything with it
 156  * like syntax check for legal use -- like it should as it's a TODO item
 157  * which is not implemented
 158  */
 159 #define PARSE_TODO(X) {          \
 160         token = lex_token(file);     \
 161         while (token != '\n') {      \
 162                 token = lex_token(file); \
 163         }                            \
 164         PARSE_TREE_ADD(X);           \
 165         break;                       \
 166 }
 167
 168 void parse_clear(struct parsenode *tree) {
 169         if (!tree) return;
 170         struct parsenode *temp = NULL;
 171         while (tree != NULL) {
 172                 temp = tree;
 173                 tree = tree->next;
 174                 mem_d (temp);
 175         }
 176
 177         /* free any potential typedefs */
 178         typedef_clear();
 179 }
 180
 181 int parse(struct lex_file *file) {
 182         struct parsenode *parsetree = NULL;
 183         struct parsenode *parseroot = NULL;
 184
 185         /*
 186          * Allocate memory for our parse tree:
 187          * the parse tree is just a singly linked list which will contain
 188          * all the data for code generation.
 189          */
 190         if (!parseroot) {
 191                 parseroot = mem_a(sizeof(struct parsenode));
 192                 if (!parseroot)
 193                         return error(ERROR_INTERNAL, "Ran out of memory", " ");
 194                 parsetree       = parseroot;
 195                 parsetree->type = -1; /* not a valid type -- root element */
 196         }
 197
 198         int     token = 0;
 199         while ((token = lex_token(file)) != ERROR_LEX      && \
 200                     token                    != ERROR_COMPILER && \
 201                     token                    != ERROR_INTERNAL && \
 202                     token                    != ERROR_PARSE    && \
 203                     token                    != ERROR_PREPRO   && file->length >= 0) {
 204                 switch (token) {
 205                         case TOKEN_IF:
 206                                 //token = lex_token(file);
 207                                 while ((token == ' ' || token == '\n') && file->length >= 0)
 208                                         token = lex_token(file);
 209
 210                                 //if (token != '(')
 211                                 //      error(ERROR_PARSE, "Expected `(` after if\n", "");
 212
 213                                 PARSE_TREE_ADD(PARSE_TYPE_IF);
 214                                 break;
 215                         case TOKEN_ELSE:
 216                                 token = lex_token(file);
 217                                 //while ((token == ' ' || token == '\n') && file->length >= 0)
 218                                 //      token = lex_token(file);
 219
 220                                 PARSE_TREE_ADD(PARSE_TYPE_ELSE);
 221                                 break;
 222                         case TOKEN_FOR:
 223                                 token = lex_token(file);
 224                                 while ((token == ' ' || token == '\n') && file->length >= 0)
 225                                         token = lex_token(file);
 226
 227                                 //PARSE_TREE_ADD(PARSE_TYPE_FOR);
 228                                 PARSE_TODO(PARSE_TYPE_FOR);
 229                                 break;
 230
 231                         /*
 232                          * This is a quick and easy way to do typedefs at parse time
 233                          * all power is in typedef_add(), in typedef.c.  We handle
 234                          * the tokens accordingly here.
 235                          */
 236                         case TOKEN_TYPEDEF: {
 237                                 char *f = NULL;
 238                                 char *t = NULL;
 239                                 token = lex_token(file);
 240                                 token = lex_token(file); f = strdup(file->lastok);
 241                                 token = lex_token(file);
 242                                 token = lex_token(file); t = strdup(file->lastok);
 243
 244                                 typedef_add(f, t);
 245
 246                                 /* free stdup strings */
 247                                 //mem_d(f);
 248                                 //mem_d(t);
 249                                 free(f);
 250                                 free(t);
 251
 252                                 while (token != '\n')
 253                                         token = lex_token(file);
 254                                 break;
 255                         }
 256
 257
 258                         case TOKEN_DO:        PARSE_TODO(PARSE_TYPE_DO);
 259                         case TOKEN_WHILE:     PARSE_TODO(PARSE_TYPE_WHILE);
 260                         case TOKEN_BREAK:     PARSE_TODO(PARSE_TYPE_BREAK);
 261                         case TOKEN_CONTINUE:  PARSE_TODO(PARSE_TYPE_CONTINUE);
 262                         case TOKEN_RETURN:    PARSE_TODO(PARSE_TYPE_RETURN);
 263                         case TOKEN_GOTO:      PARSE_TODO(PARSE_TYPE_GOTO);
 264                         case TOKEN_VOID:      PARSE_TODO(PARSE_TYPE_VOID);
 265                         case TOKEN_STRING:    PARSE_TODO(PARSE_TYPE_STRING);
 266                         case TOKEN_FLOAT:     PARSE_TODO(PARSE_TYPE_FLOAT);
 267                         case TOKEN_VECTOR:    PARSE_TODO(PARSE_TYPE_VECTOR);
 268                         case TOKEN_ENTITY:    PARSE_TODO(PARSE_TYPE_ENTITY);
 269
 270                         /*
 271                          * From here down is all language punctuation:  There is no
 272                          * need to actual create tokens from these because they're already
 273                          * tokenized as these individual tokens (which are in a special area
 274                          * of the ascii table which doesn't conflict with our other tokens
 275                          * which are higer than the ascii table.)
 276                          */
 277                         case '#':
 278                                 /*
 279                                  * Skip the preprocessor for now:  We'll implement our own
 280                                  * eventually.  For now we need to make sure directives are
 281                                  * not accidently tokenized.
 282                                  */
 283                                 token = lex_token(file);
 284                                 token = lex_token(file);
 285
 286                                 /* skip all tokens to end of directive */
 287                                 while (token != '\n')
 288                                         token = lex_token(file);
 289                                 break;
 290
 291                         case '.':
 292                                 token = lex_token(file);
 293                                 PARSE_TREE_ADD(PARSE_TYPE_DOT);
 294                                 break;
 295
 296                         case '(':
 297                                 token = lex_token(file);
 298                                 PARSE_TREE_ADD(PARSE_TYPE_LPARTH);
 299                                 break;
 300                         case ')':
 301                                 token = lex_token(file);
 302                                 PARSE_TREE_ADD(PARSE_TYPE_RPARTH);
 303                                 break;
 304
 305                         case '&':               /* &  */
 306                                 token = lex_token(file);
 307                                 if (token == '&') { /* && */
 308                                         token = lex_token(file);
 309                                         PARSE_TREE_ADD(PARSE_TYPE_LAND);
 310                                         break;
 311                                 }
 312                                 PARSE_TREE_ADD(PARSE_TYPE_BAND);
 313                                 break;
 314                         case '|':               /* |  */
 315                                 token = lex_token(file);
 316                                 if (token == '|') { /* || */
 317                                         token = lex_token(file);
 318                                         PARSE_TREE_ADD(PARSE_TYPE_LOR);
 319                                         break;
 320                                 }
 321                                 PARSE_TREE_ADD(PARSE_TYPE_BOR);
 322                                 break;
 323                         case '!':
 324                                 token = lex_token(file);
 325                                 if (token == '=') { /* != */
 326                                         token = lex_token(file);
 327                                         PARSE_TREE_ADD(PARSE_TYPE_LNEQ);
 328                                         break;
 329                                 }
 330                                 PARSE_TREE_ADD(PARSE_TYPE_LNOT);
 331                                 break;
 332                         case '<':               /* <  */
 333                                 token = lex_token(file);
 334                                 if (token == '=') { /* <= */
 335                                         token = lex_token(file);
 336                                         PARSE_TREE_ADD(PARSE_TYPE_LTEQ);
 337                                         break;
 338                                 }
 339                                 PARSE_TREE_ADD(PARSE_TYPE_LT);
 340                                 break;
 341                         case '>':               /* >  */
 342                                 token = lex_token(file);
 343                                 if (token == '=') { /* >= */
 344                                         token = lex_token(file);
 345                                         PARSE_TREE_ADD(PARSE_TYPE_GTEQ);
 346                                         break;
 347                                 }
 348                                 PARSE_TREE_ADD(PARSE_TYPE_GT);
 349                                 break;
 350                         case '=':
 351                                 token = lex_token(file);
 352                                 if (token == '=') { /* == */
 353                                         token = lex_token(file);
 354                                         PARSE_TREE_ADD(PARSE_TYPE_EQEQ);
 355                                         break;
 356                                 }
 357                                 PARSE_TREE_ADD(PARSE_TYPE_EQUAL);
 358                                 break;
 359                         case ';':
 360                                 token = lex_token(file);
 361                                 PARSE_TREE_ADD(PARSE_TYPE_DONE);
 362                                 break;
 363                         case '-':
 364                                 token = lex_token(file);
 365                                 PARSE_TREE_ADD(PARSE_TYPE_MINUS);
 366                                 break;
 367                         case '+':
 368                                 token = lex_token(file);
 369                                 PARSE_TREE_ADD(PARSE_TYPE_ADD);
 370                                 break;
 371                         case '{':
 372                                 token = lex_token(file);
 373                                 PARSE_TREE_ADD(PARSE_TYPE_LBS);
 374                                 break;
 375                         case '}':
 376                                 token = lex_token(file);
 377                                 PARSE_TREE_ADD(PARSE_TYPE_RBS);
 378                                 break;
 379
 380                         /*
 381                          * TODO: Fix lexer to spit out ( ) as tokens, it seems the
 382                          * using '(' or ')' in parser doesn't work properly unless
 383                          * there are spaces before them to allow the lexer to properly
 384                          * seperate identifiers. -- otherwise it eats all of it.
 385                          */
 386                         case LEX_IDENT:
 387                                 token = lex_token(file);
 388                                 PARSE_TREE_ADD(PARSE_TYPE_IDENT);
 389                                 break;
 390                 }
 391         }
 392         parse_debug(parseroot);
 393         lex_reset(file);
 394         parse_clear(parseroot);
 395
 396         return 1;
 397 }