From 5426d9e2a6b820e34809d639838b26643df9ab17 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Tue, 8 Feb 2022 00:29:10 +0800 Subject: fix errors There are multiple subtle errors in the previous version, both in the codes and in the description of the BNF format. This version should fix some problems now. This version can successfully parse the grammar of its own grammar format, which is quite nice. See test/check_reader.c for parsing this format. --- src/cnp.c | 131 +++++++++++++++++++++++++++++++++++++++++++++++++------------- 1 file changed, 105 insertions(+), 26 deletions(-) (limited to 'src/cnp.c') diff --git a/src/cnp.c b/src/cnp.c index 3c76f52..b28f967 100644 --- a/src/cnp.c +++ b/src/cnp.c @@ -1,6 +1,21 @@ +#include #include #include "cnp.h" +#define TITO struct timespec tic, toc + +#define TIC do { \ + clock_gettime(CLOCK_MONOTONIC_RAW, &tic); \ + } while (0) + +#define TOC do { \ + clock_gettime(CLOCK_MONOTONIC_RAW, &toc); \ + printf("\nTotal time = %f seconds\n", \ + (toc.tv_nsec - tic.tv_nsec) / \ + 1000000000.0 + \ + toc.tv_sec - tic.tv_sec); \ + } while (0) + struct Environment_s { grammar_info *gi; /* RESULT_TS and RESULT_PS are temporary arrays used in the @@ -32,7 +47,6 @@ nt_add(Environment *env, NUM X, NUM j) for (NUM i = 0; i < rg_len(RG); i++) { BOOL result = test_select(env, *(env->string+j), X, rg_nth(RG, i)); - /* fleprintf("i = %ld, after test select\n", i); */ for (NUM k = 0; k < grammar_left_len(GI->g); k++) { ht_reset(env->result_ts+k, DELETE_KEY); @@ -42,12 +56,10 @@ nt_add(Environment *env, NUM X, NUM j) if (env->error) break; if (result) { - /* fleprintf("i = %ld, j = %ld\n", i, j); */ env->error = desc_add(env->pr, env->pu, j, (pair4) { .x = X, .y = i, .z = 0, .u = j }); - /* fleprintf("env->error = %d\n", env->error); */ /* print_procr(env->pr); */ /* fleprintf("pr len = %ld\n", env->pr->len); * fleprintf("pr ini = %d\n", (env->pr->array)->initialized); */ @@ -73,22 +85,40 @@ test_select(Environment *env, NUM b, NUM X, CCR_MOD(List *) tnts) ht *result_ts = env->result_ts; ht *result_ps = env->result_ps; + ht_reset(result_ts, DELETE_KEY); + ht_reset(result_ps, DELETE_KEY); + if (tnt_first(gi->pts, gi->pps, gi->nts, grammar_left_len(gi->g), tnts, result_ts, result_ps)) { fleprintf0("Fail to find the first set of the TNT string.\n"); goto cleanup; } + /* if (X == 3) { + * fleprintf0("for empty the first has "); + * for (NUM i = 0; i < ht_size(result_ts); i++) { + * eprintf("%ld", **((NUM **)ht_keys(result_ts)+i)); + * if (i+1data.nt == 1) + * fleprintf("first of tnts is %ld\n", + * ((TNT *)list_nth(tnts, 0))->data.nt); + * } */ if (ht_find(result_ts, &b) != NULL) { result = 1; + +#ifdef DEBUG + fleprintf("test succeeds against %ld\n", b); +#endif + goto success; } - + /* fleprintf("hi, size = %ld\n", ht_size(result_ps)); */ for (NUM i = 0; i < ht_size(result_ps); i++) { - PTD *ptdp = grammar_ptd(gi->g, **((PT **) ht_keys(result_ps+i))); + PTD *ptdp = grammar_ptd(gi->g, **((PT **) ht_keys(result_ps)+i)); if (ptd_run(ptdp, b)) { - /* fleprintf("i = %ld\n", i); */ result = 1; goto success; } @@ -104,24 +134,27 @@ test_select(Environment *env, NUM b, NUM X, CCR_MOD(List *) tnts) goto success; break; default: - if (!(gi->nts+TOP->data.nt)) goto success; + if (!(*(gi->nts+(TOP->data.nt)))) goto success; break; } #undef TOP } - + /* fleprintf("hi %ld\n", X); */ if (ht_find(gi->sts+X, &b) != NULL) { result = 1; + +#ifdef DEBUG + fleprintf("followed by %ld\n", b); +#endif + goto success; } for (NUM i = 0; i < ht_size(gi->sps+X); i++) { - PTD *ptdp = grammar_ptd(gi->g, **((PT **) ht_keys(gi->sps+X))); - /* fleprintf("i = %ld\n", i); */ + PTD *ptdp = grammar_ptd(gi->g, **((PT **) ht_keys(gi->sps+X)+i)); if (ptd_run(ptdp, b)) { - /* fleprintf("i = %ld\n", i); */ result = 1; goto success; } @@ -154,9 +187,11 @@ rtn_internal(pair6 label) label.v, label.w }))) return; - /* fleprintf("added descriptor (%ld, %ld, %ld, %ld, %ld)\n", - * label.z, label.u, label.v, label.w, - * rtn_internal_num); */ +#ifdef DEBUG + fleprintf("added descriptor (%ld, %ld, %ld, %ld, %ld)\n", + label.z, label.u, label.v, label.w, + rtn_internal_num); +#endif if ((rtn_internal_env->error = bsr_add(rtn_internal_env->gi->g, @@ -175,9 +210,11 @@ rtn(Environment *env, NUM X, NUM k, NUM j) pair3 label = (pair3) { .x = X, .y = k, .z = j }; pair2 label2 = (pair2) { .x = X, .y = k }; - if (spa_belong(env->spap, label)) return; +#ifdef DEBUG + fleprintf("encounter %ld, %ld, %ld\n", X, k, j); +#endif - /* fleprintf0("new spa\n"); */ + if (spa_belong(env->spap, label)) return; if ((env->error = spa_insert(env->spap, label))) return; @@ -267,7 +304,12 @@ cnp_call(Environment *env, pair3 label, NUM i, NUM j) } NUM X = (NUM) xtnt->data.nt; - /* fleprintf("X = %ld, j = %ld\n", X, j); */ + +#ifdef DEBUG + fleprintf0("X = "); + eprint_name(list_nth(grammar_names(env->gi->g), X)); + eprintf(", j = %ld\n", j); +#endif pair2 node = (pair2) { .x = X, .y = j }; pair4 u = (pair4) @@ -279,11 +321,21 @@ cnp_call(Environment *env, pair3 label, NUM i, NUM j) }; if (!(crf_find_node(env->crfp, node))) { + +#ifdef DEBUG + fleprintf("adding node (%ld, %ld)\n", X, j); +#endif + if (crf_add_node(env->crfp, node)) { fleprintf0("fail to add node to crf\n"); goto cleanup; } +#ifdef DEBUG + fleprintf("adding edge to (%ld, %ld, %ld, %ld)\n", + u.x, u.y, u.z, u.u); +#endif + if (crf_add_edge(env->crfp, node, u)) { fleprintf0("fail to add edge to crf\n"); goto cleanup; @@ -292,11 +344,14 @@ cnp_call(Environment *env, pair3 label, NUM i, NUM j) /* errors will be stored in ENV, so we simply return */ nt_add(env, X, j); - /* fleprintf("X = %ld, j = %ld\n", X, j); */ - return; } +#ifdef DEBUG + fleprintf("adding edge to (%ld, %ld, %ld, %ld)\n", + u.x, u.y, u.z, u.u); +#endif + if (!(crf_find_edge(env->crfp, node, u))) { if (crf_add_edge(env->crfp, node, u)) { fleprintf0("fail to add edge to crf\n"); @@ -378,11 +433,13 @@ env_follow_p(CCR_MOD(Environment *) env, NUM X, NUM t) for (NUM i = 0; i < ht_size(env->gi->sps+X); i++) { PTD *ptdp = grammar_ptd(env->gi->g, - **((PT **) ht_keys(env->gi->sps+X))); + **((PT **) ht_keys(env->gi->sps+X)+i)); if (ptd_run(ptdp, t)) return 1; } - /* fleprintf("X = %ld, t = %ld\n", X, t); */ +#ifdef DEBUG + fleprintf("X = %ld, t = %ld\n", X, t); +#endif return 0; } @@ -679,6 +736,9 @@ cnp_parse(Grammar *g, str *string) if (env_follow_p(env, current_prodecor->x, *(num_string+current_grade))) { +#ifdef DEBUG + fleprintf0("returning from an empty rule\n"); +#endif rtn(env, current_prodecor->x, current_prodecor->u, current_grade); } @@ -693,6 +753,9 @@ cnp_parse(Grammar *g, str *string) if (current_prodecor->z == list_length(right)) { if (env_follow_p(env, current_prodecor->x, *(num_string+current_grade))) { +#ifdef DEBUG + fleprintf0("returning from the end\n"); +#endif rtn(env, current_prodecor->x, current_prodecor->u, current_grade); } @@ -744,7 +807,17 @@ cnp_parse(Grammar *g, str *string) ((TNT *) list_nth(right, current_prodecor->z-1))->type == PREDICATE) { #ifdef DEBUG - fleprintf0("found terminal\n"); + if (((TNT *) list_nth(right, current_prodecor->z-1))->type == + TERMINAL) + fleprintf("found terminal %ld\n", + ((TNT *) + list_nth + (right, current_prodecor->z-1))->data.t); + else + fleprintf("found predicate terminal %ld\n", + ((TNT *) + list_nth + (right, current_prodecor->z-1))->data.pt); #endif /* add to BSR set */ errorp = @@ -771,8 +844,12 @@ cnp_parse(Grammar *g, str *string) goto continue_label; } + #ifdef DEBUG fleprintf0("terminal not at the end\n"); + fleprintf("testing X = %ld, z = %ld, input = %ld\n", + current_prodecor->x, current_prodecor->z, + *(num_string+current_grade)); #endif /* else test select */ tnts = @@ -818,10 +895,12 @@ cnp_parse(Grammar *g, str *string) .z = current_prodecor->z }, current_prodecor->u, current_grade); - /* fleprintf("after call { %ld, %ld, %ld, %ld, %ld }\n", - * current_prodecor->x, current_prodecor->y, - * current_prodecor->z, current_prodecor->u, - * current_grade); */ +#ifdef DEBUG + fleprintf("after call { %ld, %ld, %ld, %ld, %ld }\n", + current_prodecor->x, current_prodecor->y, + current_prodecor->z, current_prodecor->u, + current_grade); +#endif continue_label: -- cgit v1.2.3-18-g5258