From f41750b4888738b8123551983d1575a4774d1f1f Mon Sep 17 00:00:00 2001 From: NeilBrown Date: Wed, 10 Mar 2021 10:51:19 +1100 Subject: [PATCH] parsergen: split out error handling. I want to split up the core parsing into the different parts so they can be documented better. Firstly: split out error handling. Signed-off-by: NeilBrown --- csrc/parsergen.mdc | 112 ++++++++++++++++++--------------------------- 1 file changed, 45 insertions(+), 67 deletions(-) diff --git a/csrc/parsergen.mdc b/csrc/parsergen.mdc index ff2ed7b..0986fc2 100644 --- a/csrc/parsergen.mdc +++ b/csrc/parsergen.mdc @@ -2726,14 +2726,6 @@ to be handled. We return whatever `asn` was returned by reducing production zero. -If we can neither shift nor reduce we have an error to handle. We pop -single entries off the stack until we can shift the `TK_error` symbol, -then drop input tokens until we find one we can shift into the new error -state. We need to ensure that something is dropped or shifted after an -error, or we could get into an infinite loop, only shifting in -`TK_error`, then reducing. So we track if there has been a shift since -the last error, and if not the next error always discards one token. - When we find `TK_in` and `TK_out` tokens which report indents we need to handle them directly as the grammar cannot express what we want to do with them. @@ -2776,32 +2768,54 @@ in the thing that preceed: Here the NEWLINE will be shifted because nothing can be reduced until the `if` is seen. -When during error handling we discard tokens read in, we want to keep -discarding until we see one that is recognised. If we had a full set -of LR(1) grammar states, this would mean looking in the look-ahead set, -but we don't keep a full look-ahead set. We only record the subset -that leads to SHIFT. We can, however, deduce the look-ahead set by -looking at the SHIFT subsets for all states that we can get to by -reducing zero or more times. So we need a little function which -checks if a given token is in any of these look-ahead sets. +If we can neither shift nor reduce we have an error to handle. There +are two possible responses to an error: we can pop single frames off the +stack until we find a frame that can shift `TK_error`, or we can discard +the current look-ahead symbol. -###### parser includes - #include "parser.h" +When we first see an error we do the first of these and set a flag to +record that we are processing an error. If the normal shift/reduce +tests fail to find that anything can be done from that state, we start +dropping tokens until either we manage to shift one, or reach end-of-file. -###### parser_run +###### parser vars - static int in_lookahead(struct token *tk, const struct state *states, int state) - { - while (state >= 0) { - if (search(&states[state], tk->num) >= 0) - return 1; - if (states[state].reduce_prod < 0) - return 0; - state = search(&states[state], states[state].reduce_sym); + int in_err = 0; + +###### did shift + + in_err = 0; + +###### handle error + + if (in_err) { + parser_trace_action(trace, "DISCARD"); + if (tk->num == TK_eof) + break; + free(tk); + tk = NULL; + } else { + struct token *err_tk; + + parser_trace_action(trace, "ERROR"); + + err_tk = tok_copy(*tk); + while (p.tos > 0 && shift(&p, TK_error, err_tk, states) == 0) + // discard this state + pop(&p, 1, do_free); + if (p.tos == 0) { + free(err_tk); + // no state accepted TK_error + break; } - return 0; + in_err = 1; } +###### parser includes + #include "parser.h" + +###### parser_run + void *parser_run(struct token_state *tokens, const struct state states[], int (*do_reduce)(int, void**, struct token_config*, void*), @@ -2812,12 +2826,11 @@ checks if a given token is in any of these look-ahead sets. struct parser p = { 0 }; struct token *tk = NULL; int accepted = 0; - int shift_since_err = 1; void *ret = NULL; + ## parser vars shift(&p, TK_eof, NULL, states); while (!accepted && p.tos > 0) { - struct token *err_tk; struct frame *tos = &p.stack[p.tos-1]; if (!tk) tk = tok_copy(token_next(tokens)); @@ -2851,9 +2864,9 @@ checks if a given token is in any of these look-ahead sets. } } if (shift(&p, tk->num, tk, states)) { - shift_since_err = 1; tk = NULL; parser_trace_action(trace, "Shift"); + ## did shift continue; } @@ -2882,42 +2895,7 @@ checks if a given token is in any of these look-ahead sets. parser_trace_action(trace, "Reduce"); continue; } - /* Error. We walk up the stack until we - * find a state which will accept TK_error. - * We then shift in TK_error and see what state - * that takes us too. - * Then we discard input tokens until - * we find one that is acceptable. - */ - parser_trace_action(trace, "ERROR"); - - err_tk = tok_copy(*tk); - while (p.tos > 0 && - shift(&p, TK_error, err_tk, states) == 0) - // discard this state - pop(&p, 1, do_free); - if (p.tos == 0) { - free(err_tk); - // no state accepted TK_error - break; - } - if (!shift_since_err) { - /* must discard at least one token to avoid - * infinite loop. - */ - if (tk->num == TK_eof) - break; - free(tk); - tk = tok_copy(token_next(tokens)); - } - shift_since_err = 0; - tos = &p.stack[p.tos-1]; - while (!in_lookahead(tk, states, tos->state) && - tk->num != TK_eof) { - free(tk); - tk = tok_copy(token_next(tokens)); - shift_since_err = 1; - } + ## handle error } free(tk); pop(&p, p.tos, do_free); -- 2.43.0