From 36adc544609b6144adefa0a000f77d2845b814e2 Mon Sep 17 00:00:00 2001 From: NeilBrown Date: Sun, 21 Jul 2013 19:18:09 +1000 Subject: [PATCH] parsergen: improve tracing. Change the tracing to print the full stack after every step. This can be cross-referenced with the report that parsergen can generate to get a full picture of how the parse is progressing. Signed-off-by: NeilBrown --- csrc/parsergen.mdc | 107 ++++++++++++++++++++++++++++++--------------- 1 file changed, 72 insertions(+), 35 deletions(-) diff --git a/csrc/parsergen.mdc b/csrc/parsergen.mdc index 78a9a72..e821e2c 100644 --- a/csrc/parsergen.mdc +++ b/csrc/parsergen.mdc @@ -40,6 +40,7 @@ There are several distinct sections. #include #include ## parser includes + ## parser functions ## parser ###### File: calc.cgm ## demo grammar @@ -1686,6 +1687,7 @@ pieces of code provided in the grammar file, so they are generated first. static void gen_parser(FILE *f, struct grammar *g, char *file, char *name) { gen_known(f, g); + gen_non_term(f, g); gen_goto(f, g); gen_states(f, g); gen_reduce(f, g, file); @@ -1700,7 +1702,7 @@ pieces of code provided in the grammar file, so they are generated first. fprintf(f, "\tconfig->known_count = sizeof(known)/sizeof(known[0]);\n"); fprintf(f, "\tconfig->ignored |= (1 << TK_line_comment) | (1 << TK_block_comment);\n"); fprintf(f, "\ttokens = token_open(code, config);\n"); - fprintf(f, "\tvoid *rv = parser_run(tokens, states, do_reduce, do_free, trace);\n"); + fprintf(f, "\tvoid *rv = parser_run(tokens, states, do_reduce, do_free, trace, non_term, config->known_count);\n"); fprintf(f, "\ttoken_close(tokens);\n"); fprintf(f, "\treturn rv;\n"); fprintf(f, "}\n\n"); @@ -1709,6 +1711,7 @@ pieces of code provided in the grammar file, so they are generated first. ### Table words table The know words is simply an array of terminal symbols. +The table of nonterminals used for tracing is a similar array. ###### functions @@ -1725,6 +1728,20 @@ The know words is simply an array of terminal symbols. fprintf(f, "};\n\n"); } + static void gen_non_term(FILE *f, struct grammar *g) + { + int i; + fprintf(f, "#line 0 \"gen_non_term\"\n"); + fprintf(f, "static const char *non_term[] = {\n"); + for (i = TK_reserved; + i < g->num_syms; + i++) + if (g->symtab[i]->type == Nonterminal) + fprintf(f, "\t\"%.*s\",\n", g->symtab[i]->name.len, + g->symtab[i]->name.txt); + fprintf(f, "};\n\n"); + } + ### States and the goto tables. For each state we record the goto table and the reducible production if @@ -1868,10 +1885,10 @@ to the appropriate type for each access. All this is handling in static void gen_reduce(FILE *f, struct grammar *g, char *file) { - int i, j; + int i; fprintf(f, "#line 0 \"gen_reduce\"\n"); fprintf(f, "static int do_reduce(int prod, int depth, void **body,\n"); - fprintf(f, " void *ret, FILE *trace)\n"); + fprintf(f, " void *ret)\n"); fprintf(f, "{\n"); fprintf(f, "\tint ret_size = 0;\n"); @@ -1883,21 +1900,6 @@ to the appropriate type for each access. All this is handling in if (p->code.txt) gen_code(p, f, g); - fprintf(f, "\t\tif (trace) {\n"); - fprintf(f, "\t\t\tfprintf(trace, \"[%%2d]%.*s ->\", depth);\n", - p->head->name.len, p->head->name.txt); - for (j = 0; j < p->body_size; j++) { - if (p->body[j]->type == Terminal) { - fputs("\t\t\tfputs(\" \", trace);\n", f); - fprintf(f, "\t\t\ttext_dump(trace, (*(struct token*)body[%d]).txt, 20);\n", j); - } else { - fprintf(f, "\t\t\tfprintf(trace, \" %.*s\");\n", - p->body[j]->name.len, - p->body[j]->name.txt); - } - } - fprintf(f, "\t\t}\n"); - if (p->head->struct_name.txt) fprintf(f, "\t\tret_size = sizeof(struct %.*s);\n", p->head->struct_name.len, @@ -2196,7 +2198,7 @@ The parser generator has nicely provided us with goto tables sorted by symbol number. We need a binary search function to find a symbol in the table. -###### parser +###### parser functions static int search(const struct state *l, int sym) { @@ -2240,7 +2242,7 @@ The `state` is the most important one and guides the parsing process. The freeing function. The symbol leads us to the right free function through `do_free`. -###### parser +###### parser functions struct parser { int state; @@ -2271,7 +2273,7 @@ function reports if it could. So `shift` finds the next state. If that succeed it extends the allocations if needed and pushed all the information onto the stacks. -###### parser +###### parser functions static int shift(struct parser *p, int sym, void *asn, @@ -2300,7 +2302,7 @@ if needed and pushed all the information onto the stacks. and frees and `asn` entries that need to be freed. It is called _after_ we reduce a production, just before we `shift` the nonterminal in. -###### parser +###### parser functions static void pop(struct parser *p, int num, void(*do_free)(short sym, void *asn)) @@ -2324,7 +2326,7 @@ copying, hence `memdup` and `tokcopy`. ###### parser includes #include -###### parser +###### parser functions void *memdup(void *m, int len) { @@ -2360,9 +2362,9 @@ We return whatever `asn` was returned by reducing production zero. ###### parser void *parser_run(struct token_state *tokens, const struct state states[], - int (*do_reduce)(int, int, void**, void*, FILE*), + int (*do_reduce)(int, int, void**, void*), void (*do_free)(short, void*), - FILE *trace) + FILE *trace, const char *non_term[], int knowns) { struct parser p = { 0 }; struct token *tk; @@ -2371,12 +2373,10 @@ We return whatever `asn` was returned by reducing production zero. tk = tok_copy(token_next(tokens)); while (!accepted) { + if (trace) + parser_trace(trace, &p, tk, states, non_term, knowns); + if (shift(&p, tk->num, tk, states)) { - if (trace) { - fputs("Shift ", trace); - text_dump(trace, tk->txt, 20); - fputs("\n", trace); - } tk = tok_copy(token_next(tokens)); continue; } @@ -2392,9 +2392,7 @@ We return whatever `asn` was returned by reducing production zero. (p.tos - states[p.state].reduce_size); bufsize = do_reduce(prod, p.tos, body, - buf, trace); - if (trace) - fputs("\n", trace); + buf); pop(&p, size, do_free); shift(&p, sym, memdup(buf, bufsize), states); @@ -2435,10 +2433,49 @@ We return whatever `asn` was returned by reducing production zero. ###### exported functions void *parser_run(struct token_state *tokens, const struct state states[], - int (*do_reduce)(int, int, void**, void*, FILE*), + int (*do_reduce)(int, int, void**, void*), void (*do_free)(short, void*), - FILE *trace); + FILE *trace, const char *non_term[], int knowns); + +### Tracing + +Being able to visualize the parser in action can be invaluable when +debugging the parser code, or trying to understand how the parse of a +particular grammar progresses. The stack contains all the important +state, so just printing out the stack every time around the parse loop +can make it possible to see exactly what is happening. + +This doesn't explicitly show each SHIFT and REDUCE action. However they +are easily deduced from the change between consecutive lines, and the +details of each state can be found by cross referencing the states list +in the stack with the "report" that parsergen can generate. +For terminal symbols, we just dump the token. For non-terminals we +print the name of the symbol. The look ahead token is reported at the +end inside square brackets. + +###### parser functions + + void parser_trace(FILE *trace, struct parser *p, + struct token *tk, const struct state states[], + const char *non_term[], int knowns) + { + int i; + for (i = 0; i < p->tos; i++) { + int sym = p->stack[i].sym; + fprintf(trace, "(%d) ", p->stack[i].state); + if (sym < TK_reserved + knowns) { + struct token *t = p->asn_stack[i]; + text_dump(trace, t->txt, 20); + } else + fputs(non_term[sym - TK_reserved - knowns], + trace); + fputs(" ", trace); + } + fprintf(trace, "(%d) [", p->state); + text_dump(trace, tk->txt, 20); + fputs("]\n", trace); + } # A Worked Example -- 2.43.0