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 "gmqcc.h"
  26
  27 /*
  28  * These are not lexical tokens:  These are parse tree types.  Most people
  29  * perform tokenizing on language punctuation which is wrong.  That stuff
  30  * is technically already tokenized, it just needs to be parsed into a tree
  31  */
  32 #define PARSE_TYPE_DO       0
  33 #define PARSE_TYPE_ELSE     1
  34 #define PARSE_TYPE_IF       2
  35 #define PARSE_TYPE_WHILE    3
  36 #define PARSE_TYPE_BREAK    4
  37 #define PARSE_TYPE_CONTINUE 5
  38 #define PARSE_TYPE_RETURN   6
  39 #define PARSE_TYPE_GOTO     7
  40 #define PARSE_TYPE_FOR      8   // extension
  41 #define PARSE_TYPE_INT      9   // extension
  42 #define PARSE_TYPE_BOOL     10  // extension
  43 #define PARSE_TYPE_VOID     11
  44 #define PARSE_TYPE_STRING   12
  45 #define PARSE_TYPE_FLOAT    13
  46 #define PARSE_TYPE_VECTOR   14
  47 #define PARSE_TYPE_ENTITY   15
  48 #define PARSE_TYPE_LAND     16
  49 #define PARSE_TYPE_LOR      17
  50 #define PARSE_TYPE_LTEQ     18
  51 #define PARSE_TYPE_GTEQ     19
  52 #define PARSE_TYPE_EQEQ     20
  53 #define PARSE_TYPE_LNEQ     21
  54 #define PARSE_TYPE_COMMA    22
  55 #define PARSE_TYPE_LNOT     23
  56 #define PARSE_TYPE_STAR     24
  57 #define PARSE_TYPE_DIVIDE   25
  58 #define PARSE_TYPE_LPARTH   26
  59 #define PARSE_TYPE_RPARTH   27
  60 #define PARSE_TYPE_MINUS    28
  61 #define PARSE_TYPE_ADD      29
  62 #define PARSE_TYPE_EQUAL    30
  63 #define PARSE_TYPE_LSS      31 // left subscript
  64 #define PARSE_TYPE_RSS      32
  65 #define PARSE_TYPE_LBS      33 // left  bracket scope
  66 #define PARSE_TYPE_RBS      34 // right bracket scope
  67 #define PARSE_TYPE_ELIP     35 // ...
  68 #define PARSE_TYPE_DOT      36
  69 #define PARSE_TYPE_LT       37
  70 #define PARSE_TYPE_GT       38
  71 #define PARSE_TYPE_BAND     39
  72 #define PARSE_TYPE_BOR      40
  73 #define PARSE_TYPE_DONE     41 // finished statement
  74
  75 /*
  76  * Adds a parse type to the parse tree, this is where all the hard
  77  * work actually begins.
  78  */
  79 #define PARSE_TREE_ADD(X)                                        \
  80         do {                                                         \
  81                 parsetree->next       = mem_a(sizeof(struct parsenode)); \
  82                 parsetree->next->next = NULL;                            \
  83                 parsetree->next->type = (X);                             \
  84                 parsetree             = parsetree->next;                 \
  85         } while (0)
  86
  87 static const char *const parse_punct[] = {
  88         "&&", "||", "<=", ">=", "==", "!=", ";", ",", "!", "*",
  89         "/" , "(" , ")" , "-" , "+" , "=" , "[" , "]", "{", "}", "...",
  90         "." , "<" , ">" , "&" , "|" , NULL
  91 };
  92
  93 #define STORE(X) {     \
  94         printf(X);         \
  95         break;             \
  96 }
  97
  98 void parse_debug(struct parsenode *tree) {
  99         while (tree && tree->next != NULL) {
 100                 /* skip blanks */
 101                 if (tree->type == 0) {
 102                         tree = tree->next;
 103                         continue;
 104                 }
 105
 106                 switch (tree->type) {
 107                         case PARSE_TYPE_ADD:       STORE("ADD    \n");
 108                         case PARSE_TYPE_BAND:      STORE("BITAND \n");
 109                         case PARSE_TYPE_BOR:       STORE("BITOR  \n");
 110                         case PARSE_TYPE_BREAK:     STORE("BREAK  \n");
 111                         case PARSE_TYPE_COMMA:     STORE("SEPERATOR\n");
 112                         case PARSE_TYPE_CONTINUE:  STORE("CONTINUE\n");
 113                         case PARSE_TYPE_DIVIDE:    STORE("DIVIDE\n");
 114                         case PARSE_TYPE_EQUAL:     STORE("ASSIGNMENT\n");
 115                         case PARSE_TYPE_GOTO:      STORE("GOTO\n");
 116                         case PARSE_TYPE_DOT:       STORE("DOT\n");
 117
 118
 119                         case PARSE_TYPE_ELIP:      STORE("DECLTYPE: VALIST\n");
 120                         case PARSE_TYPE_ENTITY:    STORE("DECLTYPE: ENTITY\n");
 121                         case PARSE_TYPE_INT:       STORE("DECLTYPE: INT\n");
 122                         case PARSE_TYPE_FLOAT:     STORE("DECLTYPE: FLOAT\n");
 123                         case PARSE_TYPE_BOOL:      STORE("DECLTYPE: BOOL\n");
 124
 125                         case PARSE_TYPE_GT:        STORE("TEST:     GREATER THAN\n");
 126                         case PARSE_TYPE_LT:        STORE("TEST:     LESS THAN\n");
 127                         case PARSE_TYPE_GTEQ:      STORE("TEST:     GREATER THAN OR EQUAL\n");
 128                         case PARSE_TYPE_LTEQ:      STORE("TEST:     LESS THAN OR EQUAL\n");
 129                         case PARSE_TYPE_LNEQ:      STORE("TEST:     NOT EQUAL\n");
 130                         case PARSE_TYPE_EQEQ:      STORE("TEST:     EQUAL-EQUAL\n");
 131
 132                         case PARSE_TYPE_LBS:       break;
 133                         case PARSE_TYPE_RBS:       break;
 134
 135                         case PARSE_TYPE_LAND:      STORE("LOGICAL:  AND\n");
 136                         case PARSE_TYPE_LNOT:      STORE("LOGICAL:  NOT\n");
 137                         case PARSE_TYPE_LOR:       STORE("LOGICAL:  OR\n");
 138                         case PARSE_TYPE_LPARTH:    STORE("PARTH:    END\n");
 139                         case PARSE_TYPE_RPARTH:    STORE("PARTH:    BEG\n");
 140
 141                         case PARSE_TYPE_FOR:       STORE("LOOP:     FOR\n");
 142                         case PARSE_TYPE_DO:        STORE("LOOP:     DO\n");
 143                         case PARSE_TYPE_ELSE:      STORE("BLOCK:    ELSE\n");
 144                         case PARSE_TYPE_IF:        STORE("BLOCK:    IF\n");
 145                 }
 146                 tree = tree->next;
 147         }
 148 }
 149
 150 /*
 151  * This just skips the token and throws it in the parse tree for later
 152  * checking / optimization / codegen, it doesn't do anything with it
 153  * like syntax check for legal use -- like it should as it's a TODO item
 154  * which is not implemented
 155  */
 156 #define PARSE_TODO(X) {       \
 157         token = lex_token(file);  \
 158         PARSE_TREE_ADD(X);        \
 159         break;                    \
 160 }
 161
 162 int parse(struct lex_file *file) {
 163         struct parsenode *parsetree = NULL;
 164         struct parsenode *parseroot = NULL;
 165
 166         /*
 167          * Allocate memory for our parse tree:
 168          * the parse tree is just a singly linked list which will contain
 169          * all the data for code generation.
 170          */
 171         if (!parseroot) {
 172                 parseroot = mem_a(sizeof(struct parsenode));
 173                 if (!parseroot)
 174                         return error(ERROR_INTERNAL, "Ran out of memory", " ");
 175                 parsetree = parseroot;
 176                 parsetree = parseroot;
 177         }
 178
 179         int     token = 0;
 180         while ((token = lex_token(file)) != ERROR_LEX      && \
 181                     token                    != ERROR_COMPILER && \
 182                     token                    != ERROR_INTERNAL && \
 183                     token                    != ERROR_PARSE    && \
 184                     token                    != ERROR_PREPRO   && file->length >= 0) {
 185                 switch (token) {
 186                         case TOKEN_IF:
 187                                 token = lex_token(file);
 188                                 while ((token == ' ' || token == '\n') && file->length >= 0)
 189                                         token = lex_token(file);
 190
 191                                 if (token != '(')
 192                                         error(ERROR_PARSE, "Expected `(` after if\n", "");
 193
 194                                 PARSE_TREE_ADD(PARSE_TYPE_IF);
 195                                 break;
 196                         case TOKEN_ELSE:
 197                                 token = lex_token(file);
 198                                 while ((token == ' ' || token == '\n') && file->length >= 0)
 199                                         token = lex_token(file);
 200
 201                                 PARSE_TREE_ADD(PARSE_TYPE_ELSE);
 202                                 break;
 203                         case TOKEN_FOR:
 204                                 token = lex_token(file);
 205                                 while ((token == ' ' || token == '\n') && file->length >= 0)
 206                                         token = lex_token(file);
 207
 208                                 PARSE_TREE_ADD(PARSE_TYPE_FOR);
 209                                 break;
 210
 211                         case LEX_IDENT:
 212                                 token = lex_token(file);
 213                                 printf("FOO: %s\n", file->lastok);
 214                                 break;
 215
 216
 217                         case TOKEN_DO:        PARSE_TODO(PARSE_TYPE_DO);
 218                         case TOKEN_WHILE:     PARSE_TODO(PARSE_TYPE_WHILE);
 219                         case TOKEN_BREAK:     PARSE_TODO(PARSE_TYPE_BREAK);
 220                         case TOKEN_CONTINUE:  PARSE_TODO(PARSE_TYPE_CONTINUE);
 221                         case TOKEN_RETURN:    PARSE_TODO(PARSE_TYPE_RETURN);
 222                         case TOKEN_GOTO:      PARSE_TODO(PARSE_TYPE_GOTO);
 223                         case TOKEN_INT:       PARSE_TODO(PARSE_TYPE_INT);
 224                         case TOKEN_VOID:      PARSE_TODO(PARSE_TYPE_VOID);
 225                         case TOKEN_STRING:    PARSE_TODO(PARSE_TYPE_STRING);
 226                         case TOKEN_FLOAT:     PARSE_TODO(PARSE_TYPE_FLOAT);
 227                         case TOKEN_VECTOR:    PARSE_TODO(PARSE_TYPE_VECTOR);
 228                         case TOKEN_ENTITY:    PARSE_TODO(PARSE_TYPE_ENTITY);
 229
 230                         /* TODO: Preprocessor */
 231                         case '#':
 232                                 token = lex_token(file);
 233                                 token = lex_token(file);
 234                                 token = lex_token(file);
 235                                 token = lex_token(file);
 236                                 token = lex_token(file);
 237                                 token = lex_token(file);
 238                                 break;
 239
 240                         /*
 241                          * From here down is all language punctuation:  There is no
 242                          * need to actual create tokens from these because they're already
 243                          * tokenized as these individual tokens (which are in a special area
 244                          * of the ascii table which doesn't conflict with our other tokens
 245                          * which are higer than the ascii table.
 246                          */
 247                         case '&':               /* &  */
 248                                 token = lex_token(file);
 249                                 if (token == '&') { /* && */
 250                                         token = lex_token(file);
 251                                         PARSE_TREE_ADD(PARSE_TYPE_LAND);
 252                                         break;
 253                                 }
 254                                 PARSE_TREE_ADD(PARSE_TYPE_BAND);
 255                                 break;
 256                         case '|':               /* |  */
 257                                 token = lex_token(file);
 258                                 if (token == '|') { /* || */
 259                                         token = lex_token(file);
 260                                         PARSE_TREE_ADD(PARSE_TYPE_LOR);
 261                                         break;
 262                                 }
 263                                 PARSE_TREE_ADD(PARSE_TYPE_BOR);
 264                                 break;
 265                         case '!':
 266                                 token = lex_token(file);
 267                                 if (token == '=') { /* != */
 268                                         token = lex_token(file);
 269                                         PARSE_TREE_ADD(PARSE_TYPE_LNEQ);
 270                                         break;
 271                                 }
 272                                 PARSE_TREE_ADD(PARSE_TYPE_LNOT);
 273                                 break;
 274                         case '<':               /* <  */
 275                                 token = lex_token(file);
 276                                 if (token == '=') { /* <= */
 277                                         token = lex_token(file);
 278                                         PARSE_TREE_ADD(PARSE_TYPE_LTEQ);
 279                                         break;
 280                                 }
 281                                 PARSE_TREE_ADD(PARSE_TYPE_LT);
 282                                 break;
 283                         case '>':               /* >  */
 284                                 token = lex_token(file);
 285                                 if (token == '=') { /* >= */
 286                                         token = lex_token(file);
 287                                         PARSE_TREE_ADD(PARSE_TYPE_GTEQ);
 288                                         break;
 289                                 }
 290                                 PARSE_TREE_ADD(PARSE_TYPE_GT);
 291                                 break;
 292                         case '=':
 293                                 token = lex_token(file);
 294                                 if (token == '=') { /* == */
 295                                         token = lex_token(file);
 296                                         PARSE_TREE_ADD(PARSE_TYPE_EQEQ);
 297                                         break;
 298                                 }
 299                                 PARSE_TREE_ADD(PARSE_TYPE_EQUAL);
 300                                 break;
 301                         case ';':
 302                                 token = lex_token(file);
 303                                 PARSE_TREE_ADD(PARSE_TYPE_DONE);
 304                                 break;
 305                         case '-':
 306                                 token = lex_token(file);
 307                                 PARSE_TREE_ADD(PARSE_TYPE_MINUS);
 308                                 break;
 309                         case '+':
 310                                 token = lex_token(file);
 311                                 PARSE_TREE_ADD(PARSE_TYPE_ADD);
 312                                 break;
 313                         case '(':
 314                                 token = lex_token(file);
 315                                 PARSE_TREE_ADD(PARSE_TYPE_LPARTH);
 316                                 break;
 317                         case ')':
 318                                 token = lex_token(file);
 319                                 PARSE_TREE_ADD(PARSE_TYPE_RPARTH);
 320                                 break;
 321                         case '{':
 322                                 token = lex_token(file);
 323                                 PARSE_TREE_ADD(PARSE_TYPE_LBS);
 324                                 break;
 325                         case '}':
 326                                 token = lex_token(file);
 327                                 PARSE_TREE_ADD(PARSE_TYPE_RBS);
 328                                 break;
 329                 }
 330         }
 331         parse_debug(parseroot);
 332         lex_reset(file);
 333
 334         return 1;
 335 }