parsergen: allow terminals to be declared.

[ocean] / csrc / parsergen.mdc

diff --git a/csrc/parsergen.mdc b/csrc/parsergen.mdc
index 3f36df9a6873c3c94f2f127d8a0ca6419e50603c..66a41b5f5a297abd1a90510c23d1d40e5e89e676 100644 (file)
--- 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.
 
 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;
 ###### 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
 
 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


@@ -241,9 +247,10 @@ symbol, but its type might be `Unknown`.
 
 ### Data types and precedence.
 
 
 ### 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
 precedence, otherwise it specifies a data type.
 
 The data type name is simply stored and applied to the head of all


@@ -296,6 +303,7 @@ Subsequent lines introduce symbols with higher precedence.
                struct token t = token_next(ts);
                char *err;
                enum assoc assoc;
                struct token t = token_next(ts);
                char *err;
                enum assoc assoc;

+               int term = 0;

                int found;
 
                if (t.num != TK_ident) {
                int found;
 
                if (t.num != TK_ident) {


@@ -308,7 +316,10 @@ Subsequent lines introduce symbols with higher precedence.
                        assoc = Right;
                else if (text_is(t.txt, "NON"))
                        assoc = Non;
                        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"))
                        g->current_type = t.txt;
                        g->type_isref = isref;
                        if (text_is(t.txt, "void"))


@@ -326,7 +337,7 @@ Subsequent lines introduce symbols with higher precedence.
                        goto abort;
                }
 
                        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);
                found = 0;
                g->prec_levels += 1;
                t = token_next(ts);


@@ -340,6 +351,10 @@ Subsequent lines introduce symbols with higher precedence.
                                        err = "$$ must be followed by a word";
                                        goto abort;
                                }
                                        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";
                        } else if (t.num != TK_ident &&
                                   t.num != TK_mark) {
                                err = "Illegal token in precedence line";


@@ -347,17 +362,19 @@ Subsequent lines introduce symbols with higher precedence.
                        }
                        s = sym_find(g, t.txt);
                        if (s->type != Unknown) {
                        }
                        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;
                                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)
                        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:
                        goto abort;
                return NULL;
        abort:


@@ -400,6 +417,21 @@ The `<` may be included for symbols declared as storing a reference
 (not a structure) and means that the reference is being moved out, so
 it will not automatically be freed.
 
 (not a structure) and means that the reference is being moved out, so
 it will not automatically be freed.
 

+Symbols that are left-recursive are a little special.  These are symbols
+that both the head of a production and the first body symbol of the same
+production.  They are problematic when they appear in other productions
+elsewhere than at the end, and when indenting is used to describe
+structure.  In this case there is no way for a smaller indent to ensure
+the left-recursive symbol cannot be extended.  When it appears at the
+end of a production, that production can be reduced to ensure the symbol
+isn't extended.  So we record left-recursive symbols while reading the
+grammar, and produce a warning when reporting the grammar if they are
+found in an unsuitable place.
+
+A symbol that is only left recursive in a production where it is
+followed by newline does not cause these problems because the newline
+will effectively terminate it.
+

 While building productions we will need to add to an array which needs to
 grow dynamically.
 
 While building productions we will need to add to an array which needs to
 grow dynamically.
 


@@ -460,6 +492,7 @@ Now we have all the bits we need to parse a full production.
 
 ###### symbol fields
        int first_production;
 
 ###### symbol fields
        int first_production;

