X-Git-Url: https://ocean-lang.org/code/?a=blobdiff_plain;ds=sidebyside;f=csrc%2Fparsergen.mdc;h=106f5f3e9f070717aac525d7a521ee159e2fb8ac;hb=9fa5048ff0bf3fda557fcefad9a9966974d10ff5;hp=9156c63041121d0ef1f0e34bc7b45932967128b8;hpb=795dc527884643585eefc9bfe2d3a5f4b2ad7376;p=ocean diff --git a/csrc/parsergen.mdc b/csrc/parsergen.mdc index 9156c63..106f5f3 100644 --- a/csrc/parsergen.mdc +++ b/csrc/parsergen.mdc @@ -105,7 +105,6 @@ symbol. struct production { unsigned short precedence; enum assoc assoc; - char line_like; ## production fields }; struct grammar { @@ -527,11 +526,7 @@ Now we have all the bits we need to parse a full production. goto abort; } vs = sym_find(g, tk.txt); - if (vs->num == TK_newline) - p.line_like = 1; - else if (vs->num == TK_out) - p.line_like = 2; - else if (vs->precedence == 0) { + if (vs->precedence == 0) { err = "symbol after $$ must have precedence"; goto abort; } else { @@ -940,54 +935,6 @@ changes happen. } } -### Setting `line_like` - -In order to be able to ignore newline tokens when not relevant, but -still include them in the parse when needed, we will need to know -which states can start a "line-like" section of code. We ignore -newlines when there is an indent since the most recent start of a -line-like symbol. - -A "line_like" symbol is simply any symbol that can derive a NEWLINE. -If a symbol cannot derive a NEWLINE, then it is only part of a line - -so is word-like. If it can derive a NEWLINE, then we consider it to -be like a line. - -Clearly the `TK_newline` token can derive a NEWLINE. Any symbol which -is the head of a production that contains a line_like symbol is also a -line-like symbol. We use a new field `line_like` to record this -attribute of symbols, and compute it in a repetitive manner similar to -`set_nullable`. - -###### symbol fields - int line_like; - -###### functions - static void set_line_like(struct grammar *g) - { - int check_again = 1; - g->symtab[TK_newline]->line_like = 1; - while (check_again) { - int p; - check_again = 0; - for (p = 0; p < g->production_count; p++) { - struct production *pr = g->productions[p]; - int s; - - if (pr->head->line_like) - continue; - - for (s = 0 ; s < pr->body_size; s++) { - if (pr->body[s]->line_like) { - pr->head->line_like = 1; - check_again = 1; - break; - } - } - } - } - } - ### Building the `first` sets When calculating what can follow a particular non-terminal, we will need @@ -1230,22 +1177,6 @@ particularly for LALR where itemsets get merged, at which point they need to be consider for completion again. So a `completed` flag is needed. -For correct handling of `TK_newline` when parsing, we will need to -know which states (itemsets) can occur at the start of a line, so we -will record a `starts_line` flag too whenever DOT is at the start of a -`line_like` symbol. - -Finally, for handling `TK_out` we need to know whether productions in the -current state started *before* the most recent indent. A state -doesn't usually keep details of individual productions, so we need to -add one extra detail. `min_prefix` is the smallest non-zero number of -symbols *before* DOT in any production in an itemset. This will allow -us to determine if the the most recent indent is sufficiently recent -to cancel it against a `TK_out`. If it was seen longer ago than the -`min_prefix`, and if the current state cannot be reduced, then the -indented section must have ended in the middle of a syntactic unit, so -an error must be signaled. - And now we can build the list of itemsets. The lookup routine returns both a success flag and a pointer to where in the list an insert should happen, so we don't need to search a second time. @@ -1259,8 +1190,6 @@ happen, so we don't need to search a second time. enum assoc assoc; unsigned short precedence; char completed; - char starts_line; - int min_prefix; }; ###### grammar fields @@ -1357,9 +1286,7 @@ may be supplemented by the LA set for the item which produced the new item. We also collect a set of all symbols which follow "DOT" (in `done`) as -this is used in the next stage. If any of these symbols are flagged as -`line_like`, then this state must be a `starts_line` state so now is a -good time to record that. +this is used in the next stage. When itemsets are created we assign a precedence to the itemset from the complete item, if there is one. We ignore the possibility of there @@ -1380,12 +1307,7 @@ so the item is ineffective. struct symbol *s; struct symset LA = INIT_SYMSET; unsigned short sn = 0; - struct symset LAnl = INIT_SYMSET; - unsigned short snnl = 0; - if (is->min_prefix == 0 || - (bs > 0 && bs < is->min_prefix)) - is->min_prefix = bs; if (bs == pr->body_size) continue; s = pr->body[bs]; @@ -1401,13 +1323,11 @@ so the item is ineffective. * not Right-associative, so we mustn't shift it. */ continue; - if (symset_find(&done, s->num) < 0) { + if (symset_find(&done, s->num) < 0) symset_add(&done, s->num, 0); - } + if (s->type != Nonterminal) continue; - if (s->line_like) - is->starts_line = 1; check_again = 1; if (type >= LALR) { // Need the LA set. @@ -1419,10 +1339,6 @@ so the item is ineffective. } sn = save_set(g, LA); LA = set_find(g, sn); - if (symset_find(&LA, TK_newline)) - symset_add(&LAnl, TK_newline, 0); - snnl = save_set(g, LAnl); - LAnl = set_find(g, snnl); } /* Add productions for this symbol */ @@ -1433,10 +1349,7 @@ so the item is ineffective. int itm = item_num(p2, 0); int pos = symset_find(&is->items, itm); if (pos < 0) { - if (g->productions[p2]->line_like) - symset_add(&is->items, itm, snnl); - else - symset_add(&is->items, itm, sn); + symset_add(&is->items, itm, sn); /* Will have re-ordered, so start * from beginning again */ i = -1; @@ -1445,8 +1358,6 @@ so the item is ineffective. struct symset tmp = INIT_SYMSET; struct symset *la = &LA; - if (g->productions[p2]->line_like) - la = &LAnl; symset_union(&tmp, &ss); if (symset_union(&tmp, la)) { is->items.data[pos] = save_set(g, tmp); @@ -1488,18 +1399,21 @@ itemsets (or merged with a pre-existing itemset). continue; if (pr->body[bp] != sym) continue; + + bp += 1; if (type >= LALR) la = is->items.data[j]; - pos = symset_find(&newitemset, pr->head->num); - if (bp + 1 == pr->body_size && + if (bp == pr->body_size && pr->precedence > 0 && pr->precedence > precedence) { // new itemset is reducible and has a precedence. precedence = pr->precedence; assoc = pr->assoc; } + pos = symset_find(&newitemset, item_num(p, bp)); + if (pos < 0) - symset_add(&newitemset, item_num(p, bp+1), la); + symset_add(&newitemset, item_num(p, bp), la); else if (type >= LALR) { // Need to merge la set. int la2 = newitemset.data[pos]; @@ -1604,7 +1518,6 @@ and we record the changeover point in `first_nonterm`. g->symtab[s->num] = s; set_nullable(g); - set_line_like(g); if (type >= SLR) build_first(g); @@ -1636,7 +1549,7 @@ 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 is considered to be "line-like" (`<`), or if it is nullable (`.`). +show if it is nullable (`.`). ###### functions @@ -1653,9 +1566,8 @@ show if it is considered to be "line-like" (`<`), or if it is nullable (`.`). if (!s) continue; - printf(" %c%c%3d%c: ", + printf(" %c%3d%c: ", s->nullable ? '.':' ', - s->line_like ? '<':' ', s->num, symtypes[s->type]); prtxt(s->name); if (s->precedence) @@ -1726,10 +1638,6 @@ it up a bit. First the items, with production number and associativity. printf(" [%d%s]", s->precedence, assoc_names[s->assoc]); } - if (pr->line_like == 1) - printf(" $$NEWLINE"); - else if (pr->line_like) - printf(" $$OUT"); printf("\n"); } @@ -1773,8 +1681,7 @@ Now we can report all the item sets complete with items, LA sets, and GO TO. for (s = 0; s < g->states; s++) { int j; struct itemset *is = g->statetab[s]; - printf(" Itemset %d:%s min prefix=%d", - s, is->starts_line?" (startsline)":"", is->min_prefix); + printf(" Itemset %d:", s); if (is->precedence) printf(" %d%s", is->precedence, assoc_names[is->assoc]); printf("\n"); @@ -2050,9 +1957,8 @@ The go to table is stored in a simple array of `sym` and corresponding short reduce_prod; short reduce_size; short reduce_sym; - char starts_line; char newline_only; - short min_prefix; + short result_size; }; ###### functions @@ -2062,10 +1968,13 @@ The go to table is stored in a simple array of `sym` and corresponding int i; fprintf(f, "#line 0 \"gen_goto\"\n"); for (i = 0; i < g->states; i++) { + struct symset gt = g->statetab[i]->go_to; int j; + + if (gt.cnt == 0) + continue; fprintf(f, "static const struct lookup goto_%d[] = {\n", i); - struct symset gt = g->statetab[i]->go_to; for (j = 0; j < gt.cnt; j++) fprintf(f, "\t{ %d, %d },\n", gt.syms[j], gt.data[j]); @@ -2096,19 +2005,25 @@ The go to table is stored in a simple array of `sym` and corresponding prod_len = pr->body_size; } } - - if (prod >= 0) - fprintf(f, "\t[%d] = { %d, goto_%d, %d, %d, %d, %d, %d, %d },\n", - i, is->go_to.cnt, i, prod, - g->productions[prod]->body_size, - g->productions[prod]->head->num, - is->starts_line, - g->productions[prod]->line_like, - is->min_prefix); + if (is->go_to.cnt) + fprintf(f, "\t[%d] = { %d, goto_%d, ", + i, is->go_to.cnt, i); else - fprintf(f, "\t[%d] = { %d, goto_%d, -1, -1, -1, %d, 0, %d },\n", - i, is->go_to.cnt, i, - is->starts_line, is->min_prefix); + fprintf(f, "\t[%d] = { 0, NULL, ", i); + if (prod >= 0) { + struct production *pr = g->productions[prod]; + struct symbol *hd = pr->head; + fprintf(f, "%d, %d, %d, ", + prod, pr->body_size, pr->head->num); + if (hd->struct_name.txt == NULL) + fprintf(f, "0 },\n"); + else + fprintf(f, "sizeof(struct %.*s%s) },\n", + hd->struct_name.len, + hd->struct_name.txt, + hd->isref ? "*" : ""); + } else + fprintf(f, "-1, -1, -1, -1 },\n"); } fprintf(f, "};\n\n"); } @@ -2204,7 +2119,7 @@ transformed, and will cause an error when the code is compiled. c = *name; } if (namlen == 0) { - if (name == *namep) + if (name == *namep || n > p->body_size) return -1; *namep = name; return n; @@ -2213,8 +2128,10 @@ transformed, and will cause an error when the code is compiled. for (i = 0; i < p->body_size; i++) { if (!subseq_match(nam, namlen, p->body[i]->name)) continue; - if (slen == 0 || p->body[i]->name.len < slen) + if (slen == 0 || p->body[i]->name.len < slen) { s = i; + slen = p->body[i]->name.len; + } if (s >= 0 && p->body[i] != p->body[s] && p->body[i]->name.len == p->body[s]->name.len) /* not unique, so s cannot be used */ @@ -2222,7 +2139,7 @@ transformed, and will cause an error when the code is compiled. } if (s < 0) return -1; - if (n == 0); + if (n == 0) n = 1; for (i = 0; i < p->body_size; i++) if (p->body[i] == p->body[s]) { @@ -2230,7 +2147,7 @@ transformed, and will cause an error when the code is compiled. if (n == 0) break; } - if (n > 1) + if (n > 0 || i == p->body_size) return -1; *namep = name; return i + 1; @@ -2301,15 +2218,15 @@ transformed, and will cause an error when the code is compiled. ###### functions static void gen_reduce(FILE *f, struct grammar *g, char *file, - struct code_node *code) + struct code_node *pre_reduce) { int i; fprintf(f, "#line 1 \"gen_reduce\"\n"); fprintf(f, "static int do_reduce(int prod, void **body, struct token_config *config, void *ret)\n"); fprintf(f, "{\n"); fprintf(f, "\tint ret_size = 0;\n"); - if (code) - code_node_print(f, code, file); + if (pre_reduce) + code_node_print(f, pre_reduce, file); fprintf(f, "#line 4 \"gen_reduce\"\n"); fprintf(f, "\tswitch(prod) {\n"); @@ -2444,7 +2361,7 @@ grammar file). case 't': tag = optarg; break; default: - fprintf(stderr, "Usage: parsergen ...\n"); + fprintf(stderr, "Usage: parsergen -[05SL1R] [-t tag] [-o output] input\n"); exit(1); } } @@ -2663,25 +2580,14 @@ table. ### Memory allocation The `scanner` returns tokens in a local variable - we want them in allocated -memory so they can live in the `asn_stack`. Similarly the `asn` produced by -a reduce is in a large buffer. Both of these require some allocation and -copying, hence `memdup` and `tok_copy`. +memory so they can live in the `asn_stack`. So we provide `tok_copy` to +make an allocated copy as required. ###### parser includes #include ###### parser functions - void *memdup(void *m, int len) - { - void *ret; - if (len == 0) - return NULL; - ret = malloc(len); - memcpy(ret, m, len); - return ret; - } - static struct token *tok_copy(struct token tk) { struct token *new = malloc(sizeof(*new)); @@ -2774,11 +2680,6 @@ stack is empty, it always chooses zero as the next state. 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. 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, @@ -2804,15 +2705,6 @@ them. next.sym = sym; next.indents = indents; next.state = newstate; - if (states[newstate].starts_line) - next.newline_permitted = 1; - else if (indents) - next.newline_permitted = 0; - else if (p->tos) - next.newline_permitted = - p->stack[p->tos-1].newline_permitted; - else - next.newline_permitted = 0; if (!start_of_line) { if (p->tos) @@ -2971,8 +2863,6 @@ checks if a given token is in any of these look-ahead sets. 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"); @@ -2982,7 +2872,7 @@ checks if a given token is in any of these look-ahead sets. if (states[tos->state].reduce_size >= 0 && states[tos->state].reduce_size <= tos->since_indent) goto force_reduce; - if (states[tos->state].min_prefix >= tos->since_indent) { + if (1) { // OK to cancel struct frame *in = tos - tos->since_indent; in->indents -= 1; @@ -2995,15 +2885,9 @@ checks if a given token is in any of these look-ahead sets. in->since_indent = 0; in->newline_permitted = 0; } - if (states[in->state].starts_line) - in->newline_permitted = 1; while (in < tos) { in += 1; in->since_indent = in[-1].since_indent + 1; - if (states[in->state].starts_line) - in->newline_permitted = 1; - else - in->newline_permitted = in[-1].newline_permitted; } } free(tk); @@ -3049,18 +2933,18 @@ checks if a given token is in any of these look-ahead sets. const struct state *nextstate = &states[tos->state]; int prod = nextstate->reduce_prod; int size = nextstate->reduce_size; - int bufsize; - static char buf[16*1024]; + int res_size = nextstate->result_size; short indents, start_of_line; body = p.asn_stack + (p.tos - size); - - bufsize = do_reduce(prod, body, config, buf); + res = res_size ? calloc(1, res_size) : NULL; + res_size = do_reduce(prod, body, config, res); + if (res_size != nextstate->result_size) + abort(); indents = pop(&p, size, &start_of_line, do_free); - res = memdup(buf, bufsize); - memset(buf, 0, bufsize); + if (!shift(&p, nextstate->reduce_sym, indents, start_of_line, res, states)) { @@ -3160,15 +3044,6 @@ end inside square brackets. [TK_newline] = "NEWLINE", [TK_eof] = "$eof", }; - static void parser_trace_state(FILE *trace, struct frame *f, const struct state states[]) - { - fprintf(trace, "(%d", f->state); - if (states[f->state].starts_line) - fprintf(trace, "s"); - if (f->newline_permitted) - fprintf(trace, "n%d", f->since_newline); - fprintf(trace, ") "); - } void parser_trace(FILE *trace, struct parser *p, struct token *tk, const struct state states[], @@ -3196,7 +3071,7 @@ end inside square brackets. fputs("/", trace); fputs(" ", trace); } - parser_trace_state(trace, f, states); + fprintf(trace, "(%d) ", f->state); } fprintf(trace, "["); if (tk->num < TK_reserved &&