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.
 
 (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 +475,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,


@@ -519,6 +535,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;


@@ -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);
                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 +1904,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