diff options
author | Bad Diode <bd@badd10de.dev> | 2021-10-31 14:46:02 +0100 |
---|---|---|
committer | Bad Diode <bd@badd10de.dev> | 2021-10-31 14:46:02 +0100 |
commit | c2065e6e5e9eca78719c58dbe21f2fadfb44f961 (patch) | |
tree | e7e7ffceb5c94d9b243c7374639ed929d32459ea | |
parent | ef0cbf240782010a4b71d32546e022dfd4f0b6bf (diff) | |
download | bdl-c2065e6e5e9eca78719c58dbe21f2fadfb44f961.tar.gz bdl-c2065e6e5e9eca78719c58dbe21f2fadfb44f961.zip |
Unify semantic analysis actions under a single function
-rw-r--r-- | src/parser.c | 160 |
1 files changed, 49 insertions, 111 deletions
diff --git a/src/parser.c b/src/parser.c index d4deb74..31eb172 100644 --- a/src/parser.c +++ b/src/parser.c | |||
@@ -419,12 +419,14 @@ symbol_in_env(Environment *env, Object *symbol) { | |||
419 | } | 419 | } |
420 | 420 | ||
421 | void | 421 | void |
422 | check_object_scope(Environment *env, Object *obj, Errors *errors) { | 422 | semantic_analysis(Environment *env, Object *obj, Errors *errors) { |
423 | if (obj == NULL) { | 423 | if (obj == NULL || obj->visited) { |
424 | return; | 424 | return; |
425 | } | 425 | } |
426 | obj->visited = true; | ||
426 | switch (obj->type) { | 427 | switch (obj->type) { |
427 | case OBJ_TYPE_SYMBOL: { | 428 | case OBJ_TYPE_SYMBOL: { |
429 | Object *found = symbol_in_env(env, obj); | ||
428 | if (symbol_in_env(env, obj) == NULL) { | 430 | if (symbol_in_env(env, obj) == NULL) { |
429 | error_push(errors, (Error){ | 431 | error_push(errors, (Error){ |
430 | .type = ERR_TYPE_PARSER, | 432 | .type = ERR_TYPE_PARSER, |
@@ -432,57 +434,56 @@ check_object_scope(Environment *env, Object *obj, Errors *errors) { | |||
432 | .line = obj->line, | 434 | .line = obj->line, |
433 | .col = obj->col, | 435 | .col = obj->col, |
434 | }); | 436 | }); |
437 | return; | ||
435 | } | 438 | } |
436 | } break; | 439 | semantic_analysis(env, found, errors); |
437 | case OBJ_TYPE_PAIR: { | ||
438 | check_object_scope(env, obj->head, errors); | ||
439 | check_object_scope(env, obj->tail, errors); | ||
440 | } break; | 440 | } break; |
441 | case OBJ_TYPE_DEF: { | 441 | case OBJ_TYPE_DEF: { |
442 | ht_insert(env->table, obj->var_name, obj->var_expr); | 442 | ht_insert(env->table, obj->var_name, obj->var_expr); |
443 | check_object_scope(env, obj->var_expr, errors); | 443 | semantic_analysis(env, obj->var_expr, errors); |
444 | } break; | 444 | } break; |
445 | case OBJ_TYPE_SET: { | 445 | case OBJ_TYPE_SET: { |
446 | check_object_scope(env, obj->var_name, errors); | 446 | semantic_analysis(env, obj->var_name, errors); |
447 | check_object_scope(env, obj->var_expr, errors); | 447 | semantic_analysis(env, obj->var_expr, errors); |
448 | } break; | 448 | } break; |
449 | case OBJ_TYPE_IF: { | 449 | case OBJ_TYPE_IF: { |
450 | check_object_scope(env, obj->condition, errors); | 450 | semantic_analysis(env, obj->condition, errors); |
451 | check_object_scope(env, obj->expr_true, errors); | 451 | semantic_analysis(env, obj->expr_true, errors); |
452 | check_object_scope(env, obj->expr_false, errors); | 452 | semantic_analysis(env, obj->expr_false, errors); |
453 | } break; | ||
454 | case OBJ_TYPE_LAMBDA: { | ||
455 | Environment *new_env = env_alloc(env); | ||
456 | obj->env = new_env; | ||
457 | for (size_t i = 0; i < array_size(obj->body); i++) { | ||
458 | Object *expr = obj->body[i]; | ||
459 | check_object_scope(new_env, expr, errors); | ||
460 | } | ||
461 | } break; | ||
462 | default: break; | ||
463 | } | ||
464 | } | ||
465 | |||
466 | void | ||
467 | remove_unused_expr(Object *obj) { | ||
468 | if (obj == NULL) { | ||
469 | return; | ||
470 | } | ||
471 | switch (obj->type) { | ||
472 | case OBJ_TYPE_DEF: | ||
473 | case OBJ_TYPE_SET: { | ||
474 | remove_unused_expr(obj->var_expr); | ||
475 | } break; | ||
476 | case OBJ_TYPE_IF: { | ||
477 | remove_unused_expr(obj->condition); | ||
478 | remove_unused_expr(obj->expr_true); | ||
479 | remove_unused_expr(obj->expr_false); | ||
480 | } break; | 453 | } break; |
481 | case OBJ_TYPE_PAIR: { | 454 | case OBJ_TYPE_PAIR: { |
482 | remove_unused_expr(obj->head); | 455 | Object *head = obj->head; |
483 | remove_unused_expr(obj->tail); | 456 | if (IS_SYMBOL(head)) { |
457 | head = symbol_in_env(env, head); | ||
458 | if (head == NULL) { | ||
459 | error_push(errors, (Error){ | ||
460 | .type = ERR_TYPE_PARSER, | ||
461 | .value = ERR_SYMBOL_NOT_FOUND, | ||
462 | .line = obj->head->line, | ||
463 | .col = obj->head->col, | ||
464 | }); | ||
465 | return; | ||
466 | } | ||
467 | } | ||
468 | if (IS_LAMBDA(head)) { | ||
469 | if (obj->n_elems != array_size(head->params)) { | ||
470 | error_push(errors, (Error){ | ||
471 | .type = ERR_TYPE_PARSER, | ||
472 | .value = ERR_NOT_ENOUGH_ARGS, | ||
473 | .line = obj->line, | ||
474 | .col = obj->col | ||
475 | }); | ||
476 | return; | ||
477 | } | ||
478 | } | ||
479 | semantic_analysis(env, obj->head, errors); | ||
480 | semantic_analysis(env, obj->tail, errors); | ||
484 | } break; | 481 | } break; |
485 | case OBJ_TYPE_LAMBDA: { | 482 | case OBJ_TYPE_LAMBDA: { |
483 | // Initialize scope for this lambda. | ||
484 | Environment *new_env = env_alloc(env); | ||
485 | obj->env = new_env; | ||
486 | // Used for removing unnecessary statements. | ||
486 | Object **new_body = NULL; | 487 | Object **new_body = NULL; |
487 | array_init(new_body, 0); | 488 | array_init(new_body, 0); |
488 | for (size_t i = 0; i < array_size(obj->body); i++) { | 489 | for (size_t i = 0; i < array_size(obj->body); i++) { |
@@ -497,7 +498,7 @@ remove_unused_expr(Object *obj) { | |||
497 | continue; | 498 | continue; |
498 | } | 499 | } |
499 | } | 500 | } |
500 | remove_unused_expr(expr); | 501 | semantic_analysis(obj->env, expr, errors); |
501 | array_push(new_body, expr); | 502 | array_push(new_body, expr); |
502 | } | 503 | } |
503 | array_free(obj->body); | 504 | array_free(obj->body); |
@@ -507,54 +508,6 @@ remove_unused_expr(Object *obj) { | |||
507 | } | 508 | } |
508 | } | 509 | } |
509 | 510 | ||
510 | void | ||
511 | check_function_args(Environment *env, Object *obj, Errors *errors) { | ||
512 | if (obj == NULL || obj->visited) { | ||
513 | return; | ||
514 | } | ||
515 | obj->visited = true; | ||
516 | switch (obj->type) { | ||
517 | case OBJ_TYPE_SYMBOL: { | ||
518 | Object *found = symbol_in_env(env, obj); | ||
519 | check_function_args(env, found, errors); | ||
520 | } break; | ||
521 | case OBJ_TYPE_DEF: | ||
522 | case OBJ_TYPE_SET: { | ||
523 | check_function_args(env, obj->var_expr, errors); | ||
524 | } break; | ||
525 | case OBJ_TYPE_IF: { | ||
526 | check_function_args(env, obj->condition, errors); | ||
527 | check_function_args(env, obj->expr_true, errors); | ||
528 | check_function_args(env, obj->expr_false, errors); | ||
529 | } break; | ||
530 | case OBJ_TYPE_PAIR: { | ||
531 | Object *head = obj->head; | ||
532 | if (IS_SYMBOL(head)) { | ||
533 | head = symbol_in_env(env, head); | ||
534 | } | ||
535 | if (IS_LAMBDA(head)) { | ||
536 | if (obj->n_elems != array_size(head->params)) { | ||
537 | error_push(errors, (Error){ | ||
538 | .type = ERR_TYPE_PARSER, | ||
539 | .value = ERR_NOT_ENOUGH_ARGS, | ||
540 | .line = obj->line, | ||
541 | .col = obj->col | ||
542 | }); | ||
543 | } | ||
544 | } | ||
545 | check_function_args(env, head, errors); | ||
546 | check_function_args(env, obj->tail, errors); | ||
547 | } break; | ||
548 | case OBJ_TYPE_LAMBDA: { | ||
549 | for (size_t i = 0; i < array_size(obj->body); i++) { | ||
550 | Object *expr = obj->body[i]; | ||
551 | check_function_args(obj->env, expr, errors); | ||
552 | } | ||
553 | } break; | ||
554 | default: break; | ||
555 | } | ||
556 | } | ||
557 | |||
558 | Root * | 511 | Root * |
559 | parse(Token *tokens, Errors *errors) { | 512 | parse(Token *tokens, Errors *errors) { |
560 | array_init(roots, 0); | 513 | array_init(roots, 0); |
@@ -589,16 +542,10 @@ parse(Token *tokens, Errors *errors) { | |||
589 | ht_insert(global_env->table, symbol, symbol); | 542 | ht_insert(global_env->table, symbol, symbol); |
590 | } | 543 | } |
591 | 544 | ||
592 | // Check that symbols are defined before usage. | 545 | // Perform semantic analysis: |
593 | for (size_t i = 0; i < array_size(roots); i++) { | 546 | // 1. Populate symbol tables and ensure symbols are in scope when used. |
594 | Object *root = roots[i]; | 547 | // 2. Removing unnecessary expressions. |
595 | check_object_scope(global_env, root, errors); | 548 | // 3. Verify number of arguments is correct in function calls. |
596 | if (errors->n != 0) { | ||
597 | return NULL; | ||
598 | } | ||
599 | } | ||
600 | |||
601 | // Remove unnecessary statements. | ||
602 | Root *final_roots = NULL; | 549 | Root *final_roots = NULL; |
603 | array_init(final_roots, 0); | 550 | array_init(final_roots, 0); |
604 | for (size_t i = 0; i < array_size(roots); i++) { | 551 | for (size_t i = 0; i < array_size(roots); i++) { |
@@ -614,24 +561,15 @@ parse(Token *tokens, Errors *errors) { | |||
614 | } | 561 | } |
615 | } | 562 | } |
616 | array_push(final_roots, root); | 563 | array_push(final_roots, root); |
617 | remove_unused_expr(root); | 564 | semantic_analysis(global_env, root, errors); |
618 | if (errors->n != 0) { | 565 | if (errors->n != 0) { |
566 | array_free(final_roots); | ||
619 | return NULL; | 567 | return NULL; |
620 | } | 568 | } |
621 | } | 569 | } |
622 | array_free(roots); | 570 | array_free(roots); |
623 | roots = final_roots; | 571 | roots = final_roots; |
624 | 572 | ||
625 | // Check that the number of arguments in function calls match the number of | ||
626 | // formal parameters. | ||
627 | for (size_t i = 0; i < array_size(roots); i++) { | ||
628 | Object *root = roots[i]; | ||
629 | check_function_args(global_env, root, errors); | ||
630 | if (errors->n != 0) { | ||
631 | return NULL; | ||
632 | } | ||
633 | } | ||
634 | |||
635 | // TODO: Type check basic expressions (e.g. arithmetic/numeric comparisons). | 573 | // TODO: Type check basic expressions (e.g. arithmetic/numeric comparisons). |
636 | // We can't be sure when we have functions unless the return type is known. | 574 | // We can't be sure when we have functions unless the return type is known. |
637 | 575 | ||