X-Git-Url: https://ocean-lang.org/code/?a=blobdiff_plain;f=csrc%2Fparsergen.mdc;h=cfaa5c4124ac811ec67b974dac3ebb1e66dc1c71;hb=31e612afbcfc44551903dc7696d7b54a2f27bc94;hp=082cf117cb1abf8e2e3d50fcc89c6a806502ee71;hpb=88cce7361c69636161470a84dbfb42fb723f4c07;p=ocean diff --git a/csrc/parsergen.mdc b/csrc/parsergen.mdc index 082cf11..cfaa5c4 100644 --- a/csrc/parsergen.mdc +++ b/csrc/parsergen.mdc @@ -1503,8 +1503,8 @@ all the tables that have been generated, plus a description of any conflicts. Firstly we have the complete list of symbols, together with the "FIRST" set if that was generated. We add a mark to each symbol to -show if it can end in a newline (`>`), if it implies the start of a -line (`<`), or if it is nullable (`.`). +show if it can end in a newline (`>`), if it is considered to be +"line-like" (`<`), or if it is nullable (`.`). ###### functions @@ -2437,21 +2437,23 @@ 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`. -The `indents` count and the `starts_indented` flag track the line -indents in the symbol. These are used to allow indent information to +The `indents` count tracks the line indents with in the symbol or +immediately follow it. These are used to allow indent information to guide parsing and error recovery. `since_newline` tracks how many stack frames since the last start-of-line (whether indented or not). So if `since_newline` is -zero, then this symbol is at the start of a line. +zero, then this symbol is at the start of a line. Similarly +`since_indent` counts the number of states since an indent, it is zero +precisely when `indents` is not zero. `newline_permitted` keeps track of whether newlines should be ignored -or not, and `starts_line` records if this state stated on a newline. +or not. The stack is most properly seen as alternating states and symbols - states, like the 'DOT' in items, are between symbols. Each frame in our stack holds a state and the symbol that was before it. The -bottom of stack holds the start state, but no symbol, as nothing came +bottom of stack holds the start state but no symbol, as nothing came before the beginning. ###### parser functions @@ -2462,7 +2464,6 @@ before the beginning. short newline_permitted; short sym; - short starts_indented; short indents; short since_newline; short since_indent; @@ -2476,12 +2477,15 @@ before the beginning. Two operations are needed on the stack - shift (which is like push) and pop. -Shift applies not only to terminals but also to non-terminals. When we -reduce a production we will pop off entries corresponding to the body -symbols, then push on an item for the head of the production. This last is -exactly the same process as shifting in a terminal so we use the same -function for both. In both cases we provide a stack frame which -contains the symbol to shift and related indent information. +Shift applies not only to terminals but also to non-terminals. When +we reduce a production we will pop off entries corresponding to the +body symbols, then push on an item for the head of the production. +This last is exactly the same process as shifting in a terminal so we +use the same function for both. In both cases we provide the symbol, +the number of indents the symbol contains (which will be zero for a +terminal symbol) and a flag indicating the the symbol was at (or was +reduced from a symbol which was at) the start of a line. The state is +deduced from the current top-of-stack state and the new symbol. To simplify other code we arrange for `shift` to fail if there is no `goto` state for the symbol. This is useful in basic parsing due to our design @@ -2491,28 +2495,26 @@ function reports if it could. `shift` is also used to push state zero onto the stack, so if the stack is empty, it always chooses zero as the next state. -So `shift` finds the next state. If that succeed it extends the allocations -if needed and pushes all the information onto the stacks. +So `shift` finds the next state. If that succeeds it extends the +allocations if needed and pushes all the information onto the stacks. -Newlines are permitted after a starts_line state until an internal -indent. So we need to find the topmost state which `starts_line` and -see if there are any indents other than immediately after it. - -So we walk down: - -- if state starts_line, then newlines_permitted. -- if any non-initial indents, newlines not permitted +Newlines are permitted after a `starts_line` state until an internal +indent. If the new frame has neither a `starts_line` state nor an +indent, newlines are permitted if the previous stack frame permitted +them. ###### parser functions - static int shift(struct parser *p, struct frame *next, + static int shift(struct parser *p, + short sym, short indents, short start_of_line, void *asn, const struct state states[]) { // Push an entry onto the stack + struct frame next = {0}; int newstate = p->tos ? search(&states[p->stack[p->tos-1].state], - next->sym) + sym) : 0; if (newstate < 0) return 0; @@ -2523,31 +2525,33 @@ So we walk down: p->asn_stack = realloc(p->asn_stack, p->stack_size * sizeof(p->asn_stack[0])); } - next->state = newstate; + next.sym = sym; + next.indents = indents; + next.state = newstate; if (states[newstate].starts_line) - next->newline_permitted = 1; - else if (next->indents) - next->newline_permitted = 0; + next.newline_permitted = 1; + else if (indents) + next.newline_permitted = 0; else if (p->tos) - next->newline_permitted = + next.newline_permitted = p->stack[p->tos-1].newline_permitted; else - next->newline_permitted = 0; + next.newline_permitted = 0; - if (next->since_newline) { + if (!start_of_line) { if (p->tos) - next->since_newline = p->stack[p->tos-1].since_newline + 1; + next.since_newline = p->stack[p->tos-1].since_newline + 1; else - next->since_newline = 1; + next.since_newline = 1; } - if (next->indents) - next->since_indent = 0; + if (indents) + next.since_indent = 0; else if (p->tos) - next->since_indent = p->stack[p->tos-1].since_indent + 1; + next.since_indent = p->stack[p->tos-1].since_indent + 1; else - next->since_indent = 1; + next.since_indent = 1; - p->stack[p->tos] = *next; + p->stack[p->tos] = next; p->asn_stack[p->tos] = asn; p->tos++; return 1; @@ -2555,29 +2559,30 @@ So we walk down: `pop` primarily moves the top of stack (`tos`) back down the required amount and frees any `asn` entries that need to be freed. It also -collects a summary of the indents in the symbols that are being -removed. It is called _after_ we reduce a production, just before we -`shift` the nonterminal in. - -`pop` is only called if there are entries to remove, so `num` is never zero. +collects a summary of the indents and line starts in the symbols that +are being removed. It is called _after_ we reduce a production, just +before we `shift` the nonterminal in. ###### parser functions - static void pop(struct parser *p, int num, struct frame *next, - void(*do_free)(short sym, void *asn)) + static int pop(struct parser *p, int num, + short *start_of_line, + void(*do_free)(short sym, void *asn)) { int i; + short indents = 0; + int sol = 0; + p->tos -= num; - next->starts_indented = - p->stack[p->tos].starts_indented; - next->since_newline = - p->stack[p->tos].since_newline; - next->indents = 0; for (i = 0; i < num; i++) { - next->indents += p->stack[p->tos+i].indents; + sol |= !p->stack[p->tos+i].since_newline; + indents += p->stack[p->tos+i].indents; do_free(p->stack[p->tos+i].sym, p->asn_stack[p->tos+i]); } + if (start_of_line) + *start_of_line = sol; + return indents; } ### Memory allocation @@ -2611,9 +2616,9 @@ copying, hence `memdup` and `tokcopy`. ### The heart of the parser. -Now we have the parser. If we can shift, we do, though newlines and -reducing indenting may block that. If not and we can reduce we do. -If the production we reduced was production zero, then we have +Now we have the parser. If we can shift we do, though newlines and +reducing indenting may block that. If not and we can reduce we do +that. If the production we reduced was production zero, then we have accepted the input and can finish. We return whatever `asn` was returned by reducing production zero. @@ -2626,16 +2631,23 @@ 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. -`TK_in` tokens are easy: we simply update the `next` stack frame to -record how many indents there are and that the next token started with -an indent. +`TK_in` tokens are easy: we simply update indent count in the top stack frame to +record how many indents there are following the previous token. -`TK_out` tokens must either be counted off against any pending indent, -or must force reductions until there is a pending indent which isn't -at the start of a production. +`TK_out` tokens must either be canceled against an indent count +within the stack. If we can reduce some symbols that are all since +the most recent indent, then we do that first. If the minimum prefix +of the current state then extents back before the most recent indent, +that indent can be cancelled. If the minimum prefix is shorter then +the indent is premature and we must start error handling, which +currently doesn't work at all. -`TK_newline` tokens are ignored precisely if there has been an indent -since the last state which could have been at the start of a line. +`TK_newline` tokens are ignored unless the top stack frame records +that they are permitted. In that case they will not be considered for +shifting if it is possible to reduce some symbols that are all since +the most recent start of line. This is how a newline forcible +terminates any line-like structure - we try to reduce down to at most +one symbol for each line where newlines are allowed. ###### parser includes #include "parser.h" @@ -2648,30 +2660,31 @@ since the last state which could have been at the start of a line. struct token_config *config) { struct parser p = { 0 }; - struct frame next = { 0 }; struct token *tk = NULL; int accepted = 0; void *ret = NULL; - shift(&p, &next, NULL, states); + shift(&p, TK_eof, 0, 1, NULL, states); while (!accepted) { struct token *err_tk; struct frame *tos = &p.stack[p.tos-1]; if (!tk) tk = tok_copy(token_next(tokens)); - next.sym = tk->num; - parser_trace(trace, &p, &next, tk, states, non_term, config->known_count); - - if (next.sym == TK_in) { - next.starts_indented = 1; - next.indents = 1; - next.since_newline = 0; + parser_trace(trace, &p, + tk, states, non_term, config->known_count); + + if (tk->num == TK_in) { + tos->indents += 1; + tos->since_newline = 0; + tos->since_indent = 0; + if (!states[tos->state].starts_line) + tos->newline_permitted = 0; free(tk); tk = NULL; parser_trace_action(trace, "Record"); continue; } - if (next.sym == TK_out) { + if (tk->num == TK_out) { if (states[tos->state].reduce_size >= 0 && states[tos->state].reduce_size <= tos->since_indent) goto force_reduce; @@ -2689,7 +2702,7 @@ since the last state which could have been at the start of a line. in->newline_permitted = 0; } if (states[in->state].starts_line) - in->newline_permitted = 0; + in->newline_permitted = 1; while (in < tos) { in += 1; in->since_indent = in[-1].since_indent + 1; @@ -2707,21 +2720,19 @@ since the last state which could have been at the start of a line. // fall through and force a REDUCE (as 'shift' // will fail). } - if (next.sym == TK_newline) { + if (tk->num == TK_newline) { if (!tos->newline_permitted) { free(tk); tk = NULL; parser_trace_action(trace, "Discard"); continue; } - if (states[tos->state].reduce_size > 0 && - states[tos->state].reduce_size < tos->since_newline) + if (tos->since_newline > 1 && + states[tos->state].reduce_size >= 0 && + states[tos->state].reduce_size <= tos->since_newline) goto force_reduce; } - if (shift(&p, &next, tk, states)) { - next.since_newline = !(tk->num == TK_newline); - next.starts_indented = 0; - next.indents = 0; + if (shift(&p, tk->num, 0, tk->num == TK_newline, tk, states)) { tk = NULL; parser_trace_action(trace, "Shift"); continue; @@ -2735,25 +2746,19 @@ since the last state which could have been at the start of a line. int size = nextstate->reduce_size; int bufsize; static char buf[16*1024]; - struct frame frame; - frame.sym = nextstate->reduce_sym; + short indents, start_of_line; body = p.asn_stack + (p.tos - size); bufsize = do_reduce(prod, body, config, buf); - if (size) - pop(&p, size, &frame, do_free); - else { - frame.indents = next.indents; - frame.starts_indented = frame.indents; - frame.since_newline = 1; - next.indents = 0; - next.starts_indented = 0; - } + indents = pop(&p, size, &start_of_line, + do_free); res = memdup(buf, bufsize); memset(buf, 0, bufsize); - if (!shift(&p, &frame, res, states)) { + if (!shift(&p, nextstate->reduce_sym, + indents, start_of_line, + res, states)) { if (prod != 0) abort(); accepted = 1; ret = res; @@ -2764,11 +2769,9 @@ since the last state which could have been at the start of a line. if (tk->num == TK_out) { // Indent problem - synthesise tokens to get us // out of here. - struct frame frame = { 0 }; fprintf(stderr, "Synthesize %d to handle indent problem\n", states[tos->state].shift_sym); - frame.sym = states[tos->state].shift_sym; - frame.since_newline = 1; - shift(&p, &frame, tok_copy(*tk), states); + shift(&p, states[tos->state].shift_sym, + 0, 1, tok_copy(*tk), states); // FIXME need to report this error somehow parser_trace_action(trace, "Synthesize"); continue; @@ -2781,13 +2784,14 @@ since the last state which could have been at the start of a line. * we find one that is acceptable. */ parser_trace_action(trace, "ERROR"); + short indents = 0, start_of_line; err_tk = tok_copy(*tk); - next.sym = TK_error; - while (shift(&p, &next, err_tk, states) == 0 + while (shift(&p, TK_error, 0, 0, + err_tk, states) == 0 && p.tos > 0) // discard this state - pop(&p, 1, &next, do_free); + indents += pop(&p, 1, &start_of_line, do_free); if (p.tos == 0) { free(err_tk); // no state accepted TK_error @@ -2799,20 +2803,21 @@ since the last state which could have been at the start of a line. free(tk); tk = tok_copy(token_next(tokens)); if (tk->num == TK_in) - next.indents += 1; + indents += 1; if (tk->num == TK_out) { - if (next.indents == 0) + if (indents == 0) break; - next.indents -= 1; + indents -= 1; // FIXME update since_indent here } } if (p.tos == 0 && tk->num == TK_eof) break; + tos = &p.stack[p.tos-1]; + tos->indents += indents; } free(tk); - if (p.tos) - pop(&p, p.tos, &next, do_free); + pop(&p, p.tos, NULL, do_free); free(p.asn_stack); free(p.stack); return ret; @@ -2858,11 +2863,11 @@ end inside square brackets. if (states[f->state].starts_line) fprintf(trace, "s"); if (f->newline_permitted) - fprintf(trace, "n%d", f->newline_permitted); + fprintf(trace, "n%d", f->since_newline); fprintf(trace, ") "); } - void parser_trace(FILE *trace, struct parser *p, struct frame *n, + void parser_trace(FILE *trace, struct parser *p, struct token *tk, const struct state states[], const char *non_term[], int knowns) { @@ -2883,8 +2888,7 @@ end inside square brackets. fputs(non_term[sym - TK_reserved - knowns], trace); if (f->indents) - fprintf(trace, "%c%d", f->starts_indented?':':'.', - f->indents); + fprintf(trace, ".%d", f->indents); if (f->since_newline == 0) fputs("/", trace); fputs(" ", trace); @@ -2897,11 +2901,6 @@ end inside square brackets. fputs(reserved_words[tk->num], trace); else text_dump(trace, tk->txt, 20); - if (n->indents) - fprintf(trace, "%c%d", n->starts_indented?':':'.', - n->indents); - if (n->since_newline == 0) - fputs("/", trace); fputs("]", trace); }