+       int left_recursive;

 
 ###### functions
        static char *parse_production(struct grammar *g,
 
 ###### functions
        static char *parse_production(struct grammar *g,


@@ -476,8 +509,10 @@ Now we have all the bits we need to parse a full production.
                tk = token_next(state);
                while (tk.num == TK_ident || tk.num == TK_mark) {
                        struct symbol *bs = sym_find(g, tk.txt);
                tk = token_next(state);
                while (tk.num == TK_ident || tk.num == TK_mark) {
                        struct symbol *bs = sym_find(g, tk.txt);

-                       if (bs->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;
                        if (bs->type == Virtual) {
                                err = "Virtual symbol not permitted in production";
                                goto abort;


@@ -519,6 +554,11 @@ Now we have all the bits we need to parse a full production.
                        }
                        tk = token_next(state);
                }
                        }
                        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";
                        goto abort;
                if (tk.num != TK_newline && tk.num != TK_eof) {
                        err = "stray tokens at end of line";
                        goto abort;


@@ -648,6 +688,21 @@ to produce errors that the parser is better positioned to handle.
                                goto abort;
                }
                token_close(state);
                                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",
                return g;
        abort:
                fprintf(stderr, "Error at line %d: %s\n",


@@ -1524,6 +1579,11 @@ changeover point in `first_nonterm`.
                                snum++;
                        }
                g->first_nonterm = snum;
                                snum++;
                        }
                g->first_nonterm = snum;

+               for (s = g->syms; s; s = s->next)
+                       if (s->num < 0 && s->type != Virtual) {
+                               s->num = snum;
+                               snum++;
+                       }

                for (s = g->syms; s; s = s->next)
                        if (s->num < 0) {
                                s->num = snum;
                for (s = g->syms; s; s = s->next)
                        if (s->num < 0) {
                                s->num = snum;


@@ -1562,7 +1622,7 @@ all the tables that have been generated, plus a description of any conflicts.
                if (g->follow)
                        report_follow(g);
                report_itemsets(g);
                if (g->follow)
                        report_follow(g);
                report_itemsets(g);

-               return report_conflicts(g, type);
+               return report_conflicts(g, type) + report_left_recursive(g);

        }
 
 Firstly we have the complete list of symbols, together with the
        }
 
 Firstly we have the complete list of symbols, together with the


@@ -1883,6 +1943,43 @@ but handled internally.
                return cnt;
        }
 
                return cnt;
        }
 

+
+### 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
 ## Generating the parser
 
 The exported part of the parser is the `parse_XX` function, where the name


@@ -1953,7 +2050,7 @@ numbers right.
                for (i = TK_reserved;
                     i < g->num_syms;
                     i++)
                for (i = TK_reserved;
                     i < g->num_syms;
                     i++)

-                       if (g->symtab[i]->type != Terminal)
+                       if (g->symtab[i]->type == Nonterminal)

                                fprintf(f, "\t\"%.*s\",\n", g->symtab[i]->name.len,
                                        g->symtab[i]->name.txt);
                fprintf(f, "};\n\n");
                                fprintf(f, "\t\"%.*s\",\n", g->symtab[i]->name.len,
                                        g->symtab[i]->name.txt);
                fprintf(f, "};\n\n");


@@ -2716,8 +2813,12 @@ accepted the input and can finish.
 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
 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.
+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
 
 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


@@ -2761,11 +2862,11 @@ in the thing that preceed:
 Here the NEWLINE will be shifted because nothing can be reduced until
 the `if` is seen.
 
 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
+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
 discarding until we see one that is recognised.  If we had a full set

-of LR(1) grammar states, this will mean looking in the look-ahead 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
 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 but
+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.
 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.


@@ -2797,6 +2898,7 @@ checks if a given token is in any of these look-ahead sets.
                struct parser p = { 0 };
                struct token *tk = NULL;
                int accepted = 0;
                struct parser p = { 0 };
                struct token *tk = NULL;
                int accepted = 0;

+               int shift_since_err = 1;

                void *ret = NULL;
 
                shift(&p, TK_eof, 0, 1, NULL, states);
                void *ret = NULL;
 
                shift(&p, TK_eof, 0, 1, NULL, states);


@@ -2868,6 +2970,7 @@ checks if a given token is in any of these look-ahead sets.
                                        goto force_reduce;
                        }
                        if (shift(&p, tk->num, 0, tk->num == TK_newline, tk, states)) {
                                        goto force_reduce;
                        }
                        if (shift(&p, tk->num, 0, tk->num == TK_newline, tk, states)) {

+                               shift_since_err = 1;

                                tk = NULL;
                                parser_trace_action(trace, "Shift");
                                continue;
                                tk = NULL;
                                parser_trace_action(trace, "Shift");
                                continue;


@@ -2932,11 +3035,22 @@ checks if a given token is in any of these look-ahead sets.
                                // no state accepted TK_error
                                break;
                        }
                                // 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));
                        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;

                                if (tk->num == TK_in)
                                        indents += 1;
                                if (tk->num == TK_out) {
                                if (tk->num == TK_in)
                                        indents += 1;
                                if (tk->num == TK_out) {