1 # LR(1) Parser Generator with 2D support #
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.
7 "2D support" means that indentation and line breaks can be significant.
9 There are several distinct sections.
11 1. `grammar_read` will read a grammar from a literate-code file and
12 store the productions, symbols, and code fragments.
13 2. `grammar_analyse` will take that grammar and build LR parsing
14 states and look-ahead tables.
15 3. `grammar_report` will present the details of the analysis
16 in a readable format and will report any conflicts.
17 4. `parser_generate` will write out C code files with various
18 tables and with the code fragments arranged in useful places.
19 5. `parser_run` is a library function intended to be linked together
20 with the generated parser tables to complete the implementation of
22 6. Finally `calc` is a test grammar for a simple calculator. The
23 `parsergen` program built from the C code in this file can extract
24 that grammar directly from this file and process it.
26 ###### File: parsergen.c
31 ## forward declarations
42 ###### File: libparser.c
49 ###### File: parsergen.mk
52 parsergen.c parsergen.mk libparser.c parser.h : parsergen.mdc
55 ## Reading the grammar
57 The grammar must be stored in a markdown literate code file as parsed by
58 "[mdcode][]". It may have up to four top level (i.e. unreferenced)
59 sections: `header`, `code`, `grammar` and `reduce`. The first two, if
60 present, will be literally copied into the generated `.c` and `.h`
61 files. The third is required and contains the grammar which is
62 tokenised with "[scanner][]". `reduce` can provide variable
63 declarations and common intialization code for all the reduction code
64 fragments in the grammar.
66 If the `--tag` option is given, then any top level header that doesn't
67 start with the tag is ignored, and the tag is striped from the rest. So
68 `--tag Foo` means that the four sections expected are `Foo: header`,
69 `Foo: code`, `Foo: grammar` and `Foo: reduce`. The tag `calc` is used
70 to extract the sample calculator from this file.
73 [scanner]: scanner.html
79 ###### parser includes
83 The grammar contains production sets, precedence/associativity
84 declarations, general terminal declarations, and data type declarations.
85 These are all parsed with _ad hoc_ parsing as we don't have a parser
88 The precedence and associativity can be set for each production, and
89 can be inherited from symbols. The data type (either structure or a
90 reference to a structure) is potentially defined for each non-terminal
91 and describes what C structure is used to store information about each
95 enum assoc {Left, Right, Non};
96 char *assoc_names[] = {"Left","Right","Non"};
99 struct text struct_name;
102 unsigned short precedence;
106 unsigned short precedence;
115 The strings reported by `mdcode` and `scanner` are `struct text` which
116 have length rather than being nul terminated. To help with printing and
117 comparing we define `text_is` and `prtxt`, which should possibly go in
118 `mdcode`. `scanner` does provide `text_dump` which is useful for
119 strings which might contain control characters.
121 `strip_tag` is a bit like `strncmp`, but adds a test for a colon,
122 because that is what we need to detect tags.
125 static int text_is(struct text t, char *s)
127 return (strlen(s) == t.len &&
128 strncmp(s, t.txt, t.len) == 0);
130 static void prtxt(struct text t)
132 printf("%.*s", t.len, t.txt);
135 static int strip_tag(struct text *t, char *tag)
137 int skip = strlen(tag) + 1;
138 if (skip >= t->len ||
139 strncmp(t->txt, tag, skip-1) != 0 ||
140 t->txt[skip-1] != ':')
142 while (skip < t->len && t->txt[skip] == ' ')
151 Productions are comprised primarily of symbols - terminal and
152 non-terminal. We do not make a syntactic distinction between the two,
153 though non-terminals must be identifiers. Non-terminal symbols are
154 those which appear in the head of a production, terminal symbols are
155 those which don't. There are also "virtual" symbols used for precedence
156 marking discussed later, and sometimes we won't know what type a symbol
159 To help with code safety it is possible to declare the terminal symbols.
160 If this is done, then any symbol used in a production that does not
161 appear in the head of any production and is not declared as a terminal
162 is treated as an error.
164 ###### forward declarations
165 enum symtype { Unknown, Virtual, Terminal, Nonterminal };
166 char *symtypes = "UVTN";
169 ###### grammar fields
170 int terminals_declared;
172 Symbols can be either `TK_ident` or `TK_mark`. They are saved in a
173 table of known symbols and the resulting parser will report them as
174 `TK_reserved + N`. A small set of identifiers are reserved for the
175 different token types that `scanner` can report.
179 static struct { int num; char *name; } reserved_words[] = {
180 { TK_error, "ERROR" },
181 { TK_number, "NUMBER" },
182 { TK_ident, "IDENTIFIER" },
184 { TK_string, "STRING" },
185 { TK_multi_string, "MULTI_STRING" },
188 { TK_newline, "NEWLINE" },
194 Note that `TK_eof` and the two `TK_*_comment` tokens cannot be
195 recognised. The former is automatically expected at the end of the text
196 being parsed. The latter are always ignored by the parser.
198 All of these symbols are stored in a simple symbol table. We use the
199 `struct text` from `mdcode` to store the name and link them together
200 into a sorted list using an insertion sort.
202 We don't have separate `find` and `insert` functions as any symbol we
203 find needs to be remembered. We simply expect `find` to always return a
204 symbol, but its type might be `Unknown`.
213 ###### grammar fields
218 static struct symbol *sym_find(struct grammar *g, struct text s)
220 struct symbol **l = &g->syms;
225 (cmp = text_cmp((*l)->name, s)) < 0)
229 n = calloc(1, sizeof(*n));
238 static void symbols_init(struct grammar *g)
240 int entries = sizeof(reserved_words)/sizeof(reserved_words[0]);
242 for (i = 0; i < entries; i++) {
245 t.txt = reserved_words[i].name;
246 t.len = strlen(t.txt);
249 s->num = reserved_words[i].num;
253 ### Data types and precedence.
255 Data type specification, precedence specification, and declaration of
256 terminals are all introduced by a dollar sign at the start of the line.
257 If the next word is `LEFT`, `RIGHT` or `NON`, then the line specifies a
258 precedence, if it is `TERM` then the line declares terminals without
259 precedence, otherwise it specifies a data type.
261 The data type name is simply stored and applied to the head of all
262 subsequent productions. It must be the name of a structure optionally
263 preceded by an asterisk which means a reference or "pointer". So
264 `$expression` maps to `struct expression` and `$*statement` maps to
265 `struct statement *`.
267 Any productions given before the first data type declaration will have
268 no data type associated with them and can carry no information. In
269 order to allow other non-terminals to have no type, the data type
270 `$void` can be given. This does *not* mean that `struct void` will be
271 used, but rather than no type will be associated with subsequent
274 The precedence line must contain a list of symbols, either terminal
275 symbols or virtual symbols. It can only contain symbols that have not
276 been seen yet, so precedence declaration must precede the productions
279 A "virtual" symbol is an identifier preceded by `$$`. Virtual symbols
280 carry precedence information but are not included in the grammar. A
281 production can declare that it inherits the precedence of a given
284 This use for `$$` precludes it from being used as a symbol in the
285 described language. Two other symbols: `${` and `}$` are also
288 Each new precedence line introduces a new precedence level and
289 declares how it associates. This level is stored in each symbol
290 listed and may be inherited by any production which uses the symbol. A
291 production inherits from the last symbol which has a precedence.
293 The symbols on the first precedence line have the lowest precedence.
294 Subsequent lines introduce symbols with higher precedence and so bind
297 Note that a declaration line (or "dollar line") can start with either of
298 two different marks: "$" or "$*". The `dollar_line()` function defined
299 here is told which was found in the `isref` argument.
301 ###### grammar fields
302 struct text current_type;
307 enum symbols { TK_virtual = TK_reserved, TK_open, TK_close };
308 static const char *known[] = { "$$", "${", "}$" };
311 static char *dollar_line(struct token_state *ts, struct grammar *g, int isref)
313 struct token t = token_next(ts);
319 if (t.num != TK_ident) {
320 err = "type or assoc expected after '$'";
323 if (text_is(t.txt, "LEFT"))
325 else if (text_is(t.txt, "RIGHT"))
327 else if (text_is(t.txt, "NON"))
329 else if (text_is(t.txt, "TERM")) {
331 g->terminals_declared = 1;
333 g->current_type = t.txt;
334 g->type_isref = isref;
335 if (text_is(t.txt, "void"))
336 g->current_type.txt = NULL;
338 if (t.num != TK_newline) {
339 err = "Extra tokens after type name";
346 err = "$* cannot be followed by a precedence";
350 // This is a precedence or TERM line, need some symbols.
354 while (t.num != TK_newline) {
355 enum symtype type = Terminal;
357 if (t.num == TK_virtual) {
360 if (t.num != TK_ident) {
361 err = "$$ must be followed by a word";
365 err = "Virtual symbols not permitted on $TERM line";
368 } else if (t.num != TK_ident &&
370 err = "Illegal token in precedence line";
373 s = sym_find(g, t.txt);
374 if (s->type != Unknown) {
375 err = "Symbols in precedence/TERM line must not already be known.";
380 s->precedence = g->prec_levels;
387 err = "No symbols given on precedence/TERM line";
391 while (t.num != TK_newline && t.num != TK_eof)
398 A production either starts with an identifier which is the head
399 non-terminal, or a vertical bar (`|`) in which case this production
400 uses the same head as the previous one. The identifier must be
401 followed by a `->` mark. All productions for a given non-terminal must
402 be grouped together with the `nonterminal ->` given only once.
404 After this a (possibly empty) sequence of identifiers and marks form
405 the body of the production. A virtual symbol may be given after the
406 body by preceding it with `$$`. If a virtual symbol is given, the
407 precedence of the production is that for the virtual symbol. If none
408 is given, the precedence is inherited from the last symbol in the
409 production which has a precedence specified.
411 After the optional precedence may come the `${` mark. This indicates
412 the start of a code fragment. If present, this must be on the same
413 line as the start of the production.
415 All of the text from the `${` through to the matching `}$` is
416 collected and forms the code-fragment for the production. It must all
417 be in one `code_node` of the literate code. The `}$` must be
418 at the end of a line.
420 Text in the code fragment will undergo substitutions where `$N` or
421 `$<N`,for some numeric `N` (or non-numeric indicator as described
422 later), will be replaced with a variable holding the parse information
423 for the particular symbol in the production. `$0` is the head of the
424 production, `$1` is the first symbol of the body, etc. The type of `$N`
425 for a terminal symbol is `struct token`. For a non-terminal, it is
426 whatever has been declared for that symbol. The `<` may be included and
427 means that the value (usually a reference) is being moved out, so it
428 will not automatically be freed. The effect of using '<' is that the
429 variable is cleared to all-zeros.
431 While building productions we will need to add to an array which needs to
435 static void array_add(void *varray, int *cnt, void *new)
437 void ***array = varray;
440 current = ((*cnt-1) | (step-1))+1;
441 if (*cnt == current) {
444 *array = realloc(*array, current * sizeof(void*));
446 (*array)[*cnt] = new;
450 Collecting the code fragment simply involves reading tokens until we
451 hit the end token `}$`, and noting the character position of the start and
455 static struct text collect_code(struct token_state *state,
460 code.txt = start.txt.txt + start.txt.len;
462 t = token_next(state);
463 while (t.node == start.node &&
464 t.num != TK_close && t.num != TK_error &&
466 if (t.num == TK_close && t.node == start.node)
467 code.len = t.txt.txt - code.txt;
473 Now we have all the bits we need to parse a full production.
478 ###### grammar fields
479 struct production **productions;
480 int production_count;
482 ###### production fields
484 struct symbol **body;
490 int first_production;
493 static char *parse_production(struct grammar *g,
495 struct token_state *state)
497 /* Head has already been parsed. */
500 struct production p, *pp;
502 memset(&p, 0, sizeof(p));
504 tk = token_next(state);
505 while (tk.num == TK_ident || tk.num == TK_mark) {
506 struct symbol *bs = sym_find(g, tk.txt);
507 if (bs->type == Unknown) {
508 if (!g->terminals_declared)
511 if (bs->type == Virtual) {
512 err = "Virtual symbol not permitted in production";
515 if (bs->precedence) {
516 p.precedence = bs->precedence;
519 array_add(&p.body, &p.body_size, bs);
520 tk = token_next(state);
522 if (tk.num == TK_virtual) {
524 tk = token_next(state);
525 if (tk.num != TK_ident) {
526 err = "word required after $$";
529 vs = sym_find(g, tk.txt);
530 if (vs->num == TK_newline)
532 else if (vs->num == TK_out)
534 else if (vs->precedence == 0) {
535 err = "symbol after $$ must have precedence";
538 p.precedence = vs->precedence;
541 tk = token_next(state);
543 if (tk.num == TK_open) {
544 p.code_line = tk.line;
545 p.code = collect_code(state, tk);
546 if (p.code.txt == NULL) {
547 err = "code fragment not closed properly";
550 tk = token_next(state);
553 if (tk.num != TK_newline && tk.num != TK_eof) {
554 err = "stray tokens at end of line";
557 pp = malloc(sizeof(*pp));
559 array_add(&g->productions, &g->production_count, pp);
562 while (tk.num != TK_newline && tk.num != TK_eof)
563 tk = token_next(state);
568 With the ability to parse productions and dollar-lines, we have nearly all
569 that we need to parse a grammar from a `code_node`.
571 The head of the first production will effectively be the `start` symbol
572 of the grammar. However it won't _actually_ be so. Processing the
573 grammar is greatly simplified if the real start symbol only has a single
574 production, and expects `$eof` as the final terminal. So when we find
575 the first explicit production we insert an extra implicit production as
576 production zero which looks like
578 ###### Example: production 0
581 where `START` is the first non-terminal given.
583 ###### create production zero
584 struct production *p = calloc(1,sizeof(*p));
585 struct text start = {"$start",6};
586 struct text eof = {"$eof",4};
587 struct text code = {"$0 = $<1;", 9};
588 p->head = sym_find(g, start);
589 p->head->type = Nonterminal;
590 p->head->struct_name = g->current_type;
591 p->head->isref = g->type_isref;
592 if (g->current_type.txt)
594 array_add(&p->body, &p->body_size, head);
595 array_add(&p->body, &p->body_size, sym_find(g, eof));
596 p->head->first_production = g->production_count;
597 array_add(&g->productions, &g->production_count, p);
599 Now we are ready to read in the grammar. We ignore comments
600 and strings so that the marks which introduce them can be
601 used as terminals in the grammar. We don't ignore numbers
602 even though we don't allow them as that causes the scanner
603 to produce errors that the parser is better positioned to handle.
604 We also ignore indentation, but we expect and use newlines.
606 To allow comments in the grammar, we explicitly check for "//" as the
607 first token on the line and those lines are skipped. "//" can still be
608 used as a terminal anywhere that a terminal is expected.
611 static struct grammar *grammar_read(struct code_node *code)
613 struct token_config conf = {
616 .words_marks = known,
617 .known_count = sizeof(known)/sizeof(known[0]),
619 .ignored = (1 << TK_line_comment)
620 | (1 << TK_block_comment)
623 | (1 << TK_multi_string)
628 struct token_state *state = token_open(code, &conf);
630 struct symbol *head = NULL;
634 g = calloc(1, sizeof(*g));
637 for (tk = token_next(state); tk.num != TK_eof;
638 tk = token_next(state)) {
639 if (tk.num == TK_newline)
641 if (tk.num == TK_ident) {
643 head = sym_find(g, tk.txt);
644 if (head->type == Nonterminal)
645 err = "This non-terminal has already be used.";
646 else if (head->type == Virtual)
647 err = "Virtual symbol not permitted in head of production";
649 head->type = Nonterminal;
650 head->struct_name = g->current_type;
651 head->isref = g->type_isref;
652 if (g->production_count == 0) {
653 ## create production zero
655 head->first_production = g->production_count;
656 tk = token_next(state);
657 if (tk.num == TK_mark &&
658 text_is(tk.txt, "->"))
659 err = parse_production(g, head, state);
661 err = "'->' missing in production";
663 } else if (tk.num == TK_mark
664 && text_is(tk.txt, "|")) {
665 // another production for same non-term
667 err = parse_production(g, head, state);
669 err = "First production must have a head";
670 } else if (tk.num == TK_mark
671 && text_is(tk.txt, "$")) {
672 err = dollar_line(state, g, 0);
673 } else if (tk.num == TK_mark
674 && text_is(tk.txt, "$*")) {
675 err = dollar_line(state, g, 1);
676 } else if (tk.num == TK_mark
677 && text_is(tk.txt, "//")) {
678 while (tk.num != TK_newline &&
680 tk = token_next(state);
682 err = "Unrecognised token at start of line.";
688 if (g->terminals_declared) {
691 for (s = g->syms; s; s = s->next) {
692 if (s->type != Unknown)
695 fprintf(stderr, "Token %.*s not declared\n",
696 s->name.len, s->name.txt);
699 free(g); // FIXME free content
705 fprintf(stderr, "Error at line %d: %s\n",
708 free(g); // FIXME free content
712 ## Analysing the grammar
714 The central task in analysing the grammar is to determine a set of
715 states to drive the parsing process. This will require finding various
716 sets of symbols and of "items". Some of these sets will need to attach
717 information to each element in the set, so they are more like maps.
719 Each "item" may have a 'look-ahead' or `LA` set associated with it.
720 Many of these will be the same as each other. To avoid memory wastage,
721 and to simplify some comparisons of sets, these sets will be stored in a
722 list of unique sets, each assigned a number.
724 Once we have the data structures in hand to manage these sets and lists,
725 we can start setting the 'nullable' flag, build the 'FIRST' sets, and
726 then create the item sets which define the various states.
730 Though we don't only store symbols in these sets, they are the main
731 things we store, so they are called symbol sets or "symsets".
733 A symset has a size, an array of shorts, and an optional array of data
734 values, which are also shorts. If the array of data is not present, we
735 store an impossible pointer, as `NULL` is used to indicate that no
736 memory has been allocated yet;
741 unsigned short *syms, *data;
743 #define NO_DATA ((unsigned short *)1)
744 const struct symset INIT_SYMSET = { 0, NULL, NO_DATA };
745 const struct symset INIT_DATASET = { 0, NULL, NULL };
747 The arrays of shorts are allocated in blocks of 8 and are kept sorted by
748 using an insertion sort. We don't explicitly record the amount of
749 allocated space as it can be derived directly from the current `cnt`
750 using `((cnt - 1) | 7) + 1`.
753 static void symset_add(struct symset *s, unsigned short key, unsigned short val)
756 int current = ((s->cnt-1) | 7) + 1;
757 if (current == s->cnt) {
759 s->syms = realloc(s->syms, sizeof(*s->syms) * current);
760 if (s->data != NO_DATA)
761 s->data = realloc(s->data, sizeof(*s->data) * current);
764 while (i > 0 && s->syms[i-1] > key) {
765 s->syms[i] = s->syms[i-1];
766 if (s->data != NO_DATA)
767 s->data[i] = s->data[i-1];
771 if (s->data != NO_DATA)
776 Finding a symbol (or item) in a `symset` uses a simple binary search.
777 We return the index where the value was found (so data can be accessed),
778 or `-1` to indicate failure.
780 static int symset_find(struct symset *ss, unsigned short key)
787 while (lo + 1 < hi) {
788 int mid = (lo + hi) / 2;
789 if (ss->syms[mid] <= key)
794 if (ss->syms[lo] == key)
799 We will often want to form the union of two symsets. When we do, we
800 will often want to know if anything changed (as that might mean there is
801 more work to do). So `symset_union` reports whether anything was added
802 to the first set. We use a slow quadratic approach as these sets are
803 rarely large. If profiling shows this to be a problem it can be
806 static int symset_union(struct symset *a, struct symset *b)
810 for (i = 0; i < b->cnt; i++)
811 if (symset_find(a, b->syms[i]) < 0) {
812 unsigned short data = 0;
813 if (b->data != NO_DATA)
815 symset_add(a, b->syms[i], data);
821 And of course we must be able to free a symset.
823 static void symset_free(struct symset ss)
826 if (ss.data != NO_DATA)
832 Some symsets are simply stored somewhere appropriate in the `grammar`
833 data structure, others needs a bit of indirection. This applies
834 particularly to "LA" sets. These will be paired with "items" in an
835 "itemset". As itemsets will be stored in a symset, the "LA" set needs
836 to be stored in the `data` field, so we need a mapping from a small
837 (short) number to an LA `symset`.
839 As mentioned earlier this involves creating a list of unique symsets.
841 For now, we just use a linear list sorted by insertion. A skiplist
842 would be more efficient and may be added later.
849 struct setlist *next;
852 ###### grammar fields
853 struct setlist *sets;
858 static int ss_cmp(struct symset a, struct symset b)
861 int diff = a.cnt - b.cnt;
864 for (i = 0; i < a.cnt; i++) {
865 diff = (int)a.syms[i] - (int)b.syms[i];
872 static int save_set(struct grammar *g, struct symset ss)
874 struct setlist **sl = &g->sets;
878 while (*sl && (cmp = ss_cmp((*sl)->ss, ss)) < 0)
885 s = malloc(sizeof(*s));
894 Finding a set by number is currently performed by a simple linear
895 search. If this turns out to hurt performance, we can store the sets in
896 a dynamic array like the productions.
898 static struct symset set_find(struct grammar *g, int num)
900 struct setlist *sl = g->sets;
901 while (sl && sl->num != num)
906 ### Setting `nullable`
908 We set `nullable` on the head symbol for any production for which all
909 the body symbols (if any) are nullable. As this is a recursive
910 definition, any change in the `nullable` setting means that we need to
911 re-evaluate where it needs to be set.
913 We simply loop around performing the same calculations until no more
920 static void set_nullable(struct grammar *g)
923 while (check_again) {
926 for (p = 0; p < g->production_count; p++) {
927 struct production *pr = g->productions[p];
930 if (pr->head->nullable)
932 for (s = 0; s < pr->body_size; s++)
933 if (! pr->body[s]->nullable)
935 if (s == pr->body_size) {
936 pr->head->nullable = 1;
943 ### Setting `line_like`
945 In order to be able to ignore newline tokens when not relevant, but
946 still include them in the parse when needed, we will need to know
947 which states can start a "line-like" section of code. We ignore
948 newlines when there is an indent since the most recent start of a
951 A "line_like" symbol is simply any symbol that can derive a NEWLINE.
952 If a symbol cannot derive a NEWLINE, then it is only part of a line -
953 so is word-like. If it can derive a NEWLINE, then we consider it to
956 Clearly the `TK_newline` token can derive a NEWLINE. Any symbol which
957 is the head of a production that contains a line_like symbol is also a
958 line-like symbol. We use a new field `line_like` to record this
959 attribute of symbols, and compute it in a repetitive manner similar to
966 static void set_line_like(struct grammar *g)
969 g->symtab[TK_newline]->line_like = 1;
970 while (check_again) {
973 for (p = 0; p < g->production_count; p++) {
974 struct production *pr = g->productions[p];
977 if (pr->head->line_like)
980 for (s = 0 ; s < pr->body_size; s++) {
981 if (pr->body[s]->line_like) {
982 pr->head->line_like = 1;
991 ### Building the `first` sets
993 When calculating what can follow a particular non-terminal, we will need
994 to know what the "first" terminal in any subsequent non-terminal might
995 be. So we calculate the `first` set for every non-terminal and store
996 them in an array. We don't bother recording the "first" set for
997 terminals as they are trivial.
999 As the "first" for one symbol might depend on the "first" of another, we
1000 repeat the calculations until no changes happen, just like with
1001 `set_nullable`. This makes use of the fact that `symset_union` reports
1002 if any change happens.
1004 The core of this, which finds the "first" of part of a production body,
1005 will be reused for computing the "follow" sets, so we split that out
1006 into a separate function, `add_first`, which also reports if it got all
1007 the way to the end of the production without finding a non-nullable
1010 ###### grammar fields
1011 struct symset *first;
1015 static int add_first(struct production *pr, int start,
1016 struct symset *target, struct grammar *g,
1021 for (s = start; s < pr->body_size; s++) {
1022 struct symbol *bs = pr->body[s];
1023 if (bs->type == Terminal) {
1024 if (symset_find(target, bs->num) < 0) {
1025 symset_add(target, bs->num, 0);
1029 } else if (symset_union(target, &g->first[bs->num]))
1035 *to_end = (s == pr->body_size);
1039 static void build_first(struct grammar *g)
1041 int check_again = 1;
1043 g->first = calloc(g->num_syms, sizeof(g->first[0]));
1044 for (s = 0; s < g->num_syms; s++)
1045 g->first[s] = INIT_SYMSET;
1047 while (check_again) {
1050 for (p = 0; p < g->production_count; p++) {
1051 struct production *pr = g->productions[p];
1052 struct symset *head = &g->first[pr->head->num];
1054 if (add_first(pr, 0, head, g, NULL))
1060 ### Building the `follow` sets.
1062 There are two different situations when we will want to generate
1063 "follow" sets. If we are doing an SLR analysis, we want to generate a
1064 single "follow" set for each non-terminal in the grammar. That is what
1065 is happening here. If we are doing an LALR or LR analysis we will want
1066 to generate a separate "LA" set for each item. We do that later in
1069 There are two parts to generating a "follow" set. Firstly we look at
1070 every place that any non-terminal appears in the body of any production,
1071 and we find the set of possible "first" symbols after there. This is
1072 done using `add_first` above and only needs to be done once as the
1073 "first" sets are now stable and will not change.
1075 ###### grammar fields
1076 struct symset *follow;
1080 for (p = 0; p < g->production_count; p++) {
1081 struct production *pr = g->productions[p];
1084 for (b = 0; b < pr->body_size - 1; b++) {
1085 struct symbol *bs = pr->body[b];
1086 if (bs->type == Terminal)
1088 add_first(pr, b+1, &g->follow[bs->num], g, NULL);
1092 The second part is to add the "follow" set of the head of a production
1093 to the "follow" sets of the final symbol in the production, and any
1094 other symbol which is followed only by `nullable` symbols. As this
1095 depends on "follow" itself we need to repeatedly perform the process
1096 until no further changes happen.
1098 Rather than 2 nested loops, one that repeats the whole process until
1099 there is no change, and one that iterates of the set of productions, we
1100 combine these two functions into a single loop.
1104 for (check_again = 0, p = 0;
1105 p < g->production_count;
1106 p < g->production_count-1
1107 ? p++ : check_again ? (check_again = 0, p = 0)
1109 struct production *pr = g->productions[p];
1112 for (b = pr->body_size - 1; b >= 0; b--) {
1113 struct symbol *bs = pr->body[b];
1114 if (bs->type == Terminal)
1116 if (symset_union(&g->follow[bs->num],
1117 &g->follow[pr->head->num]))
1124 We now just need to create and initialise the `follow` list to get a
1128 static void build_follow(struct grammar *g)
1130 int s, check_again, p;
1131 g->follow = calloc(g->num_syms, sizeof(g->follow[0]));
1132 for (s = 0; s < g->num_syms; s++)
1133 g->follow[s] = INIT_SYMSET;
1137 ### Building itemsets and states
1139 There are three different levels of detail that can be chosen for
1140 building the itemsets and states for the LR grammar. They are:
1142 1. LR(0), LR(0.5), or SLR(1), where no look-ahead is included in the
1143 itemsets - look-ahead, if used at all, is simply the 'follow' sets
1145 2. LALR(1) where we build look-ahead sets with each item and merge
1146 the LA sets when we find two paths to the same "kernel" set of items.
1147 3. LR(1) where different look-ahead for any item in the set means
1148 a different item set must be created.
1150 ###### forward declarations
1151 enum grammar_type { LR0, LR05, SLR, LALR, LR1 };
1153 We need to be able to look through existing states to see if a newly
1154 generated state already exists. For now we use a simple sorted linked
1157 An item is a pair of numbers: the production number and the position of
1158 "DOT", which is an index into the body of the production. As the
1159 numbers are not enormous we can combine them into a single "short" and
1160 store them in a `symset` - 5 bits for "DOT" and 11 bits for the
1161 production number (so 2000 productions with maximum of 31 symbols in the
1164 Comparing the itemsets will be a little different to comparing symsets
1165 as we want to do the lookup after generating the "kernel" of an
1166 itemset, so we need to ignore the offset=zero items which are added during
1169 To facilitate this, we modify the "DOT" number so that "0" sorts to
1170 the end of the list in the symset, and then only compare items before
1174 static inline unsigned short item_num(int production, int dot)
1176 return production | ((31-dot) << 11);
1178 static inline int item_prod(unsigned short item)
1180 return item & 0x7ff;
1182 static inline int item_dot(unsigned short item)
1184 return (31-(item >> 11)) & 0x1f;
1187 For LR(1) analysis we need to compare not just the itemset in a state
1188 but also the LA sets. As we assign each unique LA set a number, we
1189 can just compare the symset and the data values together.
1192 static int itemset_cmp(struct symset a, struct symset b,
1193 enum grammar_type type)
1199 i < a.cnt && i < b.cnt &&
1200 item_dot(a.syms[i]) > 0 &&
1201 item_dot(b.syms[i]) > 0;
1203 int diff = a.syms[i] - b.syms[i];
1207 diff = a.data[i] - b.data[i];
1212 if (i == a.cnt || item_dot(a.syms[i]) == 0)
1216 if (i == b.cnt || item_dot(b.syms[i]) == 0)
1222 if (type < LR1 || av == -1)
1225 a.data[i] - b.data[i];
1228 It will be helpful to know if an itemset has been "completed" or not,
1229 particularly for LALR where itemsets get merged, at which point they
1230 need to be consider for completion again. So a `completed` flag is
1233 For correct handling of `TK_newline` when parsing, we will need to
1234 know which states (itemsets) can occur at the start of a line, so we
1235 will record a `starts_line` flag too whenever DOT is at the start of a
1238 Finally, for handling `TK_out` we need to know whether productions in the
1239 current state started *before* the most recent indent. A state
1240 doesn't usually keep details of individual productions, so we need to
1241 add one extra detail. `min_prefix` is the smallest non-zero number of
1242 symbols *before* DOT in any production in an itemset. This will allow
1243 us to determine if the the most recent indent is sufficiently recent
1244 to cancel it against a `TK_out`. If it was seen longer ago than the
1245 `min_prefix`, and if the current state cannot be reduced, then the
1246 indented section must have ended in the middle of a syntactic unit, so
1247 an error must be signaled.
1249 And now we can build the list of itemsets. The lookup routine returns
1250 both a success flag and a pointer to where in the list an insert should
1251 happen, so we don't need to search a second time.
1255 struct itemset *next;
1257 struct symset items;
1258 struct symset go_to;
1260 unsigned short precedence;
1266 ###### grammar fields
1267 struct itemset *items;
1271 static int itemset_find(struct grammar *g, struct itemset ***where,
1272 struct symset kernel, enum grammar_type type)
1274 struct itemset **ip;
1276 for (ip = &g->items; *ip ; ip = & (*ip)->next) {
1277 struct itemset *i = *ip;
1279 diff = itemset_cmp(i->items, kernel, type);
1292 Adding an itemset may require merging the LA sets if LALR analysis is
1293 happening. If any new LA set adds any symbols that weren't in the old
1294 LA set, we clear the `completed` flag so that the dependants of this
1295 itemset will be recalculated and their LA sets updated.
1297 `add_itemset` must consume the symsets it is passed, either by adding
1298 them to a data structure, of freeing them.
1300 static int add_itemset(struct grammar *g, struct symset ss,
1301 enum assoc assoc, unsigned short precedence,
1302 enum grammar_type type)
1304 struct itemset **where, *is;
1306 int found = itemset_find(g, &where, ss, type);
1308 is = calloc(1, sizeof(*is));
1309 is->state = g->states;
1313 is->precedence = precedence;
1315 is->go_to = INIT_DATASET;
1324 for (i = 0; i < ss.cnt; i++) {
1325 struct symset temp = INIT_SYMSET, s;
1326 if (ss.data[i] == is->items.data[i])
1328 s = set_find(g, is->items.data[i]);
1329 symset_union(&temp, &s);
1330 s = set_find(g, ss.data[i]);
1331 if (symset_union(&temp, &s)) {
1332 is->items.data[i] = save_set(g, temp);
1343 To build all the itemsets, we first insert the initial itemset made from
1344 production zero, complete each itemset, and then generate new itemsets
1345 from old until no new ones can be made.
1347 Completing an itemset means finding all the items where "DOT" is
1348 followed by a nonterminal and adding "DOT=0" items for every production
1349 from that non-terminal - providing each item hasn't already been added.
1350 When we add such an item it might get inserted before the current
1351 one, so to make sure we process it we reset the loop counter to the
1354 If LA sets are needed, the LA set for each new item is found using
1355 `add_first` which was developed earlier for `FIRST` and `FOLLOW`. This
1356 may be supplemented by the LA set for the item which produced the new
1359 We also collect a set of all symbols which follow "DOT" (in `done`) as
1360 this is used in the next stage. If any of these symbols are flagged as
1361 `line_like`, then this state must be a `starts_line` state so now is a
1362 good time to record that.
1364 When itemsets are created we assign a precedence to the itemset from the
1365 complete item, if there is one. We ignore the possibility of there
1366 being two and don't (currently) handle precedence in such grammars.
1367 When completing a grammar we ignore any item where DOT is followed by a
1368 terminal with a precedence lower than that for the itemset. Unless the
1369 terminal has right associativity, we also ignore items where the
1370 terminal has the same precedence. The result is that unwanted items are
1371 still in the itemset, but the terminal doesn't get into the go to set,
1372 so the item is ineffective.
1374 ###### complete itemset
1375 for (i = 0; i < is->items.cnt; i++) {
1376 int p = item_prod(is->items.syms[i]);
1377 int bs = item_dot(is->items.syms[i]);
1378 struct production *pr = g->productions[p];
1381 struct symset LA = INIT_SYMSET;
1382 unsigned short sn = 0;
1383 struct symset LAnl = INIT_SYMSET;
1384 unsigned short snnl = 0;
1386 if (is->min_prefix == 0 ||
1387 (bs > 0 && bs < is->min_prefix))
1388 is->min_prefix = bs;
1389 if (bs == pr->body_size)
1392 if (s->precedence && is->precedence &&
1393 is->precedence > s->precedence)
1394 /* This terminal has a low precedence and
1395 * shouldn't be shifted
1398 if (s->precedence && is->precedence &&
1399 is->precedence == s->precedence && s->assoc != Right)
1400 /* This terminal has a matching precedence and is
1401 * not Right-associative, so we mustn't shift it.
1404 if (symset_find(&done, s->num) < 0) {
1405 symset_add(&done, s->num, 0);
1407 if (s->type != Nonterminal)
1410 is->starts_line = 1;
1415 add_first(pr, bs+1, &LA, g, &to_end);
1417 struct symset ss = set_find(g, is->items.data[i]);
1418 symset_union(&LA, &ss);
1420 sn = save_set(g, LA);
1421 LA = set_find(g, sn);
1422 if (symset_find(&LA, TK_newline))
1423 symset_add(&LAnl, TK_newline, 0);
1424 snnl = save_set(g, LAnl);
1425 LAnl = set_find(g, snnl);
1428 /* Add productions for this symbol */
1429 for (p2 = s->first_production;
1430 p2 < g->production_count &&
1431 g->productions[p2]->head == s;
1433 int itm = item_num(p2, 0);
1434 int pos = symset_find(&is->items, itm);
1436 if (g->productions[p2]->line_like)
1437 symset_add(&is->items, itm, snnl);
1439 symset_add(&is->items, itm, sn);
1440 /* Will have re-ordered, so start
1441 * from beginning again */
1443 } else if (type >= LALR) {
1444 struct symset ss = set_find(g, is->items.data[pos]);
1445 struct symset tmp = INIT_SYMSET;
1446 struct symset *la = &LA;
1448 if (g->productions[p2]->line_like)
1450 symset_union(&tmp, &ss);
1451 if (symset_union(&tmp, la)) {
1452 is->items.data[pos] = save_set(g, tmp);
1460 For each symbol we found (and placed in `done`) we collect all the items
1461 for which this symbol is next, and create a new itemset with "DOT"
1462 advanced over the symbol. This is then added to the collection of
1463 itemsets (or merged with a pre-existing itemset).
1465 ###### derive itemsets
1466 // Now we have a completed itemset, so we need to
1467 // compute all the 'next' itemsets and create them
1468 // if they don't exist.
1469 for (i = 0; i < done.cnt; i++) {
1471 unsigned short state;
1472 struct symbol *sym = g->symtab[done.syms[i]];
1473 enum assoc assoc = Non;
1474 unsigned short precedence = 0;
1475 struct symset newitemset = INIT_SYMSET;
1477 newitemset = INIT_DATASET;
1479 for (j = 0; j < is->items.cnt; j++) {
1480 int itm = is->items.syms[j];
1481 int p = item_prod(itm);
1482 int bp = item_dot(itm);
1483 struct production *pr = g->productions[p];
1484 unsigned short la = 0;
1487 if (bp == pr->body_size)
1489 if (pr->body[bp] != sym)
1494 la = is->items.data[j];
1495 if (bp == pr->body_size &&
1496 pr->precedence > 0 &&
1497 pr->precedence > precedence) {
1498 // new itemset is reducible and has a precedence.
1499 precedence = pr->precedence;
1502 pos = symset_find(&newitemset, item_num(p, bp));
1505 symset_add(&newitemset, item_num(p, bp), la);
1506 else if (type >= LALR) {
1507 // Need to merge la set.
1508 int la2 = newitemset.data[pos];
1510 struct symset ss = set_find(g, la2);
1511 struct symset LA = INIT_SYMSET;
1512 symset_union(&LA, &ss);
1513 ss = set_find(g, la);
1514 if (symset_union(&LA, &ss))
1515 newitemset.data[pos] = save_set(g, LA);
1521 state = add_itemset(g, newitemset, assoc, precedence, type);
1522 if (symset_find(&is->go_to, done.syms[i]) < 0)
1523 symset_add(&is->go_to, done.syms[i], state);
1526 All that is left is to create the initial itemset from production zero, and
1527 with `TK_eof` as the LA set.
1530 static void build_itemsets(struct grammar *g, enum grammar_type type)
1532 struct symset first = INIT_SYMSET;
1535 unsigned short la = 0;
1537 // LA set just has eof
1538 struct symset eof = INIT_SYMSET;
1539 symset_add(&eof, TK_eof, 0);
1540 la = save_set(g, eof);
1541 first = INIT_DATASET;
1543 // production 0, offset 0 (with no data)
1544 symset_add(&first, item_num(0, 0), la);
1545 add_itemset(g, first, Non, 0, type);
1546 for (check_again = 0, is = g->items;
1548 is = is->next ?: check_again ? (check_again = 0, g->items) : NULL) {
1550 struct symset done = INIT_SYMSET;
1561 ### Completing the analysis.
1563 The exact process of analysis depends on which level was requested. For
1564 `LR0` and `LR05` we don't need first and follow sets at all. For `LALR` and
1565 `LR1` we need first, but not follow. For `SLR` we need both.
1567 We don't build the "action" tables that you might expect as the parser
1568 doesn't use them. They will be calculated to some extent if needed for
1571 Once we have built everything we allocate arrays for the two lists:
1572 symbols and itemsets. This allows more efficient access during
1573 reporting. The symbols are grouped as terminals and then non-terminals,
1574 and we record the changeover point in `first_nonterm`.
1576 ###### grammar fields
1577 struct symbol **symtab;
1578 struct itemset **statetab;
1581 ###### grammar_analyse
1583 static void grammar_analyse(struct grammar *g, enum grammar_type type)
1587 int snum = TK_reserved;
1588 for (s = g->syms; s; s = s->next)
1589 if (s->num < 0 && s->type == Terminal) {
1593 g->first_nonterm = snum;
1594 for (s = g->syms; s; s = s->next)
1595 if (s->num < 0 && s->type != Virtual) {
1599 for (s = g->syms; s; s = s->next)
1605 g->symtab = calloc(g->num_syms, sizeof(g->symtab[0]));
1606 for (s = g->syms; s; s = s->next)
1607 g->symtab[s->num] = s;
1617 build_itemsets(g, type);
1619 g->statetab = calloc(g->states, sizeof(g->statetab[0]));
1620 for (is = g->items; is ; is = is->next)
1621 g->statetab[is->state] = is;
1624 ## Reporting on the Grammar
1626 The purpose of the report is to give the grammar developer insight into
1627 how the grammar parser will work. It is basically a structured dump of
1628 all the tables that have been generated, plus a description of any conflicts.
1630 ###### grammar_report
1631 static int grammar_report(struct grammar *g, enum grammar_type type)
1637 return report_conflicts(g, type);
1640 Firstly we have the complete list of symbols, together with the
1641 "FIRST" set if that was generated. We add a mark to each symbol to
1642 show if it is considered to be "line-like" (`<`), or if it is nullable (`.`).
1646 static void report_symbols(struct grammar *g)
1650 printf("SYMBOLS + FIRST:\n");
1652 printf("SYMBOLS:\n");
1654 for (n = 0; n < g->num_syms; n++) {
1655 struct symbol *s = g->symtab[n];
1659 printf(" %c%c%3d%c: ",
1660 s->nullable ? '.':' ',
1661 s->line_like ? '<':' ',
1662 s->num, symtypes[s->type]);
1665 printf(" (%d%s)", s->precedence,
1666 assoc_names[s->assoc]);
1668 if (g->first && s->type == Nonterminal) {
1671 for (j = 0; j < g->first[n].cnt; j++) {
1674 prtxt(g->symtab[g->first[n].syms[j]]->name);
1681 Then we have the follow sets if they were computed.
1683 static void report_follow(struct grammar *g)
1686 printf("FOLLOW:\n");
1687 for (n = 0; n < g->num_syms; n++)
1688 if (g->follow[n].cnt) {
1692 prtxt(g->symtab[n]->name);
1693 for (j = 0; j < g->follow[n].cnt; j++) {
1696 prtxt(g->symtab[g->follow[n].syms[j]]->name);
1702 And finally the item sets. These include the GO TO tables and, for
1703 LALR and LR1, the LA set for each item. Lots of stuff, so we break
1704 it up a bit. First the items, with production number and associativity.
1706 static void report_item(struct grammar *g, int itm)
1708 int p = item_prod(itm);
1709 int dot = item_dot(itm);
1710 struct production *pr = g->productions[p];
1714 prtxt(pr->head->name);
1716 for (i = 0; i < pr->body_size; i++) {
1717 printf(" %s", (dot == i ? ". ": ""));
1718 prtxt(pr->body[i]->name);
1720 if (dot == pr->body_size)
1723 if (pr->precedence && dot == pr->body_size)
1724 printf(" (%d%s)", pr->precedence,
1725 assoc_names[pr->assoc]);
1726 if (dot < pr->body_size &&
1727 pr->body[dot]->precedence) {
1728 struct symbol *s = pr->body[dot];
1729 printf(" [%d%s]", s->precedence,
1730 assoc_names[s->assoc]);
1732 if (pr->line_like == 1)
1733 printf(" $$NEWLINE");
1734 else if (pr->line_like)
1739 The LA sets which are (possibly) reported with each item:
1741 static void report_la(struct grammar *g, int lanum)
1743 struct symset la = set_find(g, lanum);
1747 printf(" LOOK AHEAD(%d)", lanum);
1748 for (i = 0; i < la.cnt; i++) {
1751 prtxt(g->symtab[la.syms[i]]->name);
1756 Then the go to sets:
1758 static void report_goto(struct grammar *g, struct symset gt)
1763 for (i = 0; i < gt.cnt; i++) {
1765 prtxt(g->symtab[gt.syms[i]]->name);
1766 printf(" -> %d\n", gt.data[i]);
1770 Now we can report all the item sets complete with items, LA sets, and GO TO.
1772 static void report_itemsets(struct grammar *g)
1775 printf("ITEM SETS(%d)\n", g->states);
1776 for (s = 0; s < g->states; s++) {
1778 struct itemset *is = g->statetab[s];
1779 printf(" Itemset %d:%s min prefix=%d",
1780 s, is->starts_line?" (startsline)":"", is->min_prefix);
1782 printf(" %d%s", is->precedence, assoc_names[is->assoc]);
1784 for (j = 0; j < is->items.cnt; j++) {
1785 report_item(g, is->items.syms[j]);
1786 if (is->items.data != NO_DATA)
1787 report_la(g, is->items.data[j]);
1789 report_goto(g, is->go_to);
1793 ### Reporting conflicts
1795 Conflict detection varies a lot among different analysis levels. However
1796 LR0 and LR0.5 are quite similar - having no follow sets - and SLR, LALR and
1797 LR1 are also similar as they have FOLLOW or LA sets.
1801 ## conflict functions
1803 static int report_conflicts(struct grammar *g, enum grammar_type type)
1806 printf("Conflicts:\n");
1808 cnt = conflicts_lr0(g, type);
1810 cnt = conflicts_slr(g, type);
1812 printf(" - no conflicts\n");
1816 LR0 conflicts are any state which have both a reducible item and
1817 a shiftable item, or two reducible items.
1819 LR05 conflicts only occur if two possible reductions exist,
1820 as shifts always over-ride reductions.
1822 ###### conflict functions
1823 static int conflicts_lr0(struct grammar *g, enum grammar_type type)
1827 for (i = 0; i < g->states; i++) {
1828 struct itemset *is = g->statetab[i];
1829 int last_reduce = -1;
1830 int prev_reduce = -1;
1831 int last_shift = -1;
1835 for (j = 0; j < is->items.cnt; j++) {
1836 int itm = is->items.syms[j];
1837 int p = item_prod(itm);
1838 int bp = item_dot(itm);
1839 struct production *pr = g->productions[p];
1841 if (bp == pr->body_size) {
1842 prev_reduce = last_reduce;
1846 if (pr->body[bp]->type == Terminal)
1849 if (type == LR0 && last_reduce >= 0 && last_shift >= 0) {
1850 printf(" State %d has both SHIFT and REDUCE:\n", i);
1851 report_item(g, is->items.syms[last_shift]);
1852 report_item(g, is->items.syms[last_reduce]);
1855 if (prev_reduce >= 0) {
1856 printf(" State %d has 2 (or more) reducible items\n", i);
1857 report_item(g, is->items.syms[prev_reduce]);
1858 report_item(g, is->items.syms[last_reduce]);
1865 SLR, LALR, and LR1 conflicts happen if two reducible items have over-lapping
1866 look ahead, or if a symbol in a look-ahead can be shifted. They differ only
1867 in the source of the look ahead set.
1869 We build two datasets to reflect the "action" table: one which maps
1870 terminals to items where that terminal could be shifted and another
1871 which maps terminals to items that could be reduced when the terminal
1872 is in look-ahead. We report when we get conflicts between the two.
1874 As a special case, if we find a SHIFT/REDUCE conflict, on the NEWLINE
1875 terminal, we ignore it. NEWLINES are handled specially with its own
1876 rules for when to shift and when to reduce. Conflicts are expected,
1877 but handled internally.
1879 static int conflicts_slr(struct grammar *g, enum grammar_type type)
1884 for (i = 0; i < g->states; i++) {
1885 struct itemset *is = g->statetab[i];
1886 struct symset shifts = INIT_DATASET;
1887 struct symset reduce = INIT_DATASET;
1891 /* First collect the shifts */
1892 for (j = 0; j < is->items.cnt; j++) {
1893 unsigned short itm = is->items.syms[j];
1894 int p = item_prod(itm);
1895 int bp = item_dot(itm);
1896 struct production *pr = g->productions[p];
1899 if (bp >= pr->body_size ||
1900 pr->body[bp]->type != Terminal)
1905 if (s->precedence && is->precedence)
1906 /* Precedence resolves this, so no conflict */
1909 if (symset_find(&shifts, s->num) < 0)
1910 symset_add(&shifts, s->num, itm);
1912 /* Now look for reductions and conflicts */
1913 for (j = 0; j < is->items.cnt; j++) {
1914 unsigned short itm = is->items.syms[j];
1915 int p = item_prod(itm);
1916 int bp = item_dot(itm);
1917 struct production *pr = g->productions[p];
1919 if (bp < pr->body_size)
1924 la = g->follow[pr->head->num];
1926 la = set_find(g, is->items.data[j]);
1928 for (k = 0; k < la.cnt; k++) {
1929 int pos = symset_find(&shifts, la.syms[k]);
1930 if (pos >= 0 && la.syms[k] != TK_newline) {
1931 printf(" State %d has SHIFT/REDUCE conflict on ", i);
1933 prtxt(g->symtab[la.syms[k]]->name);
1935 report_item(g, shifts.data[pos]);
1936 report_item(g, itm);
1938 pos = symset_find(&reduce, la.syms[k]);
1940 symset_add(&reduce, la.syms[k], itm);
1943 printf(" State %d has REDUCE/REDUCE conflict on ", i);
1944 prtxt(g->symtab[la.syms[k]]->name);
1946 report_item(g, itm);
1947 report_item(g, reduce.data[pos]);
1951 symset_free(shifts);
1952 symset_free(reduce);
1958 ## Generating the parser
1960 The exported part of the parser is the `parse_XX` function, where the name
1961 `XX` is based on the name of the parser files.
1963 This takes a `code_node`, a partially initialized `token_config`, and an
1964 optional `FILE` to send tracing to. The `token_config` gets the list of
1965 known words added and then is used with the `code_node` to initialize the
1968 `parse_XX` then calls the library function `parser_run` to actually complete
1969 the parse. This needs the `states` table and functions to call the various
1970 pieces of code provided in the grammar file, so they are generated first.
1972 ###### parser_generate
1974 static void gen_parser(FILE *f, struct grammar *g, char *file, char *name,
1975 struct code_node *pre_reduce)
1981 gen_reduce(f, g, file, pre_reduce);
1984 fprintf(f, "#line 0 \"gen_parser\"\n");
1985 fprintf(f, "void *parse_%s(struct code_node *code, struct token_config *config, FILE *trace)\n",
1988 fprintf(f, "\tstruct token_state *tokens;\n");
1989 fprintf(f, "\tconfig->words_marks = known;\n");
1990 fprintf(f, "\tconfig->known_count = sizeof(known)/sizeof(known[0]);\n");
1991 fprintf(f, "\ttokens = token_open(code, config);\n");
1992 fprintf(f, "\tvoid *rv = parser_run(tokens, states, do_reduce, do_free, trace, non_term, config);\n");
1993 fprintf(f, "\ttoken_close(tokens);\n");
1994 fprintf(f, "\treturn rv;\n");
1995 fprintf(f, "}\n\n");
1998 ### Known words table
2000 The known words table is simply an array of terminal symbols.
2001 The table of nonterminals used for tracing is a similar array.
2005 static void gen_known(FILE *f, struct grammar *g)
2008 fprintf(f, "#line 0 \"gen_known\"\n");
2009 fprintf(f, "static const char *known[] = {\n");
2010 for (i = TK_reserved;
2011 i < g->num_syms && g->symtab[i]->type == Terminal;
2013 fprintf(f, "\t\"%.*s\",\n", g->symtab[i]->name.len,
2014 g->symtab[i]->name.txt);
2015 fprintf(f, "};\n\n");
2018 static void gen_non_term(FILE *f, struct grammar *g)
2021 fprintf(f, "#line 0 \"gen_non_term\"\n");
2022 fprintf(f, "static const char *non_term[] = {\n");
2023 for (i = TK_reserved;
2026 if (g->symtab[i]->type == Nonterminal)
2027 fprintf(f, "\t\"%.*s\",\n", g->symtab[i]->name.len,
2028 g->symtab[i]->name.txt);
2029 fprintf(f, "};\n\n");
2032 ### States and the goto tables.
2034 For each state we record the goto table and details of the reducible
2035 production if there is one.
2036 Some of the details of the reducible production are stored in the
2037 `do_reduce` function to come later. Here we store the production
2038 number, the body size (useful for stack management), and the resulting
2039 symbol (useful for knowing how to free data later).
2041 The go to table is stored in a simple array of `sym` and corresponding
2044 ###### exported types
2052 const struct lookup * go_to;
2063 static void gen_goto(FILE *f, struct grammar *g)
2066 fprintf(f, "#line 0 \"gen_goto\"\n");
2067 for (i = 0; i < g->states; i++) {
2068 struct symset gt = g->statetab[i]->go_to;
2073 fprintf(f, "static const struct lookup goto_%d[] = {\n",
2075 for (j = 0; j < gt.cnt; j++)
2076 fprintf(f, "\t{ %d, %d },\n",
2077 gt.syms[j], gt.data[j]);
2082 static void gen_states(FILE *f, struct grammar *g)
2085 fprintf(f, "#line 0 \"gen_states\"\n");
2086 fprintf(f, "static const struct state states[] = {\n");
2087 for (i = 0; i < g->states; i++) {
2088 struct itemset *is = g->statetab[i];
2089 int j, prod = -1, prod_len;
2091 for (j = 0; j < is->items.cnt; j++) {
2092 int itm = is->items.syms[j];
2093 int p = item_prod(itm);
2094 int bp = item_dot(itm);
2095 struct production *pr = g->productions[p];
2097 if (bp < pr->body_size)
2099 /* This is what we reduce - choose longest */
2100 if (prod < 0 || prod_len < pr->body_size) {
2102 prod_len = pr->body_size;
2106 fprintf(f, "\t[%d] = { %d, goto_%d, ",
2107 i, is->go_to.cnt, i);
2109 fprintf(f, "\t[%d] = { 0, NULL, ", i);
2111 struct production *pr = g->productions[prod];
2112 fprintf(f, "%d, %d, %d, %d, %d, %d },\n", prod,
2119 fprintf(f, "-1, -1, -1, %d, 0, %d },\n",
2120 is->starts_line, is->min_prefix);
2122 fprintf(f, "};\n\n");
2125 ### The `do_reduce` function and the code
2127 When the parser engine decides to reduce a production, it calls
2128 `do_reduce` which runs the code that was included with the production,
2131 This code needs to be able to store data somewhere. Rather than
2132 requiring `do_reduce` to `malloc` that "somewhere", we pass in a large
2133 buffer and have `do_reduce` return the size to be saved.
2135 In order for the code to access "global" context, we pass in the
2136 "config" pointer that was passed to the parser function. If the `struct
2137 token_config` is embedded in some larger structure, the reducing code
2138 can access the larger structure using pointer manipulation. Performing
2139 that pointer manipulation, and any other common code or variables for
2140 all reduce actions, can be provided in code node called "reduce" which
2141 is passed around in `pre_reduce` which you might have already noticed.
2143 The code fragments require translation when written out. Any `$N` needs
2144 to be converted to a reference either to that buffer (if `$0`) or to the
2145 structure returned by a previous reduction. These pointers need to be
2146 cast to the appropriate type for each access. All this is handled in
2149 `gen_code` also allows symbol references to contain a '`<`' as in
2150 '`$<2`'. This is particularly useful for references (or pointers), but
2151 can be used with structures too. The `<` implies that the value is
2152 being moved out, so the object will not be automatically freed. It is
2153 equivalent to assigning `NULL` to the pointer or filling a structure
2156 Instead of a number `N`, the `$` or `$<` can be followed by some letters
2157 and possibly a number. A number by itself (other than zero) selects a
2158 symbol from the body of the production. A sequence of letters selects
2159 the shortest symbol in the body which contains those letters in the
2160 given order. If a number follows the letters, then a later occurrence
2161 of that symbol is chosen. So "`$AB2`" will refer to the structure
2162 attached to the second occurrence of the shortest symbol which contains
2163 an `A` followed by a `B`. If there is no unique shortest system, or if
2164 the number given is too large, then the symbol reference is not
2165 transformed, and will cause an error when the code is compiled.
2169 static int textchr(struct text t, char c, int s)
2172 for (i = s; i < t.len; i++)
2178 static int subseq_match(char *seq, int slen, struct text name)
2182 st = textchr(name, *seq, st);
2192 static int choose_sym(char **namep, int len, struct production *p)
2194 char *name = *namep;
2203 ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'))) {
2209 while (len > 0 && (c >= '0' && c <= '9')) {
2212 n = n * 10 + (c - '0');
2216 if (name == *namep || n > p->body_size)
2222 for (i = 0; i < p->body_size; i++) {
2223 if (!subseq_match(nam, namlen, p->body[i]->name))
2225 if (slen == 0 || p->body[i]->name.len < slen) {
2227 slen = p->body[i]->name.len;
2229 if (s >= 0 && p->body[i] != p->body[s] &&
2230 p->body[i]->name.len == p->body[s]->name.len)
2231 /* not unique, so s cannot be used */
2238 for (i = 0; i < p->body_size; i++)
2239 if (p->body[i] == p->body[s]) {
2244 if (n > 0 || i == p->body_size)
2250 static void gen_code(struct production *p, FILE *f, struct grammar *g)
2253 char *used = calloc(1, p->body_size);
2256 fprintf(f, "\t\t\t");
2257 for (c = p->code.txt; c < p->code.txt + p->code.len; c++) {
2271 n = choose_sym(&c, p->code.txt + p->code.len - c, p);
2280 fprintf(f, "(*(struct %.*s*%s)ret)",
2281 p->head->struct_name.len,
2282 p->head->struct_name.txt,
2283 p->head->isref ? "*":"");
2284 else if (p->body[n-1]->type == Terminal)
2285 fprintf(f, "(*(struct token *)body[%d])",
2287 else if (p->body[n-1]->struct_name.txt == NULL)
2288 fprintf(f, "$%d", n);
2290 fprintf(f, "(*(struct %.*s*%s)body[%d])",
2291 p->body[n-1]->struct_name.len,
2292 p->body[n-1]->struct_name.txt,
2293 p->body[n-1]->isref ? "*":"", n-1);
2299 for (i = 0; i < p->body_size; i++) {
2300 if (p->body[i]->struct_name.txt &&
2302 // assume this has been copied out
2303 if (p->body[i]->isref)
2304 fprintf(f, "\t\t*(void**)body[%d] = NULL;\n", i);
2306 fprintf(f, "\t\tmemset(body[%d], 0, sizeof(struct %.*s));\n", i, p->body[i]->struct_name.len, p->body[i]->struct_name.txt);
2314 static void gen_reduce(FILE *f, struct grammar *g, char *file,
2315 struct code_node *pre_reduce)
2318 fprintf(f, "#line 1 \"gen_reduce\"\n");
2319 fprintf(f, "static int do_reduce(int prod, void **body, struct token_config *config, void *ret)\n");
2321 fprintf(f, "\tint ret_size = 0;\n");
2323 code_node_print(f, pre_reduce, file);
2325 fprintf(f, "#line 4 \"gen_reduce\"\n");
2326 fprintf(f, "\tswitch(prod) {\n");
2327 for (i = 0; i < g->production_count; i++) {
2328 struct production *p = g->productions[i];
2329 fprintf(f, "\tcase %d:\n", i);
2332 fprintf(f, "#line %d \"%s\"\n", p->code_line, file);
2336 if (p->head->struct_name.txt)
2337 fprintf(f, "\t\tret_size = sizeof(struct %.*s%s);\n",
2338 p->head->struct_name.len,
2339 p->head->struct_name.txt,
2340 p->head->isref ? "*":"");
2342 fprintf(f, "\t\tbreak;\n");
2344 fprintf(f, "\t}\n\treturn ret_size;\n}\n\n");
2349 As each non-terminal can potentially cause a different type of data
2350 structure to be allocated and filled in, we need to be able to free it when
2353 It is particularly important to have fine control over freeing during error
2354 recovery where individual stack frames might need to be freed.
2356 For this, the grammar author is required to defined a `free_XX` function for
2357 each structure that is used by a non-terminal. `do_free` will call whichever
2358 is appropriate given a symbol number, and will call `free` (as is
2359 appropriate for tokens) on any terminal symbol.
2363 static void gen_free(FILE *f, struct grammar *g)
2367 fprintf(f, "#line 0 \"gen_free\"\n");
2368 fprintf(f, "static void do_free(short sym, void *asn)\n");
2370 fprintf(f, "\tif (!asn) return;\n");
2371 fprintf(f, "\tif (sym < %d) {\n", g->first_nonterm);
2372 fprintf(f, "\t\tfree(asn);\n\t\treturn;\n\t}\n");
2373 fprintf(f, "\tswitch(sym) {\n");
2375 for (i = 0; i < g->num_syms; i++) {
2376 struct symbol *s = g->symtab[i];
2378 s->type != Nonterminal ||
2379 s->struct_name.txt == NULL)
2382 fprintf(f, "\tcase %d:\n", s->num);
2384 fprintf(f, "\t\tfree_%.*s(*(void**)asn);\n",
2386 s->struct_name.txt);
2387 fprintf(f, "\t\tfree(asn);\n");
2389 fprintf(f, "\t\tfree_%.*s(asn);\n",
2391 s->struct_name.txt);
2392 fprintf(f, "\t\tbreak;\n");
2394 fprintf(f, "\t}\n}\n\n");
2397 ## The main routine.
2399 There are three key parts to the "main" function of parsergen: processing
2400 the arguments, loading the grammar file, and dealing with the grammar.
2402 ### Argument processing.
2404 Command line options allow the selection of analysis mode, name of output
2405 file, and whether or not a report should be generated. By default we create
2406 a report only if no code output was requested.
2408 The `parse_XX` function name uses the basename of the output file which
2409 should not have a suffix (`.c`). `.c` is added to the given name for the
2410 code, and `.h` is added for the header (if header text is specifed in the
2417 static const struct option long_options[] = {
2418 { "LR0", 0, NULL, '0' },
2419 { "LR05", 0, NULL, '5' },
2420 { "SLR", 0, NULL, 'S' },
2421 { "LALR", 0, NULL, 'L' },
2422 { "LR1", 0, NULL, '1' },
2423 { "tag", 1, NULL, 't' },
2424 { "report", 0, NULL, 'R' },
2425 { "output", 1, NULL, 'o' },
2426 { NULL, 0, NULL, 0 }
2428 const char *options = "05SL1t:Ro:";
2430 ###### process arguments
2432 char *outfile = NULL;
2437 enum grammar_type type = LR05;
2438 while ((opt = getopt_long(argc, argv, options,
2439 long_options, NULL)) != -1) {
2454 outfile = optarg; break;
2456 tag = optarg; break;
2458 fprintf(stderr, "Usage: parsergen -[05SL1R] [-t tag] [-o output] input\n");
2463 infile = argv[optind++];
2465 fprintf(stderr, "No input file given\n");
2468 if (outfile && report == 1)
2471 if (name && strchr(name, '/'))
2472 name = strrchr(name, '/')+1;
2474 if (optind < argc) {
2475 fprintf(stderr, "Excess command line arguments\n");
2479 ### Loading the grammar file
2481 To be able to run `mdcode` and `scanner` on the grammar we need to memory
2484 Once we have extracted the code (with `mdcode`) we expect to find three
2485 or four sections: header, code, grammar, reduce.
2486 Anything else that is not excluded by the `--tag` option is an error.
2488 "header", "code", and "reduce" are optional, though it is hard to build
2489 a working parser without the first two. "grammar" must be provided.
2493 #include <sys/mman.h>
2498 static void pr_err(char *msg)
2501 fprintf(stderr, "%s\n", msg);
2505 struct section *table;
2509 fd = open(infile, O_RDONLY);
2511 fprintf(stderr, "parsergen: cannot open %s: %s\n",
2512 infile, strerror(errno));
2515 len = lseek(fd, 0, 2);
2516 file = mmap(NULL, len, PROT_READ, MAP_SHARED, fd, 0);
2517 table = code_extract(file, file+len, pr_err);
2519 struct code_node *hdr = NULL;
2520 struct code_node *code = NULL;
2521 struct code_node *gram = NULL;
2522 struct code_node *pre_reduce = NULL;
2523 for (s = table; s; s = s->next) {
2524 struct text sec = s->section;
2525 if (tag && !strip_tag(&sec, tag))
2527 if (text_is(sec, "header"))
2529 else if (text_is(sec, "code"))
2531 else if (text_is(sec, "grammar"))
2533 else if (text_is(sec, "reduce"))
2534 pre_reduce = s->code;
2536 fprintf(stderr, "Unknown content section: %.*s\n",
2537 s->section.len, s->section.txt);
2542 ### Processing the input
2544 As we need to append an extention to a filename and then open it for
2545 writing, and we need to do this twice, it helps to have a separate function.
2549 static FILE *open_ext(char *base, char *ext)
2551 char *fn = malloc(strlen(base) + strlen(ext) + 1);
2553 strcat(strcpy(fn, base), ext);
2559 If we can read the grammar, then we analyse and optionally report on it. If
2560 the report finds conflicts we will exit with an error status.
2562 ###### process input
2563 struct grammar *g = NULL;
2565 fprintf(stderr, "No grammar section provided\n");
2568 g = grammar_read(gram);
2570 fprintf(stderr, "Failure to parse grammar\n");
2575 grammar_analyse(g, type);
2577 if (grammar_report(g, type))
2581 If a "headers" section is defined, we write it out and include a declaration
2582 for the `parse_XX` function so it can be used from separate code.
2584 if (rv == 0 && hdr && outfile) {
2585 FILE *f = open_ext(outfile, ".h");
2587 code_node_print(f, hdr, infile);
2588 fprintf(f, "void *parse_%s(struct code_node *code, struct token_config *config, FILE *trace);\n",
2592 fprintf(stderr, "Cannot create %s.h\n",
2598 And if all goes well and an output file was provided, we create the `.c`
2599 file with the code section (if any) and the parser tables and function.
2601 if (rv == 0 && outfile) {
2602 FILE *f = open_ext(outfile, ".c");
2605 code_node_print(f, code, infile);
2606 gen_parser(f, g, infile, name, pre_reduce);
2609 fprintf(stderr, "Cannot create %s.c\n",
2615 And that about wraps it up. We need to set the locale so that UTF-8 is
2616 recognised properly, and link with `libicuuc` as `libmdcode` requires that.
2618 ###### File: parsergen.mk
2619 parsergen : parsergen.o libscanner.o libmdcode.o
2620 $(CC) $(CFLAGS) -o parsergen parsergen.o libscanner.o libmdcode.o -licuuc
2627 int main(int argc, char *argv[])
2632 setlocale(LC_ALL,"");
2634 ## process arguments
2641 ## The SHIFT/REDUCE parser
2643 Having analysed the grammar and generated all the tables, we only need
2644 the shift/reduce engine to bring it all together.
2646 ### Goto table lookup
2648 The parser generator has nicely provided us with goto tables sorted by
2649 symbol number. We need a binary search function to find a symbol in the
2652 ###### parser functions
2654 static int search(const struct state *l, int sym)
2657 int hi = l->go_to_cnt;
2661 while (lo + 1 < hi) {
2662 int mid = (lo + hi) / 2;
2663 if (l->go_to[mid].sym <= sym)
2668 if (l->go_to[lo].sym == sym)
2669 return l->go_to[lo].state;
2674 ### Memory allocation
2676 The `scanner` returns tokens in a local variable - we want them in allocated
2677 memory so they can live in the `asn_stack`. Similarly the `asn` produced by
2678 a reduce is in a large buffer. Both of these require some allocation and
2679 copying, hence `memdup` and `tok_copy`.
2681 ###### parser includes
2684 ###### parser functions
2686 void *memdup(void *m, int len)
2692 memcpy(ret, m, len);
2696 static struct token *tok_copy(struct token tk)
2698 struct token *new = malloc(sizeof(*new));
2703 ### The state stack.
2705 The core data structure for the parser is the stack. This tracks all
2706 the symbols that have been recognised or partially recognised.
2708 The stack usually won't grow very large - maybe a few tens of entries.
2709 So we dynamically grow an array as required but never bother to
2710 shrink it down again.
2712 We keep the stack as two separate allocations. One, `asn_stack` stores
2713 the "abstract syntax nodes" which are created by each reduction. When
2714 we call `do_reduce` we need to pass an array of the `asn`s of the body
2715 of the production, and by keeping a separate `asn` stack, we can just
2716 pass a pointer into this stack.
2718 The other allocation stores all other stack fields of which there are
2719 several. The `state` is the most important one and guides the parsing
2720 process. The `sym` is nearly unnecessary as it is implicit in the
2721 state. However when we want to free entries from the `asn_stack`, it
2722 helps to know what type they are so we can call the right freeing
2723 function. The symbol leads us to the right free function through
2726 The `indents` count tracks the line indents with-in the symbol or
2727 immediately follow it. These are used to allow indent information to
2728 guide parsing and error recovery.
2730 `since_newline` tracks how many stack frames since the last
2731 start-of-line (whether indented or not). So if `since_newline` is
2732 zero, then this symbol is at the start of a line. Similarly
2733 `since_indent` counts the number of states since an indent, it is zero
2734 precisely when `indents` is not zero.
2736 `newline_permitted` keeps track of whether newlines should be ignored
2739 The stack is most properly seen as alternating states and symbols -
2740 states, like the 'DOT' in items, are between symbols. Each frame in
2741 our stack holds a state and the symbol that was before it. The
2742 bottom of stack holds the start state but no symbol, as nothing came
2743 before the beginning. As we need to store some value, `TK_eof` is used
2744 to mark the beginning of the file as well as the end.
2746 ###### parser functions
2751 short newline_permitted;
2755 short since_newline;
2765 Two operations are needed on the stack - shift (which is like push) and pop.
2767 Shift applies not only to terminals but also to non-terminals. When we
2768 reduce a production we will pop off frames corresponding to the body
2769 symbols, then push on a frame for the head of the production. This last
2770 is exactly the same process as shifting in a terminal so we use the same
2771 function for both. In both cases we provide the symbol, the number of
2772 indents the symbol contains (which will be zero for a terminal symbol)
2773 and a flag indicating the the symbol was at (or was reduced from a
2774 symbol which was at) the start of a line. The state is deduced from the
2775 current top-of-stack state and the new symbol.
2777 To simplify other code we arrange for `shift` to fail if there is no `goto`
2778 state for the symbol. This is useful in basic parsing due to our design
2779 that we shift when we can, and reduce when we cannot. So the `shift`
2780 function reports if it could.
2782 `shift` is also used to push state zero onto the stack, so if the
2783 stack is empty, it always chooses zero as the next state.
2785 So `shift` finds the next state. If that succeeds it extends the
2786 allocations if needed and pushes all the information onto the stacks.
2788 Newlines are permitted after a `starts_line` state until an internal
2789 indent. If the new frame has neither a `starts_line` state nor an
2790 indent, newlines are permitted if the previous stack frame permitted
2793 ###### parser functions
2795 static int shift(struct parser *p,
2796 short sym, short indents, short start_of_line,
2798 const struct state states[])
2800 // Push an entry onto the stack
2801 struct frame next = {0};
2802 int newstate = p->tos
2803 ? search(&states[p->stack[p->tos-1].state],
2808 if (p->tos >= p->stack_size) {
2809 p->stack_size += 10;
2810 p->stack = realloc(p->stack, p->stack_size
2811 * sizeof(p->stack[0]));
2812 p->asn_stack = realloc(p->asn_stack, p->stack_size
2813 * sizeof(p->asn_stack[0]));
2816 next.indents = indents;
2817 next.state = newstate;
2818 if (states[newstate].starts_line)
2819 next.newline_permitted = 1;
2821 next.newline_permitted = 0;
2823 next.newline_permitted =
2824 p->stack[p->tos-1].newline_permitted;
2826 next.newline_permitted = 0;
2828 if (!start_of_line) {
2830 next.since_newline = p->stack[p->tos-1].since_newline + 1;
2832 next.since_newline = 1;
2835 next.since_indent = 0;
2837 next.since_indent = p->stack[p->tos-1].since_indent + 1;
2839 next.since_indent = 1;
2841 p->stack[p->tos] = next;
2842 p->asn_stack[p->tos] = asn;
2847 `pop` primarily moves the top of stack (`tos`) back down the required
2848 amount and frees any `asn` entries that need to be freed. It also
2849 collects a summary of the indents and line starts in the symbols that
2850 are being removed. It is called _after_ we reduce a production, just
2851 before we `shift` the nonterminal in.
2853 ###### parser functions
2855 static int pop(struct parser *p, int num,
2856 short *start_of_line,
2857 void(*do_free)(short sym, void *asn))
2864 for (i = 0; i < num; i++) {
2865 sol |= !p->stack[p->tos+i].since_newline;
2866 indents += p->stack[p->tos+i].indents;
2867 do_free(p->stack[p->tos+i].sym,
2868 p->asn_stack[p->tos+i]);
2871 *start_of_line = sol;
2875 ### The heart of the parser.
2877 Now we have the parser. For each token we might shift it, trigger a
2878 reduction, or start error handling. 2D tokens (IN, OUT, EOL) also need
2881 We return whatever `asn` was returned by reducing production zero.
2883 If we can neither shift nor reduce we have an error to handle. We pop
2884 single entries off the stack until we can shift the `TK_error` symbol,
2885 then drop input tokens until we find one we can shift into the new error
2886 state. We need to ensure that something is dropped or shifted after an
2887 error, or we could get into an infinite loop, only shifting in
2888 `TK_error`, then reducing. So we track if there has been a shift since
2889 the last error, and if not the next error always discards one token.
2891 When we find `TK_in` and `TK_out` tokens which report indents we need
2892 to handle them directly as the grammar cannot express what we want to
2895 `TK_in` tokens are easy: we simply update indent count in the top stack frame to
2896 record how many indents there are following the previous token.
2898 `TK_out` tokens must be canceled against an indent count
2899 within the stack. If we can reduce some symbols that are all since
2900 the most recent indent, then we do that first. If the minimum prefix
2901 of the current state then extends back before the most recent indent,
2902 that indent can be cancelled. If the minimum prefix is shorter then
2903 the indent had ended prematurely and we must start error handling, which
2904 is still a work-in-progress.
2906 `TK_newline` tokens are ignored unless the top stack frame records
2907 that they are permitted. In that case they will not be considered for
2908 shifting if it is possible to reduce some symbols that are all since
2909 the most recent start of line. This is how a newline forcibly
2910 terminates any line-like structure - we try to reduce down to at most
2911 one symbol for each line where newlines are allowed.
2912 A consequence of this is that a rule like
2914 ###### Example: newlines - broken
2918 IfStatement -> Newlines if ....
2920 cannot work, as the NEWLINE will never be shifted as the empty string
2921 will be reduced first. Optional sets of newlines need to be include
2922 in the thing that preceed:
2924 ###### Example: newlines - works
2928 IfStatement -> If ....
2930 Here the NEWLINE will be shifted because nothing can be reduced until
2933 When during error handling we discard tokens read in, we want to keep
2934 discarding until we see one that is recognised. If we had a full set
2935 of LR(1) grammar states, this would mean looking in the look-ahead set,
2936 but we don't keep a full look-ahead set. We only record the subset
2937 that leads to SHIFT. We can, however, deduce the look-ahead set by
2938 looking at the SHIFT subsets for all states that we can get to by
2939 reducing zero or more times. So we need a little function which
2940 checks if a given token is in any of these look-ahead sets.
2942 ###### parser includes
2947 static int in_lookahead(struct token *tk, const struct state *states, int state)
2949 while (state >= 0) {
2950 if (search(&states[state], tk->num) >= 0)
2952 if (states[state].reduce_prod < 0)
2954 state = search(&states[state], states[state].reduce_sym);
2959 void *parser_run(struct token_state *tokens,
2960 const struct state states[],
2961 int (*do_reduce)(int, void**, struct token_config*, void*),
2962 void (*do_free)(short, void*),
2963 FILE *trace, const char *non_term[],
2964 struct token_config *config)
2966 struct parser p = { 0 };
2967 struct token *tk = NULL;
2969 int shift_since_err = 1;
2972 shift(&p, TK_eof, 0, 1, NULL, states);
2973 while (!accepted && p.tos > 0) {
2974 struct token *err_tk;
2975 struct frame *tos = &p.stack[p.tos-1];
2977 tk = tok_copy(token_next(tokens));
2978 parser_trace(trace, &p,
2979 tk, states, non_term, config->known_count);
2981 if (tk->num == TK_in) {
2983 tos->since_newline = 0;
2984 tos->since_indent = 0;
2985 if (!states[tos->state].starts_line)
2986 tos->newline_permitted = 0;
2989 parser_trace_action(trace, "Record");
2992 if (tk->num == TK_out) {
2993 if (states[tos->state].reduce_size >= 0 &&
2994 states[tos->state].reduce_size <= tos->since_indent)
2996 if (states[tos->state].min_prefix >= tos->since_indent) {
2998 struct frame *in = tos - tos->since_indent;
3000 if (in->indents == 0) {
3001 /* Reassess since_indent and newline_permitted */
3003 in->since_indent = in[-1].since_indent + 1;
3004 in->newline_permitted = in[-1].newline_permitted;
3006 in->since_indent = 0;
3007 in->newline_permitted = 0;
3009 if (states[in->state].starts_line)
3010 in->newline_permitted = 1;
3013 in->since_indent = in[-1].since_indent + 1;
3014 if (states[in->state].starts_line)
3015 in->newline_permitted = 1;
3017 in->newline_permitted = in[-1].newline_permitted;
3022 parser_trace_action(trace, "Cancel");
3025 // fall through to error handling as both SHIFT and REDUCE
3028 if (tk->num == TK_newline) {
3029 if (!tos->newline_permitted) {
3032 parser_trace_action(trace, "Discard");
3035 if (tos->since_newline > 1 &&
3036 states[tos->state].reduce_size >= 0 &&
3037 states[tos->state].reduce_size <= tos->since_newline)
3040 if (shift(&p, tk->num, 0, tk->num == TK_newline, tk, states)) {
3041 shift_since_err = 1;
3043 parser_trace_action(trace, "Shift");
3047 if (states[tos->state].reduce_prod >= 0 &&
3048 states[tos->state].newline_only &&
3049 !(tk->num == TK_newline ||
3050 tk->num == TK_eof ||
3051 tk->num == TK_out ||
3052 (tos->indents == 0 && tos->since_newline == 0))) {
3053 /* Anything other than newline or out or eof
3054 * in an error unless we are already at start
3055 * of line, as this production must end at EOL.
3057 } else if (states[tos->state].reduce_prod >= 0) {
3060 const struct state *nextstate = &states[tos->state];
3061 int prod = nextstate->reduce_prod;
3062 int size = nextstate->reduce_size;
3064 static char buf[16*1024];
3065 short indents, start_of_line;
3067 body = p.asn_stack + (p.tos - size);
3069 bufsize = do_reduce(prod, body, config, buf);
3071 indents = pop(&p, size, &start_of_line,
3073 res = memdup(buf, bufsize);
3074 memset(buf, 0, bufsize);
3075 if (!shift(&p, nextstate->reduce_sym,
3076 indents, start_of_line,
3078 if (prod != 0) abort();
3082 parser_trace_action(trace, "Reduce");
3085 /* Error. We walk up the stack until we
3086 * find a state which will accept TK_error.
3087 * We then shift in TK_error and see what state
3088 * that takes us too.
3089 * Then we discard input tokens until
3090 * we find one that is acceptable.
3092 parser_trace_action(trace, "ERROR");
3093 short indents = 0, start_of_line;
3095 err_tk = tok_copy(*tk);
3097 shift(&p, TK_error, 0, 0,
3098 err_tk, states) == 0)
3099 // discard this state
3100 indents += pop(&p, 1, &start_of_line, do_free);
3103 // no state accepted TK_error
3106 if (!shift_since_err) {
3107 /* must discard at least one token to avoid
3110 if (tk->num == TK_eof)
3113 tk = tok_copy(token_next(tokens));
3115 shift_since_err = 0;
3116 tos = &p.stack[p.tos-1];
3117 while (!in_lookahead(tk, states, tos->state) &&
3118 tk->num != TK_eof) {
3120 tk = tok_copy(token_next(tokens));
3121 shift_since_err = 1;
3122 if (tk->num == TK_in)
3124 if (tk->num == TK_out) {
3128 // FIXME update since_indent here
3131 tos->indents += indents;
3134 pop(&p, p.tos, NULL, do_free);
3140 ###### exported functions
3141 void *parser_run(struct token_state *tokens,
3142 const struct state states[],
3143 int (*do_reduce)(int, void**, struct token_config*, void*),
3144 void (*do_free)(short, void*),
3145 FILE *trace, const char *non_term[],
3146 struct token_config *config);
3150 Being able to visualize the parser in action can be invaluable when
3151 debugging the parser code, or trying to understand how the parse of a
3152 particular grammar progresses. The stack contains all the important
3153 state, so just printing out the stack every time around the parse loop
3154 can make it possible to see exactly what is happening.
3156 This doesn't explicitly show each SHIFT and REDUCE action. However they
3157 are easily deduced from the change between consecutive lines, and the
3158 details of each state can be found by cross referencing the states list
3159 in the stack with the "report" that parsergen can generate.
3161 For terminal symbols, we just dump the token. For non-terminals we
3162 print the name of the symbol. The look ahead token is reported at the
3163 end inside square brackets.
3165 ###### parser functions
3167 static char *reserved_words[] = {
3168 [TK_error] = "ERROR",
3171 [TK_newline] = "NEWLINE",
3174 static void parser_trace_state(FILE *trace, struct frame *f, const struct state states[])
3176 fprintf(trace, "(%d", f->state);
3177 if (states[f->state].starts_line)
3178 fprintf(trace, "s");
3179 if (f->newline_permitted)
3180 fprintf(trace, "n%d", f->since_newline);
3181 fprintf(trace, ") ");
3184 void parser_trace(FILE *trace, struct parser *p,
3185 struct token *tk, const struct state states[],
3186 const char *non_term[], int knowns)
3191 for (i = 0; i < p->tos; i++) {
3192 struct frame *f = &p->stack[i];
3195 if (sym < TK_reserved &&
3196 reserved_words[sym] != NULL)
3197 fputs(reserved_words[sym], trace);
3198 else if (sym < TK_reserved + knowns) {
3199 struct token *t = p->asn_stack[i];
3200 text_dump(trace, t->txt, 20);
3202 fputs(non_term[sym - TK_reserved - knowns],
3205 fprintf(trace, ".%d", f->indents);
3206 if (f->since_newline == 0)
3210 parser_trace_state(trace, f, states);
3212 fprintf(trace, "[");
3213 if (tk->num < TK_reserved &&
3214 reserved_words[tk->num] != NULL)
3215 fputs(reserved_words[tk->num], trace);
3217 text_dump(trace, tk->txt, 20);
3218 fprintf(trace, ":%d:%d]", tk->line, tk->col);
3221 void parser_trace_action(FILE *trace, char *action)
3224 fprintf(trace, " - %s\n", action);
3229 The obvious example for a parser is a calculator.
3231 As `scanner` provides number parsing function using `libgmp` it is not much
3232 work to perform arbitrary rational number calculations.
3234 This calculator takes one expression, or an equality test, per line.
3235 The results are printed and if any equality test fails, the program
3236 exits with an error.
3238 ###### File: parsergen.mk
3239 calc.c calc.h : parsergen parsergen.mdc
3240 ./parsergen --tag calc -o calc parsergen.mdc
3241 calc : calc.o libparser.o libscanner.o libmdcode.o libnumber.o
3242 $(CC) $(CFLAGS) -o calc calc.o libparser.o libscanner.o libmdcode.o libnumber.o -licuuc -lgmp
3244 ./calc parsergen.mdc
3249 #include "parse_number.h"
3250 // what do we use for a demo-grammar? A calculator of course.
3262 #include <sys/mman.h>
3268 #include "scanner.h"
3273 static void free_number(struct number *n)
3279 static int text_is(struct text t, char *s)
3281 return (strlen(s) == t.len &&
3282 strncmp(s, t.txt, t.len) == 0);
3285 int main(int argc, char *argv[])
3287 int fd = open(argv[1], O_RDONLY);
3288 int len = lseek(fd, 0, 2);
3289 char *file = mmap(NULL, len, PROT_READ, MAP_SHARED, fd, 0);
3290 struct section *table = code_extract(file, file+len, NULL);
3292 struct token_config config = {
3293 .ignored = (1 << TK_line_comment)
3296 .number_chars = ".,_+-",
3300 for (s = table; s; s = s->next)
3301 if (text_is(s->section, "example: input"))
3302 parse_calc(s->code, &config, argc > 2 ? stderr : NULL);
3304 struct section *t = table->next;
3305 code_free(table->code);
3317 Session -> Session Line
3320 Line -> Expression NEWLINE ${ gmp_printf("Answer = %Qd\n", $1.val);
3321 { mpf_t fl; mpf_init2(fl, 20); mpf_set_q(fl, $1.val);
3322 gmp_printf(" or as a decimal: %Fg\n", fl);
3326 | Expression = Expression NEWLINE ${
3327 if (mpq_equal($1.val, $3.val))
3328 gmp_printf("Both equal %Qd\n", $1.val);
3330 gmp_printf("NOT EQUAL: %Qd\n != : %Qd\n",
3335 | NEWLINE ${ printf("Blank line\n"); }$
3336 | ERROR NEWLINE ${ printf("Skipped a bad line\n"); }$
3339 Expression -> Expression + Expression ${ mpq_init($0.val); mpq_add($0.val, $1.val, $3.val); }$
3340 | Expression - Expression ${ mpq_init($0.val); mpq_sub($0.val, $1.val, $3.val); }$
3341 | Expression * Expression ${ mpq_init($0.val); mpq_mul($0.val, $1.val, $3.val); }$
3342 | Expression / Expression ${ mpq_init($0.val); mpq_div($0.val, $1.val, $3.val); }$
3343 | Expression // Expression ${ {
3346 mpz_init(z0); mpz_init(z1); mpz_init(z2);
3347 mpz_tdiv_q(z1, mpq_numref($1.val), mpq_denref($1.val));
3348 mpz_tdiv_q(z2, mpq_numref($3.val), mpq_denref($3.val));
3349 mpz_tdiv_q(z0, z1, z2);
3350 mpq_set_z($0.val, z0);
3351 mpz_clear(z0); mpz_clear(z1); mpz_clear(z2);
3353 | NUMBER ${ if (number_parse($0.val, $0.tail, $1.txt) == 0) mpq_init($0.val); }$
3354 | ( Expression ) ${ mpq_init($0.val); mpq_set($0.val, $2.val); }$
3359 3.1415926535 - 355/113
3361 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9
3363 1 * 1000 + 2 * 100 + 3 * 10 + 4 * 1
code / ocean / blob