parser.c

   1 #include <stdio.h>
   2 #include <stdarg.h>
   3
   4 #include "gmqcc.h"
   5 #include "lexer.h"
   6
   7 typedef struct {
   8     lex_file *lex;
   9     int      tok;
  10
  11     MEM_VECTOR_MAKE(ast_value*, globals);
  12     MEM_VECTOR_MAKE(ast_function*, functions);
  13
  14     ast_function *function;
  15     MEM_VECTOR_MAKE(ast_value*, locals);
  16     size_t blocklocal;
  17 } parser_t;
  18
  19 MEM_VEC_FUNCTIONS(parser_t, ast_value*, globals)
  20 MEM_VEC_FUNCTIONS(parser_t, ast_value*, locals)
  21 MEM_VEC_FUNCTIONS(parser_t, ast_function*, functions)
  22
  23 void parseerror(parser_t *parser, const char *fmt, ...)
  24 {
  25         va_list ap;
  26
  27     if (parser)
  28             printf("error %s:%lu: ", parser->lex->tok->ctx.file, (unsigned long)parser->lex->tok->ctx.line);
  29         else
  30             printf("error: ");
  31
  32         va_start(ap, fmt);
  33         vprintf(fmt, ap);
  34         va_end(ap);
  35
  36         printf("\n");
  37 }
  38
  39 bool parser_next(parser_t *parser)
  40 {
  41     /* lex_do kills the previous token */
  42     parser->tok = lex_do(parser->lex);
  43     if (parser->tok == TOKEN_EOF || parser->tok >= TOKEN_ERROR)
  44         return false;
  45     return true;
  46 }
  47
  48 /* lift a token out of the parser so it's not destroyed by parser_next */
  49 token *parser_lift(parser_t *parser)
  50 {
  51     token *tok = parser->lex->tok;
  52     parser->lex->tok = NULL;
  53     return tok;
  54 }
  55
  56 #define parser_tokval(p) (p->lex->tok->value)
  57 #define parser_token(p)  (p->lex->tok)
  58 #define parser_ctx(p)    (p->lex->tok->ctx)
  59
  60 ast_value* parser_find_global(parser_t *parser, const char *name)
  61 {
  62     size_t i;
  63     for (i = 0; i < parser->globals_count; ++i) {
  64         if (!strcmp(parser->globals[i]->name, name))
  65             return parser->globals[i];
  66     }
  67     return NULL;
  68 }
  69
  70 ast_value* parser_find_local(parser_t *parser, const char *name, size_t upto)
  71 {
  72     size_t i;
  73     for (i = parser->locals_count; i > upto;) {
  74         --i;
  75         if (!strcmp(parser->locals[i]->name, name))
  76             return parser->locals[i];
  77     }
  78     return NULL;
  79 }
  80
  81 ast_value* parser_find_var(parser_t *parser, const char *name)
  82 {
  83     ast_value *v;
  84     v         = parser_find_local(parser, name, 0);
  85     if (!v) v = parser_find_global(parser, name);
  86     return v;
  87 }
  88
  89 typedef struct {
  90     MEM_VECTOR_MAKE(ast_value*, p);
  91 } paramlist_t;
  92 MEM_VEC_FUNCTIONS(paramlist_t, ast_value*, p)
  93
  94 static ast_value *parser_parse_type(parser_t *parser, int basetype, bool *isfunc)
  95 {
  96     paramlist_t params;
  97     ast_value *var;
  98     lex_ctx   ctx = parser_ctx(parser);
  99     int vtype = basetype;
 100     int temptype;
 101
 102     MEM_VECTOR_INIT(&params, p);
 103
 104     *isfunc = false;
 105
 106     if (parser->tok == '(') {
 107         *isfunc = true;
 108         while (true) {
 109             ast_value *param;
 110             bool dummy;
 111
 112             if (!parser_next(parser)) {
 113                 MEM_VECTOR_CLEAR(&params, p);
 114                 return NULL;
 115             }
 116
 117             if (parser->tok == ')')
 118                 break;
 119
 120             temptype = parser_token(parser)->constval.t;
 121             if (!parser_next(parser)) {
 122                 MEM_VECTOR_CLEAR(&params, p);
 123                 return NULL;
 124             }
 125             param = parser_parse_type(parser, temptype, &dummy);
 126             (void)dummy;
 127
 128             if (!param) {
 129                 MEM_VECTOR_CLEAR(&params, p);
 130                 return NULL;
 131             }
 132
 133             if (!paramlist_t_p_add(&params, param)) {
 134                 MEM_VECTOR_CLEAR(&params, p);
 135                 parseerror(parser, "Out of memory while parsing typename");
 136                 return NULL;
 137             }
 138
 139             if (parser->tok == ',')
 140                 continue;
 141             if (parser->tok == ')')
 142                 break;
 143             MEM_VECTOR_CLEAR(&params, p);
 144             parseerror(parser, "Unexpected token");
 145             return NULL;
 146         }
 147         if (!parser_next(parser)) {
 148             MEM_VECTOR_CLEAR(&params, p);
 149             return NULL;
 150         }
 151     }
 152
 153     var = ast_value_new(ctx, "<unnamed>", vtype);
 154     if (!var) {
 155         MEM_VECTOR_CLEAR(&params, p);
 156         return NULL;
 157     }
 158     MEM_VECTOR_MOVE(&params, p, var, params);
 159     return var;
 160 }
 161
 162 static bool parser_expression(parser_t *parser, ast_block *block)
 163 {
 164     parseerror(parser, "TODO: statements/expressions");
 165     return false;
 166 }
 167
 168 static bool parser_variable(parser_t *parser, bool global);
 169 static bool parser_body_do(parser_t *parser, ast_block *block)
 170 {
 171     if (parser->tok == TOKEN_TYPENAME)
 172     {
 173         /* local variable */
 174         if (!parser_variable(parser, false))
 175             return false;
 176         return true;
 177     }
 178     else if (parser->tok == '{')
 179     {
 180         /* a block */
 181     }
 182     else
 183         return parser_expression(parser_t *parser, ast_block *block);
 184 }
 185
 186 static ast_block* parser_parse_block(parser_t *parser)
 187 {
 188     size_t oldblocklocal;
 189     ast_block *block = NULL;
 190
 191     oldblocklocal = parser->blocklocal;
 192     parser->blocklocal = parser->locals_count;
 193
 194     if (!parser_next(parser)) { /* skip the '{' */
 195         parseerror(parser, "expected function body");
 196         goto cleanup;
 197     }
 198
 199     block = ast_block_new(parser_ctx(parser));
 200
 201     while (parser->tok != TOKEN_EOF && parser->tok < TOKEN_ERROR)
 202     {
 203         if (parser->tok == '}')
 204             break;
 205
 206         if (!parser_body_do(parser, block)) {
 207             ast_block_delete(block);
 208             block = NULL;
 209             goto cleanup;
 210         }
 211     }
 212
 213     if (parser->tok != '}') {
 214         ast_block_delete(block);
 215         block = NULL;
 216     } else {
 217         (void)parser_next(parser);
 218     }
 219
 220 cleanup:
 221     parser->blocklocal = oldblocklocal;
 222     return block;
 223 }
 224
 225 static bool parser_variable(parser_t *parser, bool global)
 226 {
 227     bool          isfunc = false;
 228     ast_function *func = NULL;
 229     lex_ctx       ctx;
 230     ast_value    *var;
 231
 232     int basetype = parser_token(parser)->constval.t;
 233
 234     while (true)
 235     {
 236         if (!parser_next(parser)) { /* skip basetype or comma */
 237             parseerror(parser, "expected variable declaration");
 238             return false;
 239         }
 240
 241         isfunc = false;
 242         func = NULL;
 243         ctx = parser_ctx(parser);
 244         var = parser_parse_type(parser, basetype, &isfunc);
 245
 246         if (!var)
 247             return false;
 248
 249         if (parser->tok != TOKEN_IDENT) {
 250             parseerror(parser, "expected variable name\n");
 251             return false;
 252         }
 253
 254         if (global && parser_find_global(parser, parser_tokval(parser))) {
 255             ast_value_delete(var);
 256             parseerror(parser, "global already exists: %s\n", parser_tokval(parser));
 257             return false;
 258         }
 259
 260         if (!global && parser_find_local(parser, parser_tokval(parser), parser->blocklocal)) {
 261             ast_value_delete(var);
 262             parseerror(parser, "local variable already exists: %s\n", parser_tokval(parser));
 263             return false;
 264         }
 265
 266         if (!ast_value_set_name(var, parser_tokval(parser))) {
 267             parseerror(parser, "failed to set variable name\n");
 268             ast_value_delete(var);
 269             return false;
 270         }
 271
 272         if (isfunc) {
 273             /* a function was defined */
 274             ast_value *fval;
 275
 276             /* turn var into a value of TYPE_FUNCTION, with the old var
 277              * as return type
 278              */
 279             fval = ast_value_new(ctx, var->name, TYPE_FUNCTION);
 280             func = ast_function_new(ctx, var->name, fval);
 281             if (!fval || !func) {
 282                 ast_value_delete(var);
 283                 if (fval) ast_value_delete(fval);
 284                 if (func) ast_function_delete(func);
 285                 return false;
 286             }
 287
 288             fval->expression.next = (ast_expression*)var;
 289             MEM_VECTOR_MOVE(var, params, fval, params);
 290
 291             if (!parser_t_functions_add(parser, func)) {
 292                 ast_value_delete(var);
 293                 if (fval) ast_value_delete(fval);
 294                 if (func) ast_function_delete(func);
 295                 return false;
 296             }
 297
 298             var = fval;
 299         }
 300
 301         if ( ( global && !parser_t_globals_add(parser, var)) ||
 302              (!global && !parser_t_locals_add(parser, var)) )
 303         {
 304             ast_value_delete(var);
 305             return false;
 306         }
 307
 308         if (!parser_next(parser)) {
 309             ast_value_delete(var);
 310             return false;
 311         }
 312
 313         if (parser->tok == ';') {
 314             if (!parser_next(parser))
 315                 return parser->tok == TOKEN_EOF;
 316             return true;
 317         }
 318
 319         if (parser->tok == ',') {
 320             /* another var */
 321             continue;
 322         }
 323
 324         if (parser->tok != '=') {
 325             parseerror(parser, "expected '=' or ';'");
 326             return false;
 327         }
 328
 329         if (!parser_next(parser))
 330             return false;
 331
 332         if (parser->tok == '#') {
 333             if (!global) {
 334                 parseerror(parser, "cannot declare builtins within functions");
 335                 return false;
 336             }
 337             if (!isfunc || !func) {
 338                 parseerror(parser, "unexpected builtin number, '%s' is not a function", var->name);
 339                 return false;
 340             }
 341             if (!parser_next(parser)) {
 342                 parseerror(parser, "expected builtin number");
 343                 return false;
 344             }
 345             if (parser->tok != TOKEN_INTCONST) {
 346                 parseerror(parser, "builtin number must be an integer constant");
 347                 return false;
 348             }
 349             if (parser_token(parser)->constval.i <= 0) {
 350                 parseerror(parser, "builtin number must be positive integer greater than zero");
 351                 return false;
 352             }
 353
 354             func->builtin = -parser_token(parser)->constval.i;
 355         } else if (parser->tok == '{') {
 356             /* function body */
 357             ast_block *block;
 358             ast_function *old = parser->function;
 359
 360             if (!global) {
 361                 parseerror(parser, "cannot declare functions within functions");
 362                 return false;
 363             }
 364
 365             parser->function = func;
 366             block = parser_parse_block(parser);
 367             parser->function = old;
 368
 369             if (!block)
 370                 return false;
 371
 372             if (!ast_function_blocks_add(func, block)) {
 373                 ast_block_delete(block);
 374                 return false;
 375             }
 376             return true;
 377         } else {
 378             parseerror(parser, "TODO, const assignment");
 379         }
 380
 381         if (!parser_next(parser))
 382             return false;
 383
 384         if (parser->tok == ',') {
 385             /* another */
 386             continue;
 387         }
 388
 389         if (parser->tok != ';') {
 390             parseerror(parser, "expected semicolon");
 391             return false;
 392         }
 393
 394         (void)parser_next(parser);
 395
 396         return true;
 397     }
 398 }
 399
 400 static bool parser_do(parser_t *parser)
 401 {
 402     if (parser->tok == TOKEN_TYPENAME)
 403     {
 404         return parser_variable(parser, true);
 405     }
 406     else if (parser->tok == TOKEN_KEYWORD)
 407     {
 408         /* handle 'var' and 'const' */
 409         return false;
 410     }
 411     else if (parser->tok == '.')
 412     {
 413         /* entity-member declaration */
 414         return false;
 415     }
 416     else
 417     {
 418         parseerror(parser, "unexpected token: %s", parser->lex->tok->value);
 419         return false;
 420     }
 421     return true;
 422 }
 423
 424 bool parser_compile(const char *filename)
 425 {
 426     size_t i;
 427     parser_t *parser;
 428     ir_builder *ir;
 429
 430     parser = (parser_t*)mem_a(sizeof(parser_t));
 431     if (!parser)
 432         return false;
 433
 434     memset(parser, 0, sizeof(parser));
 435
 436     MEM_VECTOR_INIT(parser, globals);
 437     MEM_VECTOR_INIT(parser, locals);
 438     parser->lex = lex_open(filename);
 439
 440     if (!parser->lex) {
 441         printf("failed to open file \"%s\"\n", filename);
 442         return false;
 443     }
 444
 445     /* initial lexer/parser state */
 446     parser->lex->flags.noops = true;
 447
 448     if (parser_next(parser))
 449     {
 450         while (parser->tok != TOKEN_EOF && parser->tok < TOKEN_ERROR)
 451         {
 452             if (!parser_do(parser)) {
 453                 if (parser->tok == TOKEN_EOF)
 454                     parseerror(parser, "unexpected eof");
 455                 else
 456                     parseerror(parser, "parse error\n");
 457                 lex_close(parser->lex);
 458                 mem_d(parser);
 459                 return false;
 460             }
 461         }
 462     }
 463
 464     lex_close(parser->lex);
 465
 466     ir = ir_builder_new("gmqcc_out");
 467     if (!ir) {
 468         printf("failed to allocate builder\n");
 469         goto cleanup;
 470     }
 471
 472     for (i = 0; i < parser->globals_count; ++i) {
 473         if (!ast_global_codegen(parser->globals[i], ir)) {
 474             printf("failed to generate global %s\n", parser->globals[i]->name);
 475         }
 476     }
 477     for (i = 0; i < parser->functions_count; ++i) {
 478         if (!ast_function_codegen(parser->functions[i], ir)) {
 479             printf("failed to generate function %s\n", parser->functions[i]->name);
 480         }
 481         if (!ir_function_finalize(parser->functions[i]->ir_func)) {
 482             printf("failed to finalize function %s\n", parser->functions[i]->name);
 483         }
 484     }
 485
 486     ir_builder_dump(ir, printf);
 487
 488 cleanup:
 489     for (i = 0; i < parser->globals_count; ++i) {
 490         ast_value_delete(parser->globals[i]);
 491     }
 492     MEM_VECTOR_CLEAR(parser, globals);
 493
 494     mem_d(parser);
 495     return true;
 496 }