parsegen: detect left-recursive symbols in non-final position.

A left-recursive symbol that appear other than at the end of a
production causes problem for indent-based parsing, as describe in the
document.  So teach parsergen to be able to report them.

Ocean currently has several of these, which I'll need to look into at a
later date.

Signed-off-by: NeilBrown <neil@brown.name>

diff --git a/csrc/parsergen.mdc b/csrc/parsergen.mdc
index 3f36df9a6873c3c94f2f127d8a0ca6419e50603c..5bf413de01b0f8bf19a44375ae23f8b1f7086790 100644 (file)
--- a/csrc/parsergen.mdc
+++ b/csrc/parsergen.mdc
@@ -400,6 +400,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.
 
+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.
 
@@ -460,6 +475,7 @@ Now we have all the bits we need to parse a full production.
 
 ###### symbol fields
        int first_production;
+       int left_recursive;
 
 ###### functions
        static char *parse_production(struct grammar *g,
@@ -519,6 +535,11 @@ 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";
                        goto abort;
@@ -1562,7 +1583,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);
+               return report_conflicts(g, type) + report_left_recursive(g);
        }
 
 Firstly we have the complete list of symbols, together with the
@@ -1883,6 +1904,43 @@ but handled internally.
                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