X-Git-Url: https://ocean-lang.org/code/?a=blobdiff_plain;f=csrc%2Fparsergen.mdc;h=2da1d65bb7b2f962af024ef6b7d7f20a9e2e1f3e;hb=50371f5f3e4351ab3ab723eb0c292d9702236b2b;hp=cdb5f82204cb670d87d570e96177d52eb1aa5e41;hpb=1e17521c96f4116042cdaf3cf2aac40284f6dec8;p=ocean diff --git a/csrc/parsergen.mdc b/csrc/parsergen.mdc index cdb5f82..2da1d65 100644 --- a/csrc/parsergen.mdc +++ b/csrc/parsergen.mdc @@ -151,11 +151,17 @@ those which don't. There are also "virtual" symbols used for precedence marking discussed later, and sometimes we won't know what type a symbol is yet. +To help with code safety it is possible to declare the terminal symbols. +If this is done, then any symbol used in a production that does not +appear in a head and is not declared is treated as an error. + ###### forward declarations enum symtype { Unknown, Virtual, Terminal, Nonterminal }; char *symtypes = "UVTN"; ###### symbol fields enum symtype type; +###### grammar fields + int terminals_declared; Symbols can be either `TK_ident` or `TK_mark`. They are saved in a table of known symbols and the resulting parser will report them as @@ -163,17 +169,18 @@ table of known symbols and the resulting parser will report them as different token types that `scanner` can report. ###### declarations - static char *reserved_words[] = { - [TK_error] = "ERROR", - [TK_number] = "NUMBER", - [TK_ident] = "IDENTIFIER", - [TK_mark] = "MARK", - [TK_string] = "STRING", - [TK_multi_string] = "MULTI_STRING", - [TK_in] = "IN", - [TK_out] = "OUT", - [TK_newline] = "NEWLINE", - [TK_eof] = "$eof", + + static struct { int num; char *name; } reserved_words[] = { + { TK_error, "ERROR" }, + { TK_number, "NUMBER" }, + { TK_ident, "IDENTIFIER" }, + { TK_mark, "MARK" }, + { TK_string, "STRING" }, + { TK_multi_string, "MULTI_STRING" }, + { TK_in, "IN" }, + { TK_out, "OUT" }, + { TK_newline, "NEWLINE" }, + { TK_eof, "$eof" }, }; ###### symbol fields short num; @@ -229,21 +236,20 @@ symbol, but its type might be `Unknown`. for (i = 0; i < entries; i++) { struct text t; struct symbol *s; - t.txt = reserved_words[i]; - if (!t.txt) - continue; + t.txt = reserved_words[i].name; t.len = strlen(t.txt); s = sym_find(g, t); s->type = Terminal; - s->num = i; + s->num = reserved_words[i].num; } } ### Data types and precedence. -Data type specification and precedence specification are both -introduced by a dollar sign at the start of the line. If the next -word is `LEFT`, `RIGHT` or `NON`, then the line specifies a +Data type specification, precedence specification, and declaration of +terminals are all introduced by a dollar sign at the start of the line. +If the next word is `LEFT`, `RIGHT` or `NON`, then the line specifies a +precedence, if it is `TERM` the the line declares terminals without precedence, otherwise it specifies a data type. The data type name is simply stored and applied to the head of all @@ -296,6 +302,7 @@ Subsequent lines introduce symbols with higher precedence. struct token t = token_next(ts); char *err; enum assoc assoc; + int term = 0; int found; if (t.num != TK_ident) { @@ -308,7 +315,10 @@ Subsequent lines introduce symbols with higher precedence. assoc = Right; else if (text_is(t.txt, "NON")) assoc = Non; - else { + else if (text_is(t.txt, "TERM")) { + term = 1; + g->terminals_declared = 1; + } else { g->current_type = t.txt; g->type_isref = isref; if (text_is(t.txt, "void")) @@ -326,7 +336,7 @@ Subsequent lines introduce symbols with higher precedence. goto abort; } - // This is a precedence line, need some symbols. + // This is a precedence or TERM line, need some symbols. found = 0; g->prec_levels += 1; t = token_next(ts); @@ -340,6 +350,10 @@ Subsequent lines introduce symbols with higher precedence. err = "$$ must be followed by a word"; goto abort; } + if (term) { + err = "Virtual symbols not permitted on $TERM line"; + goto abort; + } } else if (t.num != TK_ident && t.num != TK_mark) { err = "Illegal token in precedence line"; @@ -347,17 +361,19 @@ Subsequent lines introduce symbols with higher precedence. } s = sym_find(g, t.txt); if (s->type != Unknown) { - err = "Symbols in precedence line must not already be known."; + err = "Symbols in precedence/TERM line must not already be known."; goto abort; } s->type = type; - s->precedence = g->prec_levels; - s->assoc = assoc; + if (!term) { + s->precedence = g->prec_levels; + s->assoc = assoc; + } found += 1; t = token_next(ts); } if (found == 0) - err = "No symbols given on precedence line"; + err = "No symbols given on precedence/TERM line"; goto abort; return NULL; abort: @@ -391,29 +407,15 @@ be in one `code_node` of the literate code. The `}$` must be at the end of a line. Text in the code fragment will undergo substitutions where `$N` or -`$type == Unknown) - bs->type = Terminal; + if (bs->type == Unknown) { + if (!g->terminals_declared) + bs->type = Terminal; + } if (bs->type == Virtual) { err = "Virtual symbol not permitted in production"; goto abort; @@ -535,10 +538,6 @@ Now we have all the bits we need to parse a full production. } tk = token_next(state); } - if (p.body_size >= 2 && - p.body[0] == p.head && - p.body[1]->num != TK_newline) - p.head->left_recursive = 1; if (tk.num != TK_newline && tk.num != TK_eof) { err = "stray tokens at end of line"; @@ -669,6 +668,21 @@ to produce errors that the parser is better positioned to handle. goto abort; } token_close(state); + if (g->terminals_declared) { + struct symbol *s; + int errs = 0; + for (s = g->syms; s; s = s->next) { + if (s->type != Unknown) + continue; + errs += 1; + fprintf(stderr, "Token %.*s not declared\n", + s->name.len, s->name.txt); + } + if (errs) { + free(g); + g = NULL; + } + } return g; abort: fprintf(stderr, "Error at line %d: %s\n", @@ -1133,15 +1147,15 @@ the end of the list in the symset, and then only compare items before the first "0". ###### declarations - static inline unsigned short item_num(int production, int index) + static inline unsigned short item_num(int production, int dot) { - return production | ((31-index) << 11); + return production | ((31-dot) << 11); } static inline int item_prod(unsigned short item) { return item & 0x7ff; } - static inline int item_index(unsigned short item) + static inline int item_dot(unsigned short item) { return (31-(item >> 11)) & 0x1f; } @@ -1159,8 +1173,8 @@ can just compare the symset and the data values together. for (i = 0; i < a.cnt && i < b.cnt && - item_index(a.syms[i]) > 0 && - item_index(b.syms[i]) > 0; + item_dot(a.syms[i]) > 0 && + item_dot(b.syms[i]) > 0; i++) { int diff = a.syms[i] - b.syms[i]; if (diff) @@ -1171,11 +1185,11 @@ can just compare the symset and the data values together. return diff; } } - if (i == a.cnt || item_index(a.syms[i]) == 0) + if (i == a.cnt || item_dot(a.syms[i]) == 0) av = -1; else av = a.syms[i]; - if (i == b.cnt || item_index(b.syms[i]) == 0) + if (i == b.cnt || item_dot(b.syms[i]) == 0) bv = -1; else bv = b.syms[i]; @@ -1331,7 +1345,7 @@ into the go to set, so the item is ineffective. ###### complete itemset for (i = 0; i < is->items.cnt; i++) { int p = item_prod(is->items.syms[i]); - int bs = item_index(is->items.syms[i]); + int bs = item_dot(is->items.syms[i]); struct production *pr = g->productions[p]; int p2; struct symbol *s; @@ -1436,7 +1450,7 @@ with a pre-existing itemset). for (j = 0; j < is->items.cnt; j++) { int itm = is->items.syms[j]; int p = item_prod(itm); - int bp = item_index(itm); + int bp = item_dot(itm); struct production *pr = g->productions[p]; unsigned short la = 0; int pos; @@ -1588,7 +1602,7 @@ all the tables that have been generated, plus a description of any conflicts. if (g->follow) report_follow(g); report_itemsets(g); - return report_conflicts(g, type) + report_left_recursive(g); + return report_conflicts(g, type); } Firstly we have the complete list of symbols, together with the @@ -1661,7 +1675,7 @@ it up a bit. First the items, with production number and associativity. static void report_item(struct grammar *g, int itm) { int p = item_prod(itm); - int dot = item_index(itm); + int dot = item_dot(itm); struct production *pr = g->productions[p]; int i; @@ -1790,7 +1804,7 @@ as shifts always over-ride reductions. for (j = 0; j < is->items.cnt; j++) { int itm = is->items.syms[j]; int p = item_prod(itm); - int bp = item_index(itm); + int bp = item_dot(itm); struct production *pr = g->productions[p]; if (bp == pr->body_size) { @@ -1847,7 +1861,7 @@ but handled internally. for (j = 0; j < is->items.cnt; j++) { unsigned short itm = is->items.syms[j]; int p = item_prod(itm); - int bp = item_index(itm); + int bp = item_dot(itm); struct production *pr = g->productions[p]; struct symbol *s; @@ -1868,7 +1882,7 @@ but handled internally. for (j = 0; j < is->items.cnt; j++) { unsigned short itm = is->items.syms[j]; int p = item_prod(itm); - int bp = item_index(itm); + int bp = item_dot(itm); struct production *pr = g->productions[p]; if (bp < pr->body_size) @@ -1910,42 +1924,6 @@ but handled internally. } -### Reporting non-final left-recursive symbols. - -Left recursive symbols are a problem for parses that honour indentation -when they appear other than at the end of the production. So we need to -report these when asked. - -###### functions - - static int report_left_recursive(struct grammar *g) - { - int p; - int bad_left_recursive = 0; - - for (p = 0; p < g->production_count; p++) { - struct production *pr = g->productions[p]; - int sn; - - for (sn = 0; sn < pr->body_size - 1; sn++) { - struct symbol *s = pr->body[sn]; - - if (s->left_recursive == 1 && - s != pr->head) { - if (!bad_left_recursive) { - bad_left_recursive = 1; - printf("Misplaced left recursive symbols.\n"); - } - printf(" "); - prtxt(s->name); - printf(" in production [%d]\n", p); - s->left_recursive = 2; - } - } - } - return bad_left_recursive; - } - ## Generating the parser The exported part of the parser is the `parse_XX` function, where the name @@ -2083,7 +2061,7 @@ The go to table is stored in a simple array of `sym` and corresponding for (j = 0; j < is->items.cnt; j++) { int itm = is->items.syms[j]; int p = item_prod(itm); - int bp = item_index(itm); + int bp = item_dot(itm); struct production *pr = g->productions[p]; if (bp < pr->body_size) @@ -2135,13 +2113,105 @@ structure returned by a previous reduction. These pointers need to be cast to the appropriate type for each access. All this is handled in `gen_code`. -`gen_code` also allows symbol references to contain a '`<`' as in '`$<2`'. -This applied only to symbols with references (or pointers), not those with structures. -The `<` implies that the reference it being moved out, so the object will not be -automatically freed. This is equivalent to assigning `NULL` to the pointer. +`gen_code` also allows symbol references to contain a '`<`' as in +'`$<2`'. This is particularly useful for references (or pointers), but +can be used with structures too. The `<` implies that the value it +being moved out, so the object will not be automatically freed. It is +equivalent to assigning `NULL` to the pointer or filling a structure +with zeros. + +Instead of a number `N`, the `$` or `$<` can be followed by some letters +and possibly a number. A number by itself (other than zero) selects a +symbol from the body of the production. A sequence of letters selects +the shortest symbol in the body which contains those letters in the given +order. If a number follows the letters, then a later occurrence of +that symbol is chosen. So "`$AB2`" will refer to the structure attached +to the second occurrence of the shortest symbol which contains an `A` +followed by a `B`. If there is no unique shortest system, or if the +number given is too large, then the symbol reference is not transformed, +and will cause an error when the code is compiled. ###### functions + static int textchr(struct text t, char c, int s) + { + int i; + for (i = s; i < t.len; i++) + if (t.txt[i] == c) + return i; + return -1; + } + + static int subseq_match(char *seq, int slen, struct text name) + { + int st = 0; + while (slen > 0) { + st = textchr(name, *seq, st); + if (st < 0) + return 0; + slen -= 1; + seq += 1; + st += 1; + } + return 1; + } + + static int choose_sym(char **namep, int len, struct production *p) + { + char *name = *namep; + char *nam = name; + int namlen; + int n = 0; + int i, s, slen; + char c; + + c = *name; + while (len > 0 && + ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'))) { + name += 1; + len -= 1; + c = *name; + } + namlen = name-nam; + while (len > 0 && (c >= '0' && c <= '9')) { + name += 1; + len -= 1; + n = n * 10 + (c - '0'); + c = *name; + } + if (namlen == 0) { + if (name == *namep) + return -1; + *namep = name; + return n; + } + slen = 0; s = -1; + 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) + s = i; + 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 */ + s = -1; + } + if (s < 0) + return -1; + if (n == 0); + n = 1; + for (i = 0; i < p->body_size; i++) + if (p->body[i] == p->body[s]) { + n -= 1; + if (n == 0) + break; + } + if (n > 1) + return -1; + *namep = name; + return i + 1; + } + static void gen_code(struct production *p, FILE *f, struct grammar *g) { char *c; @@ -2163,24 +2233,19 @@ automatically freed. This is equivalent to assigning `NULL` to the pointer. use = 1; c++; } - if (*c < '0' || *c > '9') { + n = choose_sym(&c, p->code.txt + p->code.len - c, p); + if (n < 0) { + fputc('$', f); if (use) fputc('<', f); fputc(*c, f); continue; } - n = *c - '0'; - while (c[1] >= '0' && c[1] <= '9') { - c += 1; - n = n * 10 + *c - '0'; - } if (n == 0) fprintf(f, "(*(struct %.*s*%s)ret)", p->head->struct_name.len, p->head->struct_name.txt, p->head->isref ? "*":""); - else if (n > p->body_size) - fprintf(f, "$%d", n); else if (p->body[n-1]->type == Terminal) fprintf(f, "(*(struct token *)body[%d])", n-1); @@ -2193,6 +2258,7 @@ automatically freed. This is equivalent to assigning `NULL` to the pointer. p->body[n-1]->isref ? "*":"", n-1); used[n-1] = use; } + c -= 1; } fputs("\n", f); for (i = 0; i < p->body_size; i++) { @@ -2868,7 +2934,7 @@ checks if a given token is in any of these look-ahead sets. void *ret = NULL; shift(&p, TK_eof, 0, 1, NULL, states); - while (!accepted) { + while (!accepted && p.tos > 0) { struct token *err_tk; struct frame *tos = &p.stack[p.tos-1]; if (!tk)