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