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