]> ocean-lang.org Git - ocean/blob - csrc/parsergen.mdc
oceani: differentiate static-sized arrays from others.
[ocean] / csrc / parsergen.mdc
1 # LR(1) Parser Generator with 2D support #
2
3 This parser generator takes a grammar description combined with code
4 fragments, analyses it, and can report details about the analysis and
5 write out C code files which can be compiled to make a parser.
6
7 "2D support" means that indentation and line breaks can be significant.
8 Indent tokens (IN and OUT) and end-of-line tokens (EOL and NEWLINE) can
9 be used to describe the grammar and the parser can selectively ignore
10 these where they aren't relevant.
11
12 There are several distinct sections.
13
14 1. `grammar_read` will read a grammar from a literate-code file and
15    store the productions, symbols, and code fragments.
16 2. `grammar_analyse` will take that grammar and build LR parsing
17    states and look-ahead tables.
18 3. `grammar_report` will present the details of the analysis
19    in a readable format and will report any conflicts.
20 4. `parser_generate` will write out C code files with various
21    tables and with the code fragments arranged in useful places.
22 5. `parser_run` is a library function intended to be linked together
23    with the generated parser tables to complete the implementation of
24    a parser.
25 6. Finally `calc` is a test grammar for a simple calculator.  The
26    `parsergen` program built from the C code in this file can extract
27    that grammar directly from this file and process it.
28
29 ###### File: parsergen.c
30         #include <unistd.h>
31         #include <stdlib.h>
32         #include <stdio.h>
33         ## includes
34         ## forward declarations
35         ## declarations
36         ## functions
37         ## grammar_read
38         ## grammar_analyse
39         ## grammar_report
40         ## parser_generate
41         ## main
42 ###### File: parser.h
43         ## exported types
44         ## exported functions
45 ###### File: libparser.c
46         #include <unistd.h>
47         #include <stdlib.h>
48         #include <stdio.h>
49         ## parser includes
50         ## parser functions
51         ## parser_run
52 ###### File: parsergen.mk
53         CFLAGS += -Wall -g
54         all :: parsergen calc
55         parsergen.c parsergen.mk libparser.c parser.h : parsergen.mdc
56                 ./md2c parsergen.mdc
57
58 ## Reading the grammar
59
60 The grammar must be stored in a markdown literate code file as parsed by
61 "[mdcode][]".  It may have up to four top level (i.e.  unreferenced)
62 sections: `header`, `code`, `grammar` and `reduce`.  The first two, if
63 present, will be literally copied into the generated `.c` and `.h`
64 files.  The third is required and contains the grammar which is
65 tokenised with "[scanner][]".  `reduce` can provide variable
66 declarations and common intialization code for all the reduction code
67 fragments in the grammar.
68
69 If the `--tag` option is given, then any top level header that doesn't
70 start with the tag is ignored, and the tag is striped from the rest.  So
71 `--tag Foo` means that the four sections expected are `Foo: header`,
72 `Foo: code`, `Foo: grammar` and `Foo: reduce`.  The tag `calc` is used
73 to extract the sample calculator from this file.
74
75 [mdcode]: mdcode.html
76 [scanner]: scanner.html
77
78 ###### includes
79         #include "mdcode.h"
80         #include "scanner.h"
81
82 ###### parser includes
83         #include "mdcode.h"
84         #include "scanner.h"
85
86 The grammar contains production sets, precedence/associativity
87 declarations, general terminal declarations, and data type declarations.
88 These are all parsed with _ad hoc_ parsing as we don't have a parser
89 generator yet.
90
91 The precedence and associativity can be set for each production, and
92 can be inherited from symbols.  The data type (either structure or a
93 reference to a structure) is potentially defined for each non-terminal
94 and describes what C structure is used to store information about each
95 symbol.
96
97 ###### declarations
98         enum assoc {Left, Right, Non};
99         char *assoc_names[] = {"Left","Right","Non"};
100
101         struct symbol {
102                 struct text struct_name;
103                 int isref;
104                 enum assoc assoc;
105                 unsigned short precedence;
106                 ## symbol fields
107         };
108         struct production {
109                 unsigned short precedence;
110                 enum assoc assoc;
111                 ## production fields
112         };
113         struct grammar {
114                 ## grammar fields
115         };
116
117 The strings reported by `mdcode` and `scanner` are `struct text` which
118 have length rather than being nul terminated.  To help with printing and
119 comparing we define `text_is` and `prtxt`, which should possibly go in
120 `mdcode`.  `scanner` does provide `text_dump` which is useful for
121 strings which might contain control characters.
122
123 `strip_tag` is a bit like `strncmp`, but adds a test for a colon,
124 because that is what we need to detect tags.
125
126 ###### functions
127         static int text_is(struct text t, char *s)
128         {
129                 return (strlen(s) == t.len &&
130                         strncmp(s, t.txt, t.len) == 0);
131         }
132         static void prtxt(struct text t)
133         {
134                 printf("%.*s", t.len, t.txt);
135         }
136
137         static int strip_tag(struct text *t, char *tag)
138         {
139                 int skip = strlen(tag) + 1;
140                 if (skip >= t->len ||
141                     strncmp(t->txt, tag, skip-1) != 0 ||
142                     t->txt[skip-1] != ':')
143                         return 0;
144                 while (skip < t->len && t->txt[skip] == ' ')
145                         skip++;
146                 t->len -= skip;
147                 t->txt += skip;
148                 return 1;
149         }
150
151 ### Symbols
152
153 Productions are comprised primarily of symbols - terminal and
154 non-terminal.  We do not make a syntactic distinction between the two,
155 though non-terminals must be identifiers while terminals can also be
156 marks.  Non-terminal symbols are those which appear in the head of a
157 production, terminal symbols are those which don't.  There are also
158 "virtual" symbols used for precedence marking discussed later, and
159 sometimes we won't know what type a symbol is yet.
160
161 To help with code safety it is possible to declare the terminal symbols.
162 If this is done, then any symbol used in a production that does not
163 appear in the head of any production and is not declared as a terminal
164 is treated as an error.
165
166 ###### forward declarations
167         enum symtype { Unknown, Virtual, Terminal, Nonterminal };
168         char *symtypes = "UVTN";
169 ###### symbol fields
170         enum symtype type;
171 ###### grammar fields
172         int terminals_declared;
173
174 Symbols can be either `TK_ident` or `TK_mark`.  They are saved in a
175 table of known symbols and the resulting parser will report them as
176 `TK_reserved + N`.  A small set of identifiers are reserved for the
177 different token types that `scanner` can report, and an even smaller set
178 are reserved for a special token that the parser can generate (`EOL`) as
179 will be described later.  This latter set cannot use predefined numbers,
180 so they are marked as `isspecial` for now and will get assigned a number
181 with the non-terminals later.
182
183 ###### declarations
184
185         static struct { int num; char *name; } reserved_words[] = {
186                 { TK_error,        "ERROR" },
187                 { TK_number,       "NUMBER" },
188                 { TK_ident,        "IDENTIFIER" },
189                 { TK_mark,         "MARK" },
190                 { TK_string,       "STRING" },
191                 { TK_multi_string, "MULTI_STRING" },
192                 { TK_in,           "IN" },
193                 { TK_out,          "OUT" },
194                 { TK_newline,      "NEWLINE" },
195                 { TK_eof,          "$eof" },
196                 { -1,              "EOL" },
197         };
198
199 ###### symbol fields
200         short num;
201         unsigned int isspecial:1;
202
203 Note that `TK_eof` and the two `TK_*_comment` tokens cannot be
204 recognised.  The former is automatically expected at the end of the text
205 being parsed. The latter are always ignored by the parser.
206
207 All of these symbols are stored in a simple symbol table.  We use the
208 `struct text` from `mdcode` to store the name and link them together
209 into a sorted list using an insertion sort.
210
211 We don't have separate `find` and `insert` functions as any symbol we
212 find needs to be remembered.  We simply expect `find` to always return a
213 symbol, but its type might be `Unknown`.
214
215 ###### includes
216         #include <string.h>
217
218 ###### symbol fields
219         struct text name;
220         struct symbol *next;
221
222 ###### grammar fields
223         struct symbol *syms;
224         int num_syms;
225
226 ###### functions
227         static struct symbol *sym_find(struct grammar *g, struct text s)
228         {
229                 struct symbol **l = &g->syms;
230                 struct symbol *n;
231                 int cmp = 1;
232
233                 while (*l &&
234                         (cmp = text_cmp((*l)->name, s)) < 0)
235                                 l = & (*l)->next;
236                 if (cmp == 0)
237                         return *l;
238                 n = calloc(1, sizeof(*n));
239                 n->name = s;
240                 n->type = Unknown;
241                 n->next = *l;
242                 n->num = -1;
243                 *l = n;
244                 return n;
245         }
246
247         static void symbols_init(struct grammar *g)
248         {
249                 int entries = sizeof(reserved_words)/sizeof(reserved_words[0]);
250                 int i;
251                 for (i = 0; i < entries; i++) {
252                         struct text t;
253                         struct symbol *s;
254                         t.txt = reserved_words[i].name;
255                         t.len = strlen(t.txt);
256                         s = sym_find(g, t);
257                         s->type = Terminal;
258                         s->num = reserved_words[i].num;
259                         s->isspecial = 1;
260                 }
261         }
262
263 ### Data types and precedence.
264
265 Data type specification, precedence specification, and declaration of
266 terminals are all introduced by a dollar sign at the start of the line.
267 If the next word is `LEFT`, `RIGHT` or `NON`, then the line specifies a
268 precedence, if it is `TERM` then the line declares terminals without
269 precedence, otherwise it specifies a data type.
270
271 The data type name is simply stored and applied to the head of all
272 subsequent productions.  It must be the name of a structure optionally
273 preceded by an asterisk which means a reference or "pointer".  So
274 `$expression` maps to `struct expression` and `$*statement` maps to
275 `struct statement *`.
276
277 Any productions given before the first data type declaration will have
278 no data type associated with them and can carry no information.  In
279 order to allow other non-terminals to have no type, the data type
280 `$void` can be given.  This does *not* mean that `struct void` will be
281 used, but rather than no type will be associated with subsequent
282 non-terminals.
283
284 The precedence line must contain a list of symbols, either terminal
285 symbols or virtual symbols.  It can only contain symbols that have not
286 been seen yet, so precedence declaration must precede the productions
287 that they affect.
288
289 A "virtual" symbol is an identifier preceded by `$$`.  Virtual symbols
290 carry precedence information but are not included in the grammar.  A
291 production can declare that it inherits the precedence of a given
292 virtual symbol.
293
294 This use of `$$` precludes it from being used as a symbol in the
295 described language.  Two other symbols: `${` and `}$` are also
296 unavailable.
297
298 Each new precedence line introduces a new precedence level and
299 declares how it associates.  This level is stored in each symbol
300 listed and may be inherited by any production which uses the symbol.  A
301 production inherits from the last symbol which has a precedence.
302
303 The symbols on the first precedence line have the lowest precedence.
304 Subsequent lines introduce symbols with higher precedence and so bind
305 more tightly.
306
307 Note that a declaration line (or "dollar line") can start with either of
308 two different marks: "$" or "$*".  The `dollar_line()` function defined
309 here is told which was found in the `isref` argument.
310
311 ###### grammar fields
312         struct text current_type;
313         int type_isref;
314         int prec_levels;
315
316 ###### declarations
317         enum symbols { TK_virtual = TK_reserved, TK_open, TK_close };
318         static const char *known[] = { "$$", "${", "}$" };
319
320 ###### functions
321         static char *dollar_line(struct token_state *ts, struct grammar *g, int isref)
322         {
323                 struct token t = token_next(ts);
324                 char *err;
325                 enum assoc assoc;
326                 int term = 0;
327                 int found;
328
329                 if (t.num != TK_ident) {
330                         err = "type or assoc expected after '$'";
331                         goto abort;
332                 }
333                 if (text_is(t.txt, "LEFT"))
334                         assoc = Left;
335                 else if (text_is(t.txt, "RIGHT"))
336                         assoc = Right;
337                 else if (text_is(t.txt, "NON"))
338                         assoc = Non;
339                 else if (text_is(t.txt, "TERM")) {
340                         term = 1;
341                         g->terminals_declared = 1;
342                 } else {
343                         g->current_type = t.txt;
344                         g->type_isref = isref;
345                         if (text_is(t.txt, "void"))
346                                 g->current_type.txt = NULL;
347                         t = token_next(ts);
348                         if (t.num != TK_newline) {
349                                 err = "Extra tokens after type name";
350                                 goto abort;
351                         }
352                         return NULL;
353                 }
354
355                 if (isref) {
356                         err = "$* cannot be followed by a precedence";
357                         goto abort;
358                 }
359
360                 // This is a precedence or TERM line, need some symbols.
361                 found = 0;
362                 g->prec_levels += 1;
363                 t = token_next(ts);
364                 while (t.num != TK_newline) {
365                         enum symtype type = Terminal;
366                         struct symbol *s;
367                         if (t.num == TK_virtual) {
368                                 type = Virtual;
369                                 t = token_next(ts);
370                                 if (t.num != TK_ident) {
371                                         err = "$$ must be followed by a word";
372                                         goto abort;
373                                 }
374                                 if (term) {
375                                         err = "Virtual symbols not permitted on $TERM line";
376                                         goto abort;
377                                 }
378                         } else if (t.num != TK_ident &&
379                                    t.num != TK_mark) {
380                                 err = "Illegal token in precedence line";
381                                 goto abort;
382                         }
383                         s = sym_find(g, t.txt);
384                         if (s->type != Unknown) {
385                                 err = "Symbols in precedence/TERM line must not already be known.";
386                                 goto abort;
387                         }
388                         s->type = type;
389                         if (!term) {
390                                 s->precedence = g->prec_levels;
391                                 s->assoc = assoc;
392                         }
393                         found += 1;
394                         t = token_next(ts);
395                 }
396                 if (found == 0) {
397                         err = "No symbols given on precedence/TERM line";
398                         goto abort;
399                 }
400                 return NULL;
401         abort:
402                 while (t.num != TK_newline && t.num != TK_eof)
403                         t = token_next(ts);
404                 return err;
405         }
406
407 ### Productions
408
409 A production either starts with an identifier which is the head
410 non-terminal, or a vertical bar (`|`) in which case this production
411 uses the same head as the previous one.  The identifier must be
412 followed by a `->` mark.  All productions for a given non-terminal must
413 be grouped together with the `nonterminal ->` given only once.
414
415 After this a (possibly empty) sequence of identifiers and marks form
416 the body of the production.  A virtual symbol may be given after the
417 body by preceding it with `$$`.  If a virtual symbol is given, the
418 precedence of the production is that for the virtual symbol.  If none
419 is given, the precedence is inherited from the last symbol in the
420 production which has a precedence specified.
421
422 After the optional precedence may come the `${` mark.  This indicates
423 the start of a code fragment.  If present, this must be on the same
424 line as the start of the production.
425
426 All of the text from the `${` through to the matching `}$` is
427 collected and forms the code-fragment for the production.  It must all
428 be in one `code_node` of the literate code.  The `}$` must be
429 at the end of a line.
430
431 Text in the code fragment will undergo substitutions where `$N` or
432 `$<N`,for some numeric `N` (or non-numeric indicator as described
433 later), will be replaced with a variable holding the parse information
434 for the particular symbol in the production.  `$0` is the head of the
435 production, `$1` is the first symbol of the body, etc.  The type of `$N`
436 for a terminal symbol is `struct token`.  For a non-terminal, it is
437 whatever has been declared for that symbol.  The `<` may be included and
438 means that the value (usually a reference) is being moved out, so it
439 will not automatically be freed.  The effect of using '<' is that the
440 variable is cleared to all-zeros.
441
442 While building productions we will need to add to an array which needs to
443 grow dynamically.
444
445 ###### functions
446         static void array_add(void *varray, int *cnt, void *new)
447         {
448                 void ***array = varray;
449                 int current = 0;
450                 const int step = 8;
451                 current = ((*cnt-1) | (step-1))+1;
452                 if (*cnt == current) {
453                         /* must grow */
454                         current += step;
455                         *array = realloc(*array, current * sizeof(void*));
456                 }
457                 (*array)[*cnt] = new;
458                 (*cnt) += 1;
459         }
460
461 Collecting the code fragment simply involves reading tokens until we
462 hit the end token `}$`, and noting the character position of the start and
463 the end.
464
465 ###### functions
466         static struct text collect_code(struct token_state *state,
467                                         struct token start)
468         {
469                 struct text code;
470                 struct token t;
471                 code.txt = start.txt.txt + start.txt.len;
472                 do
473                         t = token_next(state);
474                 while (t.node == start.node &&
475                        t.num != TK_close && t.num != TK_error &&
476                        t.num != TK_eof);
477                 if (t.num == TK_close && t.node == start.node)
478                         code.len = t.txt.txt - code.txt;
479                 else
480                         code.txt = NULL;
481                 return code;
482         }
483
484 Now we have all the bits we need to parse a full production.
485
486 ###### includes
487         #include <memory.h>
488
489 ###### grammar fields
490         struct production **productions;
491         int production_count;
492
493 ###### production fields
494         struct symbol  *head;
495         struct symbol **body;
496         int             body_size;
497         struct text     code;
498         int             code_line;
499
500 ###### symbol fields
501         int first_production;
502
503 ###### functions
504         static char *parse_production(struct grammar *g,
505                                       struct symbol *head,
506                                       struct token_state *state)
507         {
508                 /* Head has already been parsed. */
509                 struct token tk;
510                 char *err;
511                 struct production p, *pp;
512
513                 memset(&p, 0, sizeof(p));
514                 p.head = head;
515                 tk = token_next(state);
516                 while (tk.num == TK_ident || tk.num == TK_mark) {
517                         struct symbol *bs = sym_find(g, tk.txt);
518                         if (bs->type == Virtual) {
519                                 err = "Virtual symbol not permitted in production";
520                                 goto abort;
521                         }
522                         if (bs->precedence) {
523                                 p.precedence = bs->precedence;
524                                 p.assoc = bs->assoc;
525                         }
526                         array_add(&p.body, &p.body_size, bs);
527                         tk = token_next(state);
528                 }
529                 if (tk.num == TK_virtual) {
530                         struct symbol *vs;
531                         tk = token_next(state);
532                         if (tk.num != TK_ident) {
533                                 err = "word required after $$";
534                                 goto abort;
535                         }
536                         vs = sym_find(g, tk.txt);
537                         if (vs->precedence == 0) {
538                                 err = "symbol after $$ must have precedence";
539                                 goto abort;
540                         } else {
541                                 p.precedence = vs->precedence;
542                                 p.assoc = vs->assoc;
543                         }
544                         tk = token_next(state);
545                 }
546                 if (tk.num == TK_open) {
547                         p.code_line = tk.line;
548                         p.code = collect_code(state, tk);
549                         if (p.code.txt == NULL) {
550                                 err = "code fragment not closed properly";
551                                 goto abort;
552                         }
553                         tk = token_next(state);
554                 }
555
556                 if (tk.num != TK_newline && tk.num != TK_eof) {
557                         err = "stray tokens at end of line";
558                         goto abort;
559                 }
560                 pp = malloc(sizeof(*pp));
561                 *pp = p;
562                 array_add(&g->productions, &g->production_count, pp);
563                 return NULL;
564         abort:
565                 while (tk.num != TK_newline && tk.num != TK_eof)
566                         tk = token_next(state);
567                 free(p.body);
568                 return err;
569         }
570
571 With the ability to parse productions and dollar-lines, we have nearly all
572 that we need to parse a grammar from a `code_node`.
573
574 The head of the first production will effectively be the `start` symbol
575 of the grammar.  However it won't _actually_ be so.  Processing the
576 grammar is greatly simplified if the real start symbol only has a single
577 production, and expects `$eof` as the final terminal.  So when we find
578 the first explicit production we insert an extra implicit production as
579 production zero which looks like
580
581 ###### Example: production 0
582         $start -> START $eof
583
584 where `START` is the first non-terminal given.
585
586 ###### create production zero
587         struct production *p = calloc(1,sizeof(*p));
588         struct text start = {"$start",6};
589         struct text eof = {"$eof",4};
590         struct text code = {"$0 = $<1;", 9};
591         p->head = sym_find(g, start);
592         p->head->type = Nonterminal;
593         p->head->struct_name = g->current_type;
594         p->head->isref = g->type_isref;
595         if (g->current_type.txt)
596                 p->code = code;
597         array_add(&p->body, &p->body_size, head);
598         array_add(&p->body, &p->body_size, sym_find(g, eof));
599         p->head->first_production = g->production_count;
600         array_add(&g->productions, &g->production_count, p);
601
602 Now we are ready to read in the grammar.  We ignore comments
603 and strings so that the marks which introduce them can be
604 used as terminals in the grammar.  We don't ignore numbers
605 even though we don't allow them as that causes the scanner
606 to produce errors that the parser is better positioned to handle.
607 We also ignore indentation, but we expect and use newlines.
608
609 To allow comments in the grammar, we explicitly check for "//" as the
610 first token on the line and those lines are skipped.  "//" can still be
611 used as a terminal anywhere that a terminal is expected.
612
613 ###### grammar_read
614         static struct grammar *grammar_read(struct code_node *code)
615         {
616                 struct token_config conf = {
617                         .word_start = "",
618                         .word_cont = "",
619                         .words_marks = known,
620                         .known_count = sizeof(known)/sizeof(known[0]),
621                         .number_chars = "",
622                         .ignored = (1 << TK_line_comment)
623                                  | (1 << TK_block_comment)
624                                  | (0 << TK_number)
625                                  | (1 << TK_string)
626                                  | (1 << TK_multi_string)
627                                  | (1 << TK_in)
628                                  | (1 << TK_out),
629                 };
630
631                 struct token_state *state = token_open(code, &conf);
632                 struct token tk;
633                 struct symbol *head = NULL;
634                 struct grammar *g;
635                 char *err = NULL;
636
637                 g = calloc(1, sizeof(*g));
638                 symbols_init(g);
639
640                 for (tk = token_next(state); tk.num != TK_eof;
641                      tk = token_next(state)) {
642                         if (tk.num == TK_newline)
643                                 continue;
644                         if (tk.num == TK_ident) {
645                                 // new non-terminal
646                                 head = sym_find(g, tk.txt);
647                                 if (head->type == Nonterminal)
648                                         err = "This non-terminal has already be used.";
649                                 else if (head->type == Virtual)
650                                         err = "Virtual symbol not permitted in head of production";
651                                 else {
652                                         head->type = Nonterminal;
653                                         head->struct_name = g->current_type;
654                                         head->isref = g->type_isref;
655                                         if (g->production_count == 0) {
656                                                 ## create production zero
657                                         }
658                                         head->first_production = g->production_count;
659                                         tk = token_next(state);
660                                         if (tk.num == TK_mark &&
661                                             text_is(tk.txt, "->"))
662                                                 err = parse_production(g, head, state);
663                                         else
664                                                 err = "'->' missing in production";
665                                 }
666                         } else if (tk.num == TK_mark
667                                    && text_is(tk.txt, "|")) {
668                                 // another production for same non-term
669                                 if (head)
670                                         err = parse_production(g, head, state);
671                                 else
672                                         err = "First production must have a head";
673                         } else if (tk.num == TK_mark
674                                    && text_is(tk.txt, "$")) {
675                                 err = dollar_line(state, g, 0);
676                         } else if (tk.num == TK_mark
677                                    && text_is(tk.txt, "$*")) {
678                                 err = dollar_line(state, g, 1);
679                         } else if (tk.num == TK_mark
680                                    && text_is(tk.txt, "//")) {
681                                 while (tk.num != TK_newline &&
682                                        tk.num != TK_eof)
683                                         tk = token_next(state);
684                         } else {
685                                 err = "Unrecognised token at start of line.";
686                         }
687                         if (err)
688                                 goto abort;
689                 }
690                 token_close(state);
691
692                 struct symbol *s;
693                 for (s = g->syms; s; s = s->next) {
694                         if (s->type != Unknown)
695                                 continue;
696                         if (!g->terminals_declared) {
697                                 s->type = Terminal;
698                                 continue;
699                         }
700                         err = "not declared";
701                         fprintf(stderr, "Token %.*s not declared\n",
702                                 s->name.len, s->name.txt);
703                 }
704                 if (err) {
705                         free(g); // FIXME free content
706                         g = NULL;
707                 }
708                 return g;
709         abort:
710                 fprintf(stderr, "Error at line %d: %s\n",
711                         tk.line, err);
712                 token_close(state);
713                 free(g); // FIXME free content
714                 return NULL;
715         }
716
717 ## Analysing the grammar
718
719 The central task in analysing the grammar is to determine a set of
720 states to drive the parsing process.  This will require finding various
721 sets of symbols and of "items".  Some of these sets will need to attach
722 information to each element in the set, so they are more like maps.
723
724 Each "item" may have a 'look-ahead' or `LA` set associated with it.
725 Many of these will be the same as each other.  To avoid memory wastage,
726 and to simplify some comparisons of sets, these sets will be stored in a
727 list of unique sets, each assigned a number.
728
729 Once we have the data structures in hand to manage these sets and lists,
730 we can start setting the 'nullable' flag, build the 'FIRST' and 'FOLLOW'
731 sets, and then create the item sets which define the various states.
732
733 ### Symbol sets.
734
735 Though we don't only store symbols in these sets, they are the main
736 things we store, so they are called symbol sets or "symsets".
737
738 A symset has a size, an array of shorts, and an optional array of data
739 values, which are also shorts.  If the array of data is not present, we
740 store an impossible pointer, as `NULL` is used to indicate that no
741 memory has been allocated yet;
742
743 ###### declarations
744         struct symset {
745                 short cnt;
746                 unsigned short *syms, *data;
747         };
748         #define NO_DATA ((unsigned short *)1)
749         const struct symset INIT_SYMSET =  { 0, NULL, NO_DATA };
750         const struct symset INIT_DATASET = { 0, NULL, NULL };
751
752 The arrays of shorts are allocated in blocks of 8 and are kept sorted by
753 using an insertion sort.  We don't explicitly record the amount of
754 allocated space as it can be derived directly from the current `cnt`
755 using `((cnt - 1) | 7) + 1`.
756
757 ###### functions
758         static void symset_add(struct symset *s, unsigned short key, unsigned short val)
759         {
760                 int i;
761                 int current = ((s->cnt-1) | 7) + 1;
762                 if (current == s->cnt) {
763                         current += 8;
764                         s->syms = realloc(s->syms, sizeof(*s->syms) * current);
765                         if (s->data != NO_DATA)
766                                 s->data = realloc(s->data, sizeof(*s->data) * current);
767                 }
768                 i = s->cnt;
769                 while (i > 0 && s->syms[i-1] > key) {
770                         s->syms[i] = s->syms[i-1];
771                         if (s->data != NO_DATA)
772                                 s->data[i] = s->data[i-1];
773                         i--;
774                 }
775                 s->syms[i] = key;
776                 if (s->data != NO_DATA)
777                         s->data[i] = val;
778                 s->cnt += 1;
779         }
780
781 Finding a symbol (or item) in a `symset` uses a simple binary search.
782 We return the index where the value was found (so data can be accessed),
783 or `-1` to indicate failure.
784
785         static int symset_find(struct symset *ss, unsigned short key)
786         {
787                 int lo = 0;
788                 int hi = ss->cnt;
789
790                 if (hi == 0)
791                         return -1;
792                 while (lo + 1 < hi) {
793                         int mid = (lo + hi) / 2;
794                         if (ss->syms[mid] <= key)
795                                 lo = mid;
796                         else
797                                 hi = mid;
798                 }
799                 if (ss->syms[lo] == key)
800                         return lo;
801                 return -1;
802         }
803
804 We will often want to form the union of two symsets.  When we do, we
805 will often want to know if anything changed (as that might mean there is
806 more work to do).  So `symset_union` reports whether anything was added
807 to the first set.  We use a slow quadratic approach as these sets are
808 rarely large.  If profiling shows this to be a problem it can be
809 optimised later.
810
811         static int symset_union(struct symset *a, struct symset *b)
812         {
813                 int i;
814                 int added = 0;
815                 for (i = 0; i < b->cnt; i++)
816                         if (symset_find(a, b->syms[i]) < 0) {
817                                 unsigned short data = 0;
818                                 if (b->data != NO_DATA)
819                                         data = b->data[i];
820                                 symset_add(a, b->syms[i], data);
821                                 added++;
822                         }
823                 return added;
824         }
825
826 And of course we must be able to free a symset.
827
828         static void symset_free(struct symset ss)
829         {
830                 free(ss.syms);
831                 if (ss.data != NO_DATA)
832                         free(ss.data);
833         }
834
835 ### Symset Storage
836
837 Some symsets are simply stored somewhere appropriate in the `grammar`
838 data structure, others needs a bit of indirection.  This applies
839 particularly to "LA" sets.  These will be paired with "items" in an
840 "itemset".  As itemsets will be stored in a symset, the "LA" set needs
841 to be stored in the `data` field, so we need a mapping from a small
842 (short) number to an LA `symset`.
843
844 As mentioned earlier this involves creating a list of unique symsets.
845
846 For now, we just use a linear list sorted by insertion.  A skiplist
847 would be more efficient and may be added later.
848
849 ###### declarations
850
851         struct setlist {
852                 struct symset ss;
853                 int num;
854                 struct setlist *next;
855         };
856
857 ###### grammar fields
858         struct setlist *sets;
859         int nextset;
860
861 ###### functions
862
863         static int ss_cmp(struct symset a, struct symset b)
864         {
865                 int i;
866                 int diff = a.cnt - b.cnt;
867                 if (diff)
868                         return diff;
869                 for (i = 0; i < a.cnt; i++) {
870                         diff = (int)a.syms[i] - (int)b.syms[i];
871                         if (diff)
872                                 return diff;
873                 }
874                 return 0;
875         }
876
877         static int save_set(struct grammar *g, struct symset ss)
878         {
879                 struct setlist **sl = &g->sets;
880                 int cmp = 1;
881                 struct setlist *s;
882
883                 while (*sl && (cmp = ss_cmp((*sl)->ss, ss)) < 0)
884                         sl = & (*sl)->next;
885                 if (cmp == 0) {
886                         symset_free(ss);
887                         return (*sl)->num;
888                 }
889
890                 s = malloc(sizeof(*s));
891                 s->ss = ss;
892                 s->num = g->nextset;
893                 g->nextset += 1;
894                 s->next = *sl;
895                 *sl = s;
896                 return s->num;
897         }
898
899 Finding a set by number is currently performed by a simple linear
900 search.  If this turns out to hurt performance, we can store the sets in
901 a dynamic array like the productions.
902
903         static struct symset set_find(struct grammar *g, int num)
904         {
905                 struct setlist *sl = g->sets;
906                 while (sl && sl->num != num)
907                         sl = sl->next;
908                 return sl->ss;
909         }
910
911 ### Setting `nullable`
912
913 We set `nullable` on the head symbol for any production for which all
914 the body symbols (if any) are nullable.  As this is a recursive
915 definition, any change in the `nullable` setting means that we need to
916 re-evaluate where it needs to be set.
917
918 We simply loop around performing the same calculations until no more
919 changes happen.
920
921 ###### symbol fields
922         int nullable;
923
924 ###### functions
925         static void set_nullable(struct grammar *g)
926         {
927                 int check_again = 1;
928                 while (check_again) {
929                         int p;
930                         check_again = 0;
931                         for (p = 0; p < g->production_count; p++) {
932                                 struct production *pr = g->productions[p];
933                                 int s;
934
935                                 if (pr->head->nullable)
936                                         continue;
937                                 for (s = 0; s < pr->body_size; s++)
938                                         if (! pr->body[s]->nullable)
939                                                 break;
940                                 if (s == pr->body_size) {
941                                         pr->head->nullable = 1;
942                                         check_again = 1;
943                                 }
944                         }
945                 }
946         }
947
948 ### Building the `first` sets
949
950 When calculating what can follow a particular non-terminal, we will need
951 to know what the "first" terminal in any subsequent non-terminal might
952 be.  So we calculate the `first` set for every non-terminal and store
953 them in an array.  We don't bother recording the "first" set for
954 terminals as they are trivial.
955
956 As the "first" for one symbol might depend on the "first" of another, we
957 repeat the calculations until no changes happen, just like with
958 `set_nullable`.  This makes use of the fact that `symset_union` reports
959 if any change happens.
960
961 The core of this, which finds the "first" of part of a production body,
962 will be reused for computing the "follow" sets, so we split that out
963 into a separate function, `add_first`, which also reports if it got all
964 the way to the end of the production without finding a non-nullable
965 symbol.
966
967 ###### grammar fields
968         struct symset *first;
969
970 ###### functions
971
972         static int add_first(struct production *pr, int start,
973                              struct symset *target, struct grammar *g,
974                              int *to_end)
975         {
976                 int s;
977                 int changed = 0;
978                 for (s = start; s < pr->body_size; s++) {
979                         struct symbol *bs = pr->body[s];
980                         if (bs->type == Terminal) {
981                                 if (symset_find(target, bs->num) < 0) {
982                                         symset_add(target, bs->num, 0);
983                                         changed = 1;
984                                 }
985                                 break;
986                         } else if (symset_union(target, &g->first[bs->num]))
987                                 changed = 1;
988                         if (!bs->nullable)
989                                 break;
990                 }
991                 if (to_end)
992                         *to_end = (s == pr->body_size);
993                 return changed;
994         }
995
996         static void build_first(struct grammar *g)
997         {
998                 int check_again = 1;
999                 int s;
1000                 g->first = calloc(g->num_syms, sizeof(g->first[0]));
1001                 for (s = 0; s < g->num_syms; s++)
1002                         g->first[s] = INIT_SYMSET;
1003
1004                 while (check_again) {
1005                         int p;
1006                         check_again = 0;
1007                         for (p = 0; p < g->production_count; p++) {
1008                                 struct production *pr = g->productions[p];
1009                                 struct symset *head = &g->first[pr->head->num];
1010
1011                                 if (add_first(pr, 0, head, g, NULL))
1012                                         check_again = 1;
1013                         }
1014                 }
1015         }
1016
1017 ### Building the `follow` sets.
1018
1019 There are two different situations when we will want to generate
1020 "follow" sets.  If we are doing an SLR analysis, we want to generate a
1021 single "follow" set for each non-terminal in the grammar.  That is what
1022 is happening here.  If we are doing an LALR or LR analysis we will want
1023 to generate a separate "LA" set for each item.  We do that later in
1024 state generation.
1025
1026 There are two parts to generating a "follow" set.  Firstly we look at
1027 every place that any non-terminal appears in the body of any production,
1028 and we find the set of possible "first" symbols after there.  This is
1029 done using `add_first` above and only needs to be done once as the
1030 "first" sets are now stable and will not change.
1031
1032 ###### grammar fields
1033         struct symset *follow;
1034
1035 ###### follow code
1036
1037         for (p = 0; p < g->production_count; p++) {
1038                 struct production *pr = g->productions[p];
1039                 int b;
1040
1041                 for (b = 0; b < pr->body_size - 1; b++) {
1042                         struct symbol *bs = pr->body[b];
1043                         if (bs->type == Terminal)
1044                                 continue;
1045                         add_first(pr, b+1, &g->follow[bs->num], g, NULL);
1046                 }
1047         }
1048
1049 The second part is to add the "follow" set of the head of a production
1050 to the "follow" sets of the final symbol in the production, and any
1051 other symbol which is followed only by `nullable` symbols.  As this
1052 depends on "follow" itself we need to repeatedly perform the process
1053 until no further changes happen.
1054
1055 Rather than 2 nested loops, one that repeats the whole process until
1056 there is no change, and one that iterates of the set of productions, we
1057 combine these two functions into a single loop.
1058
1059 ###### follow code
1060
1061         for (check_again = 0, p = 0;
1062              p < g->production_count;
1063              p < g->production_count-1
1064                 ? p++ : check_again ? (check_again = 0, p = 0)
1065                               : p++) {
1066                 struct production *pr = g->productions[p];
1067                 int b;
1068
1069                 for (b = pr->body_size - 1; b >= 0; b--) {
1070                         struct symbol *bs = pr->body[b];
1071                         if (bs->type == Terminal)
1072                                 break;
1073                         if (symset_union(&g->follow[bs->num],
1074                                          &g->follow[pr->head->num]))
1075                                 check_again = 1;
1076                         if (!bs->nullable)
1077                                 break;
1078                 }
1079         }
1080
1081 We now just need to create and initialise the `follow` list to get a
1082 complete function.
1083
1084 ###### functions
1085         static void build_follow(struct grammar *g)
1086         {
1087                 int s, check_again, p;
1088                 g->follow = calloc(g->num_syms, sizeof(g->follow[0]));
1089                 for (s = 0; s < g->num_syms; s++)
1090                         g->follow[s] = INIT_SYMSET;
1091                 ## follow code
1092         }
1093
1094 ### Building itemsets and states
1095
1096 There are three different levels of detail that can be chosen for
1097 building the itemsets and states for the LR grammar.  They are:
1098
1099 1. LR(0), LR(0.5), or SLR(1), where no look-ahead is included in the
1100    itemsets - look-ahead, if used at all, is simply the 'follow' sets
1101    already computed,
1102 2. LALR(1) where we build look-ahead sets with each item and merge
1103    the LA sets when we find two paths to the same "kernel" set of items.
1104 3. LR(1) where different look-ahead for any item in the set means
1105    a different item set must be created.
1106
1107 ###### forward declarations
1108         enum grammar_type { LR0, LR05, SLR, LALR, LR1 };
1109
1110 We need to be able to look through existing states to see if a newly
1111 generated state already exists.  For now we use a simple sorted linked
1112 list.
1113
1114 An item is a pair of numbers: the production number and the position of
1115 "DOT", which is an index into the body of the production.  As the
1116 numbers are not enormous we can combine them into a single "short" and
1117 store them in a `symset` - 5 bits for "DOT" and 11 bits for the
1118 production number (so 2000 productions with maximum of 31 symbols in the
1119 body).
1120
1121 Comparing the itemsets will be a little different to comparing symsets
1122 as we want to do the lookup after generating the "kernel" of an
1123 itemset, so we need to ignore the offset=zero items which are added during
1124 completion.
1125
1126 To facilitate this, we modify the "DOT" number so that "0" sorts to
1127 the end of the list in the symset, and then only compare items before
1128 the first "0".
1129
1130 ###### declarations
1131         static inline unsigned short item_num(int production, int dot)
1132         {
1133                 return production | ((31-dot) << 11);
1134         }
1135         static inline int item_prod(unsigned short item)
1136         {
1137                 return item & 0x7ff;
1138         }
1139         static inline int item_dot(unsigned short item)
1140         {
1141                 return (31-(item >> 11)) & 0x1f;
1142         }
1143
1144 For LR(1) analysis we need to compare not just the itemset in a state
1145 but also the LA sets.  As we assign each unique LA set a number, we
1146 can just compare the symset and the data values together.
1147
1148 ###### functions
1149         static int itemset_cmp(struct symset a, struct symset b,
1150                                enum grammar_type type)
1151         {
1152                 int i;
1153                 int av, bv;
1154
1155                 for (i = 0;
1156                      i < a.cnt && i < b.cnt &&
1157                      item_dot(a.syms[i]) > 0 &&
1158                      item_dot(b.syms[i]) > 0;
1159                      i++) {
1160                         int diff = a.syms[i] - b.syms[i];
1161                         if (diff)
1162                                 return diff;
1163                         if (type == LR1) {
1164                                 diff = a.data[i] - b.data[i];
1165                                 if (diff)
1166                                         return diff;
1167                         }
1168                 }
1169                 if (i == a.cnt || item_dot(a.syms[i]) == 0)
1170                         av = -1;
1171                 else
1172                         av = a.syms[i];
1173                 if (i == b.cnt || item_dot(b.syms[i]) == 0)
1174                         bv = -1;
1175                 else
1176                         bv = b.syms[i];
1177                 if (av - bv)
1178                         return av - bv;
1179                 if (type < LR1 || av == -1)
1180                         return 0;
1181                 return
1182                         a.data[i] - b.data[i];
1183         }
1184
1185 It will be helpful to know if an itemset has been "completed" or not,
1186 particularly for LALR where itemsets get merged, at which point they
1187 need to be consider for completion again.  So a `completed` flag is
1188 needed.
1189
1190 And now we can build the list of itemsets.  The lookup routine returns
1191 both a success flag and a pointer to where in the list an insert should
1192 happen, so we don't need to search a second time.
1193
1194 ###### declarations
1195         struct itemset {
1196                 struct itemset *next;
1197                 short state;
1198                 struct symset items;
1199                 struct symset go_to;
1200                 enum assoc assoc;
1201                 unsigned short precedence;
1202                 char completed;
1203         };
1204
1205 ###### grammar fields
1206         struct itemset *items;
1207         int states;
1208
1209 ###### functions
1210         static int itemset_find(struct grammar *g, struct itemset ***where,
1211                                 struct symset kernel, enum grammar_type type)
1212         {
1213                 struct itemset **ip;
1214
1215                 for (ip = &g->items; *ip ; ip = & (*ip)->next) {
1216                         struct itemset *i = *ip;
1217                         int diff;
1218                         diff = itemset_cmp(i->items, kernel, type);
1219                         if (diff < 0)
1220                                 continue;
1221                         if (diff > 0)
1222                                 break;
1223                         /* found */
1224                         *where = ip;
1225                         return 1;
1226                 }
1227                 *where = ip;
1228                 return 0;
1229         }
1230
1231 Adding an itemset may require merging the LA sets if LALR analysis is
1232 happening.  If any new LA set adds any symbols that weren't in the old
1233 LA set, we clear the `completed` flag so that the dependants of this
1234 itemset will be recalculated and their LA sets updated.
1235
1236 `add_itemset` must consume the symsets it is passed, either by adding
1237 them to a data structure, of freeing them.
1238
1239         static int add_itemset(struct grammar *g, struct symset ss,
1240                                enum assoc assoc, unsigned short precedence,
1241                                enum grammar_type type)
1242         {
1243                 struct itemset **where, *is;
1244                 int i;
1245                 int found = itemset_find(g, &where, ss, type);
1246                 if (!found) {
1247                         is = calloc(1, sizeof(*is));
1248                         is->state = g->states;
1249                         g->states += 1;
1250                         is->items = ss;
1251                         is->assoc = assoc;
1252                         is->precedence = precedence;
1253                         is->next = *where;
1254                         is->go_to = INIT_DATASET;
1255                         *where = is;
1256                         return is->state;
1257                 }
1258                 is = *where;
1259                 if (type != LALR) {
1260                         symset_free(ss);
1261                         return is->state;
1262                 }
1263                 for (i = 0; i < ss.cnt; i++) {
1264                         struct symset temp = INIT_SYMSET, s;
1265                         if (ss.data[i] == is->items.data[i])
1266                                 continue;
1267                         s = set_find(g, is->items.data[i]);
1268                         symset_union(&temp, &s);
1269                         s = set_find(g, ss.data[i]);
1270                         if (symset_union(&temp, &s)) {
1271                                 is->items.data[i] = save_set(g, temp);
1272                                 is->completed = 0;
1273                         } else
1274                                 symset_free(temp);
1275                 }
1276                 symset_free(ss);
1277                 return is->state;
1278         }
1279
1280 #### The build
1281
1282 To build all the itemsets, we first insert the initial itemset made from
1283 production zero, complete each itemset, and then generate new itemsets
1284 from old until no new ones can be made.
1285
1286 Completing an itemset means finding all the items where "DOT" is
1287 followed by a nonterminal and adding "DOT=0" items for every production
1288 from that non-terminal - providing each item hasn't already been added.
1289 When we add such an item it might get inserted before the current
1290 one, so to make sure we process it we reset the loop counter to the
1291 start.
1292
1293 If LA sets are needed, the LA set for each new item is found using
1294 `add_first` which was developed earlier for `FIRST` and `FOLLOW`.  This
1295 may be supplemented by the LA set for the item which produced the new
1296 item.
1297
1298 We also collect a set of all symbols which follow "DOT" (in `done`) as
1299 this is used in the next stage.
1300
1301 When itemsets are created we assign a precedence to the itemset from the
1302 complete item, if there is one.  We ignore the possibility of there
1303 being two and don't (currently) handle precedence in such grammars.
1304 When completing a grammar we ignore any item where DOT is followed by a
1305 terminal with a precedence lower than that for the itemset.  Unless the
1306 terminal has right associativity, we also ignore items where the
1307 terminal has the same precedence.  The result is that unwanted items are
1308 still in the itemset, but the terminal doesn't get into the go to set,
1309 so the item is ineffective.
1310
1311 ###### complete itemset
1312         for (i = 0; i < is->items.cnt; i++) {
1313                 int p = item_prod(is->items.syms[i]);
1314                 int bs = item_dot(is->items.syms[i]);
1315                 struct production *pr = g->productions[p];
1316                 int p2;
1317                 struct symbol *s;
1318                 struct symset LA = INIT_SYMSET;
1319                 unsigned short sn = 0;
1320
1321                 if (bs == pr->body_size)
1322                         continue;
1323                 s = pr->body[bs];
1324                 if (s->precedence && is->precedence &&
1325                     is->precedence > s->precedence)
1326                         /* This terminal has a low precedence and
1327                          * shouldn't be shifted
1328                          */
1329                         continue;
1330                 if (s->precedence && is->precedence &&
1331                     is->precedence == s->precedence && s->assoc != Right)
1332                         /* This terminal has a matching precedence and is
1333                          * not Right-associative, so we mustn't shift it.
1334                          */
1335                         continue;
1336                 if (symset_find(&done, s->num) < 0)
1337                         symset_add(&done, s->num, 0);
1338
1339                 if (s->type != Nonterminal)
1340                         continue;
1341                 check_again = 1;
1342                 if (type >= LALR) {
1343                         // Need the LA set.
1344                         int to_end;
1345                         add_first(pr, bs+1, &LA, g, &to_end);
1346                         if (to_end) {
1347                                 struct symset ss = set_find(g, is->items.data[i]);
1348                                 symset_union(&LA, &ss);
1349                         }
1350                         sn = save_set(g, LA);
1351                         LA = set_find(g, sn);
1352                 }
1353
1354                 /* Add productions for this symbol */
1355                 for (p2 = s->first_production;
1356                      p2 < g->production_count &&
1357                       g->productions[p2]->head == s;
1358                      p2++) {
1359                         int itm = item_num(p2, 0);
1360                         int pos = symset_find(&is->items, itm);
1361                         if (pos < 0) {
1362                                 symset_add(&is->items, itm, sn);
1363                                 /* Will have re-ordered, so start
1364                                  * from beginning again */
1365                                 i = -1;
1366                         } else if (type >= LALR) {
1367                                 struct symset ss = set_find(g, is->items.data[pos]);
1368                                 struct symset tmp = INIT_SYMSET;
1369                                 struct symset *la = &LA;
1370
1371                                 symset_union(&tmp, &ss);
1372                                 if (symset_union(&tmp, la)) {
1373                                         is->items.data[pos] = save_set(g, tmp);
1374                                         i = -1;
1375                                 } else
1376                                         symset_free(tmp);
1377                         }
1378                 }
1379         }
1380
1381 For each symbol we found (and placed in `done`) we collect all the items
1382 for which this symbol is next, and create a new itemset with "DOT"
1383 advanced over the symbol.  This is then added to the collection of
1384 itemsets (or merged with a pre-existing itemset).
1385
1386 ###### derive itemsets
1387         // Now we have a completed itemset, so we need to
1388         // compute all the 'next' itemsets and create them
1389         // if they don't exist.
1390         for (i = 0; i < done.cnt; i++) {
1391                 int j;
1392                 unsigned short state;
1393                 struct symbol *sym = g->symtab[done.syms[i]];
1394                 enum assoc assoc = Non;
1395                 unsigned short precedence = 0;
1396                 struct symset newitemset = INIT_SYMSET;
1397                 if (type >= LALR)
1398                         newitemset = INIT_DATASET;
1399
1400                 for (j = 0; j < is->items.cnt; j++) {
1401                         int itm = is->items.syms[j];
1402                         int p = item_prod(itm);
1403                         int bp = item_dot(itm);
1404                         struct production *pr = g->productions[p];
1405                         unsigned short la = 0;
1406                         int pos;
1407
1408                         if (bp == pr->body_size)
1409                                 continue;
1410                         if (pr->body[bp] != sym)
1411                                 continue;
1412
1413                         bp += 1;
1414                         if (type >= LALR)
1415                                 la = is->items.data[j];
1416                         if (bp == pr->body_size &&
1417                             pr->precedence > 0 &&
1418                             pr->precedence > precedence) {
1419                                 // new itemset is reducible and has a precedence.
1420                                 precedence = pr->precedence;
1421                                 assoc = pr->assoc;
1422                         }
1423                         pos = symset_find(&newitemset, item_num(p, bp));
1424
1425                         if (pos < 0)
1426                                 symset_add(&newitemset, item_num(p, bp), la);
1427                         else if (type >= LALR) {
1428                                 // Need to merge la set.
1429                                 int la2 = newitemset.data[pos];
1430                                 if (la != la2) {
1431                                         struct symset ss = set_find(g, la2);
1432                                         struct symset LA = INIT_SYMSET;
1433                                         symset_union(&LA, &ss);
1434                                         ss = set_find(g, la);
1435                                         if (symset_union(&LA, &ss))
1436                                                 newitemset.data[pos] = save_set(g, LA);
1437                                         else
1438                                                 symset_free(LA);
1439                                 }
1440                         }
1441                 }
1442                 state = add_itemset(g, newitemset, assoc, precedence, type);
1443                 if (symset_find(&is->go_to, done.syms[i]) < 0)
1444                         symset_add(&is->go_to, done.syms[i], state);
1445         }
1446
1447 All that is left is to create the initial itemset from production zero, and
1448 with `TK_eof` as the LA set.
1449
1450 ###### functions
1451         static void build_itemsets(struct grammar *g, enum grammar_type type)
1452         {
1453                 struct symset first = INIT_SYMSET;
1454                 struct itemset *is;
1455                 int check_again;
1456                 unsigned short la = 0;
1457                 if (type >= LALR) {
1458                         // LA set just has eof
1459                         struct symset eof = INIT_SYMSET;
1460                         symset_add(&eof, TK_eof, 0);
1461                         la = save_set(g, eof);
1462                         first = INIT_DATASET;
1463                 }
1464                 // production 0, offset 0 (with no data)
1465                 symset_add(&first, item_num(0, 0), la);
1466                 add_itemset(g, first, Non, 0, type);
1467                 for (check_again = 0, is = g->items;
1468                      is;
1469                      is = is->next ?: check_again ? (check_again = 0, g->items) : NULL) {
1470                         int i;
1471                         struct symset done = INIT_SYMSET;
1472                         if (is->completed)
1473                                 continue;
1474                         is->completed = 1;
1475                         check_again = 1;
1476                         ## complete itemset
1477                         ## derive itemsets
1478                         symset_free(done);
1479                 }
1480         }
1481
1482 ### Completing the analysis.
1483
1484 The exact process of analysis depends on which level was requested.  For
1485 `LR0` and `LR05` we don't need first and follow sets at all.  For `LALR` and
1486 `LR1` we need first, but not follow.  For `SLR` we need both.
1487
1488 We don't build the "action" tables that you might expect as the parser
1489 doesn't use them.  They will be calculated to some extent if needed for
1490 a report.
1491
1492 Once we have built everything we allocate arrays for the two lists:
1493 symbols and itemsets.  This allows more efficient access during
1494 reporting.  The symbols are grouped as terminals, then non-terminals,
1495 then virtual, with the start of non-terminals recorded as `first_nonterm`.
1496 Special terminals -- meaning just EOL -- are included with the
1497 non-terminals so that they are not expected by the scanner.
1498
1499 ###### grammar fields
1500         struct symbol **symtab;
1501         struct itemset **statetab;
1502         int first_nonterm;
1503
1504 ###### grammar_analyse
1505
1506         static void grammar_analyse(struct grammar *g, enum grammar_type type)
1507         {
1508                 struct symbol *s;
1509                 struct itemset *is;
1510                 int snum = TK_reserved;
1511                 for (s = g->syms; s; s = s->next)
1512                         if (s->num < 0 && s->type == Terminal && !s->isspecial) {
1513                                 s->num = snum;
1514                                 snum++;
1515                         }
1516                 g->first_nonterm = snum;
1517                 for (s = g->syms; s; s = s->next)
1518                         if (s->num < 0 && s->type != Virtual) {
1519                                 s->num = snum;
1520                                 snum++;
1521                         }
1522                 for (s = g->syms; s; s = s->next)
1523                         if (s->num < 0) {
1524                                 s->num = snum;
1525                                 snum++;
1526                         }
1527                 g->num_syms = snum;
1528                 g->symtab = calloc(g->num_syms, sizeof(g->symtab[0]));
1529                 for (s = g->syms; s; s = s->next)
1530                         g->symtab[s->num] = s;
1531
1532                 set_nullable(g);
1533                 if (type >= SLR)
1534                         build_first(g);
1535
1536                 if (type == SLR)
1537                         build_follow(g);
1538
1539                 build_itemsets(g, type);
1540
1541                 g->statetab = calloc(g->states, sizeof(g->statetab[0]));
1542                 for (is = g->items; is ; is = is->next)
1543                         g->statetab[is->state] = is;
1544         }
1545
1546 ## Reporting on the Grammar
1547
1548 The purpose of the report is to give the grammar developer insight into
1549 how the grammar parser will work.  It is basically a structured dump of
1550 all the tables that have been generated, plus a description of any conflicts.
1551
1552 ###### grammar_report
1553         static int grammar_report(struct grammar *g, enum grammar_type type)
1554         {
1555                 report_symbols(g);
1556                 if (g->follow)
1557                         report_follow(g);
1558                 report_itemsets(g);
1559                 return report_conflicts(g, type);
1560         }
1561
1562 Firstly we have the complete list of symbols, together with the
1563 "FIRST" set if that was generated.  We add a mark to each symbol to
1564 show if it is nullable (`.`).
1565
1566 ###### functions
1567
1568         static void report_symbols(struct grammar *g)
1569         {
1570                 int n;
1571                 if (g->first)
1572                         printf("SYMBOLS + FIRST:\n");
1573                 else
1574                         printf("SYMBOLS:\n");
1575
1576                 for (n = 0; n < g->num_syms; n++) {
1577                         struct symbol *s = g->symtab[n];
1578                         if (!s)
1579                                 continue;
1580
1581                         printf(" %c%3d%c: ",
1582                                s->nullable ? '.':' ',
1583                                s->num, symtypes[s->type]);
1584                         prtxt(s->name);
1585                         if (s->precedence)
1586                                 printf(" (%d%s)", s->precedence,
1587                                        assoc_names[s->assoc]);
1588
1589                         if (g->first && s->type == Nonterminal) {
1590                                 int j;
1591                                 char c = ':';
1592                                 for (j = 0; j < g->first[n].cnt; j++) {
1593                                         printf("%c ", c);
1594                                         c = ',';
1595                                         prtxt(g->symtab[g->first[n].syms[j]]->name);
1596                                 }
1597                         }
1598                         printf("\n");
1599                 }
1600         }
1601
1602 Then we have the follow sets if they were computed.
1603
1604         static void report_follow(struct grammar *g)
1605         {
1606                 int n;
1607                 printf("FOLLOW:\n");
1608                 for (n = 0; n < g->num_syms; n++)
1609                         if (g->follow[n].cnt) {
1610                                 int j;
1611                                 char c = ':';
1612                                 printf("  ");
1613                                 prtxt(g->symtab[n]->name);
1614                                 for (j = 0; j < g->follow[n].cnt; j++) {
1615                                         printf("%c ", c);
1616                                         c = ',';
1617                                         prtxt(g->symtab[g->follow[n].syms[j]]->name);
1618                                 }
1619                                 printf("\n");
1620                         }
1621         }
1622
1623 And finally the item sets.  These include the GO TO tables and, for
1624 LALR and LR1, the LA set for each item.  Lots of stuff, so we break
1625 it up a bit.  First the items, with production number and associativity.
1626
1627         static void report_item(struct grammar *g, int itm)
1628         {
1629                 int p = item_prod(itm);
1630                 int dot = item_dot(itm);
1631                 struct production *pr = g->productions[p];
1632                 int i;
1633
1634                 printf("    ");
1635                 prtxt(pr->head->name);
1636                 printf(" ->");
1637                 for (i = 0; i < pr->body_size; i++) {
1638                         printf(" %s", (dot == i ? ". ": ""));
1639                         prtxt(pr->body[i]->name);
1640                 }
1641                 if (dot == pr->body_size)
1642                         printf(" .");
1643                 printf(" [%d]", p);
1644                 if (pr->precedence && dot == pr->body_size)
1645                         printf(" (%d%s)", pr->precedence,
1646                                assoc_names[pr->assoc]);
1647                 if (dot < pr->body_size &&
1648                     pr->body[dot]->precedence) {
1649                         struct symbol *s = pr->body[dot];
1650                         printf(" [%d%s]", s->precedence,
1651                                assoc_names[s->assoc]);
1652                 }
1653                 printf("\n");
1654         }
1655
1656 The LA sets which are (possibly) reported with each item:
1657
1658         static void report_la(struct grammar *g, int lanum)
1659         {
1660                 struct symset la = set_find(g, lanum);
1661                 int i;
1662                 char c = ':';
1663
1664                 printf("        LOOK AHEAD(%d)", lanum);
1665                 for (i = 0; i < la.cnt; i++) {
1666                         printf("%c ", c);
1667                         c = ',';
1668                         prtxt(g->symtab[la.syms[i]]->name);
1669                 }
1670                 printf("\n");
1671         }
1672
1673 Then the go to sets:
1674
1675         static void report_goto(struct grammar *g, struct symset gt)
1676         {
1677                 int i;
1678                 printf("    GOTO:\n");
1679
1680                 for (i = 0; i < gt.cnt; i++) {
1681                         printf("      ");
1682                         prtxt(g->symtab[gt.syms[i]]->name);
1683                         printf(" -> %d\n", gt.data[i]);
1684                 }
1685         }
1686
1687 Now we can report all the item sets complete with items, LA sets, and GO TO.
1688
1689         static void report_itemsets(struct grammar *g)
1690         {
1691                 int s;
1692                 printf("ITEM SETS(%d)\n", g->states);
1693                 for (s = 0; s < g->states; s++) {
1694                         int j;
1695                         struct itemset *is = g->statetab[s];
1696                         printf("  Itemset %d:", s);
1697                         if (is->precedence)
1698                                 printf(" %d%s", is->precedence, assoc_names[is->assoc]);
1699                         printf("\n");
1700                         for (j = 0; j < is->items.cnt; j++) {
1701                                 report_item(g, is->items.syms[j]);
1702                                 if (is->items.data != NO_DATA)
1703                                         report_la(g, is->items.data[j]);
1704                         }
1705                         report_goto(g, is->go_to);
1706                 }
1707         }
1708
1709 ### Reporting conflicts
1710
1711 Conflict detection varies a lot among different analysis levels.  However
1712 LR0 and LR0.5 are quite similar - having no follow sets - and SLR, LALR and
1713 LR1 are also similar as they have FOLLOW or LA sets.
1714
1715 ###### functions
1716
1717         ## conflict functions
1718
1719         static int report_conflicts(struct grammar *g, enum grammar_type type)
1720         {
1721                 int cnt = 0;
1722                 printf("Conflicts:\n");
1723                 if (type < SLR)
1724                         cnt = conflicts_lr0(g, type);
1725                 else
1726                         cnt = conflicts_slr(g, type);
1727                 if (cnt == 0)
1728                         printf(" - no conflicts\n");
1729                 return cnt;
1730         }
1731
1732 LR0 conflicts are any state which have both a reducible item and
1733 a shiftable item, or two reducible items.
1734
1735 LR05 conflicts only occur if two possible reductions exist,
1736 as shifts always over-ride reductions.
1737
1738 ###### conflict functions
1739         static int conflicts_lr0(struct grammar *g, enum grammar_type type)
1740         {
1741                 int i;
1742                 int cnt = 0;
1743                 for (i = 0; i < g->states; i++) {
1744                         struct itemset *is = g->statetab[i];
1745                         int last_reduce = -1;
1746                         int prev_reduce = -1;
1747                         int last_shift = -1;
1748                         int j;
1749                         if (!is)
1750                                 continue;
1751                         for (j = 0; j < is->items.cnt; j++) {
1752                                 int itm = is->items.syms[j];
1753                                 int p = item_prod(itm);
1754                                 int bp = item_dot(itm);
1755                                 struct production *pr = g->productions[p];
1756
1757                                 if (bp == pr->body_size) {
1758                                         prev_reduce = last_reduce;
1759                                         last_reduce = j;
1760                                         continue;
1761                                 }
1762                                 if (pr->body[bp]->type == Terminal)
1763                                         last_shift = j;
1764                         }
1765                         if (type == LR0 && last_reduce >= 0 && last_shift >= 0) {
1766                                 printf("  State %d has both SHIFT and REDUCE:\n", i);
1767                                 report_item(g, is->items.syms[last_shift]);
1768                                 report_item(g, is->items.syms[last_reduce]);
1769                                 cnt++;
1770                         }
1771                         if (prev_reduce >= 0) {
1772                                 printf("  State %d has 2 (or more) reducible items\n", i);
1773                                 report_item(g, is->items.syms[prev_reduce]);
1774                                 report_item(g, is->items.syms[last_reduce]);
1775                                 cnt++;
1776                         }
1777                 }
1778                 return cnt;
1779         }
1780
1781 SLR, LALR, and LR1 conflicts happen if two reducible items have over-lapping
1782 look ahead, or if a symbol in a look-ahead can be shifted.  They differ only
1783 in the source of the look ahead set.
1784
1785 We build two datasets to reflect the "action" table: one which maps
1786 terminals to items where that terminal could be shifted and another
1787 which maps terminals to items that could be reduced when the terminal
1788 is in look-ahead.  We report when we get conflicts between the two.
1789
1790         static int conflicts_slr(struct grammar *g, enum grammar_type type)
1791         {
1792                 int i;
1793                 int cnt = 0;
1794
1795                 for (i = 0; i < g->states; i++) {
1796                         struct itemset *is = g->statetab[i];
1797                         struct symset shifts = INIT_DATASET;
1798                         struct symset reduce = INIT_DATASET;
1799                         int j;
1800                         if (!is)
1801                                 continue;
1802                         /* First collect the shifts */
1803                         for (j = 0; j < is->items.cnt; j++) {
1804                                 unsigned short itm = is->items.syms[j];
1805                                 int p = item_prod(itm);
1806                                 int bp = item_dot(itm);
1807                                 struct production *pr = g->productions[p];
1808                                 struct symbol *s;
1809
1810                                 if (bp >= pr->body_size ||
1811                                     pr->body[bp]->type != Terminal)
1812                                         /* not shiftable */
1813                                         continue;
1814
1815                                 s = pr->body[bp];
1816                                 if (s->precedence && is->precedence)
1817                                         /* Precedence resolves this, so no conflict */
1818                                         continue;
1819
1820                                 if (symset_find(&shifts, s->num) < 0)
1821                                         symset_add(&shifts, s->num, itm);
1822                         }
1823                         /* Now look for reductions and conflicts */
1824                         for (j = 0; j < is->items.cnt; j++) {
1825                                 unsigned short itm = is->items.syms[j];
1826                                 int p = item_prod(itm);
1827                                 int bp = item_dot(itm);
1828                                 struct production *pr = g->productions[p];
1829
1830                                 if (bp < pr->body_size)
1831                                         continue;
1832                                 /* reducible */
1833                                 struct symset la;
1834                                 if (type == SLR)
1835                                         la = g->follow[pr->head->num];
1836                                 else
1837                                         la = set_find(g, is->items.data[j]);
1838                                 int k;
1839                                 for (k = 0; k < la.cnt; k++) {
1840                                         int pos = symset_find(&shifts, la.syms[k]);
1841                                         if (pos >= 0) {
1842                                                 printf("  State %d has SHIFT/REDUCE conflict on ", i);
1843                                                 cnt++;
1844                                                         prtxt(g->symtab[la.syms[k]]->name);
1845                                                 printf(":\n");
1846                                                 report_item(g, shifts.data[pos]);
1847                                                 report_item(g, itm);
1848                                         }
1849                                         pos = symset_find(&reduce, la.syms[k]);
1850                                         if (pos < 0) {
1851                                                 symset_add(&reduce, la.syms[k], itm);
1852                                                 continue;
1853                                         }
1854                                         printf("  State %d has REDUCE/REDUCE conflict on ", i);
1855                                         prtxt(g->symtab[la.syms[k]]->name);
1856                                         printf(":\n");
1857                                         report_item(g, itm);
1858                                         report_item(g, reduce.data[pos]);
1859                                         cnt++;
1860                                 }
1861                         }
1862                         symset_free(shifts);
1863                         symset_free(reduce);
1864                 }
1865                 return cnt;
1866         }
1867
1868
1869 ## Generating the parser
1870
1871 The exported part of the parser is the `parse_XX` function, where the name
1872 `XX` is based on the name of the parser files.
1873
1874 This takes a `code_node`, a partially initialized `token_config`, and an
1875 optional `FILE` to send tracing to.  The `token_config` gets the list of
1876 known words added and then is used with the `code_node` to initialize the
1877 scanner.
1878
1879 `parse_XX` then calls the library function `parser_run` to actually complete
1880 the parse.  This needs the `states` table and functions to call the various
1881 pieces of code provided in the grammar file, so they are generated first.
1882
1883 ###### parser_generate
1884
1885         static void gen_parser(FILE *f, struct grammar *g, char *file, char *name,
1886                                struct code_node *pre_reduce)
1887         {
1888                 gen_known(f, g);
1889                 gen_non_term(f, g);
1890                 gen_goto(f, g);
1891                 gen_states(f, g);
1892                 gen_reduce(f, g, file, pre_reduce);
1893                 gen_free(f, g);
1894
1895                 fprintf(f, "#line 0 \"gen_parser\"\n");
1896                 fprintf(f, "void *parse_%s(struct code_node *code, struct token_config *config, FILE *trace)\n",
1897                         name);
1898                 fprintf(f, "{\n");
1899                 fprintf(f, "\tstruct token_state *tokens;\n");
1900                 fprintf(f, "\tconfig->words_marks = known;\n");
1901                 fprintf(f, "\tconfig->known_count = sizeof(known)/sizeof(known[0]);\n");
1902                 fprintf(f, "\ttokens = token_open(code, config);\n");
1903                 fprintf(f, "\tvoid *rv = parser_run(tokens, states, do_reduce, do_free, trace, non_term, config);\n");
1904                 fprintf(f, "\ttoken_close(tokens);\n");
1905                 fprintf(f, "\treturn rv;\n");
1906                 fprintf(f, "}\n\n");
1907         }
1908
1909 ### Known words table
1910
1911 The known words table is simply an array of terminal symbols.
1912 The table of nonterminals used for tracing is a similar array.
1913
1914 ###### functions
1915
1916         static void gen_known(FILE *f, struct grammar *g)
1917         {
1918                 int i;
1919                 fprintf(f, "#line 0 \"gen_known\"\n");
1920                 fprintf(f, "static const char *known[] = {\n");
1921                 for (i = TK_reserved;
1922                      i < g->num_syms && g->symtab[i]->type == Terminal;
1923                      i++)
1924                         fprintf(f, "\t\"%.*s\",\n", g->symtab[i]->name.len,
1925                                 g->symtab[i]->name.txt);
1926                 fprintf(f, "};\n\n");
1927         }
1928
1929         static void gen_non_term(FILE *f, struct grammar *g)
1930         {
1931                 int i;
1932                 fprintf(f, "#line 0 \"gen_non_term\"\n");
1933                 fprintf(f, "static const char *non_term[] = {\n");
1934                 for (i = TK_reserved;
1935                      i < g->num_syms;
1936                      i++)
1937                         if (g->symtab[i]->type == Nonterminal ||
1938                             g->symtab[i]->isspecial)
1939                                 fprintf(f, "\t\"%.*s\",\n", g->symtab[i]->name.len,
1940                                         g->symtab[i]->name.txt);
1941                 fprintf(f, "};\n\n");
1942         }
1943
1944 ### States and the goto tables.
1945
1946 For each state we record the goto table and details of the reducible
1947 production if there is one.
1948 Some of the details of the reducible production are stored in the
1949 `do_reduce` function to come later.  Here we store the production
1950 number, the body size (useful for stack management), and the resulting
1951 symbol (useful for knowing how to free data later).
1952
1953 The go to table is stored in a simple array of `sym` and corresponding
1954 `state`.
1955
1956 ###### exported types
1957
1958         struct lookup {
1959                 short sym;
1960                 short state;
1961         };
1962         struct state {
1963                 short go_to_cnt;
1964                 const struct lookup * go_to;
1965                 short reduce_prod;
1966                 short reduce_size;
1967                 short reduce_sym;
1968                 short result_size;
1969         };
1970
1971 ###### functions
1972
1973         static void gen_goto(FILE *f, struct grammar *g)
1974         {
1975                 int i;
1976                 fprintf(f, "#line 0 \"gen_goto\"\n");
1977                 for (i = 0; i < g->states; i++) {
1978                         struct symset gt = g->statetab[i]->go_to;
1979                         int j;
1980
1981                         if (gt.cnt == 0)
1982                                 continue;
1983                         fprintf(f, "static const struct lookup goto_%d[] = {\n",
1984                                 i);
1985                         for (j = 0; j < gt.cnt; j++)
1986                                 fprintf(f, "\t{ %d, %d },\n",
1987                                         gt.syms[j], gt.data[j]);
1988                         fprintf(f, "};\n");
1989                 }
1990         }
1991
1992         static void gen_states(FILE *f, struct grammar *g)
1993         {
1994                 int i;
1995                 fprintf(f, "#line 0 \"gen_states\"\n");
1996                 fprintf(f, "static const struct state states[] = {\n");
1997                 for (i = 0; i < g->states; i++) {
1998                         struct itemset *is = g->statetab[i];
1999                         int j, prod = -1, prod_len;
2000
2001                         for (j = 0; j < is->items.cnt; j++) {
2002                                 int itm = is->items.syms[j];
2003                                 int p = item_prod(itm);
2004                                 int bp = item_dot(itm);
2005                                 struct production *pr = g->productions[p];
2006
2007                                 if (bp < pr->body_size)
2008                                         continue;
2009                                 /* This is what we reduce - choose longest */
2010                                 if (prod < 0 || prod_len < pr->body_size) {
2011                                         prod = p;
2012                                         prod_len = pr->body_size;
2013                                 }
2014                         }
2015                         if (is->go_to.cnt)
2016                                 fprintf(f, "\t[%d] = { %d, goto_%d, ",
2017                                         i, is->go_to.cnt, i);
2018                         else
2019                                 fprintf(f, "\t[%d] = { 0, NULL, ", i);
2020                         if (prod >= 0) {
2021                                 struct production *pr = g->productions[prod];
2022                                 struct symbol *hd = pr->head;
2023                                 fprintf(f, "%d, %d, %d, ", 
2024                                         prod, pr->body_size, pr->head->num);
2025                                 if (hd->struct_name.txt == NULL)
2026                                         fprintf(f, "0 },\n");
2027                                 else
2028                                         fprintf(f, "sizeof(struct %.*s%s) },\n",
2029                                                 hd->struct_name.len,
2030                                                 hd->struct_name.txt,
2031                                                 hd->isref ? "*" : "");
2032                         } else
2033                                 fprintf(f, "-1, -1, -1, -1 },\n");
2034                 }
2035                 fprintf(f, "};\n\n");
2036         }
2037
2038 ### The `do_reduce` function and the code
2039
2040 When the parser engine decides to reduce a production, it calls
2041 `do_reduce` which runs the code that was included with the production,
2042 if any.
2043
2044 This code needs to be able to store data somewhere so we record the size
2045 of the data expected with each state so it can be allocated before
2046 `do_reduce` is called.
2047
2048 In order for the code to access "global" context, we pass in the
2049 "config" pointer that was passed to the parser function.  If the `struct
2050 token_config` is embedded in some larger structure, the reducing code
2051 can access the larger structure using pointer manipulation.  Performing
2052 that pointer manipulation, and any other common code or variables for
2053 all reduce actions, can be provided in code node called "reduce" which
2054 is passed around in `pre_reduce` which you might have already noticed.
2055
2056 The code fragments require translation when written out.  Any `$N` needs
2057 to be converted to a reference either to that buffer (if `$0`) or to the
2058 structure returned by a previous reduction.  These pointers need to be
2059 cast to the appropriate type for each access.  All this is handled in
2060 `gen_code`.
2061
2062 `gen_code` also allows symbol references to contain a '`<`' as in
2063 '`$<2`'.  This is particularly useful for references (or pointers), but
2064 can be used with structures too.  The `<` implies that the value is
2065 being moved out, so the object will not be automatically freed.  It is
2066 equivalent to assigning `NULL` to the pointer or filling a structure
2067 with zeros.
2068
2069 Instead of a number `N`, the `$` or `$<` can be followed by some letters
2070 and possibly a number.  A number by itself (other than zero) selects a
2071 symbol from the body of the production.  A sequence of letters selects
2072 the shortest symbol in the body which contains those letters in the
2073 given order.  If a number follows the letters, then a later occurrence
2074 of that symbol is chosen.  So "`$AB2`" will refer to the structure
2075 attached to the second occurrence of the shortest symbol which contains
2076 an `A` followed by a `B`.  If there is no unique shortest system, or if
2077 the number given is too large, then the symbol reference is not
2078 transformed, and will cause an error when the code is compiled.
2079
2080 ###### functions
2081
2082         static int textchr(struct text t, char c, int s)
2083         {
2084                 int i;
2085                 for (i = s; i < t.len; i++)
2086                         if (t.txt[i] == c)
2087                                 return i;
2088                 return -1;
2089         }
2090
2091         static int subseq_match(char *seq, int slen, struct text name)
2092         {
2093                 int st = 0;
2094                 while (slen > 0) {
2095                         st = textchr(name, *seq, st);
2096                         if (st < 0)
2097                                 return 0;
2098                         slen -= 1;
2099                         seq += 1;
2100                         st += 1;
2101                 }
2102                 return 1;
2103         }
2104
2105         static int choose_sym(char **namep, int len, struct production *p)
2106         {
2107                 char *name = *namep;
2108                 char *nam = name;
2109                 int namlen;
2110                 int n = 0;
2111                 int i, s, slen;
2112                 char c;
2113
2114                 c = *name;
2115                 while (len > 0 &&
2116                        ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'))) {
2117                         name += 1;
2118                         len -= 1;
2119                         c = *name;
2120                 }
2121                 namlen = name-nam;
2122                 while (len > 0 && (c >= '0' && c <= '9')) {
2123                         name += 1;
2124                         len -= 1;
2125                         n = n * 10 + (c - '0');
2126                         c = *name;
2127                 }
2128                 if (namlen == 0) {
2129                         if (name == *namep || n > p->body_size)
2130                                 return -1;
2131                         *namep = name;
2132                         return n;
2133                 }
2134                 slen = 0; s = -1;
2135                 for (i = 0; i < p->body_size; i++) {
2136                         if (!subseq_match(nam, namlen, p->body[i]->name))
2137                                 continue;
2138                         if (slen == 0 || p->body[i]->name.len < slen) {
2139                                 s = i;
2140                                 slen = p->body[i]->name.len;
2141                         }
2142                         if (s >= 0 && p->body[i] != p->body[s] &&
2143                             p->body[i]->name.len == p->body[s]->name.len)
2144                                 /* not unique, so s cannot be used */
2145                                 s = -1;
2146                 }
2147                 if (s < 0)
2148                         return -1;
2149                 if (n == 0)
2150                         n = 1;
2151                 for (i = 0; i < p->body_size; i++)
2152                         if (p->body[i] == p->body[s]) {
2153                                 n -= 1;
2154                                 if (n == 0)
2155                                         break;
2156                         }
2157                 if (n > 0 || i == p->body_size)
2158                         return -1;
2159                 *namep = name;
2160                 return i + 1;
2161         }
2162
2163         static void gen_code(struct production *p, FILE *f, struct grammar *g)
2164         {
2165                 char *c;
2166                 char *used = calloc(1, p->body_size);
2167                 int i;
2168
2169                 fprintf(f, "\t\t\t");
2170                 for (c = p->code.txt; c < p->code.txt + p->code.len; c++) {
2171                         int n;
2172                         int use = 0;
2173                         if (*c != '$') {
2174                                 fputc(*c, f);
2175                                 if (*c == '\n')
2176                                         fputs("\t\t\t", f);
2177                                 continue;
2178                         }
2179                         c++;
2180                         if (*c == '<') {
2181                                 use = 1;
2182                                 c++;
2183                         }
2184                         n = choose_sym(&c, p->code.txt + p->code.len - c, p);
2185                         if (n < 0) {
2186                                 fputc('$', f);
2187                                 if (use)
2188                                         fputc('<', f);
2189                                 fputc(*c, f);
2190                                 continue;
2191                         }
2192                         if (n == 0)
2193                                 fprintf(f, "(*(struct %.*s*%s)ret)",
2194                                         p->head->struct_name.len,
2195                                         p->head->struct_name.txt,
2196                                         p->head->isref ? "*":"");
2197                         else if (p->body[n-1]->type == Terminal)
2198                                 fprintf(f, "(*(struct token *)body[%d])",
2199                                         n-1);
2200                         else if (p->body[n-1]->struct_name.txt == NULL)
2201                                 fprintf(f, "$%d", n);
2202                         else {
2203                                 fprintf(f, "(*(struct %.*s*%s)body[%d])",
2204                                         p->body[n-1]->struct_name.len,
2205                                         p->body[n-1]->struct_name.txt,
2206                                         p->body[n-1]->isref ? "*":"", n-1);
2207                                 used[n-1] = use;
2208                         }
2209                         c -= 1;
2210                 }
2211                 fputs("\n", f);
2212                 for (i = 0; i < p->body_size; i++) {
2213                         if (p->body[i]->struct_name.txt &&
2214                             used[i]) {
2215                                 // assume this has been copied out
2216                                 if (p->body[i]->isref)
2217                                         fprintf(f, "\t\t*(void**)body[%d] = NULL;\n", i);
2218                                 else
2219                                         fprintf(f, "\t\tmemset(body[%d], 0, sizeof(struct %.*s));\n", i, p->body[i]->struct_name.len, p->body[i]->struct_name.txt);
2220                         }
2221                 }
2222                 free(used);
2223         }
2224
2225 ###### functions
2226
2227         static void gen_reduce(FILE *f, struct grammar *g, char *file,
2228                                struct code_node *pre_reduce)
2229         {
2230                 int i;
2231                 fprintf(f, "#line 1 \"gen_reduce\"\n");
2232                 fprintf(f, "static int do_reduce(int prod, void **body, struct token_config *config, void *ret)\n");
2233                 fprintf(f, "{\n");
2234                 fprintf(f, "\tint ret_size = 0;\n");
2235                 if (pre_reduce)
2236                         code_node_print(f, pre_reduce, file);
2237
2238                 fprintf(f, "#line 4 \"gen_reduce\"\n");
2239                 fprintf(f, "\tswitch(prod) {\n");
2240                 for (i = 0; i < g->production_count; i++) {
2241                         struct production *p = g->productions[i];
2242                         fprintf(f, "\tcase %d:\n", i);
2243
2244                         if (p->code.txt) {
2245                                 fprintf(f, "#line %d \"%s\"\n", p->code_line, file);
2246                                 gen_code(p, f, g);
2247                         }
2248
2249                         if (p->head->struct_name.txt)
2250                                 fprintf(f, "\t\tret_size = sizeof(struct %.*s%s);\n",
2251                                         p->head->struct_name.len,
2252                                         p->head->struct_name.txt,
2253                                         p->head->isref ? "*":"");
2254
2255                         fprintf(f, "\t\tbreak;\n");
2256                 }
2257                 fprintf(f, "\t}\n\treturn ret_size;\n}\n\n");
2258         }
2259
2260 ### `do_free`
2261
2262 As each non-terminal can potentially cause a different type of data
2263 structure to be allocated and filled in, we need to be able to free it when
2264 done.
2265
2266 It is particularly important to have fine control over freeing during error
2267 recovery where individual stack frames might need to be freed.
2268
2269 For this, the grammar author is required to defined a `free_XX` function for
2270 each structure that is used by a non-terminal.  `do_free` will call whichever
2271 is appropriate given a symbol number, and will call `free` (as is
2272 appropriate for tokens) on any terminal symbol.
2273
2274 ###### functions
2275
2276         static void gen_free(FILE *f, struct grammar *g)
2277         {
2278                 int i;
2279
2280                 fprintf(f, "#line 0 \"gen_free\"\n");
2281                 fprintf(f, "static void do_free(short sym, void *asn)\n");
2282                 fprintf(f, "{\n");
2283                 fprintf(f, "\tif (!asn) return;\n");
2284                 fprintf(f, "\tif (sym < %d", g->first_nonterm);
2285                 /* Need to handle special terminals too */
2286                 for (i = 0; i < g->num_syms; i++) {
2287                         struct symbol *s = g->symtab[i];
2288                         if (i >= g->first_nonterm && s->type == Terminal &&
2289                             s->isspecial)
2290                                 fprintf(f, " || sym == %d", s->num);
2291                 }
2292                 fprintf(f, ") {\n");
2293                 fprintf(f, "\t\tfree(asn);\n\t\treturn;\n\t}\n");
2294                 fprintf(f, "\tswitch(sym) {\n");
2295
2296                 for (i = 0; i < g->num_syms; i++) {
2297                         struct symbol *s = g->symtab[i];
2298                         if (!s ||
2299                             s->type != Nonterminal ||
2300                             s->struct_name.txt == NULL)
2301                                 continue;
2302
2303                         fprintf(f, "\tcase %d:\n", s->num);
2304                         if (s->isref) {
2305                                 fprintf(f, "\t\tfree_%.*s(*(void**)asn);\n",
2306                                         s->struct_name.len,
2307                                         s->struct_name.txt);
2308                                 fprintf(f, "\t\tfree(asn);\n");
2309                         } else
2310                                 fprintf(f, "\t\tfree_%.*s(asn);\n",
2311                                         s->struct_name.len,
2312                                         s->struct_name.txt);
2313                         fprintf(f, "\t\tbreak;\n");
2314                 }
2315                 fprintf(f, "\t}\n}\n\n");
2316         }
2317
2318 ## The main routine.
2319
2320 There are three key parts to the "main" function of parsergen: processing
2321 the arguments, loading the grammar file, and dealing with the grammar.
2322
2323 ### Argument processing.
2324
2325 Command line options allow the selection of analysis mode, name of output
2326 file, and whether or not a report should be generated.  By default we create
2327 a report only if no code output was requested.
2328
2329 The `parse_XX` function name uses the basename of the output file which
2330 should not have a suffix (`.c`).  `.c` is added to the given name for the
2331 code, and `.h` is added for the header (if header text is specifed in the
2332 grammar file).
2333
2334 ###### includes
2335         #include <getopt.h>
2336
2337 ###### declarations
2338         static const struct option long_options[] = {
2339                 { "LR0",        0, NULL, '0' },
2340                 { "LR05",       0, NULL, '5' },
2341                 { "SLR",        0, NULL, 'S' },
2342                 { "LALR",       0, NULL, 'L' },
2343                 { "LR1",        0, NULL, '1' },
2344                 { "tag",        1, NULL, 't' },
2345                 { "report",     0, NULL, 'R' },
2346                 { "output",     1, NULL, 'o' },
2347                 { NULL,         0, NULL, 0   }
2348         };
2349         const char *options = "05SL1t:Ro:";
2350
2351 ###### process arguments
2352         int opt;
2353         char *outfile = NULL;
2354         char *infile;
2355         char *name;
2356         char *tag = NULL;
2357         int report = 1;
2358         enum grammar_type type = LR05;
2359         while ((opt = getopt_long(argc, argv, options,
2360                                   long_options, NULL)) != -1) {
2361                 switch(opt) {
2362                 case '0':
2363                         type = LR0; break;
2364                 case '5':
2365                         type = LR05; break;
2366                 case 'S':
2367                         type = SLR; break;
2368                 case 'L':
2369                         type = LALR; break;
2370                 case '1':
2371                         type = LR1; break;
2372                 case 'R':
2373                         report = 2; break;
2374                 case 'o':
2375                         outfile = optarg; break;
2376                 case 't':
2377                         tag = optarg; break;
2378                 default:
2379                         fprintf(stderr, "Usage: parsergen -[05SL1R] [-t tag] [-o output] input\n");
2380                         exit(1);
2381                 }
2382         }
2383         if (optind < argc)
2384                 infile = argv[optind++];
2385         else {
2386                 fprintf(stderr, "No input file given\n");
2387                 exit(1);
2388         }
2389         if (outfile && report == 1)
2390                 report = 0;
2391         name = outfile;
2392         if (name && strchr(name, '/'))
2393                 name = strrchr(name, '/')+1;
2394
2395         if (optind < argc) {
2396                 fprintf(stderr, "Excess command line arguments\n");
2397                 exit(1);
2398         }
2399
2400 ### Loading the grammar file
2401
2402 To be able to run `mdcode` and `scanner` on the grammar we need to memory
2403 map it.
2404
2405 Once we have extracted the code (with `mdcode`) we expect to find three
2406 or four sections: header, code, grammar, reduce.
2407 Anything else that is not excluded by the `--tag` option is an error.
2408
2409 "header", "code", and "reduce" are optional, though it is hard to build
2410 a working parser without the first two.  "grammar" must be provided.
2411
2412 ###### includes
2413         #include <fcntl.h>
2414         #include <sys/mman.h>
2415         #include <errno.h>
2416
2417 ###### functions
2418         static int errs;
2419         static void pr_err(char *msg)
2420         {
2421                 errs++;
2422                 fprintf(stderr, "%s\n", msg);
2423         }
2424
2425 ###### load file
2426         struct section *table;
2427         int fd;
2428         int len;
2429         char *file;
2430         fd = open(infile, O_RDONLY);
2431         if (fd < 0) {
2432                 fprintf(stderr, "parsergen: cannot open %s: %s\n",
2433                         infile, strerror(errno));
2434                 exit(1);
2435         }
2436         len = lseek(fd, 0, 2);
2437         file = mmap(NULL, len, PROT_READ, MAP_SHARED, fd, 0);
2438         table = code_extract(file, file+len, pr_err);
2439
2440         struct code_node *hdr = NULL;
2441         struct code_node *code = NULL;
2442         struct code_node *gram = NULL;
2443         struct code_node *pre_reduce = NULL;
2444         for (s = table; s; s = s->next) {
2445                 struct text sec = s->section;
2446                 if (tag && !strip_tag(&sec, tag))
2447                         continue;
2448                 if (text_is(sec, "header"))
2449                         hdr = s->code;
2450                 else if (text_is(sec, "code"))
2451                         code = s->code;
2452                 else if (text_is(sec, "grammar"))
2453                         gram = s->code;
2454                 else if (text_is(sec, "reduce"))
2455                         pre_reduce = s->code;
2456                 else {
2457                         fprintf(stderr, "Unknown content section: %.*s\n",
2458                                 s->section.len, s->section.txt);
2459                         rv |= 2;
2460                 }
2461         }
2462
2463 ### Processing the input
2464
2465 As we need to append an extention to a filename and then open it for
2466 writing, and we need to do this twice, it helps to have a separate function.
2467
2468 ###### functions
2469
2470         static FILE *open_ext(char *base, char *ext)
2471         {
2472                 char *fn = malloc(strlen(base) + strlen(ext) + 1);
2473                 FILE *f;
2474                 strcat(strcpy(fn, base), ext);
2475                 f = fopen(fn, "w");
2476                 free(fn);
2477                 return f;
2478         }
2479
2480 If we can read the grammar, then we analyse and optionally report on it.  If
2481 the report finds conflicts we will exit with an error status.
2482
2483 ###### process input
2484         struct grammar *g = NULL;
2485         if (gram == NULL) {
2486                 fprintf(stderr, "No grammar section provided\n");
2487                 rv |= 2;
2488         } else {
2489                 g = grammar_read(gram);
2490                 if (!g) {
2491                         fprintf(stderr, "Failure to parse grammar\n");
2492                         rv |= 2;
2493                 }
2494         }
2495         if (g) {
2496                 grammar_analyse(g, type);
2497                 if (report)
2498                         if (grammar_report(g, type))
2499                                 rv |= 1;
2500         }
2501
2502 If a "headers" section is defined, we write it out and include a declaration
2503 for the `parse_XX` function so it can be used from separate code.
2504
2505         if (rv == 0 && hdr && outfile) {
2506                 FILE *f = open_ext(outfile, ".h");
2507                 if (f) {
2508                         code_node_print(f, hdr, infile);
2509                         fprintf(f, "void *parse_%s(struct code_node *code, struct token_config *config, FILE *trace);\n",
2510                                 name);
2511                         fclose(f);
2512                 } else {
2513                         fprintf(stderr, "Cannot create %s.h\n",
2514                                 outfile);
2515                         rv |= 4;
2516                 }
2517         }
2518
2519 And if all goes well and an output file was provided, we create the `.c`
2520 file with the code section (if any) and the parser tables and function.
2521
2522         if (rv == 0 && outfile) {
2523                 FILE *f = open_ext(outfile, ".c");
2524                 if (f) {
2525                         if (code)
2526                                 code_node_print(f, code, infile);
2527                         gen_parser(f, g, infile, name, pre_reduce);
2528                         fclose(f);
2529                 } else {
2530                         fprintf(stderr, "Cannot create %s.c\n",
2531                                 outfile);
2532                         rv |= 4;
2533                 }
2534         }
2535
2536 And that about wraps it up.  We need to set the locale so that UTF-8 is
2537 recognised properly, and link with `libicuuc` as `libmdcode` requires that.
2538
2539 ###### File: parsergen.mk
2540         parsergen : parsergen.o libscanner.o libmdcode.o
2541                 $(CC) $(CFLAGS) -o parsergen parsergen.o libscanner.o libmdcode.o -licuuc
2542
2543 ###### includes
2544         #include <locale.h>
2545
2546 ###### main
2547
2548         int main(int argc, char *argv[])
2549         {
2550                 struct section *s;
2551                 int rv = 0;
2552
2553                 setlocale(LC_ALL,"");
2554
2555                 ## process arguments
2556                 ## load file
2557                 ## process input
2558
2559                 return rv;
2560         }
2561
2562 ## The SHIFT/REDUCE parser
2563
2564 Having analysed the grammar and generated all the tables, we only need
2565 the shift/reduce engine to bring it all together.
2566
2567 ### Goto table lookup
2568
2569 The parser generator has nicely provided us with goto tables sorted by
2570 symbol number.  We need a binary search function to find a symbol in the
2571 table.
2572
2573 ###### parser functions
2574
2575         static int search(const struct state *l, int sym)
2576         {
2577                 int lo = 0;
2578                 int hi = l->go_to_cnt;
2579
2580                 if (hi == 0)
2581                         return -1;
2582                 while (lo + 1 < hi) {
2583                         int mid = (lo + hi) / 2;
2584                         if (l->go_to[mid].sym <= sym)
2585                                 lo = mid;
2586                         else
2587                                 hi = mid;
2588                 }
2589                 if (l->go_to[lo].sym == sym)
2590                         return l->go_to[lo].state;
2591                 else
2592                         return -1;
2593         }
2594
2595 ### Memory allocation
2596
2597 The `scanner` returns tokens in a local variable - we want them in allocated
2598 memory so they can live in the `asn_stack`.  So we provide `tok_copy` to
2599 make an allocated copy as required.
2600
2601 ###### parser includes
2602         #include <memory.h>
2603
2604 ###### parser functions
2605
2606         static struct token *tok_copy(struct token tk)
2607         {
2608                 struct token *new = malloc(sizeof(*new));
2609                 *new = tk;
2610                 return new;
2611         }
2612
2613 ### The state stack.
2614
2615 The core data structure for the parser is the stack.  This tracks all
2616 the symbols that have been recognised or partially recognised.
2617
2618 The stack usually won't grow very large - maybe a few tens of entries.
2619 So we dynamically grow an array as required but never bother to
2620 shrink it down again.
2621
2622 We keep the stack as two separate allocations.  One, `asn_stack`, stores
2623 the "abstract syntax nodes" which are created by each reduction.  When
2624 we call `do_reduce` we need to pass an array of the `asn`s of the body
2625 of the production, and by keeping a separate `asn` stack, we can just
2626 pass a pointer into this stack.
2627
2628 The other allocation stores all other stack fields of which there are
2629 two.  The `state` is the most important one and guides the parsing
2630 process.  The `sym` is nearly unnecessary as it is implicit in the
2631 state.  However when we want to free entries from the `asn_stack`, it
2632 helps to know what type they are so we can call the right freeing
2633 function.  The symbol leads us to the right free function through
2634 `do_free`.
2635
2636 The stack is most properly seen as alternating states and symbols -
2637 states, like the 'DOT' in items, are between symbols.  Each frame in
2638 our stack holds a state and the symbol that was before it.  The
2639 bottom of stack holds the start state but no symbol, as nothing came
2640 before the beginning.  As we need to store some value, `TK_eof` is used
2641 to mark the beginning of the file as well as the end.
2642
2643 ###### parser functions
2644
2645         struct parser {
2646                 struct frame {
2647                         short state;
2648                         short sym;
2649                 } *stack;
2650                 void **asn_stack;
2651                 int stack_size;
2652                 int tos;
2653
2654                 ## parser state
2655         };
2656
2657 #### Shift and pop
2658
2659 Two operations are needed on the stack - shift (which is like push) and pop.
2660
2661 Shift applies not only to terminals but also to non-terminals.  When we
2662 reduce a production we will pop off frames corresponding to the body
2663 symbols, then push on a frame for the head of the production.  This last
2664 is exactly the same process as shifting in a terminal so we use the same
2665 function for both.  In both cases we provide the symbol.  The state is
2666 deduced from the current top-of-stack state and the new symbol.
2667
2668 To simplify other code we arrange for `shift` to fail if there is no `goto`
2669 state for the symbol.  This is useful in basic parsing due to our design
2670 that we shift when we can, and reduce when we cannot.  So the `shift`
2671 function reports if it could.
2672
2673 `shift` is also used to push state zero onto the stack, so if the
2674 stack is empty, it always chooses zero as the next state.
2675
2676 So `shift` finds the next state.  If that succeeds it extends the
2677 allocations if needed and pushes all the information onto the stacks.
2678
2679 An extra complication is added to `shift` by the `EOL` token.  This
2680 token must be generated when a `NEWLINE` is seen, but an `EOL` is
2681 expected.  When this happens, the `NEWLINE` is NOT consumed, so multiple
2682 EOL can appear before a NEWLINE.  To indicate that the token was shifted
2683 by not consumed, `shift` can return the special value `2`.  The token
2684 number for `EOL` cannot be statically declared, so when the parser
2685 starts we need to look through the array of non-terminals to find the
2686 EOL.
2687
2688 ###### parser state
2689         int tk_eol;
2690
2691 ###### find eol
2692         p.tk_eol = 0;
2693         while (strcmp(non_term[p.tk_eol], "EOL") != 0)
2694                 p.tk_eol += 1;
2695         p.tk_eol += TK_reserved + config->known_count;
2696
2697
2698 ###### parser functions
2699
2700         static int shift(struct parser *p,
2701                          short sym, void *asn,
2702                          const struct state states[])
2703         {
2704                 struct frame next = {0};
2705                 int ret;
2706                 int newstate = p->tos
2707                         ? search(&states[p->stack[p->tos-1].state],
2708                                  sym)
2709                         : 0;
2710                 if (newstate >= 0)
2711                         ret = 1;
2712                 else if (sym != TK_newline)
2713                         return 0;
2714                 else {
2715                         // have a NEWLINE, might need an EOL
2716                         sym = p->tk_eol;
2717                         newstate = p->tos
2718                                 ? search(&states[p->stack[p->tos-1].state],
2719                                          sym)
2720                                 : 0;
2721                         if (newstate < 0)
2722                                 return 0;
2723                         ret = 2;
2724                         asn = tok_copy(*(struct token*)asn);
2725                 }
2726
2727                 if (p->tos >= p->stack_size) {
2728                         p->stack_size += 10;
2729                         p->stack = realloc(p->stack, p->stack_size
2730                                            * sizeof(p->stack[0]));
2731                         p->asn_stack = realloc(p->asn_stack, p->stack_size
2732                                            * sizeof(p->asn_stack[0]));
2733                 }
2734                 next.sym = sym;
2735                 next.state = newstate;
2736
2737                 p->stack[p->tos] = next;
2738                 p->asn_stack[p->tos] = asn;
2739                 p->tos++;
2740                 return ret;
2741         }
2742
2743 `pop` primarily moves the top of stack (`tos`) back down the required
2744 amount and frees any `asn` entries that need to be freed.  It is called
2745 _after_ we reduce a production, just before we `shift` the nonterminal
2746 in.
2747
2748 ###### parser functions
2749
2750         static void pop(struct parser *p, int num,
2751                         void(*do_free)(short sym, void *asn))
2752         {
2753                 int i;
2754
2755                 p->tos -= num;
2756                 for (i = 0; i < num; i++)
2757                         do_free(p->stack[p->tos+i].sym, p->asn_stack[p->tos+i]);
2758         }
2759
2760 ### The heart of the parser.
2761
2762 Now we have the parser.  For each token we might shift it, trigger a
2763 reduction, or start error handling.  2D tokens (IN, OUT, NEWLINE, EOL)
2764 might also be ignored.  Ignoring tokens is combined with shifting.
2765
2766 ###### parser vars
2767
2768         struct parser p = { 0 };
2769         struct token *tk = NULL;
2770         int accepted = 0;
2771
2772 ###### heart of parser
2773
2774         shift(&p, TK_eof, NULL, states);
2775         while (!accepted && p.tos > 0) {
2776                 struct frame *tos = &p.stack[p.tos-1];
2777                 if (!tk)
2778                         tk = tok_copy(token_next(tokens));
2779                 parser_trace(trace, &p,
2780                              tk, states, non_term, config->known_count);
2781
2782                 ## try shift or ignore
2783                 ## try reduce
2784                 ## handle error
2785         }
2786
2787 Indents are ignored unless they can be shifted onto the stack
2788 immediately.  The end of an indented section - the OUT token - is
2789 ignored precisely when the indent was ignored.  To keep track of this we
2790 need a small stack of flags, which is easily stored as bits in an
2791 `unsigned long`.  This will never overflow and the scanner only allows
2792 20 levels of indentation.
2793
2794 ###### parser state
2795         unsigned long ignored_indents;
2796
2797 NEWLINE/EOL is ignored when in an indented section of text which was not
2798 explicitly expected by the grammar.  So if the most recent indent is
2799 ignored, so is any EOL token.
2800
2801 For other tokens, we shift the next token if that is possible, otherwise
2802 we try to reduce a production.
2803
2804 ###### try shift or ignore
2805
2806         if ((tk->num == TK_newline || tk->num == TK_out) &&
2807             (p.ignored_indents & 1)) {
2808                 /* indented, so ignore OUT and NEWLINE */
2809                 if (tk->num == TK_out)
2810                         p.ignored_indents >>= 1;
2811                 free(tk);
2812                 tk = NULL;
2813                 parser_trace_action(trace, "Ignore");
2814                 continue;
2815         }
2816
2817         switch (shift(&p, tk->num, tk, states)) {
2818         case 1:
2819                 if (tk->num == TK_out)
2820                         p.ignored_indents >>= 1;
2821                 if (tk->num == TK_in)
2822                         p.ignored_indents <<= 1;
2823
2824                 tk = NULL;
2825                 /* fallthrough */
2826         case 2:
2827                 parser_trace_action(trace, tk ? "ShiftEOL" : "Shift");
2828                 ## did shift
2829                 continue;
2830         }
2831
2832         if (tk->num == TK_in) {
2833                 /* No indent expected here, so ignore IN */
2834                 free(tk);
2835                 tk = NULL;
2836                 p.ignored_indents <<= 1;
2837                 p.ignored_indents |= 1;
2838                 parser_trace_action(trace, "Ignore");
2839                 continue;
2840         }
2841
2842 We have already discussed the bulk of the handling of a "reduce" action,
2843 with the `pop()` and `shift()` functions doing much of the work.  There
2844 is a little more complexity needed to manage storage for the asn (Abstract
2845 Syntax Node), and also a test of whether the reduction is permitted.
2846
2847 When we try to shift the result of reducing production-zero, it will
2848 fail because there is no next state.  In this case the asn will not have
2849 been stored on the stack, so it get stored in the `ret` variable, and we
2850 report that that input has been accepted.
2851
2852 ###### parser vars
2853
2854         void *ret = NULL;
2855
2856 ###### try reduce
2857
2858         if (states[tos->state].reduce_prod >= 0) {
2859                 void **body;
2860                 void *res;
2861                 const struct state *nextstate = &states[tos->state];
2862                 int prod = nextstate->reduce_prod;
2863                 int size = nextstate->reduce_size;
2864                 int res_size = nextstate->result_size;
2865
2866                 body = p.asn_stack + (p.tos - size);
2867                 res = res_size ? calloc(1, res_size) : NULL;
2868                 res_size = do_reduce(prod, body, config, res);
2869                 if (res_size != nextstate->result_size)
2870                         abort();
2871                 pop(&p, size, do_free);
2872                 if (!shift(&p, nextstate->reduce_sym, res, states)) {
2873                         accepted = 1;
2874                         ret = res;
2875                         parser_trace_action(trace, "Accept");
2876                 } else
2877                         parser_trace_action(trace, "Reduce");
2878                 continue;
2879         }
2880
2881 If we can neither shift nor reduce we have an error to handle.  There
2882 are two possible responses to an error: we can pop single frames off the
2883 stack until we find a frame that can shift `TK_error`, or we can discard
2884 the current look-ahead symbol.
2885
2886 When we first see an error we do the first of these and set a flag to
2887 record that we are processing an error.  If the normal shift/reduce
2888 tests fail to find that anything can be done from that state, we start
2889 dropping tokens until either we manage to shift one, or reach end-of-file.
2890
2891 ###### parser vars
2892
2893         int in_err = 0;
2894
2895 ###### did shift
2896
2897         in_err = 0;
2898
2899 ###### handle error
2900
2901         if (in_err) {
2902                 parser_trace_action(trace, "DISCARD");
2903                 if (tk->num == TK_eof)
2904                         break;
2905                 free(tk);
2906                 tk = NULL;
2907         } else {
2908                 struct token *err_tk;
2909
2910                 parser_trace_action(trace, "ERROR");
2911
2912                 err_tk = tok_copy(*tk);
2913                 while (p.tos > 0 && shift(&p, TK_error, err_tk, states) == 0)
2914                         // discard this state
2915                         pop(&p, 1, do_free);
2916                 if (p.tos == 0) {
2917                         free(err_tk);
2918                         // no state accepted TK_error
2919                         break;
2920                 }
2921                 in_err = 1;
2922         }
2923
2924 ###### parser includes
2925         #include "parser.h"
2926
2927 ###### parser_run
2928
2929         void *parser_run(struct token_state *tokens,
2930                          const struct state states[],
2931                          int (*do_reduce)(int, void**, struct token_config*, void*),
2932                          void (*do_free)(short, void*),
2933                          FILE *trace, const char *non_term[],
2934                          struct token_config *config)
2935         {
2936                 ## parser vars
2937
2938                 ## find eol
2939
2940                 ## heart of parser
2941
2942                 free(tk);
2943                 pop(&p, p.tos, do_free);
2944                 free(p.asn_stack);
2945                 free(p.stack);
2946                 return ret;
2947         }
2948
2949 ###### exported functions
2950         void *parser_run(struct token_state *tokens,
2951                          const struct state states[],
2952                          int (*do_reduce)(int, void**, struct token_config*, void*),
2953                          void (*do_free)(short, void*),
2954                          FILE *trace, const char *non_term[],
2955                          struct token_config *config);
2956
2957 ### Tracing
2958
2959 Being able to visualize the parser in action can be invaluable when
2960 debugging the parser code, or trying to understand how the parse of a
2961 particular grammar progresses.  The stack contains all the important
2962 state, so just printing out the stack every time around the parse loop
2963 can make it possible to see exactly what is happening.
2964
2965 This doesn't explicitly show each SHIFT and REDUCE action.  However they
2966 are easily deduced from the change between consecutive lines, and the
2967 details of each state can be found by cross referencing the states list
2968 in the stack with the "report" that parsergen can generate.
2969
2970 For terminal symbols, we just dump the token.  For non-terminals we
2971 print the name of the symbol.  The look ahead token is reported at the
2972 end inside square brackets.
2973
2974 ###### parser functions
2975
2976         static char *reserved_words[] = {
2977                 [TK_error]        = "ERROR",
2978                 [TK_in]           = "IN",
2979                 [TK_out]          = "OUT",
2980                 [TK_newline]      = "NEWLINE",
2981                 [TK_eof]          = "$eof",
2982         };
2983
2984         void parser_trace(FILE *trace, struct parser *p,
2985                           struct token *tk, const struct state states[],
2986                           const char *non_term[], int knowns)
2987         {
2988                 int i;
2989                 if (!trace)
2990                         return;
2991                 for (i = 0; i < p->tos; i++) {
2992                         struct frame *f = &p->stack[i];
2993                         if (i) {
2994                                 int sym = f->sym;
2995                                 if (sym < TK_reserved &&
2996                                     reserved_words[sym] != NULL)
2997                                         fputs(reserved_words[sym], trace);
2998                                 else if (sym < TK_reserved + knowns) {
2999                                         struct token *t = p->asn_stack[i];
3000                                         text_dump(trace, t->txt, 20);
3001                                 } else
3002                                         fputs(non_term[sym - TK_reserved - knowns],
3003                                               trace);
3004                                 fputs(" ", trace);
3005                         }
3006                         fprintf(trace, "(%d) ", f->state);
3007                 }
3008                 fprintf(trace, "[");
3009                 if (tk->num < TK_reserved &&
3010                     reserved_words[tk->num] != NULL)
3011                         fputs(reserved_words[tk->num], trace);
3012                 else
3013                         text_dump(trace, tk->txt, 20);
3014                 fprintf(trace, ":%d:%d]", tk->line, tk->col);
3015         }
3016
3017         void parser_trace_action(FILE *trace, char *action)
3018         {
3019                 if (trace)
3020                         fprintf(trace, " - %s\n", action);
3021         }
3022
3023 # A Worked Example
3024
3025 The obvious example for a parser is a calculator.
3026
3027 As `scanner` provides number parsing function using `libgmp` it is not much
3028 work to perform arbitrary rational number calculations.
3029
3030 This calculator takes one expression, or an equality test, per line.
3031 The results are printed and if any equality test fails, the program
3032 exits with an error.
3033
3034 ###### File: parsergen.mk
3035         calc.c calc.h : parsergen parsergen.mdc
3036                 ./parsergen --tag calc -o calc parsergen.mdc
3037         calc : calc.o libparser.o libscanner.o libmdcode.o libnumber.o
3038                 $(CC) $(CFLAGS) -o calc calc.o libparser.o libscanner.o libmdcode.o libnumber.o -licuuc -lgmp
3039         calctest : calc
3040                 ./calc parsergen.mdc
3041         demos :: calctest
3042
3043 # calc: header
3044
3045         #include "parse_number.h"
3046         // what do we use for a demo-grammar?  A calculator of course.
3047         struct number {
3048                 mpq_t val;
3049                 char tail[2];
3050                 int err;
3051         };
3052
3053 # calc: code
3054
3055         #include <stdlib.h>
3056         #include <unistd.h>
3057         #include <fcntl.h>
3058         #include <sys/mman.h>
3059         #include <stdio.h>
3060         #include <malloc.h>
3061         #include <gmp.h>
3062         #include <string.h>
3063         #include "mdcode.h"
3064         #include "scanner.h"
3065         #include "parser.h"
3066
3067         #include "calc.h"
3068
3069         static void free_number(struct number *n)
3070         {
3071                 mpq_clear(n->val);
3072                 free(n);
3073         }
3074
3075         static int text_is(struct text t, char *s)
3076         {
3077                 return (strlen(s) == t.len &&
3078                         strncmp(s, t.txt, t.len) == 0);
3079         }
3080
3081         int main(int argc, char *argv[])
3082         {
3083                 int fd = open(argv[1], O_RDONLY);
3084                 int len = lseek(fd, 0, 2);
3085                 char *file = mmap(NULL, len, PROT_READ, MAP_SHARED, fd, 0);
3086                 struct section *table = code_extract(file, file+len, NULL);
3087                 struct section *s;
3088                 struct token_config config = {
3089                         .ignored = (1 << TK_line_comment)
3090                                  | (1 << TK_in)
3091                                  | (1 << TK_out),
3092                         .number_chars = ".,_+-",
3093                         .word_start = "",
3094                         .word_cont = "",
3095                 };
3096                 for (s = table; s; s = s->next)
3097                         if (text_is(s->section, "example: input"))
3098                                 parse_calc(s->code, &config, argc > 2 ? stderr : NULL);
3099                 while (table) {
3100                         struct section *t = table->next;
3101                         code_free(table->code);
3102                         free(table);
3103                         table = t;
3104                 }
3105                 exit(0);
3106         }
3107
3108 # calc: grammar
3109
3110         $LEFT + -
3111         $LEFT * / //
3112
3113         Session -> Session Line
3114                 | Line
3115
3116         Line -> Expression NEWLINE ${ gmp_printf("Answer = %Qd\n", $1.val);
3117                                         { mpf_t fl; mpf_init2(fl, 20); mpf_set_q(fl, $1.val);
3118                                         gmp_printf("  or as a decimal: %Fg\n", fl);
3119                                         mpf_clear(fl);
3120                                         }
3121                                      }$
3122                 | Expression = Expression NEWLINE ${
3123                         if (mpq_equal($1.val, $3.val))
3124                                 gmp_printf("Both equal %Qd\n", $1.val);
3125                         else {
3126                                 gmp_printf("NOT EQUAL: %Qd\n      != : %Qd\n",
3127                                         $1.val, $3.val);
3128                                 exit(1);
3129                         }
3130                 }$
3131                 | NEWLINE ${ printf("Blank line\n"); }$
3132                 | ERROR NEWLINE ${ printf("Skipped a bad line\n"); }$
3133
3134         $number
3135         Expression -> Expression + Expression ${ mpq_init($0.val); mpq_add($0.val, $1.val, $3.val); }$
3136                 | Expression - Expression ${ mpq_init($0.val); mpq_sub($0.val, $1.val, $3.val); }$
3137                 | Expression * Expression ${ mpq_init($0.val); mpq_mul($0.val, $1.val, $3.val); }$
3138                 | Expression / Expression ${ mpq_init($0.val); mpq_div($0.val, $1.val, $3.val); }$
3139                 | Expression // Expression ${ {
3140                         mpz_t z0, z1, z2;
3141                         mpq_init($0.val);
3142                         mpz_init(z0); mpz_init(z1); mpz_init(z2);
3143                         mpz_tdiv_q(z1, mpq_numref($1.val), mpq_denref($1.val));
3144                         mpz_tdiv_q(z2, mpq_numref($3.val), mpq_denref($3.val));
3145                         mpz_tdiv_q(z0, z1, z2);
3146                         mpq_set_z($0.val, z0);
3147                         mpz_clear(z0); mpz_clear(z1); mpz_clear(z2);
3148                 } }$
3149                 | NUMBER ${ if (number_parse($0.val, $0.tail, $1.txt) == 0) mpq_init($0.val); }$
3150                 | ( Expression ) ${ mpq_init($0.val); mpq_set($0.val, $2.val); }$
3151
3152 # example: input
3153
3154         355/113
3155         3.1415926535 - 355/113
3156         2 + 4 * 5
3157         1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9
3158         10 * 9 / 2
3159         1 * 1000 + 2 * 100 + 3 * 10 + 4 * 1
3160
3161         355//113
3162
3163         error