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.
24 ###### File: parsergen.c
29 ## forward declarations
40 ###### File: libparser.c
47 ###### File: parsergen.mk
50 parsergen.c parsergen.mk libparser.c parser.h : parsergen.mdc
53 ## Reading the grammar
55 The grammar must be stored in a markdown literate code file as parsed
56 by "[mdcode][]". It must have three top level (i.e. unreferenced)
57 sections: `header`, `code`, and `grammar`. The first two will be
58 literally copied into the generated `.c` and `.h`. files. The last
59 contains the grammar. This is tokenised with "[scanner][]".
61 If the `--tag` option is given, then any top level header that doesn't
62 start with the tag is ignored, and the tag is striped from the rest. So
64 means that the three needed sections must be `Foo: header`, `Foo: code`,
65 and `Foo: grammar`. The tag `calc` is used to extract the same calculator
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;
110 The strings reported by `mdcode` and `scanner` are `struct text` which have
111 length rather than being null terminated. To help with printing and
112 comparing we define `text_is` and `prtxt`, which should possibly go in
113 `mdcode`. `scanner` does provide `text_dump` which is useful for strings
114 which might contain control characters.
116 `strip_tag` is a bit like `strncmp`, but adds a test for a colon,
117 because that is what we need to detect tags.
120 static int text_is(struct text t, char *s)
122 return (strlen(s) == t.len &&
123 strncmp(s, t.txt, t.len) == 0);
125 static void prtxt(struct text t)
127 printf("%.*s", t.len, t.txt);
130 static int strip_tag(struct text *t, char *tag)
132 int skip = strlen(tag) + 1;
133 if (skip >= t->len ||
134 strncmp(t->txt, tag, skip-1) != 0 ||
135 t->txt[skip-1] != ':')
137 while (skip < t->len && t->txt[skip] == ' ')
146 Productions are comprised primarily of symbols - terminal and
147 non-terminal. We do not make a syntactic distinction between the two,
148 though non-terminals must be identifiers. Non-terminal symbols are
149 those which appear in the head of a production, terminal symbols are
150 those which don't. There are also "virtual" symbols used for precedence
151 marking discussed later, and sometimes we won't know what type a symbol
154 ###### forward declarations
155 enum symtype { Unknown, Virtual, Terminal, Nonterminal };
156 char *symtypes = "UVTN";
160 Symbols can be either `TK_ident` or `TK_mark`. They are saved in a
161 table of known symbols and the resulting parser will report them as
162 `TK_reserved + N`. A small set of identifiers are reserved for the
163 different token types that `scanner` can report.
166 static char *reserved_words[] = {
167 [TK_error] = "ERROR",
168 [TK_number] = "NUMBER",
169 [TK_ident] = "IDENTIFIER",
171 [TK_string] = "STRING",
172 [TK_multi_string] = "MULTI_STRING",
175 [TK_newline] = "NEWLINE",
181 Note that `TK_eof` and the two `TK_*_comment` tokens cannot be
182 recognised. The former is automatically expected at the end of the text
183 being parsed. The latter are always ignored by the parser.
185 All of these symbols are stored in a simple symbol table. We use the
186 `struct text` from `mdcode` to store the name and link them together
187 into a sorted list using an insertion sort.
189 We don't have separate `find` and `insert` functions as any symbol we
190 find needs to be remembered. We simply expect `find` to always return a
191 symbol, but its type might be `Unknown`.
200 ###### grammar fields
205 static struct symbol *sym_find(struct grammar *g, struct text s)
207 struct symbol **l = &g->syms;
212 (cmp = text_cmp((*l)->name, s)) < 0)
216 n = calloc(1, sizeof(*n));
225 static void symbols_init(struct grammar *g)
227 int entries = sizeof(reserved_words)/sizeof(reserved_words[0]);
229 for (i = 0; i < entries; i++) {
232 t.txt = reserved_words[i];
235 t.len = strlen(t.txt);
242 ### Data types and precedence.
244 Data type specification and precedence specification are both
245 introduced by a dollar sign at the start of the line. If the next
246 word is `LEFT`, `RIGHT` or `NON`, then the line specifies a
247 precedence, otherwise it specifies a data type.
249 The data type name is simply stored and applied to the head of all
250 subsequent productions. It must be the name of a structure optionally
251 preceded by an asterisk which means a reference or "pointer". So
252 `$expression` maps to `struct expression` and `$*statement` maps to
253 `struct statement *`.
255 Any productions given before the first data type declaration will have
256 no data type associated with them and can carry no information. In
257 order to allow other non-terminals to have no type, the data type
258 `$void` can be given. This does *not* mean that `struct void` will be
259 used, but rather than no type will be associated with future
262 The precedence line must contain a list of symbols - typically
263 terminal symbols, but not necessarily. It can only contain symbols
264 that have not been seen yet, so precedence declaration must precede
265 the productions that they affect.
267 A precedence line may also contain a "virtual" symbol which is an
268 identifier preceded by `$$`. Virtual terminals carry precedence
269 information but are not included in the grammar. A production can
270 declare that it inherits the precedence of a given virtual symbol.
272 This use for `$$` precludes it from being used as a symbol in the
273 described language. Two other symbols: `${` and `}$` are also
276 Each new precedence line introduces a new precedence level and
277 declares how it associates. This level is stored in each symbol
278 listed and may be inherited by any production which uses the symbol. A
279 production inherits from the last symbol which has a precedence.
281 The symbols on the first precedence line have the lowest precedence.
282 Subsequent lines introduce symbols with higher precedence.
284 ###### grammar fields
285 struct text current_type;
290 enum symbols { TK_virtual = TK_reserved, TK_open, TK_close };
291 static const char *known[] = { "$$", "${", "}$" };
294 static char *dollar_line(struct token_state *ts, struct grammar *g, int isref)
296 struct token t = token_next(ts);
301 if (t.num != TK_ident) {
302 err = "type or assoc expected after '$'";
305 if (text_is(t.txt, "LEFT"))
307 else if (text_is(t.txt, "RIGHT"))
309 else if (text_is(t.txt, "NON"))
312 g->current_type = t.txt;
313 g->type_isref = isref;
314 if (text_is(t.txt, "void"))
315 g->current_type.txt = NULL;
317 if (t.num != TK_newline) {
318 err = "Extra tokens after type name";
325 err = "$* cannot be followed by a precedence";
329 // This is a precedence line, need some symbols.
333 while (t.num != TK_newline) {
334 enum symtype type = Terminal;
336 if (t.num == TK_virtual) {
339 if (t.num != TK_ident) {
340 err = "$$ must be followed by a word";
343 } else if (t.num != TK_ident &&
345 err = "Illegal token in precedence line";
348 s = sym_find(g, t.txt);
349 if (s->type != Unknown) {
350 err = "Symbols in precedence line must not already be known.";
354 s->precedence = g->prec_levels;
360 err = "No symbols given on precedence line";
364 while (t.num != TK_newline && t.num != TK_eof)
371 A production either starts with an identifier which is the head
372 non-terminal, or a vertical bar (`|`) in which case this production
373 uses the same head as the previous one. The identifier must be
374 followed by a `->` mark. All productions for a given non-terminal must
375 be grouped together with the `nonterminal ->` given only once.
377 After this a (possibly empty) sequence of identifiers and marks form
378 the body of the production. A virtual symbol may be given after the
379 body by preceding it with `$$`. If a virtual symbol is given, the
380 precedence of the production is that for the virtual symbol. If none
381 is given, the precedence is inherited from the last symbol in the
382 production which has a precedence specified.
384 After the optional precedence may come the `${` mark. This indicates
385 the start of a code fragment. If present, this must be on the same
386 line as the start of the production.
388 All of the text from the `${` through to the matching `}$` is
389 collected and forms the code-fragment for the production. It must all
390 be in one `code_node` of the literate code. The `}$` must be
391 at the end of a line.
393 Text in the code fragment will undergo substitutions where `$N` or
394 `$<N`,for some numeric `N`, will be replaced with a variable holding
395 the parse information for the particular symbol in the production.
396 `$0` is the head of the production, `$1` is the first symbol of the
397 body, etc. The type of `$N` for a terminal symbol is `struct token`.
398 For a non-terminal, it is whatever has been declared for that symbol.
399 The `<` may be included for symbols declared as storing a reference
400 (not a structure) and means that the reference is being moved out, so
401 it will not automatically be freed.
403 While building productions we will need to add to an array which needs to
407 static void array_add(void *varray, int *cnt, void *new)
409 void ***array = varray;
412 current = ((*cnt-1) | (step-1))+1;
413 if (*cnt == current) {
416 *array = realloc(*array, current * sizeof(void*));
418 (*array)[*cnt] = new;
422 Collecting the code fragment simply involves reading tokens until we
423 hit the end token `}$`, and noting the character position of the start and
427 static struct text collect_code(struct token_state *state,
432 code.txt = start.txt.txt + start.txt.len;
434 t = token_next(state);
435 while (t.node == start.node &&
436 t.num != TK_close && t.num != TK_error &&
438 if (t.num == TK_close && t.node == start.node)
439 code.len = t.txt.txt - code.txt;
445 Now we have all the bits we need to parse a full production.
450 ###### grammar fields
451 struct production **productions;
452 int production_count;
454 ###### production fields
456 struct symbol **body;
462 int first_production;
465 static char *parse_production(struct grammar *g,
467 struct token_state *state)
469 /* Head has already been parsed. */
472 struct production p, *pp;
474 memset(&p, 0, sizeof(p));
476 tk = token_next(state);
477 while (tk.num == TK_ident || tk.num == TK_mark) {
478 struct symbol *bs = sym_find(g, tk.txt);
479 if (bs->type == Unknown)
481 if (bs->type == Virtual) {
482 err = "Virtual symbol not permitted in production";
485 if (bs->precedence) {
486 p.precedence = bs->precedence;
489 array_add(&p.body, &p.body_size, bs);
490 tk = token_next(state);
492 if (tk.num == TK_virtual) {
494 tk = token_next(state);
495 if (tk.num != TK_ident) {
496 err = "word required after $$";
499 vs = sym_find(g, tk.txt);
500 if (vs->num == TK_newline)
502 else if (vs->precedence == 0) {
503 err = "symbol after $$ must have precedence";
506 p.precedence = vs->precedence;
509 tk = token_next(state);
511 if (tk.num == TK_open) {
512 p.code_line = tk.line;
513 p.code = collect_code(state, tk);
514 if (p.code.txt == NULL) {
515 err = "code fragment not closed properly";
518 tk = token_next(state);
520 if (tk.num != TK_newline && tk.num != TK_eof) {
521 err = "stray tokens at end of line";
524 pp = malloc(sizeof(*pp));
526 array_add(&g->productions, &g->production_count, pp);
529 while (tk.num != TK_newline && tk.num != TK_eof)
530 tk = token_next(state);
534 With the ability to parse production and dollar-lines, we have nearly all
535 that we need to parse a grammar from a `code_node`.
537 The head of the first production will effectively be the `start` symbol of
538 the grammar. However it won't _actually_ be so. Processing the grammar is
539 greatly simplified if the real start symbol only has a single production,
540 and expects `$eof` as the final terminal. So when we find the first
541 explicit production we insert an extra production as production zero which
544 ###### Example: production 0
547 where `START` is the first non-terminal given.
549 ###### create production zero
550 struct production *p = calloc(1,sizeof(*p));
551 struct text start = {"$start",6};
552 struct text eof = {"$eof",4};
553 struct text code = {"$0 = $<1;", 9};
554 p->head = sym_find(g, start);
555 p->head->type = Nonterminal;
556 p->head->struct_name = g->current_type;
557 p->head->isref = g->type_isref;
558 if (g->current_type.txt)
560 array_add(&p->body, &p->body_size, head);
561 array_add(&p->body, &p->body_size, sym_find(g, eof));
562 p->head->first_production = g->production_count;
563 array_add(&g->productions, &g->production_count, p);
565 Now we are ready to read in the grammar. We ignore comments
566 and strings so that the marks which introduce them can be
567 used as terminals in the grammar. We don't ignore numbers
568 even though we don't allow them as that causes the scanner
569 to produce errors that the parser is better positioned to handle.
572 static struct grammar *grammar_read(struct code_node *code)
574 struct token_config conf = {
577 .words_marks = known,
578 .known_count = sizeof(known)/sizeof(known[0]),
580 .ignored = (1 << TK_line_comment)
581 | (1 << TK_block_comment)
584 | (1 << TK_multi_string)
589 struct token_state *state = token_open(code, &conf);
591 struct symbol *head = NULL;
595 g = calloc(1, sizeof(*g));
598 for (tk = token_next(state); tk.num != TK_eof;
599 tk = token_next(state)) {
600 if (tk.num == TK_newline)
602 if (tk.num == TK_ident) {
604 head = sym_find(g, tk.txt);
605 if (head->type == Nonterminal)
606 err = "This non-terminal has already be used.";
607 else if (head->type == Virtual)
608 err = "Virtual symbol not permitted in head of production";
610 head->type = Nonterminal;
611 head->struct_name = g->current_type;
612 head->isref = g->type_isref;
613 if (g->production_count == 0) {
614 ## create production zero
616 head->first_production = g->production_count;
617 tk = token_next(state);
618 if (tk.num == TK_mark &&
619 text_is(tk.txt, "->"))
620 err = parse_production(g, head, state);
622 err = "'->' missing in production";
624 } else if (tk.num == TK_mark
625 && text_is(tk.txt, "|")) {
626 // another production for same non-term
628 err = parse_production(g, head, state);
630 err = "First production must have a head";
631 } else if (tk.num == TK_mark
632 && text_is(tk.txt, "$")) {
633 err = dollar_line(state, g, 0);
634 } else if (tk.num == TK_mark
635 && text_is(tk.txt, "$*")) {
636 err = dollar_line(state, g, 1);
638 err = "Unrecognised token at start of line.";
646 fprintf(stderr, "Error at line %d: %s\n",
653 ## Analysing the grammar
655 The central task in analysing the grammar is to determine a set of
656 states to drive the parsing process. This will require finding
657 various sets of symbols and of "items". Some of these sets will need
658 to attach information to each element in the set, so they are more
661 Each "item" may have a 'look-ahead' or `LA` set associated with
662 it. Many of these will be the same as each other. To avoid memory
663 wastage, and to simplify some comparisons of sets, these sets will be
664 stored in a list of unique sets, each assigned a number.
666 Once we have the data structures in hand to manage these sets and
667 lists, we can start setting the 'nullable' flag, build the 'FIRST'
668 sets, and then create the item sets which define the various states.
672 Though we don't only store symbols in these sets, they are the main
673 things we store, so they are called symbol sets or "symsets".
675 A symset has a size, an array of shorts, and an optional array of data
676 values, which are also shorts. If the array of data is not present,
677 we store an impossible pointer, as `NULL` is used to indicate that no
678 memory has been allocated yet;
683 unsigned short *syms, *data;
685 #define NO_DATA ((unsigned short *)1)
686 const struct symset INIT_SYMSET = { 0, NULL, NO_DATA };
687 const struct symset INIT_DATASET = { 0, NULL, NULL };
689 The arrays of shorts are allocated in blocks of 8 and are kept sorted
690 by using an insertion sort. We don't explicitly record the amount of
691 allocated space as it can be derived directly from the current `cnt` using
692 `((cnt - 1) | 7) + 1`.
695 static void symset_add(struct symset *s, unsigned short key, unsigned short val)
698 int current = ((s->cnt-1) | 7) + 1;
699 if (current == s->cnt) {
701 s->syms = realloc(s->syms, sizeof(*s->syms) * current);
702 if (s->data != NO_DATA)
703 s->data = realloc(s->data, sizeof(*s->data) * current);
706 while (i > 0 && s->syms[i-1] > key) {
707 s->syms[i] = s->syms[i-1];
708 if (s->data != NO_DATA)
709 s->data[i] = s->data[i-1];
713 if (s->data != NO_DATA)
718 Finding a symbol (or item) in a `symset` uses a simple binary search.
719 We return the index where the value was found (so data can be accessed),
720 or `-1` to indicate failure.
722 static int symset_find(struct symset *ss, unsigned short key)
729 while (lo + 1 < hi) {
730 int mid = (lo + hi) / 2;
731 if (ss->syms[mid] <= key)
736 if (ss->syms[lo] == key)
741 We will often want to form the union of two symsets. When we do, we
742 will often want to know if anything changed (as that might mean there
743 is more work to do). So `symset_union` reports whether anything was
744 added to the first set. We use a slow quadratic approach as these
745 sets don't really get very big. If profiles shows this to be a problem it
746 can be optimised later.
748 static int symset_union(struct symset *a, struct symset *b)
752 for (i = 0; i < b->cnt; i++)
753 if (symset_find(a, b->syms[i]) < 0) {
754 unsigned short data = 0;
755 if (b->data != NO_DATA)
757 symset_add(a, b->syms[i], data);
763 And of course we must be able to free a symset.
765 static void symset_free(struct symset ss)
768 if (ss.data != NO_DATA)
774 Some symsets are simply stored somewhere appropriate in the `grammar`
775 data structure, others needs a bit of indirection. This applies
776 particularly to "LA" sets. These will be paired with "items" in an
777 "itemset". As itemsets will be stored in a symset, the "LA" set needs to be
778 stored in the `data` field, so we need a mapping from a small (short)
779 number to an LA `symset`.
781 As mentioned earlier this involves creating a list of unique symsets.
783 For now, we just use a linear list sorted by insertion. A skiplist
784 would be more efficient and may be added later.
791 struct setlist *next;
794 ###### grammar fields
795 struct setlist *sets;
800 static int ss_cmp(struct symset a, struct symset b)
803 int diff = a.cnt - b.cnt;
806 for (i = 0; i < a.cnt; i++) {
807 diff = (int)a.syms[i] - (int)b.syms[i];
814 static int save_set(struct grammar *g, struct symset ss)
816 struct setlist **sl = &g->sets;
820 while (*sl && (cmp = ss_cmp((*sl)->ss, ss)) < 0)
827 s = malloc(sizeof(*s));
836 Finding a set by number is currently performed by a simple linear search.
837 If this turns out to hurt performance, we can store the sets in a dynamic
838 array like the productions.
840 static struct symset set_find(struct grammar *g, int num)
842 struct setlist *sl = g->sets;
843 while (sl && sl->num != num)
848 ### Setting `nullable`
850 We set `nullable` on the head symbol for any production for which all
851 the body symbols (if any) are nullable. As this is a recursive
852 definition, any change in the `nullable` setting means that we need to
853 re-evaluate where it needs to be set.
855 We simply loop around performing the same calculations until no more
862 static void set_nullable(struct grammar *g)
865 while (check_again) {
868 for (p = 0; p < g->production_count; p++) {
869 struct production *pr = g->productions[p];
872 if (pr->head->nullable)
874 for (s = 0; s < pr->body_size; s++)
875 if (! pr->body[s]->nullable)
877 if (s == pr->body_size) {
878 pr->head->nullable = 1;
885 ### Setting `line_like`
887 In order to be able to ignore newline tokens when not relevant, but
888 still include them in the parse when needed, we will need to know
889 which states can start a "line-like" section of code. We ignore
890 newlines when there is an indent since the most recent start of a
893 A "line_like" symbol is simply any symbol that can derive a NEWLINE.
894 If a symbol cannot derive a NEWLINE, then it is only part of a line -
895 so is word-like. If it can derive a NEWLINE, then we consider it to
898 Clearly the `TK_newline` token can derive a NEWLINE. Any symbol which
899 is the head of a production that contains a line_like symbol is also a
900 line-like symbol. We use a new field `line_like` to record this
901 attribute of symbols, and compute it in a repetitive manner similar to
908 static void set_line_like(struct grammar *g)
911 g->symtab[TK_newline]->line_like = 1;
912 while (check_again) {
915 for (p = 0; p < g->production_count; p++) {
916 struct production *pr = g->productions[p];
919 if (pr->head->line_like)
922 for (s = 0 ; s < pr->body_size; s++) {
923 if (pr->body[s]->line_like) {
924 pr->head->line_like = 1;
933 ### Building the `first` sets
935 When calculating what can follow a particular non-terminal, we will need to
936 know what the "first" terminal in any subsequent non-terminal might be. So
937 we calculate the `first` set for every non-terminal and store them in an
938 array. We don't bother recording the "first" set for terminals as they are
941 As the "first" for one symbol might depend on the "first" of another,
942 we repeat the calculations until no changes happen, just like with
943 `set_nullable`. This makes use of the fact that `symset_union`
944 reports if any change happens.
946 The core of this, which finds the "first" of part of a production body,
947 will be reused for computing the "follow" sets, so we split it out
948 into a separate function.
950 ###### grammar fields
951 struct symset *first;
955 static int add_first(struct production *pr, int start,
956 struct symset *target, struct grammar *g,
961 for (s = start; s < pr->body_size; s++) {
962 struct symbol *bs = pr->body[s];
963 if (bs->type == Terminal) {
964 if (symset_find(target, bs->num) < 0) {
965 symset_add(target, bs->num, 0);
969 } else if (symset_union(target, &g->first[bs->num]))
975 *to_end = (s == pr->body_size);
979 static void build_first(struct grammar *g)
983 g->first = calloc(g->num_syms, sizeof(g->first[0]));
984 for (s = 0; s < g->num_syms; s++)
985 g->first[s] = INIT_SYMSET;
987 while (check_again) {
990 for (p = 0; p < g->production_count; p++) {
991 struct production *pr = g->productions[p];
992 struct symset *head = &g->first[pr->head->num];
994 if (add_first(pr, 0, head, g, NULL))
1000 ### Building the `follow` sets.
1002 There are two different situations when we will want to generate "follow"
1003 sets. If we are doing an SLR analysis, we want to generate a single
1004 "follow" set for each non-terminal in the grammar. That is what is
1005 happening here. If we are doing an LALR or LR analysis we will want
1006 to generate a separate "LA" set for each item. We do that later
1007 in state generation.
1009 There are two parts to generating a "follow" set. Firstly we look at
1010 every place that any non-terminal appears in the body of any
1011 production, and we find the set of possible "first" symbols after
1012 there. This is done using `add_first` above and only needs to be done
1013 once as the "first" sets are now stable and will not change.
1017 for (p = 0; p < g->production_count; p++) {
1018 struct production *pr = g->productions[p];
1021 for (b = 0; b < pr->body_size - 1; b++) {
1022 struct symbol *bs = pr->body[b];
1023 if (bs->type == Terminal)
1025 add_first(pr, b+1, &g->follow[bs->num], g, NULL);
1029 The second part is to add the "follow" set of the head of a production
1030 to the "follow" sets of the final symbol in the production, and any
1031 other symbol which is followed only by `nullable` symbols. As this
1032 depends on "follow" itself we need to repeatedly perform the process
1033 until no further changes happen.
1037 for (again = 0, p = 0;
1038 p < g->production_count;
1039 p < g->production_count-1
1040 ? p++ : again ? (again = 0, p = 0)
1042 struct production *pr = g->productions[p];
1045 for (b = pr->body_size - 1; b >= 0; b--) {
1046 struct symbol *bs = pr->body[b];
1047 if (bs->type == Terminal)
1049 if (symset_union(&g->follow[bs->num],
1050 &g->follow[pr->head->num]))
1057 We now just need to create and initialise the `follow` list to get a
1060 ###### grammar fields
1061 struct symset *follow;
1064 static void build_follow(struct grammar *g)
1067 g->follow = calloc(g->num_syms, sizeof(g->follow[0]));
1068 for (s = 0; s < g->num_syms; s++)
1069 g->follow[s] = INIT_SYMSET;
1073 ### Building itemsets and states
1075 There are three different levels of detail that can be chosen for
1076 building the itemsets and states for the LR grammar. They are:
1078 1. LR(0) or SLR(1), where no look-ahead is considered.
1079 2. LALR(1) where we build look-ahead sets with each item and merge
1080 the LA sets when we find two paths to the same "kernel" set of items.
1081 3. LR(1) where different look-ahead for any item in the set means
1082 a different state must be created.
1084 ###### forward declarations
1085 enum grammar_type { LR0, LR05, SLR, LALR, LR1 };
1087 We need to be able to look through existing states to see if a newly
1088 generated state already exists. For now we use a simple sorted linked
1091 An item is a pair of numbers: the production number and the position of
1092 "DOT", which is an index into the body of the production.
1093 As the numbers are not enormous we can combine them into a single "short"
1094 and store them in a `symset` - 4 bits for "DOT" and 12 bits for the
1095 production number (so 4000 productions with maximum of 15 symbols in the
1098 Comparing the itemsets will be a little different to comparing symsets
1099 as we want to do the lookup after generating the "kernel" of an
1100 itemset, so we need to ignore the offset=zero items which are added during
1103 To facilitate this, we modify the "DOT" number so that "0" sorts to
1104 the end of the list in the symset, and then only compare items before
1108 static inline unsigned short item_num(int production, int index)
1110 return production | ((31-index) << 11);
1112 static inline int item_prod(unsigned short item)
1114 return item & 0x7ff;
1116 static inline int item_index(unsigned short item)
1118 return (31-(item >> 11)) & 0x1f;
1121 For LR(1) analysis we need to compare not just the itemset in a state
1122 but also the LA sets. As we assign each unique LA set a number, we
1123 can just compare the symset and the data values together.
1126 static int itemset_cmp(struct symset a, struct symset b,
1127 enum grammar_type type)
1133 i < a.cnt && i < b.cnt &&
1134 item_index(a.syms[i]) > 0 &&
1135 item_index(b.syms[i]) > 0;
1137 int diff = a.syms[i] - b.syms[i];
1141 diff = a.data[i] - b.data[i];
1146 if (i == a.cnt || item_index(a.syms[i]) == 0)
1150 if (i == b.cnt || item_index(b.syms[i]) == 0)
1156 if (type < LR1 || av == -1)
1159 a.data[i] - b.data[i];
1162 It will be helpful to know if an itemset has been "completed" or not,
1163 particularly for LALR where itemsets get merged, at which point they
1164 need to be consider for completion again. So a `completed` flag is needed.
1166 For correct handling of `TK_newline` when parsing, we will need to
1167 know which states (itemsets) can occur at the start of a line, so we
1168 will record a `starts_line` flag too whenever DOT is at the start of a
1171 Finally, for handling `TK_out` we need to know whether productions in the
1172 current state started *before* the most recent indent. A state
1173 doesn't usually keep details of individual productions, so we need to
1174 add one extra detail. `min_prefix` is the smallest non-zero number of
1175 symbols *before* DOT in any production in an itemset. This will allow
1176 us to determine if the the most recent indent is sufficiently recent
1177 to cancel it against a `TK_out`. If it was seen longer ago than the
1178 `min_prefix`, and if the current state cannot be reduced, then the
1179 indented section must have ended in the middle of a syntactic unit, so
1180 an error must be signaled.
1182 And now we can build the list of itemsets. The lookup routine returns
1183 both a success flag and a pointer to where in the list an insert
1184 should happen, so we don't need to search a second time.
1188 struct itemset *next;
1190 struct symset items;
1191 struct symset go_to;
1193 unsigned short precedence;
1199 ###### grammar fields
1200 struct itemset *items;
1204 static int itemset_find(struct grammar *g, struct itemset ***where,
1205 struct symset kernel, enum grammar_type type)
1207 struct itemset **ip;
1209 for (ip = &g->items; *ip ; ip = & (*ip)->next) {
1210 struct itemset *i = *ip;
1212 diff = itemset_cmp(i->items, kernel, type);
1225 Adding an itemset may require merging the LA sets if LALR analysis is
1226 happening. If any new LA set adds any symbols that weren't in the old LA set, we
1227 clear the `completed` flag so that the dependants of this itemset will be
1228 recalculated and their LA sets updated.
1230 `add_itemset` must consume the symsets it is passed, either by adding
1231 them to a data structure, of freeing them.
1233 static int add_itemset(struct grammar *g, struct symset ss,
1234 enum assoc assoc, unsigned short precedence,
1235 enum grammar_type type)
1237 struct itemset **where, *is;
1239 int found = itemset_find(g, &where, ss, type);
1241 is = calloc(1, sizeof(*is));
1242 is->state = g->states;
1246 is->precedence = precedence;
1248 is->go_to = INIT_DATASET;
1257 for (i = 0; i < ss.cnt; i++) {
1258 struct symset temp = INIT_SYMSET, s;
1259 if (ss.data[i] == is->items.data[i])
1261 s = set_find(g, is->items.data[i]);
1262 symset_union(&temp, &s);
1263 s = set_find(g, ss.data[i]);
1264 if (symset_union(&temp, &s)) {
1265 is->items.data[i] = save_set(g, temp);
1276 To build all the itemsets, we first insert the initial itemset made
1277 from production zero, complete each itemset, and then generate new
1278 itemsets from old until no new ones can be made.
1280 Completing an itemset means finding all the items where "DOT" is followed by
1281 a nonterminal and adding "DOT=0" items for every production from that
1282 non-terminal - providing each item hasn't already been added.
1284 If LA sets are needed, the LA set for each new item is found using
1285 `add_first` which was developed earlier for `FIRST` and `FOLLOW`. This may
1286 be supplemented by the LA set for the item which produce the new item.
1288 We also collect a set of all symbols which follow "DOT" (in `done`) as this
1289 is used in the next stage.
1290 If any of these symbols are flagged as `line_like`, then this
1291 state must be a `starts_line` state so now is a good time to record that.
1293 When itemsets are created we assign a precedence to the itemset from
1294 the complete item, if there is one. We ignore the possibility of
1295 there being two and don't (currently) handle precedence in such
1296 grammars. When completing a grammar we ignore any item where DOT is
1297 followed by a terminal with a precedence lower than that for the
1298 itemset. Unless the terminal has right associativity, we also ignore
1299 items where the terminal has the same precedence. The result is that
1300 unwanted items are still in the itemset, but the terminal doesn't get
1301 into the go to set, so the item is ineffective.
1303 ###### complete itemset
1304 for (i = 0; i < is->items.cnt; i++) {
1305 int p = item_prod(is->items.syms[i]);
1306 int bs = item_index(is->items.syms[i]);
1307 struct production *pr = g->productions[p];
1310 struct symset LA = INIT_SYMSET;
1311 unsigned short sn = 0;
1312 struct symset LAnl = INIT_SYMSET;
1313 unsigned short snnl = 0;
1315 if (is->min_prefix == 0 ||
1316 (bs > 0 && bs < is->min_prefix))
1317 is->min_prefix = bs;
1318 if (bs == pr->body_size)
1321 if (s->precedence && is->precedence &&
1322 is->precedence > s->precedence)
1323 /* This terminal has a low precedence and
1324 * shouldn't be shifted
1327 if (s->precedence && is->precedence &&
1328 is->precedence == s->precedence && s->assoc != Right)
1329 /* This terminal has a matching precedence and is
1330 * not Right-associative, so we mustn't shift it.
1333 if (symset_find(&done, s->num) < 0) {
1334 symset_add(&done, s->num, 0);
1336 is->starts_line = 1;
1338 if (s->type != Nonterminal)
1344 add_first(pr, bs+1, &LA, g, &to_end);
1346 struct symset ss = set_find(g, is->items.data[i]);
1347 symset_union(&LA, &ss);
1349 sn = save_set(g, LA);
1350 LA = set_find(g, sn);
1351 symset_add(&LAnl, TK_newline, 0);
1352 snnl = save_set(g, LAnl);
1353 LAnl = set_find(g, snnl);
1356 /* Add productions for this symbol */
1357 for (p2 = s->first_production;
1358 p2 < g->production_count &&
1359 g->productions[p2]->head == s;
1361 int itm = item_num(p2, 0);
1362 int pos = symset_find(&is->items, itm);
1364 if (g->productions[p2]->line_like)
1365 symset_add(&is->items, itm, snnl);
1367 symset_add(&is->items, itm, sn);
1368 /* Will have re-ordered, so start
1369 * from beginning again */
1371 } else if (type >= LALR) {
1372 struct symset ss = set_find(g, is->items.data[pos]);
1373 struct symset tmp = INIT_SYMSET;
1374 struct symset *la = &LA;
1376 if (g->productions[p2]->line_like)
1378 symset_union(&tmp, &ss);
1379 if (symset_union(&tmp, la)) {
1380 is->items.data[pos] = save_set(g, tmp);
1388 For each symbol we found (and placed in `done`) we collect all the items for
1389 which this symbol is next, and create a new itemset with "DOT" advanced over
1390 the symbol. This is then added to the collection of itemsets (or merged
1391 with a pre-existing itemset).
1393 ###### derive itemsets
1394 // Now we have a completed itemset, so we need to
1395 // compute all the 'next' itemsets and create them
1396 // if they don't exist.
1397 for (i = 0; i < done.cnt; i++) {
1399 unsigned short state;
1400 struct symbol *sym = g->symtab[done.syms[i]];
1401 enum assoc assoc = Non;
1402 unsigned short precedence = 0;
1403 struct symset newitemset = INIT_SYMSET;
1405 newitemset = INIT_DATASET;
1407 for (j = 0; j < is->items.cnt; j++) {
1408 int itm = is->items.syms[j];
1409 int p = item_prod(itm);
1410 int bp = item_index(itm);
1411 struct production *pr = g->productions[p];
1412 unsigned short la = 0;
1415 if (bp == pr->body_size)
1417 if (pr->body[bp] != sym)
1420 la = is->items.data[j];
1421 pos = symset_find(&newitemset, pr->head->num);
1422 if (bp + 1 == pr->body_size &&
1423 pr->precedence > 0 &&
1424 pr->precedence > precedence) {
1425 // new itemset is reducible and has a precedence.
1426 precedence = pr->precedence;
1430 symset_add(&newitemset, item_num(p, bp+1), la);
1431 else if (type >= LALR) {
1432 // Need to merge la set.
1433 int la2 = newitemset.data[pos];
1435 struct symset ss = set_find(g, la2);
1436 struct symset LA = INIT_SYMSET;
1437 symset_union(&LA, &ss);
1438 ss = set_find(g, la);
1439 if (symset_union(&LA, &ss))
1440 newitemset.data[pos] = save_set(g, LA);
1446 state = add_itemset(g, newitemset, assoc, precedence, type);
1447 if (symset_find(&is->go_to, done.syms[i]) < 0)
1448 symset_add(&is->go_to, done.syms[i], state);
1451 All that is left is to create the initial itemset from production zero, and
1452 with `TK_eof` as the LA set.
1455 static void build_itemsets(struct grammar *g, enum grammar_type type)
1457 struct symset first = INIT_SYMSET;
1460 unsigned short la = 0;
1462 // LA set just has eof
1463 struct symset eof = INIT_SYMSET;
1464 symset_add(&eof, TK_eof, 0);
1465 la = save_set(g, eof);
1466 first = INIT_DATASET;
1468 // production 0, offset 0 (with no data)
1469 symset_add(&first, item_num(0, 0), la);
1470 add_itemset(g, first, Non, 0, type);
1471 for (again = 0, is = g->items;
1473 is = is->next ?: again ? (again = 0, g->items) : NULL) {
1475 struct symset done = INIT_SYMSET;
1486 ### Completing the analysis.
1488 The exact process of analysis depends on which level was requested. For
1489 `LR0` and `LR05` we don't need first and follow sets at all. For `LALR` and
1490 `LR1` we need first, but not follow. For `SLR` we need both.
1492 We don't build the "action" tables that you might expect as the parser
1493 doesn't use them. They will be calculated to some extent if needed for
1496 Once we have built everything we allocate arrays for the two lists:
1497 symbols and itemsets. This allows more efficient access during reporting.
1498 The symbols are grouped as terminals and non-terminals and we record the
1499 changeover point in `first_nonterm`.
1501 ###### grammar fields
1502 struct symbol **symtab;
1503 struct itemset **statetab;
1506 ###### grammar_analyse
1508 static void grammar_analyse(struct grammar *g, enum grammar_type type)
1512 int snum = TK_reserved;
1513 for (s = g->syms; s; s = s->next)
1514 if (s->num < 0 && s->type == Terminal) {
1518 g->first_nonterm = snum;
1519 for (s = g->syms; s; s = s->next)
1525 g->symtab = calloc(g->num_syms, sizeof(g->symtab[0]));
1526 for (s = g->syms; s; s = s->next)
1527 g->symtab[s->num] = s;
1537 build_itemsets(g, type);
1539 g->statetab = calloc(g->states, sizeof(g->statetab[0]));
1540 for (is = g->items; is ; is = is->next)
1541 g->statetab[is->state] = is;
1544 ## Reporting on the Grammar
1546 The purpose of the report is to give the grammar developer insight into
1547 how the grammar parser will work. It is basically a structured dump of
1548 all the tables that have been generated, plus a description of any conflicts.
1550 ###### grammar_report
1551 static int grammar_report(struct grammar *g, enum grammar_type type)
1557 return report_conflicts(g, type);
1560 Firstly we have the complete list of symbols, together with the
1561 "FIRST" set if that was generated. We add a mark to each symbol to
1562 show if it can end in a newline (`>`), if it is considered to be
1563 "line-like" (`<`), or if it is nullable (`.`).
1567 static void report_symbols(struct grammar *g)
1571 printf("SYMBOLS + FIRST:\n");
1573 printf("SYMBOLS:\n");
1575 for (n = 0; n < g->num_syms; n++) {
1576 struct symbol *s = g->symtab[n];
1580 printf(" %c%c%3d%c: ",
1581 s->nullable ? '.':' ',
1582 s->line_like ? '<':' ',
1583 s->num, symtypes[s->type]);
1586 printf(" (%d%s)", s->precedence,
1587 assoc_names[s->assoc]);
1589 if (g->first && s->type == Nonterminal) {
1592 for (j = 0; j < g->first[n].cnt; j++) {
1595 prtxt(g->symtab[g->first[n].syms[j]]->name);
1602 Then we have the follow sets if they were computed.
1604 static void report_follow(struct grammar *g)
1607 printf("FOLLOW:\n");
1608 for (n = 0; n < g->num_syms; n++)
1609 if (g->follow[n].cnt) {
1613 prtxt(g->symtab[n]->name);
1614 for (j = 0; j < g->follow[n].cnt; j++) {
1617 prtxt(g->symtab[g->follow[n].syms[j]]->name);
1623 And finally the item sets. These include the GO TO tables and, for
1624 LALR and LR1, the LA set for each item. Lots of stuff, so we break
1625 it up a bit. First the items, with production number and associativity.
1627 static void report_item(struct grammar *g, int itm)
1629 int p = item_prod(itm);
1630 int dot = item_index(itm);
1631 struct production *pr = g->productions[p];
1635 prtxt(pr->head->name);
1637 for (i = 0; i < pr->body_size; i++) {
1638 printf(" %s", (dot == i ? ". ": ""));
1639 prtxt(pr->body[i]->name);
1641 if (dot == pr->body_size)
1644 if (pr->precedence && dot == pr->body_size)
1645 printf(" (%d%s)", pr->precedence,
1646 assoc_names[pr->assoc]);
1647 if (dot < pr->body_size &&
1648 pr->body[dot]->precedence) {
1649 struct symbol *s = pr->body[dot];
1650 printf(" [%d%s]", s->precedence,
1651 assoc_names[s->assoc]);
1654 printf(" $$NEWLINE");
1658 The LA sets which are (possibly) reported with each item:
1660 static void report_la(struct grammar *g, int lanum)
1662 struct symset la = set_find(g, lanum);
1666 printf(" LOOK AHEAD(%d)", lanum);
1667 for (i = 0; i < la.cnt; i++) {
1670 prtxt(g->symtab[la.syms[i]]->name);
1675 Then the go to sets:
1677 static void report_goto(struct grammar *g, struct symset gt)
1682 for (i = 0; i < gt.cnt; i++) {
1684 prtxt(g->symtab[gt.syms[i]]->name);
1685 printf(" -> %d\n", gt.data[i]);
1689 Now we can report all the item sets complete with items, LA sets, and GO TO.
1691 static void report_itemsets(struct grammar *g)
1694 printf("ITEM SETS(%d)\n", g->states);
1695 for (s = 0; s < g->states; s++) {
1697 struct itemset *is = g->statetab[s];
1698 printf(" Itemset %d:%s min prefix=%d",
1699 s, is->starts_line?" (startsline)":"", is->min_prefix);
1701 printf(" %d%s", is->precedence, assoc_names[is->assoc]);
1703 for (j = 0; j < is->items.cnt; j++) {
1704 report_item(g, is->items.syms[j]);
1705 if (is->items.data != NO_DATA)
1706 report_la(g, is->items.data[j]);
1708 report_goto(g, is->go_to);
1712 ### Reporting conflicts
1714 Conflict detection varies a lot among different analysis levels. However
1715 LR0 and LR0.5 are quite similar - having no follow sets, and SLR, LALR and
1716 LR1 are also similar as they have FOLLOW or LA sets.
1720 ## conflict functions
1722 static int report_conflicts(struct grammar *g, enum grammar_type type)
1725 printf("Conflicts:\n");
1727 cnt = conflicts_lr0(g, type);
1729 cnt = conflicts_slr(g, type);
1731 printf(" - no conflicts\n");
1735 LR0 conflicts are any state which have both a reducible item and
1736 a shiftable item, or two reducible items.
1738 LR05 conflicts only occur if two possible reductions exist,
1739 as shifts always over-ride reductions.
1741 ###### conflict functions
1742 static int conflicts_lr0(struct grammar *g, enum grammar_type type)
1746 for (i = 0; i < g->states; i++) {
1747 struct itemset *is = g->statetab[i];
1748 int last_reduce = -1;
1749 int prev_reduce = -1;
1750 int last_shift = -1;
1754 for (j = 0; j < is->items.cnt; j++) {
1755 int itm = is->items.syms[j];
1756 int p = item_prod(itm);
1757 int bp = item_index(itm);
1758 struct production *pr = g->productions[p];
1760 if (bp == pr->body_size) {
1761 prev_reduce = last_reduce;
1765 if (pr->body[bp]->type == Terminal)
1768 if (type == LR0 && last_reduce >= 0 && last_shift >= 0) {
1769 printf(" State %d has both SHIFT and REDUCE:\n", i);
1770 report_item(g, is->items.syms[last_shift]);
1771 report_item(g, is->items.syms[last_reduce]);
1774 if (prev_reduce >= 0) {
1775 printf(" State %d has 2 (or more) reducible items\n", i);
1776 report_item(g, is->items.syms[prev_reduce]);
1777 report_item(g, is->items.syms[last_reduce]);
1784 SLR, LALR, and LR1 conflicts happen if two reducible items have over-lapping
1785 look ahead, or if a symbol in a look-ahead can be shifted. They differ only
1786 in the source of the look ahead set.
1788 We build two datasets to reflect the "action" table: one which maps
1789 terminals to items where that terminal could be shifted and another
1790 which maps terminals to items that could be reduced when the terminal
1791 is in look-ahead. We report when we get conflicts between the two.
1793 As a special case, if we find a SHIFT/REDUCE conflict, where a
1794 terminal that could be shifted is in the lookahead set of some
1795 reducable item, then set check if the reducable item also have
1796 `TK_newline` in its lookahead set. If it does, then a newline will
1797 force the reduction, but anything else can reasonably be shifted, so
1798 that isn't really a conflict. Such apparent conflicts do not get
1799 counted, and are reported as non-critical. This will not affect a
1800 "traditional" grammar that does not include newlines as token.
1802 static int conflicts_slr(struct grammar *g, enum grammar_type type)
1807 for (i = 0; i < g->states; i++) {
1808 struct itemset *is = g->statetab[i];
1809 struct symset shifts = INIT_DATASET;
1810 struct symset reduce = INIT_DATASET;
1814 /* First collect the shifts */
1815 for (j = 0; j < is->items.cnt; j++) {
1816 unsigned short itm = is->items.syms[j];
1817 int p = item_prod(itm);
1818 int bp = item_index(itm);
1819 struct production *pr = g->productions[p];
1822 if (bp >= pr->body_size ||
1823 pr->body[bp]->type != Terminal)
1828 if (s->precedence && is->precedence)
1829 /* Precedence resolves this, so no conflict */
1832 if (symset_find(&shifts, s->num) < 0)
1833 symset_add(&shifts, s->num, itm);
1835 /* Now look for reductions and conflicts */
1836 for (j = 0; j < is->items.cnt; j++) {
1837 unsigned short itm = is->items.syms[j];
1838 int p = item_prod(itm);
1839 int bp = item_index(itm);
1840 struct production *pr = g->productions[p];
1842 if (bp < pr->body_size)
1847 la = g->follow[pr->head->num];
1849 la = set_find(g, is->items.data[j]);
1851 for (k = 0; k < la.cnt; k++) {
1852 int pos = symset_find(&shifts, la.syms[k]);
1853 if (pos >= 0 && la.syms[k] != TK_newline) {
1854 if (symset_find(&la, TK_newline) < 0) {
1855 printf(" State %d has SHIFT/REDUCE conflict on ", i);
1858 printf(" State %d has non-critical SHIFT/REDUCE conflict on ", i);
1859 prtxt(g->symtab[la.syms[k]]->name);
1861 report_item(g, shifts.data[pos]);
1862 report_item(g, itm);
1864 pos = symset_find(&reduce, la.syms[k]);
1866 symset_add(&reduce, la.syms[k], itm);
1869 printf(" State %d has REDUCE/REDUCE conflict on ", i);
1870 prtxt(g->symtab[la.syms[k]]->name);
1872 report_item(g, itm);
1873 report_item(g, reduce.data[pos]);
1877 symset_free(shifts);
1878 symset_free(reduce);
1883 ## Generating the parser
1885 The exported part of the parser is the `parse_XX` function, where the name
1886 `XX` is based on the name of the parser files.
1888 This takes a `code_node`, a partially initialized `token_config`, and an
1889 optional `FILE` to send tracing to. The `token_config` gets the list of
1890 known words added and then is used with the `code_node` to initialize the
1893 `parse_XX` then calls the library function `parser_run` to actually complete
1894 the parse. This needs the `states` table and function to call the various
1895 pieces of code provided in the grammar file, so they are generated first.
1897 ###### parser_generate
1899 static void gen_parser(FILE *f, struct grammar *g, char *file, char *name,
1900 struct code_node *pre_reduce)
1906 gen_reduce(f, g, file, pre_reduce);
1909 fprintf(f, "#line 0 \"gen_parser\"\n");
1910 fprintf(f, "void *parse_%s(struct code_node *code, struct token_config *config, FILE *trace)\n",
1913 fprintf(f, "\tstruct token_state *tokens;\n");
1914 fprintf(f, "\tconfig->words_marks = known;\n");
1915 fprintf(f, "\tconfig->known_count = sizeof(known)/sizeof(known[0]);\n");
1916 fprintf(f, "\tconfig->ignored |= (1 << TK_line_comment) | (1 << TK_block_comment);\n");
1917 fprintf(f, "\ttokens = token_open(code, config);\n");
1918 fprintf(f, "\tvoid *rv = parser_run(tokens, states, do_reduce, do_free, trace, non_term, config);\n");
1919 fprintf(f, "\ttoken_close(tokens);\n");
1920 fprintf(f, "\treturn rv;\n");
1921 fprintf(f, "}\n\n");
1924 ### Known words table
1926 The known words table is simply an array of terminal symbols.
1927 The table of nonterminals used for tracing is a similar array. We
1928 include virtual symbols in the table of non_terminals to keep the
1933 static void gen_known(FILE *f, struct grammar *g)
1936 fprintf(f, "#line 0 \"gen_known\"\n");
1937 fprintf(f, "static const char *known[] = {\n");
1938 for (i = TK_reserved;
1939 i < g->num_syms && g->symtab[i]->type == Terminal;
1941 fprintf(f, "\t\"%.*s\",\n", g->symtab[i]->name.len,
1942 g->symtab[i]->name.txt);
1943 fprintf(f, "};\n\n");
1946 static void gen_non_term(FILE *f, struct grammar *g)
1949 fprintf(f, "#line 0 \"gen_non_term\"\n");
1950 fprintf(f, "static const char *non_term[] = {\n");
1951 for (i = TK_reserved;
1954 if (g->symtab[i]->type != Terminal)
1955 fprintf(f, "\t\"%.*s\",\n", g->symtab[i]->name.len,
1956 g->symtab[i]->name.txt);
1957 fprintf(f, "};\n\n");
1960 ### States and the goto tables.
1962 For each state we record the goto table, the reducible production if
1963 there is one, or a symbol to shift for error recovery.
1964 Some of the details of the reducible production are stored in the
1965 `do_reduce` function to come later. Here we store the production number,
1966 the body size (useful for stack management) and the resulting symbol (useful
1967 for knowing how to free data later).
1969 The go to table is stored in a simple array of `sym` and corresponding
1972 ###### exported types
1980 const struct lookup * go_to;
1991 static void gen_goto(FILE *f, struct grammar *g)
1994 fprintf(f, "#line 0 \"gen_goto\"\n");
1995 for (i = 0; i < g->states; i++) {
1997 fprintf(f, "static const struct lookup goto_%d[] = {\n",
1999 struct symset gt = g->statetab[i]->go_to;
2000 for (j = 0; j < gt.cnt; j++)
2001 fprintf(f, "\t{ %d, %d },\n",
2002 gt.syms[j], gt.data[j]);
2009 static void gen_states(FILE *f, struct grammar *g)
2012 fprintf(f, "#line 0 \"gen_states\"\n");
2013 fprintf(f, "static const struct state states[] = {\n");
2014 for (i = 0; i < g->states; i++) {
2015 struct itemset *is = g->statetab[i];
2016 int j, prod = -1, prod_len;
2018 for (j = 0; j < is->items.cnt; j++) {
2019 int itm = is->items.syms[j];
2020 int p = item_prod(itm);
2021 int bp = item_index(itm);
2022 struct production *pr = g->productions[p];
2024 if (bp < pr->body_size)
2026 /* This is what we reduce */
2027 if (prod < 0 || prod_len < pr->body_size) {
2029 prod_len = pr->body_size;
2034 fprintf(f, "\t[%d] = { %d, goto_%d, %d, %d, %d, %d, %d, %d },\n",
2035 i, is->go_to.cnt, i, prod,
2036 g->productions[prod]->body_size,
2037 g->productions[prod]->head->num,
2039 g->productions[prod]->line_like,
2042 fprintf(f, "\t[%d] = { %d, goto_%d, -1, -1, -1, %d, 0, %d },\n",
2043 i, is->go_to.cnt, i,
2044 is->starts_line, is->min_prefix);
2046 fprintf(f, "};\n\n");
2049 ### The `do_reduce` function and the code
2051 When the parser engine decides to reduce a production, it calls `do_reduce`.
2052 This has two functions.
2054 Firstly, if a non-NULL `trace` file is passed, it prints out details of the
2055 production being reduced. Secondly it runs the code that was included with
2056 the production if any.
2058 This code needs to be able to store data somewhere. Rather than requiring
2059 `do_reduce` to `malloc` that "somewhere", we pass in a large buffer and have
2060 `do_reduce` return the size to be saved.
2062 In order for the code to access "global" context, we pass in the
2063 "config" pointer that was passed to parser function. If the `struct
2064 token_config` is embedded in some larger structure, the reducing code
2065 can access the larger structure using pointer manipulation.
2067 The code fragment requires translation when written out. Any `$N` needs to
2068 be converted to a reference either to that buffer (if `$0`) or to the
2069 structure returned by a previous reduction. These pointers need to be cast
2070 to the appropriate type for each access. All this is handled in
2073 `gen_code` also allows symbol references to contain a '`<`' as in '`$<2`'.
2074 This applied only to symbols with references (or pointers), not those with structures.
2075 The `<` implies that the reference it being moved out, so the object will not be
2076 automatically freed. This is equivalent to assigning `NULL` to the pointer.
2080 static void gen_code(struct production *p, FILE *f, struct grammar *g)
2083 char *used = calloc(1, p->body_size);
2086 fprintf(f, "\t\t\t");
2087 for (c = p->code.txt; c < p->code.txt + p->code.len; c++) {
2101 if (*c < '0' || *c > '9') {
2108 while (c[1] >= '0' && c[1] <= '9') {
2110 n = n * 10 + *c - '0';
2113 fprintf(f, "(*(struct %.*s*%s)ret)",
2114 p->head->struct_name.len,
2115 p->head->struct_name.txt,
2116 p->head->isref ? "*":"");
2117 else if (n > p->body_size)
2118 fprintf(f, "$%d", n);
2119 else if (p->body[n-1]->type == Terminal)
2120 fprintf(f, "(*(struct token *)body[%d])",
2122 else if (p->body[n-1]->struct_name.txt == NULL)
2123 fprintf(f, "$%d", n);
2125 fprintf(f, "(*(struct %.*s*%s)body[%d])",
2126 p->body[n-1]->struct_name.len,
2127 p->body[n-1]->struct_name.txt,
2128 p->body[n-1]->isref ? "*":"", n-1);
2133 for (i = 0; i < p->body_size; i++) {
2134 if (p->body[i]->struct_name.txt &&
2136 // assume this has been copied out
2137 if (p->body[i]->isref)
2138 fprintf(f, "\t\t*(void**)body[%d] = NULL;\n", i);
2140 fprintf(f, "\t\tmemset(body[%d], 0, sizeof(struct %.*s));\n", i, p->body[i]->struct_name.len, p->body[i]->struct_name.txt);
2148 static void gen_reduce(FILE *f, struct grammar *g, char *file,
2149 struct code_node *code)
2152 fprintf(f, "#line 1 \"gen_reduce\"\n");
2153 fprintf(f, "static int do_reduce(int prod, void **body, struct token_config *config, void *ret)\n");
2155 fprintf(f, "\tint ret_size = 0;\n");
2157 code_node_print(f, code, file);
2159 fprintf(f, "#line 4 \"gen_reduce\"\n");
2160 fprintf(f, "\tswitch(prod) {\n");
2161 for (i = 0; i < g->production_count; i++) {
2162 struct production *p = g->productions[i];
2163 fprintf(f, "\tcase %d:\n", i);
2166 fprintf(f, "#line %d \"%s\"\n", p->code_line, file);
2170 if (p->head->struct_name.txt)
2171 fprintf(f, "\t\tret_size = sizeof(struct %.*s%s);\n",
2172 p->head->struct_name.len,
2173 p->head->struct_name.txt,
2174 p->head->isref ? "*":"");
2176 fprintf(f, "\t\tbreak;\n");
2178 fprintf(f, "\t}\n\treturn ret_size;\n}\n\n");
2183 As each non-terminal can potentially cause a different type of data
2184 structure to be allocated and filled in, we need to be able to free it when
2187 It is particularly important to have fine control over freeing during error
2188 recovery where individual stack frames might need to be freed.
2190 For this, the grammar author is required to defined a `free_XX` function for
2191 each structure that is used by a non-terminal. `do_free` will call whichever
2192 is appropriate given a symbol number, and will call `free` (as is
2193 appropriate for tokens) on any terminal symbol.
2197 static void gen_free(FILE *f, struct grammar *g)
2201 fprintf(f, "#line 0 \"gen_free\"\n");
2202 fprintf(f, "static void do_free(short sym, void *asn)\n");
2204 fprintf(f, "\tif (!asn) return;\n");
2205 fprintf(f, "\tif (sym < %d) {\n", g->first_nonterm);
2206 fprintf(f, "\t\tfree(asn);\n\t\treturn;\n\t}\n");
2207 fprintf(f, "\tswitch(sym) {\n");
2209 for (i = 0; i < g->num_syms; i++) {
2210 struct symbol *s = g->symtab[i];
2212 s->type != Nonterminal ||
2213 s->struct_name.txt == NULL)
2216 fprintf(f, "\tcase %d:\n", s->num);
2218 fprintf(f, "\t\tfree_%.*s(*(void**)asn);\n",
2220 s->struct_name.txt);
2221 fprintf(f, "\t\tfree(asn);\n");
2223 fprintf(f, "\t\tfree_%.*s(asn);\n",
2225 s->struct_name.txt);
2226 fprintf(f, "\t\tbreak;\n");
2228 fprintf(f, "\t}\n}\n\n");
2231 ## The main routine.
2233 There are three key parts to the "main" function of parsergen: processing
2234 the arguments, loading the grammar file, and dealing with the grammar.
2236 ### Argument processing.
2238 Command line options allow the selection of analysis mode, name of output
2239 file, and whether or not a report should be generated. By default we create
2240 a report only if no code output was requested.
2242 The `parse_XX` function name uses the basename of the output file which
2243 should not have a suffix (`.c`). `.c` is added to the given name for the
2244 code, and `.h` is added for the header (if header text is specifed in the
2251 static const struct option long_options[] = {
2252 { "LR0", 0, NULL, '0' },
2253 { "LR05", 0, NULL, '5' },
2254 { "SLR", 0, NULL, 'S' },
2255 { "LALR", 0, NULL, 'L' },
2256 { "LR1", 0, NULL, '1' },
2257 { "tag", 1, NULL, 't' },
2258 { "report", 0, NULL, 'R' },
2259 { "output", 1, NULL, 'o' },
2260 { NULL, 0, NULL, 0 }
2262 const char *options = "05SL1t:Ro:";
2264 ###### process arguments
2266 char *outfile = NULL;
2271 enum grammar_type type = LR05;
2272 while ((opt = getopt_long(argc, argv, options,
2273 long_options, NULL)) != -1) {
2288 outfile = optarg; break;
2290 tag = optarg; break;
2292 fprintf(stderr, "Usage: parsergen ...\n");
2297 infile = argv[optind++];
2299 fprintf(stderr, "No input file given\n");
2302 if (outfile && report == 1)
2305 if (name && strchr(name, '/'))
2306 name = strrchr(name, '/')+1;
2308 if (optind < argc) {
2309 fprintf(stderr, "Excess command line arguments\n");
2313 ### Loading the grammar file
2315 To be able to run `mdcode` and `scanner` on the grammar we need to memory
2318 Once we have extracted the code (with `mdcode`) we expect to find three
2319 sections: header, code, and grammar. Anything else that is not
2320 excluded by the `--tag` option is an error.
2322 "header" and "code" are optional, though it is hard to build a working
2323 parser with neither. "grammar" must be provided.
2327 #include <sys/mman.h>
2332 static void pr_err(char *msg)
2335 fprintf(stderr, "%s\n", msg);
2339 struct section *table;
2343 fd = open(infile, O_RDONLY);
2345 fprintf(stderr, "parsergen: cannot open %s: %s\n",
2346 infile, strerror(errno));
2349 len = lseek(fd, 0, 2);
2350 file = mmap(NULL, len, PROT_READ, MAP_SHARED, fd, 0);
2351 table = code_extract(file, file+len, pr_err);
2353 struct code_node *hdr = NULL;
2354 struct code_node *code = NULL;
2355 struct code_node *gram = NULL;
2356 struct code_node *pre_reduce = NULL;
2357 for (s = table; s; s = s->next) {
2358 struct text sec = s->section;
2359 if (tag && !strip_tag(&sec, tag))
2361 if (text_is(sec, "header"))
2363 else if (text_is(sec, "code"))
2365 else if (text_is(sec, "grammar"))
2367 else if (text_is(sec, "reduce"))
2368 pre_reduce = s->code;
2370 fprintf(stderr, "Unknown content section: %.*s\n",
2371 s->section.len, s->section.txt);
2376 ### Processing the input
2378 As we need to append an extention to a filename and then open it for
2379 writing, and we need to do this twice, it helps to have a separate function.
2383 static FILE *open_ext(char *base, char *ext)
2385 char *fn = malloc(strlen(base) + strlen(ext) + 1);
2387 strcat(strcpy(fn, base), ext);
2393 If we can read the grammar, then we analyse and optionally report on it. If
2394 the report finds conflicts we will exit with an error status.
2396 ###### process input
2397 struct grammar *g = NULL;
2399 fprintf(stderr, "No grammar section provided\n");
2402 g = grammar_read(gram);
2404 fprintf(stderr, "Failure to parse grammar\n");
2409 grammar_analyse(g, type);
2411 if (grammar_report(g, type))
2415 If a "headers" section is defined, we write it out and include a declaration
2416 for the `parse_XX` function so it can be used from separate code.
2418 if (rv == 0 && hdr && outfile) {
2419 FILE *f = open_ext(outfile, ".h");
2421 code_node_print(f, hdr, infile);
2422 fprintf(f, "void *parse_%s(struct code_node *code, struct token_config *config, FILE *trace);\n",
2426 fprintf(stderr, "Cannot create %s.h\n",
2432 And if all goes well and an output file was provided, we create the `.c`
2433 file with the code section (if any) and the parser tables and function.
2435 if (rv == 0 && outfile) {
2436 FILE *f = open_ext(outfile, ".c");
2439 code_node_print(f, code, infile);
2440 gen_parser(f, g, infile, name, pre_reduce);
2443 fprintf(stderr, "Cannot create %s.c\n",
2449 And that about wraps it up. We need to set the locale so that UTF-8 is
2450 recognised properly, and link with `libicuuc` as `libmdcode` requires that.
2452 ###### File: parsergen.mk
2453 parsergen : parsergen.o libscanner.o libmdcode.o
2454 $(CC) $(CFLAGS) -o parsergen parsergen.o libscanner.o libmdcode.o -licuuc
2461 int main(int argc, char *argv[])
2466 setlocale(LC_ALL,"");
2468 ## process arguments
2475 ## The SHIFT/REDUCE parser
2477 Having analysed the grammar and generated all the tables, we only need the
2478 shift/reduce engine to bring it all together.
2480 ### Goto table lookup
2482 The parser generator has nicely provided us with goto tables sorted by
2483 symbol number. We need a binary search function to find a symbol in the
2486 ###### parser functions
2488 static int search(const struct state *l, int sym)
2491 int hi = l->go_to_cnt;
2495 while (lo + 1 < hi) {
2496 int mid = (lo + hi) / 2;
2497 if (l->go_to[mid].sym <= sym)
2502 if (l->go_to[lo].sym == sym)
2503 return l->go_to[lo].state;
2508 ### The state stack.
2510 The core data structure for the parser is the stack. This tracks all the
2511 symbols that have been recognised or partially recognised.
2513 The stack usually won't grow very large - maybe a few tens of entries. So
2514 we dynamically resize and array as required but never bother to shrink it
2517 We keep the stack as two separate allocations. One, `asn_stack` stores the
2518 "abstract syntax nodes" which are created by each reduction. When we call
2519 `do_reduce` we need to pass an array of the `asn`s of the body of the
2520 production, and by keeping a separate `asn` stack, we can just pass a
2521 pointer into this stack.
2523 The other allocation stores all other stack fields of which there are six.
2524 The `state` is the most important one and guides the parsing process. The
2525 `sym` is nearly unnecessary. However when we want to free entries from the
2526 `asn_stack`, it helps to know what type they are so we can call the right
2527 freeing function. The symbol leads us to the right free function through
2530 The `indents` count tracks the line indents with-in the symbol or
2531 immediately follow it. These are used to allow indent information to
2532 guide parsing and error recovery.
2534 `since_newline` tracks how many stack frames since the last
2535 start-of-line (whether indented or not). So if `since_newline` is
2536 zero, then this symbol is at the start of a line. Similarly
2537 `since_indent` counts the number of states since an indent, it is zero
2538 precisely when `indents` is not zero.
2540 `newline_permitted` keeps track of whether newlines should be ignored
2543 The stack is most properly seen as alternating states and symbols -
2544 states, like the 'DOT' in items, are between symbols. Each frame in
2545 our stack holds a state and the symbol that was before it. The
2546 bottom of stack holds the start state but no symbol, as nothing came
2547 before the beginning.
2549 ###### parser functions
2554 short newline_permitted;
2558 short since_newline;
2568 Two operations are needed on the stack - shift (which is like push) and pop.
2570 Shift applies not only to terminals but also to non-terminals. When
2571 we reduce a production we will pop off entries corresponding to the
2572 body symbols, then push on an item for the head of the production.
2573 This last is exactly the same process as shifting in a terminal so we
2574 use the same function for both. In both cases we provide the symbol,
2575 the number of indents the symbol contains (which will be zero for a
2576 terminal symbol) and a flag indicating the the symbol was at (or was
2577 reduced from a symbol which was at) the start of a line. The state is
2578 deduced from the current top-of-stack state and the new symbol.
2580 To simplify other code we arrange for `shift` to fail if there is no `goto`
2581 state for the symbol. This is useful in basic parsing due to our design
2582 that we shift when we can, and reduce when we cannot. So the `shift`
2583 function reports if it could.
2585 `shift` is also used to push state zero onto the stack, so if the
2586 stack is empty, it always chooses zero as the next state.
2588 So `shift` finds the next state. If that succeeds it extends the
2589 allocations if needed and pushes all the information onto the stacks.
2591 Newlines are permitted after a `starts_line` state until an internal
2592 indent. If the new frame has neither a `starts_line` state nor an
2593 indent, newlines are permitted if the previous stack frame permitted
2596 ###### parser functions
2598 static int shift(struct parser *p,
2599 short sym, short indents, short start_of_line,
2601 const struct state states[])
2603 // Push an entry onto the stack
2604 struct frame next = {0};
2605 int newstate = p->tos
2606 ? search(&states[p->stack[p->tos-1].state],
2611 if (p->tos >= p->stack_size) {
2612 p->stack_size += 10;
2613 p->stack = realloc(p->stack, p->stack_size
2614 * sizeof(p->stack[0]));
2615 p->asn_stack = realloc(p->asn_stack, p->stack_size
2616 * sizeof(p->asn_stack[0]));
2619 next.indents = indents;
2620 next.state = newstate;
2621 if (states[newstate].starts_line)
2622 next.newline_permitted = 1;
2624 next.newline_permitted = 0;
2626 next.newline_permitted =
2627 p->stack[p->tos-1].newline_permitted;
2629 next.newline_permitted = 0;
2631 if (!start_of_line) {
2633 next.since_newline = p->stack[p->tos-1].since_newline + 1;
2635 next.since_newline = 1;
2638 next.since_indent = 0;
2640 next.since_indent = p->stack[p->tos-1].since_indent + 1;
2642 next.since_indent = 1;
2644 p->stack[p->tos] = next;
2645 p->asn_stack[p->tos] = asn;
2650 `pop` primarily moves the top of stack (`tos`) back down the required
2651 amount and frees any `asn` entries that need to be freed. It also
2652 collects a summary of the indents and line starts in the symbols that
2653 are being removed. It is called _after_ we reduce a production, just
2654 before we `shift` the nonterminal in.
2656 ###### parser functions
2658 static int pop(struct parser *p, int num,
2659 short *start_of_line,
2660 void(*do_free)(short sym, void *asn))
2667 for (i = 0; i < num; i++) {
2668 sol |= !p->stack[p->tos+i].since_newline;
2669 indents += p->stack[p->tos+i].indents;
2670 do_free(p->stack[p->tos+i].sym,
2671 p->asn_stack[p->tos+i]);
2674 *start_of_line = sol;
2678 ### Memory allocation
2680 The `scanner` returns tokens in a local variable - we want them in allocated
2681 memory so they can live in the `asn_stack`. Similarly the `asn` produced by
2682 a reduce is in a large buffer. Both of these require some allocation and
2683 copying, hence `memdup` and `tokcopy`.
2685 ###### parser includes
2688 ###### parser functions
2690 void *memdup(void *m, int len)
2696 memcpy(ret, m, len);
2700 static struct token *tok_copy(struct token tk)
2702 struct token *new = malloc(sizeof(*new));
2707 ### The heart of the parser.
2709 Now we have the parser. If we can shift we do, though newlines and
2710 reducing indenting may block that. If not and we can reduce we do
2711 that. If the production we reduced was production zero, then we have
2712 accepted the input and can finish.
2714 We return whatever `asn` was returned by reducing production zero.
2716 If we can neither shift nor reduce we have an error to handle. We pop
2717 single entries off the stack until we can shift the `TK_error` symbol, then
2718 drop input tokens until we find one we can shift into the new error state.
2720 When we find `TK_in` and `TK_out` tokens which report indents we need
2721 to handle them directly as the grammar cannot express what we want to
2724 `TK_in` tokens are easy: we simply update indent count in the top stack frame to
2725 record how many indents there are following the previous token.
2727 `TK_out` tokens must be canceled against an indent count
2728 within the stack. If we can reduce some symbols that are all since
2729 the most recent indent, then we do that first. If the minimum prefix
2730 of the current state then extends back before the most recent indent,
2731 that indent can be cancelled. If the minimum prefix is shorter then
2732 the indent had ended prematurely and we must start error handling, which
2733 is still a work-in-progress.
2735 `TK_newline` tokens are ignored unless the top stack frame records
2736 that they are permitted. In that case they will not be considered for
2737 shifting if it is possible to reduce some symbols that are all since
2738 the most recent start of line. This is how a newline forcibly
2739 terminates any line-like structure - we try to reduce down to at most
2740 one symbol for each line where newlines are allowed.
2741 A consequence of this is that a rule like
2743 ###### Example: newlines - broken
2747 IfStatement -> Newlines if ....
2749 cannot work, as the NEWLINE will never be shifted as the empty string
2750 will be reduced first. Optional sets of newlines need to be include
2751 in the thing that preceed:
2753 ###### Example: newlines - works
2757 IfStatement -> If ....
2759 Here the NEWLINE will be shifted because nothing can be reduced until
2762 When, during error handling, we discard token read in, we want to keep
2763 discarding until we see one that is recognised. If we had a full set
2764 of LR(1) grammar states, this will mean looking in the look-ahead set,
2765 but we don't keep a full look-ahead set. We only record the subset
2766 that leads to SHIFT. We can, however, deduce the look-ahead set but
2767 looking at the SHIFT subsets for all states that we can get to by
2768 reducing zero or more times. So we need a little function which
2769 checks if a given token is in any of these look-ahead sets.
2771 ###### parser includes
2776 static int in_lookahead(struct token *tk, const struct state *states, int state)
2778 while (state >= 0) {
2779 if (search(&states[state], tk->num) >= 0)
2781 if (states[state].reduce_prod < 0)
2783 state = search(&states[state], states[state].reduce_sym);
2788 void *parser_run(struct token_state *tokens,
2789 const struct state states[],
2790 int (*do_reduce)(int, void**, struct token_config*, void*),
2791 void (*do_free)(short, void*),
2792 FILE *trace, const char *non_term[],
2793 struct token_config *config)
2795 struct parser p = { 0 };
2796 struct token *tk = NULL;
2800 shift(&p, TK_eof, 0, 1, NULL, states);
2802 struct token *err_tk;
2803 struct frame *tos = &p.stack[p.tos-1];
2805 tk = tok_copy(token_next(tokens));
2806 parser_trace(trace, &p,
2807 tk, states, non_term, config->known_count);
2809 if (tk->num == TK_in) {
2811 tos->since_newline = 0;
2812 tos->since_indent = 0;
2813 if (!states[tos->state].starts_line)
2814 tos->newline_permitted = 0;
2817 parser_trace_action(trace, "Record");
2820 if (tk->num == TK_out) {
2821 if (states[tos->state].reduce_size >= 0 &&
2822 states[tos->state].reduce_size <= tos->since_indent)
2824 if (states[tos->state].min_prefix >= tos->since_indent) {
2826 struct frame *in = tos - tos->since_indent;
2828 if (in->indents == 0) {
2829 /* Reassess since_indent and newline_permitted */
2831 in->since_indent = in[-1].since_indent + 1;
2832 in->newline_permitted = in[-1].newline_permitted;
2834 in->since_indent = 0;
2835 in->newline_permitted = 0;
2837 if (states[in->state].starts_line)
2838 in->newline_permitted = 1;
2841 in->since_indent = in[-1].since_indent + 1;
2842 if (states[in->state].starts_line)
2843 in->newline_permitted = 1;
2845 in->newline_permitted = in[-1].newline_permitted;
2850 parser_trace_action(trace, "Cancel");
2853 // fall through to error handling as both SHIFT and REDUCE
2856 if (tk->num == TK_newline) {
2857 if (!tos->newline_permitted) {
2860 parser_trace_action(trace, "Discard");
2863 if (tos->since_newline > 1 &&
2864 states[tos->state].reduce_size >= 0 &&
2865 states[tos->state].reduce_size <= tos->since_newline)
2868 if (shift(&p, tk->num, 0, tk->num == TK_newline, tk, states)) {
2870 parser_trace_action(trace, "Shift");
2874 if (states[tos->state].reduce_prod >= 0 &&
2875 states[tos->state].newline_only &&
2876 tk->num != TK_newline && tk->num != TK_eof && tk->num != TK_out) {
2877 /* Anything other than newline in an error as this
2878 * production must end at EOL
2880 } else if (states[tos->state].reduce_prod >= 0) {
2883 const struct state *nextstate = &states[tos->state];
2884 int prod = nextstate->reduce_prod;
2885 int size = nextstate->reduce_size;
2887 static char buf[16*1024];
2888 short indents, start_of_line;
2890 body = p.asn_stack + (p.tos - size);
2892 bufsize = do_reduce(prod, body, config, buf);
2894 indents = pop(&p, size, &start_of_line,
2896 res = memdup(buf, bufsize);
2897 memset(buf, 0, bufsize);
2898 if (!shift(&p, nextstate->reduce_sym,
2899 indents, start_of_line,
2901 if (prod != 0) abort();
2905 parser_trace_action(trace, "Reduce");
2908 /* Error. We walk up the stack until we
2909 * find a state which will accept TK_error.
2910 * We then shift in TK_error and see what state
2911 * that takes us too.
2912 * Then we discard input tokens until
2913 * we find one that is acceptable.
2915 parser_trace_action(trace, "ERROR");
2916 short indents = 0, start_of_line;
2918 err_tk = tok_copy(*tk);
2920 shift(&p, TK_error, 0, 0,
2921 err_tk, states) == 0)
2922 // discard this state
2923 indents += pop(&p, 1, &start_of_line, do_free);
2926 // no state accepted TK_error
2929 tos = &p.stack[p.tos-1];
2930 while (!in_lookahead(tk, states, tos->state) &&
2931 tk->num != TK_eof) {
2933 tk = tok_copy(token_next(tokens));
2934 if (tk->num == TK_in)
2936 if (tk->num == TK_out) {
2940 // FIXME update since_indent here
2943 tos->indents += indents;
2946 pop(&p, p.tos, NULL, do_free);
2952 ###### exported functions
2953 void *parser_run(struct token_state *tokens,
2954 const struct state states[],
2955 int (*do_reduce)(int, void**, struct token_config*, void*),
2956 void (*do_free)(short, void*),
2957 FILE *trace, const char *non_term[],
2958 struct token_config *config);
2962 Being able to visualize the parser in action can be invaluable when
2963 debugging the parser code, or trying to understand how the parse of a
2964 particular grammar progresses. The stack contains all the important
2965 state, so just printing out the stack every time around the parse loop
2966 can make it possible to see exactly what is happening.
2968 This doesn't explicitly show each SHIFT and REDUCE action. However they
2969 are easily deduced from the change between consecutive lines, and the
2970 details of each state can be found by cross referencing the states list
2971 in the stack with the "report" that parsergen can generate.
2973 For terminal symbols, we just dump the token. For non-terminals we
2974 print the name of the symbol. The look ahead token is reported at the
2975 end inside square brackets.
2977 ###### parser functions
2979 static char *reserved_words[] = {
2980 [TK_error] = "ERROR",
2983 [TK_newline] = "NEWLINE",
2986 static void parser_trace_state(FILE *trace, struct frame *f, const struct state states[])
2988 fprintf(trace, "(%d", f->state);
2989 if (states[f->state].starts_line)
2990 fprintf(trace, "s");
2991 if (f->newline_permitted)
2992 fprintf(trace, "n%d", f->since_newline);
2993 fprintf(trace, ") ");
2996 void parser_trace(FILE *trace, struct parser *p,
2997 struct token *tk, const struct state states[],
2998 const char *non_term[], int knowns)
3003 for (i = 0; i < p->tos; i++) {
3004 struct frame *f = &p->stack[i];
3007 if (sym < TK_reserved &&
3008 reserved_words[sym] != NULL)
3009 fputs(reserved_words[sym], trace);
3010 else if (sym < TK_reserved + knowns) {
3011 struct token *t = p->asn_stack[i];
3012 text_dump(trace, t->txt, 20);
3014 fputs(non_term[sym - TK_reserved - knowns],
3017 fprintf(trace, ".%d", f->indents);
3018 if (f->since_newline == 0)
3022 parser_trace_state(trace, f, states);
3024 fprintf(trace, "[");
3025 if (tk->num < TK_reserved &&
3026 reserved_words[tk->num] != NULL)
3027 fputs(reserved_words[tk->num], trace);
3029 text_dump(trace, tk->txt, 20);
3033 void parser_trace_action(FILE *trace, char *action)
3036 fprintf(trace, " - %s\n", action);
3041 The obvious example for a parser is a calculator.
3043 As `scanner` provides number parsing function using `libgmp` is it not much
3044 work to perform arbitrary rational number calculations.
3046 This calculator takes one expression, or an equality test, per line. The
3047 results are printed and if any equality test fails, the program exits with
3050 ###### File: parsergen.mk
3051 calc.c calc.h : parsergen parsergen.mdc
3052 ./parsergen --tag calc -o calc parsergen.mdc
3053 calc : calc.o libparser.o libscanner.o libmdcode.o libnumber.o
3054 $(CC) $(CFLAGS) -o calc calc.o libparser.o libscanner.o libmdcode.o libnumber.o -licuuc -lgmp
3056 ./calc parsergen.mdc
3062 // what do we use for a demo-grammar? A calculator of course.
3074 #include <sys/mman.h>
3080 #include "scanner.h"
3086 static void free_number(struct number *n)
3092 static int text_is(struct text t, char *s)
3094 return (strlen(s) == t.len &&
3095 strncmp(s, t.txt, t.len) == 0);
3098 int main(int argc, char *argv[])
3100 int fd = open(argv[1], O_RDONLY);
3101 int len = lseek(fd, 0, 2);
3102 char *file = mmap(NULL, len, PROT_READ, MAP_SHARED, fd, 0);
3103 struct section *table = code_extract(file, file+len, NULL);
3105 struct token_config config = {
3106 .ignored = (1 << TK_line_comment)
3107 | (1 << TK_block_comment)
3110 .number_chars = ".,_+-",
3114 for (s = table; s; s = s->next)
3115 if (text_is(s->section, "example: input"))
3116 parse_calc(s->code, &config, argc > 2 ? stderr : NULL);
3118 struct section *t = table->next;
3119 code_free(table->code);
3131 Session -> Session Line
3134 Line -> Expression NEWLINE ${ gmp_printf("Answer = %Qd\n", $1.val);
3135 { mpf_t fl; mpf_init2(fl, 20); mpf_set_q(fl, $1.val);
3136 gmp_printf(" or as a decimal: %Fg\n", fl);
3140 | Expression = Expression NEWLINE ${
3141 if (mpq_equal($1.val, $3.val))
3142 gmp_printf("Both equal %Qd\n", $1.val);
3144 gmp_printf("NOT EQUAL: %Qd\n != : %Qd\n",
3149 | NEWLINE ${ printf("Blank line\n"); }$
3150 | ERROR NEWLINE ${ printf("Skipped a bad line\n"); }$
3153 Expression -> Expression + Expression ${ mpq_init($0.val); mpq_add($0.val, $1.val, $3.val); }$
3154 | Expression - Expression ${ mpq_init($0.val); mpq_sub($0.val, $1.val, $3.val); }$
3155 | Expression * Expression ${ mpq_init($0.val); mpq_mul($0.val, $1.val, $3.val); }$
3156 | Expression / Expression ${ mpq_init($0.val); mpq_div($0.val, $1.val, $3.val); }$
3157 | NUMBER ${ if (number_parse($0.val, $0.tail, $1.txt) == 0) mpq_init($0.val); }$
3158 | ( Expression ) ${ mpq_init($0.val); mpq_set($0.val, $2.val); }$
3163 3.1415926535 - 355/113
3165 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9
3167 1 * 1000 + 2 * 100 + 3 * 10 + 4 * 1
code / ocean / blob