X-Git-Url: https://ocean-lang.org/code/?p=ocean;a=blobdiff_plain;f=csrc%2Fparsergen.mdc;h=d2ff89844d2e616e0f10e470c0a7dbffde9492a7;hp=bc1a604d3a8d696bb666d4262c735740b3648d92;hb=5281589bf4d9a66ce106b160e1272f1c51d7ac15;hpb=25d7f048bbeb8611842b67eb011e7af87b6b4dc0 diff --git a/csrc/parsergen.mdc b/csrc/parsergen.mdc index bc1a604..d2ff898 100644 --- a/csrc/parsergen.mdc +++ b/csrc/parsergen.mdc @@ -21,7 +21,6 @@ There are several distinct sections. `parsergen` program built from the C code in this file can extract that grammar directly from this file and process it. - ###### File: parsergen.c #include #include @@ -839,7 +838,6 @@ array like the productions. return sl->ss; } - ### Setting `nullable` We set `nullable` on the head symbol for any production for which all @@ -877,7 +875,7 @@ changes happen. } } -### Setting `can_eol` and `line_like` +### 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 @@ -885,30 +883,25 @@ 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. -To know which symbols are line-like, we first need to know which -symbols start with a NEWLINE token. Any symbol which is followed by a -NEWLINE, or anything that starts with a NEWLINE, is deemed to be a line-like symbol. -Certainly when trying to parse one of these we must take note of NEWLINEs. - -Clearly the `TK_newline` token can start with a NEWLINE. Any symbol -which is the head of a production that contains a starts-with-NEWLINE -symbol preceeded only by nullable symbols is also a -starts-with-NEWLINE symbol. We use a new field `can_eol` to record -this attribute of symbols, and compute it in a repetitive manner -similar to `set_nullable`. +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. -Once we have that, we can determine which symbols are `line_like` by -seeing which are followed by a `can_eol` symbol in any production. +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 can_eol; int line_like; ###### functions - static void set_can_eol(struct grammar *g) + static void set_line_like(struct grammar *g) { int check_again = 1; - g->symtab[TK_newline]->can_eol = 1; + g->symtab[TK_newline]->line_like = 1; while (check_again) { int p; check_again = 0; @@ -916,35 +909,20 @@ seeing which are followed by a `can_eol` symbol in any production. struct production *pr = g->productions[p]; int s; - if (pr->head->can_eol) + if (pr->head->line_like) continue; for (s = 0 ; s < pr->body_size; s++) { - if (pr->body[s]->can_eol) { - pr->head->can_eol = 1; + if (pr->body[s]->line_like) { + pr->head->line_like = 1; check_again = 1; break; } - if (!pr->body[s]->nullable) - break; } } } } - static void set_line_like(struct grammar *g) - { - int p; - for (p = 0; p < g->production_count; p++) { - struct production *pr = g->productions[p]; - int s; - - for (s = 1; s < pr->body_size; s++) - if (pr->body[s]->can_eol) - pr->body[s-1]->line_like = 1; - } - } - ### Building the `first` sets When calculating what can follow a particular non-terminal, we will need to @@ -1180,9 +1158,10 @@ 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. +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 where production in the +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 @@ -1301,7 +1280,7 @@ be supplemented by the LA set for the item which produce 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 starting a line, then this +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. When itemsets are created we assign a precedence to the itemset from @@ -1532,7 +1511,6 @@ changeover point in `first_nonterm`. g->symtab[s->num] = s; set_nullable(g); - set_can_eol(g); set_line_like(g); if (type >= SLR) build_first(g); @@ -1583,9 +1561,8 @@ show if it can end in a newline (`>`), if it is considered to be if (!s) continue; - printf(" %c%c%c%3d%c: ", + printf(" %c%c%3d%c: ", s->nullable ? '.':' ', - s->can_eol ? '>':' ', s->line_like ? '<':' ', s->num, symtypes[s->type]); prtxt(s->name); @@ -1679,7 +1656,6 @@ The LA sets which are (possibly) reported with each item: Then the go to sets: - static void report_goto(struct grammar *g, struct symset gt) { int i; @@ -1796,6 +1772,15 @@ terminals to items where that terminal could be shifted and another which maps terminals to items that could be reduced when the terminal is in look-ahead. We report when we get conflicts between the two. +As a special case, if we find a SHIFT/REDUCE conflict, where a +terminal that could be shifted is in the lookahead set of some +reducable item, then set check if the reducable item also have +`TK_newline` in its lookahead set. If it does, then a newline will +force the reduction, but anything else can reasonably be shifted, so +that isn't really a conflict. Such apparent conflicts do not get +counted, and are reported as non-critical. This will not affect a +"traditional" grammar that does not include newlines as token. + static int conflicts_slr(struct grammar *g, enum grammar_type type) { int i; @@ -1823,7 +1808,7 @@ is in look-ahead. We report when we get conflicts between the two. symset_add(&shifts, sym, itm); } } - /* Now look for reduction and conflicts */ + /* Now look for reductions and conflicts */ for (j = 0; j < is->items.cnt; j++) { unsigned short itm = is->items.syms[j]; int p = item_prod(itm); @@ -1842,12 +1827,15 @@ is in look-ahead. We report when we get conflicts between the two. for (k = 0; k < la.cnt; k++) { int pos = symset_find(&shifts, la.syms[k]); if (pos >= 0) { - printf(" State %d has SHIFT/REDUCE conflict on ", i); + if (symset_find(&la, TK_newline) < 0) { + printf(" State %d has SHIFT/REDUCE conflict on ", i); + cnt++; + } else + printf(" State %d has non-critical SHIFT/REDUCE conflict on ", i); prtxt(g->symtab[la.syms[k]]->name); printf(":\n"); report_item(g, shifts.data[pos]); report_item(g, itm); - cnt++; } pos = symset_find(&reduce, la.syms[k]); if (pos < 0) { @@ -1868,7 +1856,6 @@ is in look-ahead. We report when we get conflicts between the two. return cnt; } - ## Generating the parser The exported part of the parser is the `parse_XX` function, where the name @@ -1885,13 +1872,14 @@ pieces of code provided in the grammar file, so they are generated first. ###### parser_generate - static void gen_parser(FILE *f, struct grammar *g, char *file, char *name) + static void gen_parser(FILE *f, struct grammar *g, char *file, char *name, + struct code_node *pre_reduce) { gen_known(f, g); gen_non_term(f, g); gen_goto(f, g); gen_states(f, g); - gen_reduce(f, g, file); + gen_reduce(f, g, file, pre_reduce); gen_free(f, g); fprintf(f, "#line 0 \"gen_parser\"\n"); @@ -1912,7 +1900,9 @@ pieces of code provided in the grammar file, so they are generated first. ### Known words table The known words table is simply an array of terminal symbols. -The table of nonterminals used for tracing is a similar array. +The table of nonterminals used for tracing is a similar array. We +include virtual symbols in the table of non_terminals to keep the +numbers right. ###### functions @@ -1937,7 +1927,7 @@ The table of nonterminals used for tracing is a similar array. for (i = TK_reserved; i < g->num_syms; i++) - if (g->symtab[i]->type == Nonterminal) + if (g->symtab[i]->type != Terminal) fprintf(f, "\t\"%.*s\",\n", g->symtab[i]->name.len, g->symtab[i]->name.txt); fprintf(f, "};\n\n"); @@ -1971,7 +1961,6 @@ The go to table is stored in a simple array of `sym` and corresponding short min_prefix; }; - ###### functions static void gen_goto(FILE *f, struct grammar *g) @@ -2126,14 +2115,18 @@ automatically freed. This is equivalent to assigning `NULL` to the pointer. ###### functions - static void gen_reduce(FILE *f, struct grammar *g, char *file) + static void gen_reduce(FILE *f, struct grammar *g, char *file, + struct code_node *code) { int i; - fprintf(f, "#line 0 \"gen_reduce\"\n"); + 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); + fprintf(f, "#line 4 \"gen_reduce\"\n"); fprintf(f, "\tswitch(prod) {\n"); for (i = 0; i < g->production_count; i++) { struct production *p = g->productions[i]; @@ -2330,6 +2323,7 @@ parser with neither. "grammar" must be provided. struct code_node *hdr = NULL; struct code_node *code = NULL; struct code_node *gram = NULL; + struct code_node *pre_reduce = NULL; for (s = table; s; s = s->next) { struct text sec = s->section; if (tag && !strip_tag(&sec, tag)) @@ -2340,6 +2334,8 @@ parser with neither. "grammar" must be provided. code = s->code; else if (text_is(sec, "grammar")) gram = s->code; + else if (text_is(sec, "reduce")) + pre_reduce = s->code; else { fprintf(stderr, "Unknown content section: %.*s\n", s->section.len, s->section.txt); @@ -2411,7 +2407,7 @@ file with the code section (if any) and the parser tables and function. if (f) { if (code) code_node_print(f, code, infile); - gen_parser(f, g, infile, name); + gen_parser(f, g, infile, name, pre_reduce); fclose(f); } else { fprintf(stderr, "Cannot create %s.c\n", @@ -2709,9 +2705,29 @@ is still a work-in-progress. `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 +the most recent start of line. This is how a newline forcibly terminates any line-like structure - we try to reduce down to at most one symbol for each line where newlines are allowed. +A consequence of this is that a rule like + +###### Example: newlines - broken + + Newlines -> + | NEWLINE Newlines + IfStatement -> Newlines if .... + +cannot work, as the NEWLINE will never be shifted as the empty string +will be reduced first. Optional sets of newlines need to be include +in the thing that preceed: + +###### Example: newlines - works + + If -> if + | NEWLINE If + IfStatement -> If .... + +Here the NEWLINE will be shifted because nothing can be reduced until +the `if` is seen. When, during error handling, we discard token read in, we want to keep discarding until we see one that is recognised. If we had a full set @@ -3000,6 +3016,9 @@ an error. ./parsergen --tag calc -o calc parsergen.mdc calc : calc.o libparser.o libscanner.o libmdcode.o libnumber.o $(CC) $(CFLAGS) -o calc calc.o libparser.o libscanner.o libmdcode.o libnumber.o -licuuc -lgmp + calctest : calc + ./calc parsergen.mdc + demos :: calctest # calc: header @@ -3020,6 +3039,7 @@ an error. #include #include #include + #include #include "mdcode.h" #include "scanner.h" #include "number.h" @@ -3033,12 +3053,19 @@ an error. free(n); } + static int text_is(struct text t, char *s) + { + return (strlen(s) == t.len && + strncmp(s, t.txt, t.len) == 0); + } + int main(int argc, char *argv[]) { int fd = open(argv[1], O_RDONLY); int len = lseek(fd, 0, 2); char *file = mmap(NULL, len, PROT_READ, MAP_SHARED, fd, 0); - struct section *s = code_extract(file, file+len, NULL); + struct section *table = code_extract(file, file+len, NULL); + struct section *s; struct token_config config = { .ignored = (1 << TK_line_comment) | (1 << TK_block_comment) @@ -3048,12 +3075,14 @@ an error. .word_start = "", .word_cont = "", }; - parse_calc(s->code, &config, argc > 2 ? stderr : NULL); - while (s) { - struct section *t = s->next; - code_free(s->code); - free(s); - s = t; + for (s = table; s; s = s->next) + if (text_is(s->section, "example: input")) + parse_calc(s->code, &config, argc > 2 ? stderr : NULL); + while (table) { + struct section *t = table->next; + code_free(table->code); + free(table); + table = t; } exit(0); } @@ -3091,3 +3120,14 @@ an error. | Expression / Expression ${ mpq_init($0.val); mpq_div($0.val, $1.val, $3.val); }$ | NUMBER ${ if (number_parse($0.val, $0.tail, $1.txt) == 0) mpq_init($0.val); }$ | ( Expression ) ${ mpq_init($0.val); mpq_set($0.val, $2.val); }$ + +# example: input + + 355/113 + 3.1415926535 - 355/113 + 2 + 4 * 5 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 * 9 / 2 + 1 * 1000 + 2 * 100 + 3 * 10 + 4 * 1 + + error