diff options
Diffstat (limited to 'src/test/check_grammar.c')
| -rw-r--r-- | src/test/check_grammar.c | 314 |
1 files changed, 279 insertions, 35 deletions
diff --git a/src/test/check_grammar.c b/src/test/check_grammar.c index 98a07cd..ca70fa9 100644 --- a/src/test/check_grammar.c +++ b/src/test/check_grammar.c @@ -1,12 +1,53 @@ +#include <string.h> #include <stdio.h> #include <stdlib.h> #include "../grammar.h" +#define READ_INTO_CPA(N, U, I, VA, VI, CP) do { \ + U = new_utf8(N, 1); \ + I = get_info((str *)U, 0); \ + VA = MYALLOC(NUM, 1); \ + VI = 0; \ + for (NUM index = 0; \ + I.value >= 0 && index < str_length((str *) U); \ + index += I.step, VI++) { \ + I = get_info((str *)U, index); \ + *(VA+VI) = I.value; \ + } \ + CP = MYALLOC(cpa, 1); \ + CP->array = VA; \ + CP->size = VI; \ + add_to_list(names, CP); \ + destroy_str((str *)U, 1); \ + } while (0) + +#define READ_TNT_STRING(LEFT, FORMAT, LEN, ...) do { \ + tnt_string = new_tnt_string(FORMAT, LEN, __VA_ARGS__); \ + if (!tnt_string) { \ + fleprintf("left = %d, f = %s, l = %d, " \ + "cannot create tnt string\n", \ + LEFT, FORMAT, LEN); \ + map_list(rules, destroy_rule_and_free_all); \ + destroy_list(rules, 0); \ + map_list(names, destroy_cpa_and_free_all); \ + destroy_list(names, 0); \ + return 1; \ + } \ + rule = new_rule(LEFT, tnt_string); \ + add_to_list(rules, rule); \ + } while (0) + +static void +print_sep() +{ + printf(", "); +} + int -main(U_ATTR int argc, U_ATTR char **argv) +main(UNUSED int argc, UNUSED char **argv) { /* check new_tnt and print it */ - TNT *tnt = new_tnt(1, 12); + TNT *tnt = new_tnt(NONTERMINAL, 12); printf("Print a TNT value of type NT: "); print_tnt(tnt); @@ -37,52 +78,59 @@ main(U_ATTR int argc, U_ATTR char **argv) List *rules = new_list(); List *names = new_list(); - for (int i = 0; i < 4; i++) { - tnt_string = new_tnt_string("ntn", 3, - (NT) 3*(i+1), - (T) 3*(i+1)*(i+1), - (NT) 3*(i+1)*(i+1)-2); + char *name = MYALLOC(char, 2); + *(name+1) = 0; + *name = 'E'; - if (!tnt_string) { - eprintf("i = %d, cannot create tnt string\n", i); + utf8* uname = NULL; - map_list(rules, destroy_rule_and_free_all); - destroy_list(rules, 0); + str_info info = EMPTY_STR_INFO; - map_list(names, destroy_cpa_and_free_all); - destroy_list(names, 0); - return 1; - } + NUM *varray = NULL; + NUM vindex = 0; + cpa *cpap = NULL; - rule = new_rule(i%3, tnt_string); - add_to_list(rules, rule); + READ_INTO_CPA(name, uname, info, varray, vindex, cpap); - char *name = MYALLOC(char, 7); - snprintf(name, 7, "Rule %d", i); + name = MYALLOC(char, 2); + *(name+1) = 0; + *name = 'T'; - utf8* uname = new_utf8(name, 6); + READ_INTO_CPA(name, uname, info, varray, vindex, cpap); - str_info info = get_info((str *)uname, 0); + name = MYALLOC(char, 2); + *(name+1) = 0; + *name = 'F'; - NUM *varray = MYALLOC(NUM, 6); - NUM vindex = 0; + READ_INTO_CPA(name, uname, info, varray, vindex, cpap); - for (NUM index = 0; - info.value >= 0 && index < str_length((str *) uname); - index += info.step, vindex++) { - info = get_info((str *)uname, index); + name = MYALLOC(char, 2); + *(name+1) = 0; + *name = 'D'; - *(varray+vindex) = info.value; - } + READ_INTO_CPA(name, uname, info, varray, vindex, cpap); - destroy_str((str *) uname, 1); + READ_TNT_STRING(0, "n", 1, (NT) 1); + READ_TNT_STRING(0, "ntn", 3, (NT) 1, (T) 43, (NT) 1); - cpa *cpap = MYALLOC(cpa, 1); - cpap->array = varray; - cpap->size = vindex; + READ_TNT_STRING(1, "n", 1, (NT) 2); + READ_TNT_STRING(1, "ntn", 3, (NT) 2, (T) 42, (NT) 2); - add_to_list(names, cpap); - } + READ_TNT_STRING(2, "n", 1, (NT) 3); + READ_TNT_STRING(2, "tnt", 3, (T) 40, (NT) 0, (T) 41); + + READ_TNT_STRING(3, "tn", 1, (T) 48, (NT) 3); + READ_TNT_STRING(3, "tn", 1, (T) 49, (NT) 3); + READ_TNT_STRING(3, "tn", 1, (T) 50, (NT) 3); + READ_TNT_STRING(3, "tn", 1, (T) 51, (NT) 3); + READ_TNT_STRING(3, "tn", 1, (T) 52, (NT) 3); + READ_TNT_STRING(3, "tn", 1, (T) 53, (NT) 3); + READ_TNT_STRING(3, "tn", 1, (T) 54, (NT) 3); + READ_TNT_STRING(3, "tn", 1, (T) 55, (NT) 3); + READ_TNT_STRING(3, "tn", 1, (T) 56, (NT) 3); + READ_TNT_STRING(3, "tn", 1, (T) 57, (NT) 3); + rule = new_rule(3, new_list()); + add_to_list(rules, rule); Grammar *g = new_grammar(); @@ -90,6 +138,202 @@ main(U_ATTR int argc, U_ATTR char **argv) print_grammar(g); + Rule_group *rg = grammar_rule(g, 0); + List *tnts = list_nth((List *) rg_right(rg), 1); + map_list(tnts, print_tnt); + printf("\n"); + + printf("\n\n"); + + /* TODO: Check first and follow sets */ + NUM left_len = grammar_left_len(g); + BOOL *epsilon_array = NULL; + ht *terminal_hts = NULL, *predicate_hts = NULL; + ht *test_terminal_hts = NULL, *test_predicate_hts = NULL; + ht *result_terminal_hts = NULL, *result_predicate_hts = NULL; + ht *tnt_ht = NULL; + List *test_tnt_string = NULL; + + SAFE_MALLOC(BOOL, epsilon_array, left_len, goto cleanup;); + + epsilon_nts(g, epsilon_array); + + printf("Printing the epsilon array...\n"); + for (NUM i = 0; i < left_len;) { + if (*(epsilon_array+i)) printf("ε"); else printf(" "); + if (++i<left_len) printf(", "); else printf("\n"); + } + + printf("\n\n"); + + SAFE_MALLOC(ht, terminal_hts, left_len, goto cleanup;); + SAFE_MALLOC(ht, predicate_hts, left_len, goto cleanup;); + + memset(terminal_hts, 0, sizeof(ht)*left_len); + memset(predicate_hts, 0, sizeof(ht)*left_len); + + for (NUM i = 0; i < left_len; i++) { + ht *temp = NULL; + temp = new_ht(left_len << 1); + *(terminal_hts+i) = *temp; + free(temp); + + temp = new_ht(left_len << 1); + *(predicate_hts+i) = *temp; + free(temp); + } + + if (nt_first(g, epsilon_array, terminal_hts, predicate_hts)) { + fleprintf0("error in generating the first set\n"); + goto cleanup; + } + + NUM ht_len = 0, *keys = NULL; + + for (NUM i = 0; i < left_len;) { + printf("Nonterminal %ld contains the following terminals in the " + "FIRST set:\n", i); + ht_len = ht_size(terminal_hts+i); + keys = ht_keys(terminal_hts+i++); + for (NUM j = 0; j < ht_len;) { + printf("T %ld", *(keys+j)); + if (++j<ht_len) printf(", "); + else printf("\n"); + } + } + + SAFE_MALLOC(ht, test_terminal_hts, left_len, goto cleanup;); + SAFE_MALLOC(ht, test_predicate_hts, left_len, goto cleanup;); + + memset(test_terminal_hts, 0, sizeof(ht)*left_len); + memset(test_predicate_hts, 0, sizeof(ht)*left_len); + + for (NUM i = 0; i < left_len; i++) { + ht *temp = NULL; + temp = new_ht(left_len << 1); + *(test_terminal_hts+i) = *temp; + free(temp); + + temp = new_ht(left_len << 1); + *(test_predicate_hts+i) = *temp; + free(temp); + } + + /* test tnt_first */ + + printf("\n\n"); + + test_tnt_string = new_tnt_string("nntt", 4, + (NT) 0, (NT) 2, (T) 90, (T) 41); + + if (tnt_first(terminal_hts, predicate_hts, epsilon_array, + left_len, test_tnt_string, + test_terminal_hts, test_predicate_hts)) { + fleprintf0("error in generating the first set\n"); + goto cleanup; + } + + printf("The TNT string "); + map_list_between(test_tnt_string, print_tnt, print_sep); + printf(" has the following FIRST set:\n"); + + ht_len = ht_size(test_terminal_hts); + keys = ht_keys(test_terminal_hts); + for (NUM i = 0; i < ht_len;) { + printf("T %ld", *(keys+i)); + if (++i<ht_len) printf(", "); + else printf("\n"); + } + + ht_len = ht_size(test_predicate_hts); + keys = ht_keys(test_predicate_hts); + for (NUM i = 0; i < ht_len;) { + printf("PT %ld", *(keys+i)); + if (++i<ht_len) printf(", "); + else printf("\n"); + } + + /* check nt_follow */ + + printf("\n\n"); + + SAFE_MALLOC(ht, result_terminal_hts, left_len, goto cleanup;); + SAFE_MALLOC(ht, result_predicate_hts, left_len, goto cleanup;); + + memset(result_terminal_hts, 0, sizeof(ht)*left_len); + memset(result_predicate_hts, 0, sizeof(ht)*left_len); + + for (NUM i = 0; i < left_len; i++) { + ht *temp = NULL; + temp = new_ht(left_len << 1); + *(result_terminal_hts+i) = *temp; + free(temp); + + temp = new_ht(left_len << 1); + *(result_predicate_hts+i) = *temp; + free(temp); + } + + if (nt_follow(g, epsilon_array, terminal_hts, predicate_hts, + result_terminal_hts, result_predicate_hts)) { + fleprintf0("Error in nt_follow\n"); + goto cleanup; + } + + for (NUM i = 0; i < left_len;) { + printf("Nonterminal %ld contains the following terminals in the " + "FOLLOW set:\n", i); + ht_len = ht_size(result_terminal_hts+i); + keys = ht_keys(result_terminal_hts+i++); + for (NUM j = 0; j < ht_len;) { + if (*(keys+j) == END_OF_INPUT) printf("T $"); + else printf("T %ld", *(keys+j)); + if (++j<ht_len) printf(", "); + else printf("\n"); + } + } + + cleanup: + if (epsilon_array) free(epsilon_array); + if (terminal_hts) { + for (NUM i = 0; i < left_len; i++) + destroy_ht(terminal_hts+i, DESTROY_NONE_NO_SELF); + free(terminal_hts); + } + + if (predicate_hts) { + for (NUM i = 0; i < left_len; i++) + destroy_ht(predicate_hts+i, DESTROY_NONE_NO_SELF); + free(predicate_hts); + } + + if (test_terminal_hts) { + for (NUM i = 0; i < left_len; i++) + destroy_ht(test_terminal_hts+i, DESTROY_NONE_NO_SELF); + free(test_terminal_hts); + } + + if (test_predicate_hts) { + for (NUM i = 0; i < left_len; i++) + destroy_ht(test_predicate_hts+i, DESTROY_NONE_NO_SELF); + free(test_predicate_hts); + } + + if (result_terminal_hts) { + for (NUM i = 0; i < left_len; i++) + destroy_ht(result_terminal_hts+i, DESTROY_NONE_NO_SELF); + free(result_terminal_hts); + } + + if (result_predicate_hts) { + for (NUM i = 0; i < left_len; i++) + destroy_ht(result_predicate_hts+i, DESTROY_NONE_NO_SELF); + free(result_predicate_hts); + } + + if (test_tnt_string) destroy_list(test_tnt_string, 1); + if (tnt_ht) destroy_ht(tnt_ht, DESTROY_NONE_SELF); + destroy_grammar(g, 1); destroy_list(rules, 1); |