1 # LR(1) Parser Generator #
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 There are several distinct sections.
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
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.
25 ###### File: parsergen.c
30 ## forward declarations
41 ###### File: libparser.c
48 ###### File: parsergen.mk
51 parsergen.c parsergen.mk libparser.c parser.h : parsergen.mdc
54 ## Reading the grammar
56 The grammar must be stored in a markdown literate code file as parsed
57 by "[mdcode][]". It must have three top level (i.e. unreferenced)
58 sections: `header`, `code`, and `grammar`. The first two will be
59 literally copied into the generated `.c` and `.h`. files. The last
60 contains the grammar. This is tokenised with "[scanner][]".
62 If the `--tag` option is given, then any top level header that doesn't
63 start with the tag is ignored, and the tag is striped from the rest. So
65 means that the three needed sections must be `Foo: header`, `Foo: code`,
69 [scanner]: scanner.html
75 ###### parser includes
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.
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
90 enum assoc {Left, Right, Non};
91 char *assoc_names[] = {"Left","Right","Non"};
94 struct text struct_name;
97 unsigned short precedence;
101 unsigned short precedence;
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.
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.
119 static int text_is(struct text t, char *s)
121 return (strlen(s) == t.len &&
122 strncmp(s, t.txt, t.len) == 0);
124 static void prtxt(struct text t)
126 printf("%.*s", t.len, t.txt);
129 static int strip_tag(struct text *t, char *tag)
131 int skip = strlen(tag) + 1;
132 if (skip >= t->len ||
133 strncmp(t->txt, tag, skip-1) != 0 ||
134 t->txt[skip-1] != ':')
136 while (skip < t->len && t->txt[skip] == ' ')
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
153 ###### forward declarations
154 enum symtype { Unknown, Virtual, Terminal, Nonterminal };
155 char *symtypes = "UVTN";
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.
165 static char *reserved_words[] = {
166 [TK_error] = "ERROR",
167 [TK_number] = "NUMBER",
168 [TK_ident] = "IDENTIFIER",
170 [TK_string] = "STRING",
171 [TK_multi_string] = "MULTI_STRING",
174 [TK_newline] = "NEWLINE",
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.
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.
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`.
199 ###### grammar fields
204 static int text_cmp(struct text a, struct text b)
209 int cmp = strncmp(a.txt, b.txt, len);
213 return a.len - b.len;
216 static struct symbol *sym_find(struct grammar *g, struct text s)
218 struct symbol **l = &g->syms;
223 (cmp = text_cmp((*l)->name, s)) < 0)
227 n = calloc(1, sizeof(*n));
236 static void symbols_init(struct grammar *g)
238 int entries = sizeof(reserved_words)/sizeof(reserved_words[0]);
240 for (i = 0; i < entries; i++) {
243 t.txt = reserved_words[i];
246 t.len = strlen(t.txt);
253 ### Data types and precedence.
255 Data type specification and precedence specification are both
256 introduced by a dollar sign at the start of the line. If the next
257 word is `LEFT`, `RIGHT` or `NON`, then the line specifies a
258 precedence, otherwise it specifies a data type.
260 The data type name is simply stored and applied to the head of all
261 subsequent productions. It must be the name of a structure optionally
262 preceded by an asterisk which means a reference or "pointer". So
263 `$expression` maps to `struct expression` and `$*statement` maps to
264 `struct statement *`.
266 Any productions given before the first data type declaration will have
267 no data type associated with them and can carry no information. In
268 order to allow other non-terminals to have no type, the data type
269 `$void` can be given. This does *not* mean that `struct void` will be
270 used, but rather than no type will be associated with future
273 The precedence line must contain a list of symbols - typically
274 terminal symbols, but not necessarily. It can only contain symbols
275 that have not been seen yet, so precedence declaration must precede
276 the productions that they affect.
278 A precedence line may also contain a "virtual" symbol which is an
279 identifier preceded by `$$`. Virtual terminals carry precedence
280 information but are not included in the grammar. A production can
281 declare that it inherits the precedence of a given virtual symbol.
283 This use for `$$` precludes it from being used as a symbol in the
284 described language. Two other symbols: `${` and `}$` are also
287 Each new precedence line introduces a new precedence level and
288 declares how it associates. This level is stored in each symbol
289 listed and may be inherited by any production which uses the symbol. A
290 production inherits from the last symbol which has a precedence.
292 ###### grammar fields
293 struct text current_type;
298 enum symbols { TK_virtual = TK_reserved, TK_open, TK_close };
299 static const char *known[] = { "$$", "${", "}$" };
302 static char *dollar_line(struct token_state *ts, struct grammar *g, int isref)
304 struct token t = token_next(ts);
309 if (t.num != TK_ident) {
310 err = "type or assoc expected after '$'";
313 if (text_is(t.txt, "LEFT"))
315 else if (text_is(t.txt, "RIGHT"))
317 else if (text_is(t.txt, "NON"))
320 g->current_type = t.txt;
321 g->type_isref = isref;
322 if (text_is(t.txt, "void"))
323 g->current_type.txt = NULL;
325 if (t.num != TK_newline) {
326 err = "Extra tokens after type name";
333 err = "$* cannot be followed by a precedence";
337 // This is a precedence line, need some symbols.
341 while (t.num != TK_newline) {
342 enum symtype type = Terminal;
344 if (t.num == TK_virtual) {
347 if (t.num != TK_ident) {
348 err = "$$ must be followed by a word";
351 } else if (t.num != TK_ident &&
353 err = "Illegal token in precedence line";
356 s = sym_find(g, t.txt);
357 if (s->type != Unknown) {
358 err = "Symbols in precedence line must not already be known.";
362 s->precedence = g->prec_levels;
367 err = "No symbols given on precedence line";
371 while (t.num != TK_newline && t.num != TK_eof)
378 A production either starts with an identifier which is the head
379 non-terminal, or a vertical bar (`|`) in which case this production
380 uses the same head as the previous one. The identifier must be
381 followed by a `->` mark. All productions for a given non-terminal must
382 be grouped together with the `nonterminal ->` given only once.
384 After this a (possibly empty) sequence of identifiers and marks form
385 the body of the production. A virtual symbol may be given after the
386 body by preceding it with `$$`. If a virtual symbol is given, the
387 precedence of the production is that for the virtual symbol. If none
388 is given, the precedence is inherited from the last symbol in the
389 production which has a precedence specified.
391 After the optional precedence may come the `${` mark. This indicates
392 the start of a code fragment. If present, this must be on the same
393 line as the start of the production.
395 All of the text from the `${` through to the matching `}$` is
396 collected and forms the code-fragment for the production. It must all
397 be in one `code_node` of the literate code. The `}$` must be
398 at the end of a line.
400 Text in the code fragment will undergo substitutions where `$N` for
401 some numeric `N` will be replaced with a variable holding the parse
402 information for the particular symbol in the production. `$0` is the
403 head of the production, `$1` is the first symbol of the body, etc.
404 The type of `$N` for a terminal symbol is `struct token`. For
405 a non-terminal, it is whatever has been declared for that symbol.
407 While building productions we will need to add to an array which needs to
411 static void array_add(void *varray, int *cnt, void *new)
413 void ***array = varray;
416 current = ((*cnt-1) | (step-1))+1;
417 if (*cnt == current) {
420 *array = realloc(*array, current * sizeof(void*));
422 (*array)[*cnt] = new;
426 Collecting the code fragment simply involves reading tokens until we
427 hit the end token `}$`, and noting the character position of the start and
431 static struct text collect_code(struct token_state *state,
436 code.txt = start.txt.txt + start.txt.len;
438 t = token_next(state);
439 while (t.node == start.node &&
440 t.num != TK_close && t.num != TK_error &&
442 if (t.num == TK_close && t.node == start.node)
443 code.len = t.txt.txt - code.txt;
449 Now we have all the bit we need to parse a full production.
454 ###### grammar fields
455 struct production **productions;
456 int production_count;
458 ###### production fields
460 struct symbol **body;
465 int first_production;
468 static char *parse_production(struct grammar *g,
470 struct token_state *state)
472 /* Head has already been parsed. */
475 struct production p, *pp;
477 memset(&p, 0, sizeof(p));
479 tk = token_next(state);
480 while (tk.num == TK_ident || tk.num == TK_mark) {
481 struct symbol *bs = sym_find(g, tk.txt);
482 if (bs->type == Unknown)
484 if (bs->type == Virtual) {
485 err = "Virtual symbol not permitted in production";
488 if (bs->precedence) {
489 p.precedence = bs->precedence;
492 array_add(&p.body, &p.body_size, bs);
493 tk = token_next(state);
495 if (tk.num == TK_virtual) {
497 tk = token_next(state);
498 if (tk.num != TK_ident) {
499 err = "word required after $$";
502 vs = sym_find(g, tk.txt);
503 if (vs->type != Virtual) {
504 err = "symbol after $$ must be virtual";
507 p.precedence = vs->precedence;
509 tk = token_next(state);
511 if (tk.num == TK_open) {
512 p.code = collect_code(state, tk);
513 if (p.code.txt == NULL) {
514 err = "code fragment not closed properly";
517 tk = token_next(state);
519 if (tk.num != TK_newline && tk.num != TK_eof) {
520 err = "stray tokens at end of line";
523 pp = malloc(sizeof(*pp));
525 array_add(&g->productions, &g->production_count, pp);
528 while (tk.num != TK_newline && tk.num != TK_eof)
529 tk = token_next(state);
533 With the ability to parse production and dollar-lines, we have nearly all
534 that we need to parse a grammar from a `code_node`.
536 The head of the first production will effectively be the `start` symbol of
537 the grammar. However it won't _actually_ be so. Processing the grammar is
538 greatly simplified if the real start symbol only has a single production,
539 and expects `$eof` as the final terminal. So when we find the first
540 explicit production we insert an extra production as production zero which
543 ###### Example: production 0
546 where `START` is the first non-terminal given.
548 ###### create production zero
549 struct production *p = calloc(1,sizeof(*p));
550 struct text start = {"$start",6};
551 struct text eof = {"$eof",4};
552 p->head = sym_find(g, start);
553 p->head->type = Nonterminal;
554 array_add(&p->body, &p->body_size, head);
555 array_add(&p->body, &p->body_size, sym_find(g, eof));
556 p->head->first_production = g->production_count;
557 array_add(&g->productions, &g->production_count, p);
559 Now we are ready to read in the grammar.
562 static struct grammar *grammar_read(struct code_node *code)
564 struct token_config conf = {
567 .words_marks = known,
568 .known_count = sizeof(known)/sizeof(known[0]),
570 .ignored = (1 << TK_line_comment)
571 | (1 << TK_block_comment)
574 | (1 << TK_multi_string)
579 struct token_state *state = token_open(code, &conf);
581 struct symbol *head = NULL;
585 g = calloc(1, sizeof(*g));
588 for (tk = token_next(state); tk.num != TK_eof;
589 tk = token_next(state)) {
590 if (tk.num == TK_newline)
592 if (tk.num == TK_ident) {
594 head = sym_find(g, tk.txt);
595 if (head->type == Nonterminal)
596 err = "This non-terminal has already be used.";
597 else if (head->type == Virtual)
598 err = "Virtual symbol not permitted in head of production";
600 head->type = Nonterminal;
601 head->struct_name = g->current_type;
602 head->isref = g->type_isref;
603 if (g->production_count == 0) {
604 ## create production zero
606 head->first_production = g->production_count;
607 tk = token_next(state);
608 if (tk.num == TK_mark &&
609 text_is(tk.txt, "->"))
610 err = parse_production(g, head, state);
612 err = "'->' missing in production";
614 } else if (tk.num == TK_mark
615 && text_is(tk.txt, "|")) {
616 // another production for same non-term
618 err = parse_production(g, head, state);
620 err = "First production must have a head";
621 } else if (tk.num == TK_mark
622 && text_is(tk.txt, "$")) {
623 err = dollar_line(state, g, 0);
624 } else if (tk.num == TK_mark
625 && text_is(tk.txt, "$*")) {
626 err = dollar_line(state, g, 1);
628 err = "Unrecognised token at start of line.";
636 fprintf(stderr, "Error at line %d: %s\n",
643 ## Analysing the grammar
645 The central task in analysing the grammar is to determine a set of
646 states to drive the parsing process. This will require finding
647 various sets of symbols and of "items". Some of these sets will need
648 to attach information to each element in the set, so they are more
651 Each "item" may have a 'look-ahead' or `LA` set associated with
652 it. Many of these will be the same as each other. To avoid memory
653 wastage, and to simplify some comparisons of sets, these sets will be
654 stored in a list of unique sets, each assigned a number.
656 Once we have the data structures in hand to manage these sets and
657 lists, we can start setting the 'nullable' flag, build the 'FIRST'
658 sets, and then create the item sets which define the various states.
662 Though we don't only store symbols in these sets, they are the main
663 things we store, so they are called symbol sets or "symsets".
665 A symset has a size, an array of shorts, and an optional array of data
666 values, which are also shorts. If the array of data is not present,
667 we store an impossible pointer, as `NULL` is used to indicate that no
668 memory has been allocated yet;
673 unsigned short *syms, *data;
675 #define NO_DATA ((unsigned short *)1)
676 const struct symset INIT_SYMSET = { 0, NULL, NO_DATA };
677 const struct symset INIT_DATASET = { 0, NULL, NULL };
679 The arrays of shorts are allocated in blocks of 8 and are kept sorted
680 by using an insertion sort. We don't explicitly record the amount of
681 allocated space as it can be derived directly from the current `cnt` using
682 `((cnt - 1) | 7) + 1`.
685 static void symset_add(struct symset *s, unsigned short key, unsigned short val)
688 int current = ((s->cnt-1) | 7) + 1;
689 if (current == s->cnt) {
691 s->syms = realloc(s->syms, sizeof(*s->syms) * current);
692 if (s->data != NO_DATA)
693 s->data = realloc(s->data, sizeof(*s->data) * current);
696 while (i > 0 && s->syms[i-1] > key) {
697 s->syms[i] = s->syms[i-1];
698 if (s->data != NO_DATA)
699 s->data[i] = s->data[i-1];
703 if (s->data != NO_DATA)
708 Finding a symbol (or item) in a `symset` uses a simple binary search.
709 We return the index where the value was found (so data can be accessed),
710 or `-1` to indicate failure.
712 static int symset_find(struct symset *ss, unsigned short key)
719 while (lo + 1 < hi) {
720 int mid = (lo + hi) / 2;
721 if (ss->syms[mid] <= key)
726 if (ss->syms[lo] == key)
731 We will often want to form the union of two symsets. When we do, we
732 will often want to know if anything changed (as they might mean there
733 is more work to do). So `symset_union` reports whether anything was
734 added to the first set. We use a slow quadratic approach as these
735 sets don't really get very big. If profiles shows this to be a problem is
736 can be optimised later.
738 static int symset_union(struct symset *a, struct symset *b)
742 for (i = 0; i < b->cnt; i++)
743 if (symset_find(a, b->syms[i]) < 0) {
744 unsigned short data = 0;
745 if (b->data != NO_DATA)
747 symset_add(a, b->syms[i], data);
753 And of course we must be able to free a symset.
755 static void symset_free(struct symset ss)
758 if (ss.data != NO_DATA)
764 Some symsets are simply stored somewhere appropriate in the `grammar`
765 data structure, others needs a bit of indirection. This applies
766 particularly to "LA" sets. These will be paired with "items" in an
767 "itemset". As itemsets will be stored in a symset, the "LA" set needs to be
768 stored in the `data` field, so we need a mapping from a small (short)
769 number to an LA `symset`.
771 As mentioned earlier this involves creating a list of unique symsets.
773 For now, we just use a linear list sorted by insertion. A skiplist
774 would be more efficient and may be added later.
781 struct setlist *next;
784 ###### grammar fields
785 struct setlist *sets;
790 static int ss_cmp(struct symset a, struct symset b)
793 int diff = a.cnt - b.cnt;
796 for (i = 0; i < a.cnt; i++) {
797 diff = (int)a.syms[i] - (int)b.syms[i];
804 static int save_set(struct grammar *g, struct symset ss)
806 struct setlist **sl = &g->sets;
810 while (*sl && (cmp = ss_cmp((*sl)->ss, ss)) < 0)
817 s = malloc(sizeof(*s));
826 Finding a set by number is currently performed by a simple linear search.
827 If this turns out to hurt performance, we can store the sets in a dynamic
828 array like the productions.
830 static struct symset set_find(struct grammar *g, int num)
832 struct setlist *sl = g->sets;
833 while (sl && sl->num != num)
839 ### Setting `nullable`
841 We set `nullable` on the head symbol for any production for which all
842 the body symbols (if any) are nullable. As this is a recursive
843 definition, any change in the `nullable` setting means that we need to
844 re-evaluate where it needs to be set.
846 We simply loop around performing the same calculations until no more
853 static void set_nullable(struct grammar *g)
856 while (check_again) {
859 for (p = 0; p < g->production_count; p++) {
860 struct production *pr = g->productions[p];
863 if (pr->head->nullable)
865 for (s = 0; s < pr->body_size; s++)
866 if (! pr->body[s]->nullable)
868 if (s == pr->body_size) {
869 pr->head->nullable = 1;
876 ### Setting `can_eol`
878 In order to be able to ignore newline tokens when not relevant, but
879 still include them in the parse when needed, we will need to know
880 which states can start a "line-like" section of code. We ignore
881 newlines when there is an indent since the most recent start of a
884 To know what is line-like, we first need to know which symbols can end
885 a line-like section, which is precisely those which can end with a
886 newline token. These symbols don't necessarily alway end with a
887 newline, but they can. Hence they are not described as "lines" but
890 Clearly the `TK_newline` token can end with a newline. Any symbol
891 which is the head of a production that contains a line-ending symbol
892 followed only by nullable symbols is also a line-ending symbol. We
893 use a new field `can_eol` to record this attribute of symbols, and
894 compute it in a repetitive manner similar to `set_nullable`.
900 static void set_can_eol(struct grammar *g)
903 g->symtab[TK_newline]->can_eol = 1;
904 while (check_again) {
907 for (p = 0; p < g->production_count; p++) {
908 struct production *pr = g->productions[p];
911 if (pr->head->can_eol)
914 for (s = pr->body_size - 1; s >= 0; s--) {
915 if (pr->body[s]->can_eol) {
916 pr->head->can_eol = 1;
920 if (!pr->body[s]->nullable)
927 ### Building the `first` sets
929 When calculating what can follow a particular non-terminal, we will need to
930 know what the "first" terminal in any subsequent non-terminal might be. So
931 we calculate the `first` set for every non-terminal and store them in an
932 array. We don't bother recording the "first" set for terminals as they are
935 As the "first" for one symbol might depend on the "first" of another,
936 we repeat the calculations until no changes happen, just like with
937 `set_nullable`. This makes use of the fact that `symset_union`
938 reports if any change happens.
940 The core of this which finds the "first" of part of a production body
941 will be reused for computing the "follow" sets, so we split it out
942 into a separate function.
944 ###### grammar fields
945 struct symset *first;
949 static int add_first(struct production *pr, int start,
950 struct symset *target, struct grammar *g,
955 for (s = start; s < pr->body_size; s++) {
956 struct symbol *bs = pr->body[s];
957 if (bs->type == Terminal) {
958 if (symset_find(target, bs->num) < 0) {
959 symset_add(target, bs->num, 0);
963 } else if (symset_union(target, &g->first[bs->num]))
969 *to_end = (s == pr->body_size);
973 static void build_first(struct grammar *g)
977 g->first = calloc(g->num_syms, sizeof(g->first[0]));
978 for (s = 0; s < g->num_syms; s++)
979 g->first[s] = INIT_SYMSET;
981 while (check_again) {
984 for (p = 0; p < g->production_count; p++) {
985 struct production *pr = g->productions[p];
986 struct symset *head = &g->first[pr->head->num];
988 if (add_first(pr, 0, head, g, NULL))
994 ### Building the `follow` sets.
996 There are two different situations when we will want to generate "follow"
997 sets. If we are doing an SLR analysis, we want to generate a single
998 "follow" set for each non-terminal in the grammar. That is what is
999 happening here. If we are doing an LALR or LR analysis we will want
1000 to generate a separate "LA" set for each item. We do that later
1001 in state generation.
1003 There are two parts to generating a "follow" set. Firstly we look at
1004 every place that any non-terminal appears in the body of any
1005 production, and we find the set of possible "first" symbols after
1006 there. This is done using `add_first` above and only needs to be done
1007 once as the "first" sets are now stable and will not change.
1011 for (p = 0; p < g->production_count; p++) {
1012 struct production *pr = g->productions[p];
1015 for (b = 0; b < pr->body_size - 1; b++) {
1016 struct symbol *bs = pr->body[b];
1017 if (bs->type == Terminal)
1019 add_first(pr, b+1, &g->follow[bs->num], g, NULL);
1023 The second part is to add the "follow" set of the head of a production
1024 to the "follow" sets of the final symbol in the production, and any
1025 other symbol which is followed only by `nullable` symbols. As this
1026 depends on "follow" itself we need to repeatedly perform the process
1027 until no further changes happen.
1031 for (again = 0, p = 0;
1032 p < g->production_count;
1033 p < g->production_count-1
1034 ? p++ : again ? (again = 0, p = 0)
1036 struct production *pr = g->productions[p];
1039 for (b = pr->body_size - 1; b >= 0; b--) {
1040 struct symbol *bs = pr->body[b];
1041 if (bs->type == Terminal)
1043 if (symset_union(&g->follow[bs->num],
1044 &g->follow[pr->head->num]))
1051 We now just need to create and initialise the `follow` list to get a
1054 ###### grammar fields
1055 struct symset *follow;
1058 static void build_follow(struct grammar *g)
1061 g->follow = calloc(g->num_syms, sizeof(g->follow[0]));
1062 for (s = 0; s < g->num_syms; s++)
1063 g->follow[s] = INIT_SYMSET;
1067 ### Building itemsets and states
1069 There are three different levels of detail that can be chosen for
1070 building the itemsets and states for the LR grammar. They are:
1072 1. LR(0) or SLR(1), where no look-ahead is considered.
1073 2. LALR(1) where we build look-ahead sets with each item and merge
1074 the LA sets when we find two paths to the same "kernel" set of items.
1075 3. LR(1) where different look-ahead for any item in the set means
1076 a different state must be created.
1078 ###### forward declarations
1079 enum grammar_type { LR0, LR05, SLR, LALR, LR1 };
1081 We need to be able to look through existing states to see if a newly
1082 generated state already exists. For now we use a simple sorted linked
1085 An item is a pair of numbers: the production number and the position of
1086 "DOT", which is an index into the body of the production.
1087 As the numbers are not enormous we can combine them into a single "short"
1088 and store them in a `symset` - 4 bits for "DOT" and 12 bits for the
1089 production number (so 4000 productions with maximum of 15 symbols in the
1092 Comparing the itemsets will be a little different to comparing symsets
1093 as we want to do the lookup after generating the "kernel" of an
1094 itemset, so we need to ignore the offset=zero items which are added during
1097 To facilitate this, we modify the "DOT" number so that "0" sorts to
1098 the end of the list in the symset, and then only compare items before
1102 static inline unsigned short item_num(int production, int index)
1104 return production | ((31-index) << 11);
1106 static inline int item_prod(unsigned short item)
1108 return item & 0x7ff;
1110 static inline int item_index(unsigned short item)
1112 return (31-(item >> 11)) & 0x1f;
1115 For LR(1) analysis we need to compare not just the itemset in a state
1116 but also the LA sets. As we assign each unique LA set a number, we
1117 can just compare the symset and the data values together.
1120 static int itemset_cmp(struct symset a, struct symset b,
1121 enum grammar_type type)
1127 i < a.cnt && i < b.cnt &&
1128 item_index(a.syms[i]) > 0 &&
1129 item_index(b.syms[i]) > 0;
1131 int diff = a.syms[i] - b.syms[i];
1135 diff = a.data[i] - b.data[i];
1140 if (i == a.cnt || item_index(a.syms[i]) == 0)
1144 if (i == b.cnt || item_index(b.syms[i]) == 0)
1150 if (type < LR1 || av == -1)
1153 a.data[i] - b.data[i];
1156 And now we can build the list of itemsets. The lookup routine returns
1157 both a success flag and a pointer to where in the list an insert
1158 should happen, so we don't need to search a second time.
1162 struct itemset *next;
1164 struct symset items;
1165 struct symset go_to;
1170 ###### grammar fields
1171 struct itemset *items;
1175 static int itemset_find(struct grammar *g, struct itemset ***where,
1176 struct symset kernel, enum grammar_type type)
1178 struct itemset **ip;
1180 for (ip = &g->items; *ip ; ip = & (*ip)->next) {
1181 struct itemset *i = *ip;
1183 diff = itemset_cmp(i->items, kernel, type);
1196 Adding an itemset may require merging the LA sets if LALR analysis is
1197 happening. If any new LA set adds any symbols that weren't in the old LA set, we
1198 clear the `completed` flag so that the dependants of this itemset will be
1199 recalculated and their LA sets updated.
1201 `add_itemset` must consume the symsets it is passed, either by adding
1202 them to a data structure, of freeing them.
1204 static int add_itemset(struct grammar *g, struct symset ss,
1205 enum grammar_type type, int starts_line)
1207 struct itemset **where, *is;
1209 int found = itemset_find(g, &where, ss, type);
1211 is = calloc(1, sizeof(*is));
1212 is->state = g->states;
1216 is->go_to = INIT_DATASET;
1217 is->starts_line = starts_line;
1226 for (i = 0; i < ss.cnt; i++) {
1227 struct symset temp = INIT_SYMSET, s;
1228 if (ss.data[i] == is->items.data[i])
1230 s = set_find(g, is->items.data[i]);
1231 symset_union(&temp, &s);
1232 s = set_find(g, ss.data[i]);
1233 if (symset_union(&temp, &s)) {
1234 is->items.data[i] = save_set(g, temp);
1245 To build all the itemsets, we first insert the initial itemset made
1246 from production zero, complete each itemset, and then generate new
1247 itemsets from old until no new ones can be made.
1249 Completing an itemset means finding all the items where "DOT" is followed by
1250 a nonterminal and adding "DOT=0" items for every production from that
1251 non-terminal - providing each item hasn't already been added.
1253 If LA sets are needed, the LA set for each new item is found using
1254 `add_first` which was developed earlier for `FIRST` and `FOLLOW`. This may
1255 be supplemented by the LA set for the item which produce the new item.
1257 We also collect a set of all symbols which follow "DOT" (in `done`) as this
1258 is used in the next stage.
1260 NOTE: precedence handling should happen here - I haven't written this yet
1263 ###### complete itemset
1264 for (i = 0; i < is->items.cnt; i++) {
1265 int p = item_prod(is->items.syms[i]);
1266 int bs = item_index(is->items.syms[i]);
1267 struct production *pr = g->productions[p];
1270 struct symset LA = INIT_SYMSET;
1271 unsigned short sn = 0;
1273 if (bs == pr->body_size)
1276 if (symset_find(&done, s->num) < 0)
1277 symset_add(&done, s->num, 0);
1278 if (s->type != Nonterminal)
1284 add_first(pr, bs+1, &LA, g, &to_end);
1286 struct symset ss = set_find(g, is->items.data[i]);
1287 symset_union(&LA, &ss);
1289 sn = save_set(g, LA);
1290 LA = set_find(g, sn);
1293 /* Add productions for this symbol */
1294 for (p2 = s->first_production;
1295 p2 < g->production_count &&
1296 g->productions[p2]->head == s;
1298 int itm = item_num(p2, 0);
1299 int pos = symset_find(&is->items, itm);
1301 symset_add(&is->items, itm, sn);
1302 /* Will have re-ordered, so start
1303 * from beginning again */
1305 } else if (type >= LALR) {
1306 struct symset ss = set_find(g, is->items.data[pos]);
1307 struct symset tmp = INIT_SYMSET;
1309 symset_union(&tmp, &ss);
1310 if (symset_union(&tmp, &LA)) {
1311 is->items.data[pos] = save_set(g, tmp);
1319 For each symbol we found (and placed in `done`) we collect all the items for
1320 which this symbol is next, and create a new itemset with "DOT" advanced over
1321 the symbol. This is then added to the collection of itemsets (or merged
1322 with a pre-existing itemset).
1324 ###### derive itemsets
1325 // Now we have a completed itemset, so we need to
1326 // compute all the 'next' itemsets and create them
1327 // if they don't exist.
1328 for (i = 0; i < done.cnt; i++) {
1330 unsigned short state;
1331 int starts_line = 0;
1332 struct symbol *sym = g->symtab[done.syms[i]];
1333 struct symset newitemset = INIT_SYMSET;
1335 newitemset = INIT_DATASET;
1338 (sym->nullable && is->starts_line))
1340 for (j = 0; j < is->items.cnt; j++) {
1341 int itm = is->items.syms[j];
1342 int p = item_prod(itm);
1343 int bp = item_index(itm);
1344 struct production *pr = g->productions[p];
1345 unsigned short la = 0;
1348 if (bp == pr->body_size)
1350 if (pr->body[bp] != sym)
1353 la = is->items.data[j];
1354 pos = symset_find(&newitemset, pr->head->num);
1356 symset_add(&newitemset, item_num(p, bp+1), la);
1357 else if (type >= LALR) {
1358 // Need to merge la set.
1359 int la2 = newitemset.data[pos];
1361 struct symset ss = set_find(g, la2);
1362 struct symset LA = INIT_SYMSET;
1363 symset_union(&LA, &ss);
1364 ss = set_find(g, la);
1365 if (symset_union(&LA, &ss))
1366 newitemset.data[pos] = save_set(g, LA);
1372 state = add_itemset(g, newitemset, type, starts_line);
1373 if (symset_find(&is->go_to, done.syms[i]) < 0)
1374 symset_add(&is->go_to, done.syms[i], state);
1377 All that is left is to crate the initial itemset from production zero, and
1378 with `TK_eof` as the LA set.
1381 static void build_itemsets(struct grammar *g, enum grammar_type type)
1383 struct symset first = INIT_SYMSET;
1386 unsigned short la = 0;
1388 // LA set just has eof
1389 struct symset eof = INIT_SYMSET;
1390 symset_add(&eof, TK_eof, 0);
1391 la = save_set(g, eof);
1392 first = INIT_DATASET;
1394 // production 0, offset 0 (with no data)
1395 symset_add(&first, item_num(0, 0), la);
1396 add_itemset(g, first, type, g->productions[0]->body[0]->can_eol);
1397 for (again = 0, is = g->items;
1399 is = is->next ?: again ? (again = 0, g->items) : NULL) {
1401 struct symset done = INIT_SYMSET;
1412 ### Completing the analysis.
1414 The exact process of analysis depends on which level was requested. For
1415 `LR0` and `LR05` we don't need first and follow sets at all. For `LALR` and
1416 `LR1` we need first, but not follow. For `SLR` we need both.
1418 We don't build the "action" tables that you might expect as the parser
1419 doesn't use them. They will be calculated to some extent if needed for
1422 Once we have built everything we allocate arrays for the two lists:
1423 symbols and itemsets. This allows more efficient access during reporting.
1424 The symbols are grouped as terminals and non-terminals and we record the
1425 changeover point in `first_nonterm`.
1427 ###### grammar fields
1428 struct symbol **symtab;
1429 struct itemset **statetab;
1432 ###### grammar_analyse
1434 static void grammar_analyse(struct grammar *g, enum grammar_type type)
1438 int snum = TK_reserved;
1439 for (s = g->syms; s; s = s->next)
1440 if (s->num < 0 && s->type == Terminal) {
1444 g->first_nonterm = snum;
1445 for (s = g->syms; s; s = s->next)
1451 g->symtab = calloc(g->num_syms, sizeof(g->symtab[0]));
1452 for (s = g->syms; s; s = s->next)
1453 g->symtab[s->num] = s;
1463 build_itemsets(g, type);
1465 g->statetab = calloc(g->states, sizeof(g->statetab[0]));
1466 for (is = g->items; is ; is = is->next)
1467 g->statetab[is->state] = is;
1470 ## Reporting on the Grammar
1472 The purpose of the report is to give the grammar developer insight into
1473 how the grammar parser will work. It is basically a structured dump of
1474 all the tables that have been generated, plus a description of any conflicts.
1476 ###### grammar_report
1477 static int grammar_report(struct grammar *g, enum grammar_type type)
1483 return report_conflicts(g, type);
1486 Firstly we have the complete list of symbols, together with the
1487 "FIRST" set if that was generated. We add a mark to each symbol to
1488 show if it can end in a newline (`>`), or if it is nullable (`.`).
1492 static void report_symbols(struct grammar *g)
1496 printf("SYMBOLS + FIRST:\n");
1498 printf("SYMBOLS:\n");
1500 for (n = 0; n < g->num_syms; n++) {
1501 struct symbol *s = g->symtab[n];
1505 printf(" %c%c%3d%c: ",
1506 s->nullable ? '.':' ',
1507 s->can_eol ? '>':' ',
1508 s->num, symtypes[s->type]);
1511 printf(" (%d%s)", s->precedence,
1512 assoc_names[s->assoc]);
1514 if (g->first && s->type == Nonterminal) {
1517 for (j = 0; j < g->first[n].cnt; j++) {
1520 prtxt(g->symtab[g->first[n].syms[j]]->name);
1527 Then we have the follow sets if they were computed.
1529 static void report_follow(struct grammar *g)
1532 printf("FOLLOW:\n");
1533 for (n = 0; n < g->num_syms; n++)
1534 if (g->follow[n].cnt) {
1538 prtxt(g->symtab[n]->name);
1539 for (j = 0; j < g->follow[n].cnt; j++) {
1542 prtxt(g->symtab[g->follow[n].syms[j]]->name);
1548 And finally the item sets. These include the GO TO tables and, for
1549 LALR and LR1, the LA set for each item. Lots of stuff, so we break
1550 it up a bit. First the items, with production number and associativity.
1552 static void report_item(struct grammar *g, int itm)
1554 int p = item_prod(itm);
1555 int dot = item_index(itm);
1556 struct production *pr = g->productions[p];
1560 prtxt(pr->head->name);
1562 for (i = 0; i < pr->body_size; i++) {
1563 printf(" %s", (dot == i ? ". ": ""));
1564 prtxt(pr->body[i]->name);
1566 if (dot == pr->body_size)
1570 printf(" (%d%s)", pr->precedence,
1571 assoc_names[pr->assoc]);
1575 The LA sets which are (possibly) reported with each item:
1577 static void report_la(struct grammar *g, int lanum)
1579 struct symset la = set_find(g, lanum);
1583 printf(" LOOK AHEAD(%d)", lanum);
1584 for (i = 0; i < la.cnt; i++) {
1587 prtxt(g->symtab[la.syms[i]]->name);
1592 Then the go to sets:
1595 static void report_goto(struct grammar *g, struct symset gt)
1600 for (i = 0; i < gt.cnt; i++) {
1602 prtxt(g->symtab[gt.syms[i]]->name);
1603 printf(" -> %d\n", gt.data[i]);
1607 Now we can report all the item sets complete with items, LA sets, and GO TO.
1609 static void report_itemsets(struct grammar *g)
1612 printf("ITEM SETS(%d)\n", g->states);
1613 for (s = 0; s < g->states; s++) {
1615 struct itemset *is = g->statetab[s];
1616 printf(" Itemset %d:%s\n", s, is->starts_line?" (startsline)":"");
1617 for (j = 0; j < is->items.cnt; j++) {
1618 report_item(g, is->items.syms[j]);
1619 if (is->items.data != NO_DATA)
1620 report_la(g, is->items.data[j]);
1622 report_goto(g, is->go_to);
1626 ### Reporting conflicts
1628 Conflict detection varies a lot among different analysis levels. However
1629 LR0 and LR0.5 are quite similar - having no follow sets, and SLR, LALR and
1630 LR1 are also similar as they have FOLLOW or LA sets.
1634 ## conflict functions
1636 static int report_conflicts(struct grammar *g, enum grammar_type type)
1639 printf("Conflicts:\n");
1641 cnt = conflicts_lr0(g, type);
1643 cnt = conflicts_slr(g, type);
1645 printf(" - no conflicts\n");
1649 LR0 conflicts are any state which have both a reducible item and
1650 a shiftable item, or two reducible items.
1652 LR05 conflicts only occurs if two possibly reductions exist,
1653 as shifts always over-ride reductions.
1655 ###### conflict functions
1656 static int conflicts_lr0(struct grammar *g, enum grammar_type type)
1660 for (i = 0; i < g->states; i++) {
1661 struct itemset *is = g->statetab[i];
1662 int last_reduce = -1;
1663 int prev_reduce = -1;
1664 int last_shift = -1;
1668 for (j = 0; j < is->items.cnt; j++) {
1669 int itm = is->items.syms[j];
1670 int p = item_prod(itm);
1671 int bp = item_index(itm);
1672 struct production *pr = g->productions[p];
1674 if (bp == pr->body_size) {
1675 prev_reduce = last_reduce;
1679 if (pr->body[bp]->type == Terminal)
1682 if (type == LR0 && last_reduce >= 0 && last_shift >= 0) {
1683 printf(" State %d has both SHIFT and REDUCE:\n", i);
1684 report_item(g, is->items.syms[last_shift]);
1685 report_item(g, is->items.syms[last_reduce]);
1688 if (prev_reduce >= 0) {
1689 printf(" State %d has 2 (or more) reducible items\n", i);
1690 report_item(g, is->items.syms[prev_reduce]);
1691 report_item(g, is->items.syms[last_reduce]);
1698 SLR, LALR, and LR1 conflicts happen if two reducible items have over-lapping
1699 look ahead, or if a symbol in a look-ahead can be shifted. They differ only
1700 in the source of the look ahead set.
1702 We build two datasets to reflect the "action" table: one which maps
1703 terminals to items where that terminal could be shifted and another
1704 which maps terminals to items that could be reduced when the terminal
1705 is in look-ahead. We report when we get conflicts between the two.
1707 static int conflicts_slr(struct grammar *g, enum grammar_type type)
1712 for (i = 0; i < g->states; i++) {
1713 struct itemset *is = g->statetab[i];
1714 struct symset shifts = INIT_DATASET;
1715 struct symset reduce = INIT_DATASET;
1719 /* First collect the shifts */
1720 for (j = 0; j < is->items.cnt; j++) {
1721 unsigned short itm = is->items.syms[j];
1722 int p = item_prod(itm);
1723 int bp = item_index(itm);
1724 struct production *pr = g->productions[p];
1726 if (bp < pr->body_size &&
1727 pr->body[bp]->type == Terminal) {
1729 int sym = pr->body[bp]->num;
1730 if (symset_find(&shifts, sym) < 0)
1731 symset_add(&shifts, sym, itm);
1734 /* Now look for reduction and conflicts */
1735 for (j = 0; j < is->items.cnt; j++) {
1736 unsigned short itm = is->items.syms[j];
1737 int p = item_prod(itm);
1738 int bp = item_index(itm);
1739 struct production *pr = g->productions[p];
1741 if (bp < pr->body_size)
1746 la = g->follow[pr->head->num];
1748 la = set_find(g, is->items.data[j]);
1750 for (k = 0; k < la.cnt; k++) {
1751 int pos = symset_find(&shifts, la.syms[k]);
1753 printf(" State %d has SHIFT/REDUCE conflict on ", i);
1754 prtxt(g->symtab[la.syms[k]]->name);
1756 report_item(g, shifts.data[pos]);
1757 report_item(g, itm);
1760 pos = symset_find(&reduce, la.syms[k]);
1762 symset_add(&reduce, la.syms[k], itm);
1765 printf(" State %d has REDUCE/REDUCE conflict on ", i);
1766 prtxt(g->symtab[la.syms[k]]->name);
1768 report_item(g, itm);
1769 report_item(g, reduce.data[pos]);
1773 symset_free(shifts);
1774 symset_free(reduce);
1780 ## Generating the parser
1782 The exported part of the parser is the `parse_XX` function, where the name
1783 `XX` is based on the name of the parser files.
1785 This takes a `code_node`, a partially initialized `token_config`, and an
1786 optional `FILE` to send tracing to. The `token_config` gets the list of
1787 known words added and then is used with the `code_node` to initialize the
1790 `parse_XX` then calls the library function `parser_run` to actually complete
1791 the parse. This needs the `states` table and function to call the various
1792 pieces of code provided in the grammar file, so they are generated first.
1794 ###### parser_generate
1796 static void gen_parser(FILE *f, struct grammar *g, char *file, char *name)
1802 gen_reduce(f, g, file);
1805 fprintf(f, "#line 0 \"gen_parser\"\n");
1806 fprintf(f, "void *parse_%s(struct code_node *code, struct token_config *config, FILE *trace)\n",
1809 fprintf(f, "\tstruct token_state *tokens;\n");
1810 fprintf(f, "\tconfig->words_marks = known;\n");
1811 fprintf(f, "\tconfig->known_count = sizeof(known)/sizeof(known[0]);\n");
1812 fprintf(f, "\tconfig->ignored |= (1 << TK_line_comment) | (1 << TK_block_comment);\n");
1813 fprintf(f, "\ttokens = token_open(code, config);\n");
1814 fprintf(f, "\tvoid *rv = parser_run(tokens, states, do_reduce, do_free, trace, non_term, config->known_count);\n");
1815 fprintf(f, "\ttoken_close(tokens);\n");
1816 fprintf(f, "\treturn rv;\n");
1817 fprintf(f, "}\n\n");
1820 ### Known words table
1822 The known words table is simply an array of terminal symbols.
1823 The table of nonterminals used for tracing is a similar array.
1827 static void gen_known(FILE *f, struct grammar *g)
1830 fprintf(f, "#line 0 \"gen_known\"\n");
1831 fprintf(f, "static const char *known[] = {\n");
1832 for (i = TK_reserved;
1833 i < g->num_syms && g->symtab[i]->type == Terminal;
1835 fprintf(f, "\t\"%.*s\",\n", g->symtab[i]->name.len,
1836 g->symtab[i]->name.txt);
1837 fprintf(f, "};\n\n");
1840 static void gen_non_term(FILE *f, struct grammar *g)
1843 fprintf(f, "#line 0 \"gen_non_term\"\n");
1844 fprintf(f, "static const char *non_term[] = {\n");
1845 for (i = TK_reserved;
1848 if (g->symtab[i]->type == Nonterminal)
1849 fprintf(f, "\t\"%.*s\",\n", g->symtab[i]->name.len,
1850 g->symtab[i]->name.txt);
1851 fprintf(f, "};\n\n");
1854 ### States and the goto tables.
1856 For each state we record the goto table, the reducible production if
1857 there is one, or a symbol to shift for error recovery.
1858 Some of the details of the reducible production are stored in the
1859 `do_reduce` function to come later. Here we store the production number,
1860 the body size (useful for stack management) and the resulting symbol (useful
1861 for knowing how to free data later).
1863 The go to table is stored in a simple array of `sym` and corresponding
1866 ###### exported types
1874 const struct lookup * go_to;
1885 static void gen_goto(FILE *f, struct grammar *g)
1888 fprintf(f, "#line 0 \"gen_goto\"\n");
1889 for (i = 0; i < g->states; i++) {
1891 fprintf(f, "static const struct lookup goto_%d[] = {\n",
1893 struct symset gt = g->statetab[i]->go_to;
1894 for (j = 0; j < gt.cnt; j++)
1895 fprintf(f, "\t{ %d, %d },\n",
1896 gt.syms[j], gt.data[j]);
1903 static void gen_states(FILE *f, struct grammar *g)
1906 fprintf(f, "#line 0 \"gen_states\"\n");
1907 fprintf(f, "static const struct state states[] = {\n");
1908 for (i = 0; i < g->states; i++) {
1909 struct itemset *is = g->statetab[i];
1910 int j, prod = -1, prod_len;
1912 int shift_len = 0, shift_remain = 0;
1913 for (j = 0; j < is->items.cnt; j++) {
1914 int itm = is->items.syms[j];
1915 int p = item_prod(itm);
1916 int bp = item_index(itm);
1917 struct production *pr = g->productions[p];
1919 if (bp < pr->body_size) {
1920 if (shift_sym < 0 ||
1921 (shift_len == bp && shift_remain > pr->body_size - bp)) {
1922 shift_sym = pr->body[bp]->num;
1924 shift_remain = pr->body_size - bp;
1928 /* This is what we reduce */
1929 if (prod < 0 || prod_len < pr->body_size) {
1931 prod_len = pr->body_size;
1936 fprintf(f, "\t[%d] = { %d, goto_%d, %d, %d, %d, 0, %d },\n",
1937 i, is->go_to.cnt, i, prod,
1938 g->productions[prod]->body_size,
1939 g->productions[prod]->head->num,
1942 fprintf(f, "\t[%d] = { %d, goto_%d, -1, -1, -1, %d, %d },\n",
1943 i, is->go_to.cnt, i, shift_sym,
1946 fprintf(f, "};\n\n");
1949 ### The `do_reduce` function and the code
1951 When the parser engine decides to reduce a production, it calls `do_reduce`.
1952 This has two functions.
1954 Firstly, if a non-NULL `trace` file is passed, it prints out details of the
1955 production being reduced. Secondly it runs the code that was included with
1956 the production if any.
1958 This code needs to be able to store data somewhere. Rather than requiring
1959 `do_reduce` to `malloc` that "somewhere", we pass in a large buffer and have
1960 `do_reduce` return the size to be saved.
1962 The code fragment requires translation when written out. Any `$N` needs to
1963 be converted to a reference either to that buffer (if `$0`) or to the
1964 structure returned by a previous reduction. These pointers need to be cast
1965 to the appropriate type for each access. All this is handling in
1971 static void gen_code(struct production *p, FILE *f, struct grammar *g)
1974 fprintf(f, "\t\t\t");
1975 for (c = p->code.txt; c < p->code.txt + p->code.len; c++) {
1984 if (*c < '0' || *c > '9') {
1989 while (c[1] >= '0' && c[1] <= '9') {
1991 n = n * 10 + *c - '0';
1994 fprintf(f, "(*(struct %.*s*%s)ret)",
1995 p->head->struct_name.len,
1996 p->head->struct_name.txt,
1997 p->head->isref ? "*":"");
1998 else if (n > p->body_size)
1999 fprintf(f, "$%d", n);
2000 else if (p->body[n-1]->type == Terminal)
2001 fprintf(f, "(*(struct token *)body[%d])",
2003 else if (p->body[n-1]->struct_name.txt == NULL)
2004 fprintf(f, "$%d", n);
2006 fprintf(f, "(*(struct %.*s*%s)body[%d])",
2007 p->body[n-1]->struct_name.len,
2008 p->body[n-1]->struct_name.txt,
2009 p->body[n-1]->isref ? "*":"", n-1);
2016 static void gen_reduce(FILE *f, struct grammar *g, char *file)
2019 fprintf(f, "#line 0 \"gen_reduce\"\n");
2020 fprintf(f, "static int do_reduce(int prod, void **body, void *ret)\n");
2022 fprintf(f, "\tint ret_size = 0;\n");
2024 fprintf(f, "\tswitch(prod) {\n");
2025 for (i = 0; i < g->production_count; i++) {
2026 struct production *p = g->productions[i];
2027 fprintf(f, "\tcase %d:\n", i);
2032 if (p->head->struct_name.txt)
2033 fprintf(f, "\t\tret_size = sizeof(struct %.*s%s);\n",
2034 p->head->struct_name.len,
2035 p->head->struct_name.txt,
2036 p->head->isref ? "*":"");
2038 fprintf(f, "\t\tbreak;\n");
2040 fprintf(f, "\t}\n\treturn ret_size;\n}\n\n");
2045 As each non-terminal can potentially cause a different type of data
2046 structure to be allocated and filled in, we need to be able to free it when
2049 It is particularly important to have fine control over freeing during error
2050 recovery where individual stack frames might need to be freed.
2052 For this, the grammar author is required to defined a `free_XX` function for
2053 each structure that is used by a non-terminal. `do_free` will call whichever
2054 is appropriate given a symbol number, and will call `free` (as is
2055 appropriate for tokens on any terminal symbol.
2059 static void gen_free(FILE *f, struct grammar *g)
2063 fprintf(f, "#line 0 \"gen_free\"\n");
2064 fprintf(f, "static void do_free(short sym, void *asn)\n");
2066 fprintf(f, "\tif (!asn) return;\n");
2067 fprintf(f, "\tif (sym < %d) {\n", g->first_nonterm);
2068 fprintf(f, "\t\tfree(asn);\n\t\treturn;\n\t}\n");
2069 fprintf(f, "\tswitch(sym) {\n");
2071 for (i = 0; i < g->num_syms; i++) {
2072 struct symbol *s = g->symtab[i];
2074 s->type != Nonterminal ||
2075 s->struct_name.txt == NULL)
2078 fprintf(f, "\tcase %d:\n", s->num);
2080 fprintf(f, "\t\tfree_%.*s(*(void**)asn);\n",
2082 s->struct_name.txt);
2084 fprintf(f, "\t\tfree_%.*s(asn);\n",
2086 s->struct_name.txt);
2087 fprintf(f, "\t\tbreak;\n");
2089 fprintf(f, "\t}\n}\n\n");
2092 ## The main routine.
2094 There are three key parts to the "main" function of parsergen: processing
2095 the arguments, loading the grammar file, and dealing with the grammar.
2097 ### Argument processing.
2099 Command line options allow the selection of analysis mode, name of output
2100 file, and whether or not a report should be generated. By default we create
2101 a report only if no code output was requested.
2103 The `parse_XX` function name uses the basename of the output file which
2104 should not have a suffix (`.c`). `.c` is added to the given name for the
2105 code, and `.h` is added for the header (if header text is specifed in the
2112 static const struct option long_options[] = {
2113 { "LR0", 0, NULL, '0' },
2114 { "LR05", 0, NULL, '5' },
2115 { "SLR", 0, NULL, 'S' },
2116 { "LALR", 0, NULL, 'L' },
2117 { "LR1", 0, NULL, '1' },
2118 { "tag", 1, NULL, 't' },
2119 { "report", 0, NULL, 'R' },
2120 { "output", 1, NULL, 'o' },
2121 { NULL, 0, NULL, 0 }
2123 const char *options = "05SL1t:Ro:";
2125 ###### process arguments
2127 char *outfile = NULL;
2132 enum grammar_type type = LR05;
2133 while ((opt = getopt_long(argc, argv, options,
2134 long_options, NULL)) != -1) {
2149 outfile = optarg; break;
2151 tag = optarg; break;
2153 fprintf(stderr, "Usage: parsergen ...\n");
2158 infile = argv[optind++];
2160 fprintf(stderr, "No input file given\n");
2163 if (outfile && report == 1)
2166 if (name && strchr(name, '/'))
2167 name = strrchr(name, '/')+1;
2169 if (optind < argc) {
2170 fprintf(stderr, "Excess command line arguments\n");
2174 ### Loading the grammar file
2176 To be able to run `mdcode` and `scanner` on the grammar we need to memory
2179 One we have extracted the code (with `mdcode`) we expect to find three
2180 sections: header, code, and grammar. Anything else that is not
2181 excluded by the `--tag` option is an error.
2183 "header" and "code" are optional, though it is hard to build a working
2184 parser with neither. "grammar" must be provided.
2188 #include <sys/mman.h>
2193 static void pr_err(char *msg)
2196 fprintf(stderr, "%s\n", msg);
2200 struct section *table;
2204 fd = open(infile, O_RDONLY);
2206 fprintf(stderr, "parsergen: cannot open %s: %s\n",
2207 infile, strerror(errno));
2210 len = lseek(fd, 0, 2);
2211 file = mmap(NULL, len, PROT_READ, MAP_SHARED, fd, 0);
2212 table = code_extract(file, file+len, pr_err);
2214 struct code_node *hdr = NULL;
2215 struct code_node *code = NULL;
2216 struct code_node *gram = NULL;
2217 for (s = table; s; s = s->next) {
2218 struct text sec = s->section;
2219 if (tag && !strip_tag(&sec, tag))
2221 if (text_is(sec, "header"))
2223 else if (text_is(sec, "code"))
2225 else if (text_is(sec, "grammar"))
2228 fprintf(stderr, "Unknown content section: %.*s\n",
2229 s->section.len, s->section.txt);
2234 ### Processing the input
2236 As we need to append an extention to a filename and then open it for
2237 writing, and we need to do this twice, it helps to have a separate function.
2241 static FILE *open_ext(char *base, char *ext)
2243 char *fn = malloc(strlen(base) + strlen(ext) + 1);
2245 strcat(strcpy(fn, base), ext);
2251 If we can read the grammar, then we analyse and optionally report on it. If
2252 the report finds conflicts we will exit with an error status.
2254 ###### process input
2255 struct grammar *g = NULL;
2257 fprintf(stderr, "No grammar section provided\n");
2260 g = grammar_read(gram);
2262 fprintf(stderr, "Failure to parse grammar\n");
2267 grammar_analyse(g, type);
2269 if (grammar_report(g, type))
2273 If a headers section is defined, we write it out and include a declaration
2274 for the `parse_XX` function so it can be used from separate code.
2276 if (rv == 0 && hdr && outfile) {
2277 FILE *f = open_ext(outfile, ".h");
2279 code_node_print(f, hdr, infile);
2280 fprintf(f, "void *parse_%s(struct code_node *code, struct token_config *config, FILE *trace);\n",
2284 fprintf(stderr, "Cannot create %s.h\n",
2290 And if all goes well and an output file was provided, we create the `.c`
2291 file with the code section (if any) and the parser tables and function.
2293 if (rv == 0 && outfile) {
2294 FILE *f = open_ext(outfile, ".c");
2297 code_node_print(f, code, infile);
2298 gen_parser(f, g, infile, name);
2301 fprintf(stderr, "Cannot create %s.c\n",
2307 And that about wraps it up. We need to set the locale so that UTF-8 is
2308 recognised properly, and link with `libicuuc` as `libmdcode` requires that.
2310 ###### File: parsergen.mk
2311 parsergen : parsergen.o libscanner.o libmdcode.o
2312 $(CC) $(CFLAGS) -o parsergen parsergen.o libscanner.o libmdcode.o -licuuc
2319 int main(int argc, char *argv[])
2324 setlocale(LC_ALL,"");
2326 ## process arguments
2333 ## The SHIFT/REDUCE parser
2335 Having analysed the grammar and generated all the tables, we only need the
2336 shift/reduce engine to bring it all together.
2338 ### Goto table lookup
2340 The parser generator has nicely provided us with goto tables sorted by
2341 symbol number. We need a binary search function to find a symbol in the
2344 ###### parser functions
2346 static int search(const struct state *l, int sym)
2349 int hi = l->go_to_cnt;
2353 while (lo + 1 < hi) {
2354 int mid = (lo + hi) / 2;
2355 if (l->go_to[mid].sym <= sym)
2360 if (l->go_to[lo].sym == sym)
2361 return l->go_to[lo].state;
2366 ### The state stack.
2368 The core data structure for the parser is the stack. This tracks all the
2369 symbols that have been recognised or partially recognised.
2371 The stack usually won't grow very large - maybe a few tens of entries. So
2372 we dynamically resize and array as required but never bother to shrink it
2375 We keep the stack as two separate allocations. One, `asn_stack` stores the
2376 "abstract syntax nodes" which are created by each reduction. When we call
2377 `do_reduce` we need to pass an array of the `asn`s of the body of the
2378 production, and by keeping a separate `asn` stack, we can just pass a
2379 pointer into this stack.
2381 The other allocation stores all other stack fields of which there are six.
2382 The `state` is the most important one and guides the parsing process. The
2383 `sym` is nearly unnecessary. However when we want to free entries from the
2384 `asn_stack`, it helps to know what type they are so we can call the right
2385 freeing function. The symbol leads us to the right free function through
2388 The `indents` count and the `starts_indented` flag track the line
2389 indents in the symbol. These are used to allow indent information to
2390 guide parsing and error recovery.
2392 `newline_permitted` keeps track of whether newlines should be ignored
2393 or not, and `starts_line` records if this state stated on a newline.
2395 As well as the stack of frames we have a `next` frame which is
2396 assembled from the incoming token and other information prior to
2397 pushing it onto the stack.
2399 ###### parser functions
2405 short starts_indented;
2407 short newline_permitted;
2416 Two operations are needed on the stack - shift (which is like push) and pop.
2418 Shift applies not only to terminals but also to non-terminals. When we
2419 reduce a production we will pop off entries corresponding to the body
2420 symbols, then push on an item for the head of the production. This last is
2421 exactly the same process as shifting in a terminal so we use the same
2424 To simplify other code we arrange for `shift` to fail if there is no `goto`
2425 state for the symbol. This is useful in basic parsing due to our design
2426 that we shift when we can, and reduce when we cannot. So the `shift`
2427 function reports if it could.
2429 So `shift` finds the next state. If that succeed it extends the allocations
2430 if needed and pushes all the information onto the stacks.
2432 ###### parser functions
2434 static int shift(struct parser *p,
2436 const struct state states[])
2438 // Push an entry onto the stack
2439 int newstate = search(&states[p->next.state], p->next.sym);
2442 if (p->tos >= p->stack_size) {
2443 p->stack_size += 10;
2444 p->stack = realloc(p->stack, p->stack_size
2445 * sizeof(p->stack[0]));
2446 p->asn_stack = realloc(p->asn_stack, p->stack_size
2447 * sizeof(p->asn_stack[0]));
2449 p->stack[p->tos] = p->next;
2450 p->asn_stack[p->tos] = asn;
2452 p->next.state = newstate;
2453 p->next.indents = 0;
2454 p->next.starts_indented = 0;
2455 // if new state doesn't start a line, we inherit newline_permitted status
2456 if (states[newstate].starts_line)
2457 p->next.newline_permitted = 1;
2461 `pop` simply moves the top of stack (`tos`) back down the required amount
2462 and frees any `asn` entries that need to be freed. It is called _after_ we
2463 reduce a production, just before we `shift` the nonterminal in.
2465 ###### parser functions
2467 static void pop(struct parser *p, int num,
2468 void(*do_free)(short sym, void *asn))
2472 for (i = 0; i < num; i++) {
2473 p->next.indents += p->stack[p->tos+i].indents;
2474 do_free(p->stack[p->tos+i].sym,
2475 p->asn_stack[p->tos+i]);
2479 p->next.state = p->stack[p->tos].state;
2480 p->next.starts_indented = p->stack[p->tos].starts_indented;
2481 p->next.newline_permitted = p->stack[p->tos].newline_permitted;
2482 if (p->next.indents > p->next.starts_indented)
2483 p->next.newline_permitted = 0;
2487 ### Memory allocation
2489 The `scanner` returns tokens in a local variable - we want them in allocated
2490 memory so they can live in the `asn_stack`. Similarly the `asn` produced by
2491 a reduce is in a large buffer. Both of these require some allocation and
2492 copying, hence `memdup` and `tokcopy`.
2494 ###### parser includes
2497 ###### parser functions
2499 void *memdup(void *m, int len)
2505 memcpy(ret, m, len);
2509 static struct token *tok_copy(struct token tk)
2511 struct token *new = malloc(sizeof(*new));
2516 ### The heart of the parser.
2518 Now we have the parser. If we can shift, we do. If not and we can reduce
2519 we do. If the production we reduced was production zero, then we have
2520 accepted the input and can finish.
2522 We return whatever `asn` was returned by reducing production zero.
2524 If we can neither shift nor reduce we have an error to handle. We pop
2525 single entries off the stack until we can shift the `TK_error` symbol, then
2526 drop input tokens until we find one we can shift into the new error state.
2528 When we find `TK_in` and `TK_out` tokens which report indents we need
2529 to handle them directly as the grammar cannot express what we want to
2532 `TK_in` tokens are easy: we simply update the `next` stack frame to
2533 record how many indents there are and that the next token started with
2536 `TK_out` tokens must either be counted off against any pending indent,
2537 or must force reductions until there is a pending indent which isn't
2538 at the start of a production.
2540 `TK_newline` tokens are ignored precisely if there has been an indent
2541 since the last state which could have been at the start of a line.
2543 ###### parser includes
2546 void *parser_run(struct token_state *tokens,
2547 const struct state states[],
2548 int (*do_reduce)(int, void**, void*),
2549 void (*do_free)(short, void*),
2550 FILE *trace, const char *non_term[], int knowns)
2552 struct parser p = { 0 };
2553 struct token *tk = NULL;
2557 p.next.newline_permitted = states[0].starts_line;
2559 struct token *err_tk;
2561 tk = tok_copy(token_next(tokens));
2562 p.next.sym = tk->num;
2564 parser_trace(trace, &p, tk, states, non_term, knowns);
2566 if (p.next.sym == TK_in) {
2567 p.next.starts_indented = 1;
2573 if (p.next.sym == TK_out) {
2574 if (p.stack[p.tos-1].indents > p.stack[p.tos-1].starts_indented ||
2575 (p.stack[p.tos-1].indents == 1 &&
2576 states[p.next.state].reduce_size > 1)) {
2577 p.stack[p.tos-1].indents -= 1;
2578 if (p.stack[p.tos-1].indents == p.stack[p.tos-1].starts_indented) {
2579 // no internal indent any more, reassess 'newline_permitted'
2580 if (states[p.stack[p.tos-1].state].starts_line)
2581 p.stack[p.tos-1].newline_permitted = 1;
2583 p.stack[p.tos-1].newline_permitted = p.stack[p.tos-2].newline_permitted;
2589 // fall through and force a REDUCE (as 'shift'
2592 if (p.next.sym == TK_newline) {
2593 if (!p.tos || ! p.stack[p.tos-1].newline_permitted) {
2599 if (shift(&p, tk, states)) {
2603 if (states[p.next.state].reduce_prod >= 0) {
2605 int prod = states[p.next.state].reduce_prod;
2606 int size = states[p.next.state].reduce_size;
2608 static char buf[16*1024];
2609 p.next.sym = states[p.next.state].reduce_sym;
2611 body = p.asn_stack +
2612 (p.tos - states[p.next.state].reduce_size);
2614 bufsize = do_reduce(prod, body, buf);
2616 pop(&p, size, do_free);
2617 shift(&p, memdup(buf, bufsize), states);
2622 if (tk->num == TK_out) {
2623 // Indent problem - synthesise tokens to get us
2625 fprintf(stderr, "Synthesize %d to handle indent problem\n", states[p.next.state].shift_sym);
2626 p.next.sym = states[p.next.state].shift_sym;
2627 shift(&p, tok_copy(*tk), states);
2628 // FIXME need to report this error somehow
2631 /* Error. We walk up the stack until we
2632 * find a state which will accept TK_error.
2633 * We then shift in TK_error and see what state
2634 * that takes us too.
2635 * Then we discard input tokens until
2636 * we find one that is acceptable.
2639 err_tk = tok_copy(*tk);
2640 p.next.sym = TK_error;
2641 while (shift(&p, err_tk, states) == 0
2643 // discard this state
2644 pop(&p, 1, do_free);
2647 // no state accepted TK_error
2650 while (search(&states[p.next.state], tk->num) < 0 &&
2651 tk->num != TK_eof) {
2653 tk = tok_copy(token_next(tokens));
2654 if (tk->num == TK_in)
2655 p.next.indents += 1;
2656 if (tk->num == TK_out) {
2657 if (p.next.indents == 0)
2659 p.next.indents -= 1;
2662 if (p.tos == 0 && tk->num == TK_eof)
2667 ret = p.asn_stack[0];
2669 pop(&p, p.tos, do_free);
2675 ###### exported functions
2676 void *parser_run(struct token_state *tokens,
2677 const struct state states[],
2678 int (*do_reduce)(int, void**, void*),
2679 void (*do_free)(short, void*),
2680 FILE *trace, const char *non_term[], int knowns);
2684 Being able to visualize the parser in action can be invaluable when
2685 debugging the parser code, or trying to understand how the parse of a
2686 particular grammar progresses. The stack contains all the important
2687 state, so just printing out the stack every time around the parse loop
2688 can make it possible to see exactly what is happening.
2690 This doesn't explicitly show each SHIFT and REDUCE action. However they
2691 are easily deduced from the change between consecutive lines, and the
2692 details of each state can be found by cross referencing the states list
2693 in the stack with the "report" that parsergen can generate.
2695 For terminal symbols, we just dump the token. For non-terminals we
2696 print the name of the symbol. The look ahead token is reported at the
2697 end inside square brackets.
2699 ###### parser functions
2701 static char *reserved_words[] = {
2702 [TK_error] = "ERROR",
2705 [TK_newline] = "NEWLINE",
2708 static void parser_trace_state(FILE *trace, struct frame *f, const struct state states[])
2710 fprintf(trace, "(%d", f->state);
2712 fprintf(trace, "%c%d", f->starts_indented?':':'.',
2714 if (states[f->state].starts_line)
2715 fprintf(trace, "s");
2716 if (f->newline_permitted)
2717 fprintf(trace, "n");
2718 fprintf(trace, ") ");
2721 void parser_trace(FILE *trace, struct parser *p,
2722 struct token *tk, const struct state states[],
2723 const char *non_term[], int knowns)
2726 for (i = 0; i < p->tos; i++) {
2727 int sym = p->stack[i].sym;
2728 parser_trace_state(trace, &p->stack[i], states);
2729 if (sym < TK_reserved &&
2730 reserved_words[sym] != NULL)
2731 fputs(reserved_words[sym], trace);
2732 else if (sym < TK_reserved + knowns) {
2733 struct token *t = p->asn_stack[i];
2734 text_dump(trace, t->txt, 20);
2736 fputs(non_term[sym - TK_reserved - knowns],
2740 parser_trace_state(trace, &p->next, states);
2741 fprintf(trace, " [");
2742 if (tk->num < TK_reserved &&
2743 reserved_words[tk->num] != NULL)
2744 fputs(reserved_words[tk->num], trace);
2746 text_dump(trace, tk->txt, 20);
2747 fputs("]\n", trace);
2752 The obvious example for a parser is a calculator.
2754 As `scanner` provides number parsing function using `libgmp` is it not much
2755 work to perform arbitrary rational number calculations.
2757 This calculator takes one expression, or an equality test per line. The
2758 results are printed and if any equality test fails, the program exits with
2761 ###### File: parsergen.mk
2762 calc.c calc.h : parsergen parsergen.mdc
2763 ./parsergen --tag calc -o calc parsergen.mdc
2764 calc : calc.o libparser.o libscanner.o libmdcode.o libnumber.o
2765 $(CC) $(CFLAGS) -o calc calc.o libparser.o libscanner.o libmdcode.o libnumber.o -licuuc -lgmp
2770 // what do we use for a demo-grammar? A calculator of course.
2782 #include <sys/mman.h>
2787 #include "scanner.h"
2793 static void free_number(struct number *n)
2799 int main(int argc, char *argv[])
2801 int fd = open(argv[1], O_RDONLY);
2802 int len = lseek(fd, 0, 2);
2803 char *file = mmap(NULL, len, PROT_READ, MAP_SHARED, fd, 0);
2804 struct section *s = code_extract(file, file+len, NULL);
2805 struct token_config config = {
2806 .ignored = (1 << TK_line_comment)
2807 | (1 << TK_block_comment)
2810 .number_chars = ".,_+-",
2814 parse_calc(s->code, &config, argc > 2 ? stderr : NULL);
2820 Session -> Session Line
2823 Line -> Expression NEWLINE ${ gmp_printf("Answer = %Qd\n", $1.val);
2824 { mpf_t fl; mpf_init2(fl, 20); mpf_set_q(fl, $1.val);
2825 gmp_printf(" or as a decimal: %Fg\n", fl);
2829 | Expression = Expression NEWLINE ${
2830 if (mpq_equal($1.val, $3.val))
2831 gmp_printf("Both equal %Qd\n", $1.val);
2833 gmp_printf("NOT EQUAL: %Qd\n != : %Qd\n",
2838 | NEWLINE ${ printf("Blank line\n"); }$
2839 | ERROR NEWLINE ${ printf("Skipped a bad line\n"); }$
2842 Expression -> Expression + Term ${ mpq_init($0.val); mpq_add($0.val, $1.val, $3.val); }$
2843 | Expression - Term ${ mpq_init($0.val); mpq_sub($0.val, $1.val, $3.val); }$
2844 | Term ${ mpq_init($0.val); mpq_set($0.val, $1.val); }$
2846 Term -> Term * Factor ${ mpq_init($0.val); mpq_mul($0.val, $1.val, $3.val); }$
2847 | Term / Factor ${ mpq_init($0.val); mpq_div($0.val, $1.val, $3.val); }$
2848 | Factor ${ mpq_init($0.val); mpq_set($0.val, $1.val); }$
2850 Factor -> NUMBER ${ if (number_parse($0.val, $0.tail, $1.txt) == 0) mpq_init($0.val); }$
2851 | ( Expression ) ${ mpq_init($0.val); mpq_set($0.val, $2.val); }$
code / ocean / blob