-# LR(1) Parser Generator #
+# LR(1) Parser Generator with 2D support #
This parser generator takes a grammar description combined with code
fragments, analyses it, and can report details about the analysis and
write out C code files which can be compiled to make a parser.
+"2D support" means that indentation and line breaks can be significant.
+Indent tokens (IN and OUT) and end-of-line tokens (EOL and NEWLINE) can
+be used to describe the grammar and the parser can selectively ignore
+these where they aren't relevant.
+
There are several distinct sections.
1. `grammar_read` will read a grammar from a literate-code file and
`parsergen` program built from the C code in this file can extract
that grammar directly from this file and process it.
-
###### File: parsergen.c
#include <unistd.h>
#include <stdlib.h>
## Reading the grammar
-The grammar must be stored in a markdown literate code file as parsed
-by "[mdcode][]". It must have three top level (i.e. unreferenced)
-sections: `header`, `code`, and `grammar`. The first two will be
-literally copied into the generated `.c` and `.h`. files. The last
-contains the grammar. This is tokenised with "[scanner][]".
+The grammar must be stored in a markdown literate code file as parsed by
+"[mdcode][]". It may have up to four top level (i.e. unreferenced)
+sections: `header`, `code`, `grammar` and `reduce`. The first two, if
+present, will be literally copied into the generated `.c` and `.h`
+files. The third is required and contains the grammar which is
+tokenised with "[scanner][]". `reduce` can provide variable
+declarations and common intialization code for all the reduction code
+fragments in the grammar.
If the `--tag` option is given, then any top level header that doesn't
start with the tag is ignored, and the tag is striped from the rest. So
-`--tag Foo`
-means that the three needed sections must be `Foo: header`, `Foo: code`,
-and `Foo: grammar`.
+`--tag Foo` means that the four sections expected are `Foo: header`,
+`Foo: code`, `Foo: grammar` and `Foo: reduce`. The tag `calc` is used
+to extract the sample calculator from this file.
[mdcode]: mdcode.html
[scanner]: scanner.html
#include "scanner.h"
The grammar contains production sets, precedence/associativity
-declarations, and data type declarations. These are all parsed with
-_ad hoc_ parsing as we don't have a parser generator yet.
+declarations, general terminal declarations, and data type declarations.
+These are all parsed with _ad hoc_ parsing as we don't have a parser
+generator yet.
-The precedence and associativity can be set for each production, but
+The precedence and associativity can be set for each production, and
can be inherited from symbols. The data type (either structure or a
reference to a structure) is potentially defined for each non-terminal
and describes what C structure is used to store information about each
## grammar fields
};
-The strings reported by `mdcode` and `scanner` are `struct text` which have
-length rather than being null terminated. To help with printing and
+The strings reported by `mdcode` and `scanner` are `struct text` which
+have length rather than being nul terminated. To help with printing and
comparing we define `text_is` and `prtxt`, which should possibly go in
-`mdcode`. `scanner` does provide `text_dump` which is useful for strings
-which might contain control characters.
+`mdcode`. `scanner` does provide `text_dump` which is useful for
+strings which might contain control characters.
`strip_tag` is a bit like `strncmp`, but adds a test for a colon,
because that is what we need to detect tags.
Productions are comprised primarily of symbols - terminal and
non-terminal. We do not make a syntactic distinction between the two,
-though non-terminals must be identifiers. Non-terminal symbols are
-those which appear in the head of a production, terminal symbols are
-those which don't. There are also "virtual" symbols used for precedence
-marking discussed later, and sometimes we won't know what type a symbol
-is yet.
+though non-terminals must be identifiers while terminals can also be
+marks. Non-terminal symbols are those which appear in the head of a
+production, terminal symbols are those which don't. There are also
+"virtual" symbols used for precedence marking discussed later, and
+sometimes we won't know what type a symbol is yet.
+
+To help with code safety it is possible to declare the terminal symbols.
+If this is done, then any symbol used in a production that does not
+appear in the head of any production and is not declared as a terminal
+is treated as an error.
###### forward declarations
enum symtype { Unknown, Virtual, Terminal, Nonterminal };
char *symtypes = "UVTN";
###### symbol fields
enum symtype type;
+###### grammar fields
+ int terminals_declared;
Symbols can be either `TK_ident` or `TK_mark`. They are saved in a
table of known symbols and the resulting parser will report them as
`TK_reserved + N`. A small set of identifiers are reserved for the
-different token types that `scanner` can report.
+different token types that `scanner` can report, and an even smaller set
+are reserved for a special token that the parser can generate (`EOL`) as
+will be described later. This latter set cannot use predefined numbers,
+so they are marked as `isspecial` for now and will get assigned a number
+with the non-terminals later.
###### declarations
- static char *reserved_words[] = {
- [TK_error] = "ERROR",
- [TK_number] = "NUMBER",
- [TK_ident] = "IDENTIFIER",
- [TK_mark] = "MARK",
- [TK_string] = "STRING",
- [TK_multi_string] = "MULTI_STRING",
- [TK_in] = "IN",
- [TK_out] = "OUT",
- [TK_newline] = "NEWLINE",
- [TK_eof] = "$eof",
+
+ static struct { int num; char *name; } reserved_words[] = {
+ { TK_error, "ERROR" },
+ { TK_number, "NUMBER" },
+ { TK_ident, "IDENTIFIER" },
+ { TK_mark, "MARK" },
+ { TK_string, "STRING" },
+ { TK_multi_string, "MULTI_STRING" },
+ { TK_in, "IN" },
+ { TK_out, "OUT" },
+ { TK_newline, "NEWLINE" },
+ { TK_eof, "$eof" },
+ { -1, "EOL" },
};
+
###### symbol fields
short num;
+ unsigned int isspecial:1;
Note that `TK_eof` and the two `TK_*_comment` tokens cannot be
recognised. The former is automatically expected at the end of the text
for (i = 0; i < entries; i++) {
struct text t;
struct symbol *s;
- t.txt = reserved_words[i];
- if (!t.txt)
- continue;
+ t.txt = reserved_words[i].name;
t.len = strlen(t.txt);
s = sym_find(g, t);
s->type = Terminal;
- s->num = i;
+ s->num = reserved_words[i].num;
+ s->isspecial = 1;
}
}
### Data types and precedence.
-Data type specification and precedence specification are both
-introduced by a dollar sign at the start of the line. If the next
-word is `LEFT`, `RIGHT` or `NON`, then the line specifies a
+Data type specification, precedence specification, and declaration of
+terminals are all introduced by a dollar sign at the start of the line.
+If the next word is `LEFT`, `RIGHT` or `NON`, then the line specifies a
+precedence, if it is `TERM` then the line declares terminals without
precedence, otherwise it specifies a data type.
The data type name is simply stored and applied to the head of all
no data type associated with them and can carry no information. In
order to allow other non-terminals to have no type, the data type
`$void` can be given. This does *not* mean that `struct void` will be
-used, but rather than no type will be associated with future
+used, but rather than no type will be associated with subsequent
non-terminals.
-The precedence line must contain a list of symbols - typically
-terminal symbols, but not necessarily. It can only contain symbols
-that have not been seen yet, so precedence declaration must precede
-the productions that they affect.
+The precedence line must contain a list of symbols, either terminal
+symbols or virtual symbols. It can only contain symbols that have not
+been seen yet, so precedence declaration must precede the productions
+that they affect.
-A precedence line may also contain a "virtual" symbol which is an
-identifier preceded by `$$`. Virtual terminals carry precedence
-information but are not included in the grammar. A production can
-declare that it inherits the precedence of a given virtual symbol.
+A "virtual" symbol is an identifier preceded by `$$`. Virtual symbols
+carry precedence information but are not included in the grammar. A
+production can declare that it inherits the precedence of a given
+virtual symbol.
-This use for `$$` precludes it from being used as a symbol in the
+This use of `$$` precludes it from being used as a symbol in the
described language. Two other symbols: `${` and `}$` are also
unavailable.
listed and may be inherited by any production which uses the symbol. A
production inherits from the last symbol which has a precedence.
+The symbols on the first precedence line have the lowest precedence.
+Subsequent lines introduce symbols with higher precedence and so bind
+more tightly.
+
+Note that a declaration line (or "dollar line") can start with either of
+two different marks: "$" or "$*". The `dollar_line()` function defined
+here is told which was found in the `isref` argument.
+
###### grammar fields
struct text current_type;
int type_isref;
struct token t = token_next(ts);
char *err;
enum assoc assoc;
+ int term = 0;
int found;
if (t.num != TK_ident) {
assoc = Right;
else if (text_is(t.txt, "NON"))
assoc = Non;
- else {
+ else if (text_is(t.txt, "TERM")) {
+ term = 1;
+ g->terminals_declared = 1;
+ } else {
g->current_type = t.txt;
g->type_isref = isref;
if (text_is(t.txt, "void"))
goto abort;
}
- // This is a precedence line, need some symbols.
+ // This is a precedence or TERM line, need some symbols.
found = 0;
g->prec_levels += 1;
t = token_next(ts);
err = "$$ must be followed by a word";
goto abort;
}
+ if (term) {
+ err = "Virtual symbols not permitted on $TERM line";
+ goto abort;
+ }
} else if (t.num != TK_ident &&
t.num != TK_mark) {
err = "Illegal token in precedence line";
}
s = sym_find(g, t.txt);
if (s->type != Unknown) {
- err = "Symbols in precedence line must not already be known.";
+ err = "Symbols in precedence/TERM line must not already be known.";
goto abort;
}
s->type = type;
- s->precedence = g->prec_levels;
- s->assoc = assoc;
+ if (!term) {
+ s->precedence = g->prec_levels;
+ s->assoc = assoc;
+ }
found += 1;
+ t = token_next(ts);
}
- if (found == 0)
- err = "No symbols given on precedence line";
+ if (found == 0) {
+ err = "No symbols given on precedence/TERM line";
goto abort;
+ }
return NULL;
abort:
while (t.num != TK_newline && t.num != TK_eof)
at the end of a line.
Text in the code fragment will undergo substitutions where `$N` or
-`$<N`,for some numeric `N`, will be replaced with a variable holding
-the parse information for the particular symbol in the production.
-`$0` is the head of the production, `$1` is the first symbol of the
-body, etc. The type of `$N` for a terminal symbol is `struct token`.
-For a non-terminal, it is whatever has been declared for that symbol.
-The `<` may be included for symbols declared as storing a reference
-(not a structure) and means that the reference is being moved out, so
-it will not automatically be freed.
+`$<N`,for some numeric `N` (or non-numeric indicator as described
+later), will be replaced with a variable holding the parse information
+for the particular symbol in the production. `$0` is the head of the
+production, `$1` is the first symbol of the body, etc. The type of `$N`
+for a terminal symbol is `struct token`. For a non-terminal, it is
+whatever has been declared for that symbol. The `<` may be included and
+means that the value (usually a reference) is being moved out, so it
+will not automatically be freed. The effect of using '<' is that the
+variable is cleared to all-zeros.
While building productions we will need to add to an array which needs to
grow dynamically.
return code;
}
-Now we have all the bit we need to parse a full production.
+Now we have all the bits we need to parse a full production.
###### includes
#include <memory.h>
struct symbol **body;
int body_size;
struct text code;
+ int code_line;
###### symbol fields
int first_production;
tk = token_next(state);
while (tk.num == TK_ident || tk.num == TK_mark) {
struct symbol *bs = sym_find(g, tk.txt);
- if (bs->type == Unknown)
- bs->type = Terminal;
if (bs->type == Virtual) {
err = "Virtual symbol not permitted in production";
goto abort;
goto abort;
}
vs = sym_find(g, tk.txt);
- if (vs->type != Virtual) {
- err = "symbol after $$ must be virtual";
+ if (vs->precedence == 0) {
+ err = "symbol after $$ must have precedence";
goto abort;
+ } else {
+ p.precedence = vs->precedence;
+ p.assoc = vs->assoc;
}
- p.precedence = vs->precedence;
- p.assoc = vs->assoc;
tk = token_next(state);
}
if (tk.num == TK_open) {
+ p.code_line = tk.line;
p.code = collect_code(state, tk);
if (p.code.txt == NULL) {
err = "code fragment not closed properly";
}
tk = token_next(state);
}
+
if (tk.num != TK_newline && tk.num != TK_eof) {
err = "stray tokens at end of line";
goto abort;
abort:
while (tk.num != TK_newline && tk.num != TK_eof)
tk = token_next(state);
+ free(p.body);
return err;
}
-With the ability to parse production and dollar-lines, we have nearly all
+With the ability to parse productions and dollar-lines, we have nearly all
that we need to parse a grammar from a `code_node`.
-The head of the first production will effectively be the `start` symbol of
-the grammar. However it won't _actually_ be so. Processing the grammar is
-greatly simplified if the real start symbol only has a single production,
-and expects `$eof` as the final terminal. So when we find the first
-explicit production we insert an extra production as production zero which
-looks like
+The head of the first production will effectively be the `start` symbol
+of the grammar. However it won't _actually_ be so. Processing the
+grammar is greatly simplified if the real start symbol only has a single
+production, and expects `$eof` as the final terminal. So when we find
+the first explicit production we insert an extra implicit production as
+production zero which looks like
###### Example: production 0
$start -> START $eof
p->head->first_production = g->production_count;
array_add(&g->productions, &g->production_count, p);
-Now we are ready to read in the grammar.
+Now we are ready to read in the grammar. We ignore comments
+and strings so that the marks which introduce them can be
+used as terminals in the grammar. We don't ignore numbers
+even though we don't allow them as that causes the scanner
+to produce errors that the parser is better positioned to handle.
+We also ignore indentation, but we expect and use newlines.
+
+To allow comments in the grammar, we explicitly check for "//" as the
+first token on the line and those lines are skipped. "//" can still be
+used as a terminal anywhere that a terminal is expected.
###### grammar_read
static struct grammar *grammar_read(struct code_node *code)
} else if (tk.num == TK_mark
&& text_is(tk.txt, "$*")) {
err = dollar_line(state, g, 1);
+ } else if (tk.num == TK_mark
+ && text_is(tk.txt, "//")) {
+ while (tk.num != TK_newline &&
+ tk.num != TK_eof)
+ tk = token_next(state);
} else {
err = "Unrecognised token at start of line.";
}
goto abort;
}
token_close(state);
+
+ struct symbol *s;
+ for (s = g->syms; s; s = s->next) {
+ if (s->type != Unknown)
+ continue;
+ if (!g->terminals_declared) {
+ s->type = Terminal;
+ continue;
+ }
+ err = "not declared";
+ fprintf(stderr, "Token %.*s not declared\n",
+ s->name.len, s->name.txt);
+ }
+ if (err) {
+ free(g); // FIXME free content
+ g = NULL;
+ }
return g;
abort:
fprintf(stderr, "Error at line %d: %s\n",
tk.line, err);
token_close(state);
- free(g);
+ free(g); // FIXME free content
return NULL;
}
## Analysing the grammar
The central task in analysing the grammar is to determine a set of
-states to drive the parsing process. This will require finding
-various sets of symbols and of "items". Some of these sets will need
-to attach information to each element in the set, so they are more
-like maps.
-
-Each "item" may have a 'look-ahead' or `LA` set associated with
-it. Many of these will be the same as each other. To avoid memory
-wastage, and to simplify some comparisons of sets, these sets will be
-stored in a list of unique sets, each assigned a number.
-
-Once we have the data structures in hand to manage these sets and
-lists, we can start setting the 'nullable' flag, build the 'FIRST'
+states to drive the parsing process. This will require finding various
+sets of symbols and of "items". Some of these sets will need to attach
+information to each element in the set, so they are more like maps.
+
+Each "item" may have a 'look-ahead' or `LA` set associated with it.
+Many of these will be the same as each other. To avoid memory wastage,
+and to simplify some comparisons of sets, these sets will be stored in a
+list of unique sets, each assigned a number.
+
+Once we have the data structures in hand to manage these sets and lists,
+we can start setting the 'nullable' flag, build the 'FIRST' and 'FOLLOW'
sets, and then create the item sets which define the various states.
### Symbol sets.
things we store, so they are called symbol sets or "symsets".
A symset has a size, an array of shorts, and an optional array of data
-values, which are also shorts. If the array of data is not present,
-we store an impossible pointer, as `NULL` is used to indicate that no
+values, which are also shorts. If the array of data is not present, we
+store an impossible pointer, as `NULL` is used to indicate that no
memory has been allocated yet;
###### declarations
const struct symset INIT_SYMSET = { 0, NULL, NO_DATA };
const struct symset INIT_DATASET = { 0, NULL, NULL };
-The arrays of shorts are allocated in blocks of 8 and are kept sorted
-by using an insertion sort. We don't explicitly record the amount of
-allocated space as it can be derived directly from the current `cnt` using
-`((cnt - 1) | 7) + 1`.
+The arrays of shorts are allocated in blocks of 8 and are kept sorted by
+using an insertion sort. We don't explicitly record the amount of
+allocated space as it can be derived directly from the current `cnt`
+using `((cnt - 1) | 7) + 1`.
###### functions
static void symset_add(struct symset *s, unsigned short key, unsigned short val)
}
We will often want to form the union of two symsets. When we do, we
-will often want to know if anything changed (as they might mean there
-is more work to do). So `symset_union` reports whether anything was
-added to the first set. We use a slow quadratic approach as these
-sets don't really get very big. If profiles shows this to be a problem is
-can be optimised later.
+will often want to know if anything changed (as that might mean there is
+more work to do). So `symset_union` reports whether anything was added
+to the first set. We use a slow quadratic approach as these sets are
+rarely large. If profiling shows this to be a problem it can be
+optimised later.
static int symset_union(struct symset *a, struct symset *b)
{
Some symsets are simply stored somewhere appropriate in the `grammar`
data structure, others needs a bit of indirection. This applies
particularly to "LA" sets. These will be paired with "items" in an
-"itemset". As itemsets will be stored in a symset, the "LA" set needs to be
-stored in the `data` field, so we need a mapping from a small (short)
-number to an LA `symset`.
+"itemset". As itemsets will be stored in a symset, the "LA" set needs
+to be stored in the `data` field, so we need a mapping from a small
+(short) number to an LA `symset`.
As mentioned earlier this involves creating a list of unique symsets.
return s->num;
}
-Finding a set by number is currently performed by a simple linear search.
-If this turns out to hurt performance, we can store the sets in a dynamic
-array like the productions.
+Finding a set by number is currently performed by a simple linear
+search. If this turns out to hurt performance, we can store the sets in
+a dynamic array like the productions.
static struct symset set_find(struct grammar *g, int num)
{
return sl->ss;
}
-
### Setting `nullable`
We set `nullable` on the head symbol for any production for which all
}
}
-### Setting `can_eol` and `line_like`
-
-In order to be able to ignore newline tokens when not relevant, but
-still include them in the parse when needed, we will need to know
-which states can start a "line-like" section of code. We ignore
-newlines when there is an indent since the most recent start of a
-line-like symbol.
-
-To know which symbols are line-like, we first need to know which
-symbols start with a NEWLINE token. Any symbol which is followed by a
-NEWLINE, or anything that starts with a NEWLINE, is deemed to be a line-like symbol.
-Certainly when trying to parse one of these we must take not of NEWLINEs.
-
-Clearly the `TK_newline` token can start with a NEWLINE. Any symbol
-which is the head of a production that contains a starts-with-NEWLINE
-symbol preceeded only by nullable symbols is also a
-starts-with-NEWLINE symbol. We use a new field `can_eol` to record
-this attribute of symbols, and compute it in a repetitive manner
-similar to `set_nullable`.
-
-Once we have that, we can determine which symbols are `line_like` be
-seeing which are followed by a `can_eol` symbol in any production.
-
-###### symbol fields
- int can_eol;
- int line_like;
-
-###### functions
- static void set_can_eol(struct grammar *g)
- {
- int check_again = 1;
- g->symtab[TK_newline]->can_eol = 1;
- while (check_again) {
- int p;
- check_again = 0;
- for (p = 0; p < g->production_count; p++) {
- struct production *pr = g->productions[p];
- int s;
-
- if (pr->head->can_eol)
- continue;
-
- for (s = 0 ; s < pr->body_size; s++) {
- if (pr->body[s]->can_eol) {
- pr->head->can_eol = 1;
- check_again = 1;
- break;
- }
- if (!pr->body[s]->nullable)
- break;
- }
- }
- }
- }
-
- static void set_line_like(struct grammar *g)
- {
- int p;
- for (p = 0; p < g->production_count; p++) {
- struct production *pr = g->productions[p];
- int s;
-
- for (s = 1; s < pr->body_size; s++)
- if (pr->body[s]->can_eol)
- pr->body[s-1]->line_like = 1;
- }
- }
-
### Building the `first` sets
-When calculating what can follow a particular non-terminal, we will need to
-know what the "first" terminal in any subsequent non-terminal might be. So
-we calculate the `first` set for every non-terminal and store them in an
-array. We don't bother recording the "first" set for terminals as they are
-trivial.
-
-As the "first" for one symbol might depend on the "first" of another,
-we repeat the calculations until no changes happen, just like with
-`set_nullable`. This makes use of the fact that `symset_union`
-reports if any change happens.
-
-The core of this which finds the "first" of part of a production body
-will be reused for computing the "follow" sets, so we split it out
-into a separate function.
+When calculating what can follow a particular non-terminal, we will need
+to know what the "first" terminal in any subsequent non-terminal might
+be. So we calculate the `first` set for every non-terminal and store
+them in an array. We don't bother recording the "first" set for
+terminals as they are trivial.
+
+As the "first" for one symbol might depend on the "first" of another, we
+repeat the calculations until no changes happen, just like with
+`set_nullable`. This makes use of the fact that `symset_union` reports
+if any change happens.
+
+The core of this, which finds the "first" of part of a production body,
+will be reused for computing the "follow" sets, so we split that out
+into a separate function, `add_first`, which also reports if it got all
+the way to the end of the production without finding a non-nullable
+symbol.
###### grammar fields
struct symset *first;
### Building the `follow` sets.
-There are two different situations when we will want to generate "follow"
-sets. If we are doing an SLR analysis, we want to generate a single
-"follow" set for each non-terminal in the grammar. That is what is
-happening here. If we are doing an LALR or LR analysis we will want
-to generate a separate "LA" set for each item. We do that later
-in state generation.
+There are two different situations when we will want to generate
+"follow" sets. If we are doing an SLR analysis, we want to generate a
+single "follow" set for each non-terminal in the grammar. That is what
+is happening here. If we are doing an LALR or LR analysis we will want
+to generate a separate "LA" set for each item. We do that later in
+state generation.
There are two parts to generating a "follow" set. Firstly we look at
-every place that any non-terminal appears in the body of any
-production, and we find the set of possible "first" symbols after
-there. This is done using `add_first` above and only needs to be done
-once as the "first" sets are now stable and will not change.
+every place that any non-terminal appears in the body of any production,
+and we find the set of possible "first" symbols after there. This is
+done using `add_first` above and only needs to be done once as the
+"first" sets are now stable and will not change.
+
+###### grammar fields
+ struct symset *follow;
###### follow code
depends on "follow" itself we need to repeatedly perform the process
until no further changes happen.
+Rather than 2 nested loops, one that repeats the whole process until
+there is no change, and one that iterates of the set of productions, we
+combine these two functions into a single loop.
+
###### follow code
- for (again = 0, p = 0;
+ for (check_again = 0, p = 0;
p < g->production_count;
p < g->production_count-1
- ? p++ : again ? (again = 0, p = 0)
+ ? p++ : check_again ? (check_again = 0, p = 0)
: p++) {
struct production *pr = g->productions[p];
int b;
break;
if (symset_union(&g->follow[bs->num],
&g->follow[pr->head->num]))
- again = 1;
+ check_again = 1;
if (!bs->nullable)
break;
}
We now just need to create and initialise the `follow` list to get a
complete function.
-###### grammar fields
- struct symset *follow;
-
###### functions
static void build_follow(struct grammar *g)
{
- int s, again, p;
+ int s, check_again, p;
g->follow = calloc(g->num_syms, sizeof(g->follow[0]));
for (s = 0; s < g->num_syms; s++)
g->follow[s] = INIT_SYMSET;
There are three different levels of detail that can be chosen for
building the itemsets and states for the LR grammar. They are:
-1. LR(0) or SLR(1), where no look-ahead is considered.
+1. LR(0), LR(0.5), or SLR(1), where no look-ahead is included in the
+ itemsets - look-ahead, if used at all, is simply the 'follow' sets
+ already computed,
2. LALR(1) where we build look-ahead sets with each item and merge
the LA sets when we find two paths to the same "kernel" set of items.
3. LR(1) where different look-ahead for any item in the set means
- a different state must be created.
+ a different item set must be created.
###### forward declarations
enum grammar_type { LR0, LR05, SLR, LALR, LR1 };
list.
An item is a pair of numbers: the production number and the position of
-"DOT", which is an index into the body of the production.
-As the numbers are not enormous we can combine them into a single "short"
-and store them in a `symset` - 4 bits for "DOT" and 12 bits for the
-production number (so 4000 productions with maximum of 15 symbols in the
+"DOT", which is an index into the body of the production. As the
+numbers are not enormous we can combine them into a single "short" and
+store them in a `symset` - 5 bits for "DOT" and 11 bits for the
+production number (so 2000 productions with maximum of 31 symbols in the
body).
Comparing the itemsets will be a little different to comparing symsets
the first "0".
###### declarations
- static inline unsigned short item_num(int production, int index)
+ static inline unsigned short item_num(int production, int dot)
{
- return production | ((31-index) << 11);
+ return production | ((31-dot) << 11);
}
static inline int item_prod(unsigned short item)
{
return item & 0x7ff;
}
- static inline int item_index(unsigned short item)
+ static inline int item_dot(unsigned short item)
{
return (31-(item >> 11)) & 0x1f;
}
for (i = 0;
i < a.cnt && i < b.cnt &&
- item_index(a.syms[i]) > 0 &&
- item_index(b.syms[i]) > 0;
+ item_dot(a.syms[i]) > 0 &&
+ item_dot(b.syms[i]) > 0;
i++) {
int diff = a.syms[i] - b.syms[i];
if (diff)
return diff;
}
}
- if (i == a.cnt || item_index(a.syms[i]) == 0)
+ if (i == a.cnt || item_dot(a.syms[i]) == 0)
av = -1;
else
av = a.syms[i];
- if (i == b.cnt || item_index(b.syms[i]) == 0)
+ if (i == b.cnt || item_dot(b.syms[i]) == 0)
bv = -1;
else
bv = b.syms[i];
a.data[i] - b.data[i];
}
+It will be helpful to know if an itemset has been "completed" or not,
+particularly for LALR where itemsets get merged, at which point they
+need to be consider for completion again. So a `completed` flag is
+needed.
+
And now we can build the list of itemsets. The lookup routine returns
-both a success flag and a pointer to where in the list an insert
-should happen, so we don't need to search a second time.
+both a success flag and a pointer to where in the list an insert should
+happen, so we don't need to search a second time.
###### declarations
struct itemset {
short state;
struct symset items;
struct symset go_to;
+ enum assoc assoc;
+ unsigned short precedence;
char completed;
- char starts_line;
- int min_prefix;
};
###### grammar fields
}
Adding an itemset may require merging the LA sets if LALR analysis is
-happening. If any new LA set adds any symbols that weren't in the old LA set, we
-clear the `completed` flag so that the dependants of this itemset will be
-recalculated and their LA sets updated.
+happening. If any new LA set adds any symbols that weren't in the old
+LA set, we clear the `completed` flag so that the dependants of this
+itemset will be recalculated and their LA sets updated.
`add_itemset` must consume the symsets it is passed, either by adding
them to a data structure, of freeing them.
static int add_itemset(struct grammar *g, struct symset ss,
+ enum assoc assoc, unsigned short precedence,
enum grammar_type type)
{
struct itemset **where, *is;
is->state = g->states;
g->states += 1;
is->items = ss;
+ is->assoc = assoc;
+ is->precedence = precedence;
is->next = *where;
is->go_to = INIT_DATASET;
*where = is;
#### The build
-To build all the itemsets, we first insert the initial itemset made
-from production zero, complete each itemset, and then generate new
-itemsets from old until no new ones can be made.
+To build all the itemsets, we first insert the initial itemset made from
+production zero, complete each itemset, and then generate new itemsets
+from old until no new ones can be made.
-Completing an itemset means finding all the items where "DOT" is followed by
-a nonterminal and adding "DOT=0" items for every production from that
-non-terminal - providing each item hasn't already been added.
+Completing an itemset means finding all the items where "DOT" is
+followed by a nonterminal and adding "DOT=0" items for every production
+from that non-terminal - providing each item hasn't already been added.
+When we add such an item it might get inserted before the current
+one, so to make sure we process it we reset the loop counter to the
+start.
If LA sets are needed, the LA set for each new item is found using
-`add_first` which was developed earlier for `FIRST` and `FOLLOW`. This may
-be supplemented by the LA set for the item which produce the new item.
-
-We also collect a set of all symbols which follow "DOT" (in `done`) as this
-is used in the next stage.
-If any of these symbols are flagged as starting a line, then this
-state must be a `starts_line` state so now is a good time to record that.
-
-NOTE: precedence handling should happen here - I haven't written this yet
-though.
+`add_first` which was developed earlier for `FIRST` and `FOLLOW`. This
+may be supplemented by the LA set for the item which produced the new
+item.
+
+We also collect a set of all symbols which follow "DOT" (in `done`) as
+this is used in the next stage.
+
+When itemsets are created we assign a precedence to the itemset from the
+complete item, if there is one. We ignore the possibility of there
+being two and don't (currently) handle precedence in such grammars.
+When completing a grammar we ignore any item where DOT is followed by a
+terminal with a precedence lower than that for the itemset. Unless the
+terminal has right associativity, we also ignore items where the
+terminal has the same precedence. The result is that unwanted items are
+still in the itemset, but the terminal doesn't get into the go to set,
+so the item is ineffective.
###### complete itemset
for (i = 0; i < is->items.cnt; i++) {
int p = item_prod(is->items.syms[i]);
- int bs = item_index(is->items.syms[i]);
+ int bs = item_dot(is->items.syms[i]);
struct production *pr = g->productions[p];
int p2;
struct symbol *s;
struct symset LA = INIT_SYMSET;
unsigned short sn = 0;
- if (is->min_prefix == 0 ||
- (bs > 0 && bs < is->min_prefix))
- is->min_prefix = bs;
if (bs == pr->body_size)
continue;
s = pr->body[bs];
- if (symset_find(&done, s->num) < 0) {
+ if (s->precedence && is->precedence &&
+ is->precedence > s->precedence)
+ /* This terminal has a low precedence and
+ * shouldn't be shifted
+ */
+ continue;
+ if (s->precedence && is->precedence &&
+ is->precedence == s->precedence && s->assoc != Right)
+ /* This terminal has a matching precedence and is
+ * not Right-associative, so we mustn't shift it.
+ */
+ continue;
+ if (symset_find(&done, s->num) < 0)
symset_add(&done, s->num, 0);
- if (s->line_like)
- is->starts_line = 1;
- }
+
if (s->type != Nonterminal)
continue;
- again = 1;
+ check_again = 1;
if (type >= LALR) {
// Need the LA set.
int to_end;
} else if (type >= LALR) {
struct symset ss = set_find(g, is->items.data[pos]);
struct symset tmp = INIT_SYMSET;
+ struct symset *la = &LA;
symset_union(&tmp, &ss);
- if (symset_union(&tmp, &LA)) {
+ if (symset_union(&tmp, la)) {
is->items.data[pos] = save_set(g, tmp);
i = -1;
- }else
+ } else
symset_free(tmp);
}
}
}
-For each symbol we found (and placed in `done`) we collect all the items for
-which this symbol is next, and create a new itemset with "DOT" advanced over
-the symbol. This is then added to the collection of itemsets (or merged
-with a pre-existing itemset).
+For each symbol we found (and placed in `done`) we collect all the items
+for which this symbol is next, and create a new itemset with "DOT"
+advanced over the symbol. This is then added to the collection of
+itemsets (or merged with a pre-existing itemset).
###### derive itemsets
// Now we have a completed itemset, so we need to
int j;
unsigned short state;
struct symbol *sym = g->symtab[done.syms[i]];
+ enum assoc assoc = Non;
+ unsigned short precedence = 0;
struct symset newitemset = INIT_SYMSET;
if (type >= LALR)
newitemset = INIT_DATASET;
for (j = 0; j < is->items.cnt; j++) {
int itm = is->items.syms[j];
int p = item_prod(itm);
- int bp = item_index(itm);
+ int bp = item_dot(itm);
struct production *pr = g->productions[p];
unsigned short la = 0;
int pos;
continue;
if (pr->body[bp] != sym)
continue;
+
+ bp += 1;
if (type >= LALR)
la = is->items.data[j];
- pos = symset_find(&newitemset, pr->head->num);
+ if (bp == pr->body_size &&
+ pr->precedence > 0 &&
+ pr->precedence > precedence) {
+ // new itemset is reducible and has a precedence.
+ precedence = pr->precedence;
+ assoc = pr->assoc;
+ }
+ pos = symset_find(&newitemset, item_num(p, bp));
+
if (pos < 0)
- symset_add(&newitemset, item_num(p, bp+1), la);
+ symset_add(&newitemset, item_num(p, bp), la);
else if (type >= LALR) {
// Need to merge la set.
int la2 = newitemset.data[pos];
}
}
}
- state = add_itemset(g, newitemset, type);
+ state = add_itemset(g, newitemset, assoc, precedence, type);
if (symset_find(&is->go_to, done.syms[i]) < 0)
symset_add(&is->go_to, done.syms[i], state);
}
-All that is left is to crate the initial itemset from production zero, and
+All that is left is to create the initial itemset from production zero, and
with `TK_eof` as the LA set.
###### functions
{
struct symset first = INIT_SYMSET;
struct itemset *is;
- int again;
+ int check_again;
unsigned short la = 0;
if (type >= LALR) {
// LA set just has eof
}
// production 0, offset 0 (with no data)
symset_add(&first, item_num(0, 0), la);
- add_itemset(g, first, type);
- for (again = 0, is = g->items;
+ add_itemset(g, first, Non, 0, type);
+ for (check_again = 0, is = g->items;
is;
- is = is->next ?: again ? (again = 0, g->items) : NULL) {
+ is = is->next ?: check_again ? (check_again = 0, g->items) : NULL) {
int i;
struct symset done = INIT_SYMSET;
if (is->completed)
continue;
is->completed = 1;
- again = 1;
+ check_again = 1;
## complete itemset
## derive itemsets
symset_free(done);
a report.
Once we have built everything we allocate arrays for the two lists:
-symbols and itemsets. This allows more efficient access during reporting.
-The symbols are grouped as terminals and non-terminals and we record the
-changeover point in `first_nonterm`.
+symbols and itemsets. This allows more efficient access during
+reporting. The symbols are grouped as terminals, then non-terminals,
+then virtual, with the start of non-terminals recorded as `first_nonterm`.
+Special terminals -- meaning just EOL -- are included with the
+non-terminals so that they are not expected by the scanner.
###### grammar fields
struct symbol **symtab;
struct itemset *is;
int snum = TK_reserved;
for (s = g->syms; s; s = s->next)
- if (s->num < 0 && s->type == Terminal) {
+ if (s->num < 0 && s->type == Terminal && !s->isspecial) {
s->num = snum;
snum++;
}
g->first_nonterm = snum;
+ for (s = g->syms; s; s = s->next)
+ if (s->num < 0 && s->type != Virtual) {
+ s->num = snum;
+ snum++;
+ }
for (s = g->syms; s; s = s->next)
if (s->num < 0) {
s->num = snum;
g->symtab[s->num] = s;
set_nullable(g);
- set_can_eol(g);
- set_line_like(g);
if (type >= SLR)
build_first(g);
Firstly we have the complete list of symbols, together with the
"FIRST" set if that was generated. We add a mark to each symbol to
-show if it can end in a newline (`>`), if it is considered to be
-"line-like" (`<`), or if it is nullable (`.`).
+show if it is nullable (`.`).
###### functions
if (!s)
continue;
- printf(" %c%c%c%3d%c: ",
+ printf(" %c%3d%c: ",
s->nullable ? '.':' ',
- s->can_eol ? '>':' ',
- s->line_like ? '<':' ',
s->num, symtypes[s->type]);
prtxt(s->name);
if (s->precedence)
static void report_item(struct grammar *g, int itm)
{
int p = item_prod(itm);
- int dot = item_index(itm);
+ int dot = item_dot(itm);
struct production *pr = g->productions[p];
int i;
if (dot == pr->body_size)
printf(" .");
printf(" [%d]", p);
- if (pr->precedence)
+ if (pr->precedence && dot == pr->body_size)
printf(" (%d%s)", pr->precedence,
assoc_names[pr->assoc]);
+ if (dot < pr->body_size &&
+ pr->body[dot]->precedence) {
+ struct symbol *s = pr->body[dot];
+ printf(" [%d%s]", s->precedence,
+ assoc_names[s->assoc]);
+ }
printf("\n");
}
Then the go to sets:
-
static void report_goto(struct grammar *g, struct symset gt)
{
int i;
for (s = 0; s < g->states; s++) {
int j;
struct itemset *is = g->statetab[s];
- printf(" Itemset %d:%s min prefix=%d\n",
- s, is->starts_line?" (startsline)":"", is->min_prefix);
+ printf(" Itemset %d:", s);
+ if (is->precedence)
+ printf(" %d%s", is->precedence, assoc_names[is->assoc]);
+ printf("\n");
for (j = 0; j < is->items.cnt; j++) {
report_item(g, is->items.syms[j]);
if (is->items.data != NO_DATA)
### Reporting conflicts
Conflict detection varies a lot among different analysis levels. However
-LR0 and LR0.5 are quite similar - having no follow sets, and SLR, LALR and
+LR0 and LR0.5 are quite similar - having no follow sets - and SLR, LALR and
LR1 are also similar as they have FOLLOW or LA sets.
###### functions
LR0 conflicts are any state which have both a reducible item and
a shiftable item, or two reducible items.
-LR05 conflicts only occurs if two possibly reductions exist,
+LR05 conflicts only occur if two possible reductions exist,
as shifts always over-ride reductions.
###### conflict functions
for (j = 0; j < is->items.cnt; j++) {
int itm = is->items.syms[j];
int p = item_prod(itm);
- int bp = item_index(itm);
+ int bp = item_dot(itm);
struct production *pr = g->productions[p];
if (bp == pr->body_size) {
for (j = 0; j < is->items.cnt; j++) {
unsigned short itm = is->items.syms[j];
int p = item_prod(itm);
- int bp = item_index(itm);
+ int bp = item_dot(itm);
struct production *pr = g->productions[p];
+ struct symbol *s;
- if (bp < pr->body_size &&
- pr->body[bp]->type == Terminal) {
- /* shiftable */
- int sym = pr->body[bp]->num;
- if (symset_find(&shifts, sym) < 0)
- symset_add(&shifts, sym, itm);
- }
+ if (bp >= pr->body_size ||
+ pr->body[bp]->type != Terminal)
+ /* not shiftable */
+ continue;
+
+ s = pr->body[bp];
+ if (s->precedence && is->precedence)
+ /* Precedence resolves this, so no conflict */
+ continue;
+
+ if (symset_find(&shifts, s->num) < 0)
+ symset_add(&shifts, s->num, itm);
}
- /* Now look for reduction and conflicts */
+ /* Now look for reductions and conflicts */
for (j = 0; j < is->items.cnt; j++) {
unsigned short itm = is->items.syms[j];
int p = item_prod(itm);
- int bp = item_index(itm);
+ int bp = item_dot(itm);
struct production *pr = g->productions[p];
if (bp < pr->body_size)
int pos = symset_find(&shifts, la.syms[k]);
if (pos >= 0) {
printf(" State %d has SHIFT/REDUCE conflict on ", i);
- prtxt(g->symtab[la.syms[k]]->name);
+ cnt++;
+ prtxt(g->symtab[la.syms[k]]->name);
printf(":\n");
report_item(g, shifts.data[pos]);
report_item(g, itm);
- cnt++;
}
pos = symset_find(&reduce, la.syms[k]);
if (pos < 0) {
known words added and then is used with the `code_node` to initialize the
scanner.
-`parse_XX` then calls the library function `parser_run` to actually complete
-the parse. This needs the `states` table and function to call the various
-pieces of code provided in the grammar file, so they are generated first.
+`parse_XX` then calls the library function `parser_run` to actually
+complete the parse. This needs the `states` table, the `reductions`
+table and functions to call the various pieces of code provided in the
+grammar file, so they are generated first.
###### parser_generate
- static void gen_parser(FILE *f, struct grammar *g, char *file, char *name)
+ static void gen_parser(FILE *f, struct grammar *g, char *file, char *name,
+ struct code_node *pre_reduce)
{
gen_known(f, g);
gen_non_term(f, g);
gen_goto(f, g);
gen_states(f, g);
- gen_reduce(f, g, file);
+ gen_reductions(f, g);
+ gen_reduce(f, g, file, pre_reduce);
gen_free(f, g);
fprintf(f, "#line 0 \"gen_parser\"\n");
fprintf(f, "\tstruct token_state *tokens;\n");
fprintf(f, "\tconfig->words_marks = known;\n");
fprintf(f, "\tconfig->known_count = sizeof(known)/sizeof(known[0]);\n");
- fprintf(f, "\tconfig->ignored |= (1 << TK_line_comment) | (1 << TK_block_comment);\n");
fprintf(f, "\ttokens = token_open(code, config);\n");
- fprintf(f, "\tvoid *rv = parser_run(tokens, states, do_reduce, do_free, trace, non_term, config);\n");
+ fprintf(f, "\tvoid *rv = parser_run(tokens, states, reductions, do_reduce, do_free, trace, non_term, config);\n");
fprintf(f, "\ttoken_close(tokens);\n");
fprintf(f, "\treturn rv;\n");
fprintf(f, "}\n\n");
for (i = TK_reserved;
i < g->num_syms;
i++)
- if (g->symtab[i]->type == Nonterminal)
+ if (g->symtab[i]->type == Nonterminal ||
+ g->symtab[i]->isspecial)
fprintf(f, "\t\"%.*s\",\n", g->symtab[i]->name.len,
g->symtab[i]->name.txt);
fprintf(f, "};\n\n");
}
-### States and the goto tables.
+### States, reductions, and the go to tables.
-For each state we record the goto table, the reducible production if
-there is one, or a symbol to shift for error recovery.
-Some of the details of the reducible production are stored in the
-`do_reduce` function to come later. Here we store the production number,
-the body size (useful for stack management) and the resulting symbol (useful
-for knowing how to free data later).
+For each state we record the go to table and the reducible production if
+there is one, the details of which are in a separate table of
+reductions. Some of the details of the reducible production are stored
+in the `do_reduce` function to come later. In the go to table we store
+the production number and in the reductions table: the body size (useful
+for stack management), the resulting symbol (useful for knowing how to
+free data later), and the size of the resulting asn object (useful for
+preallocation space.
The go to table is stored in a simple array of `sym` and corresponding
`state`.
short sym;
short state;
};
+ struct reduction {
+ short size;
+ short sym;
+ short result_size;
+ };
struct state {
+ short reduce_prod;
short go_to_cnt;
const struct lookup * go_to;
- short reduce_prod;
- short reduce_size;
- short reduce_sym;
- short shift_sym;
- short starts_line;
- short min_prefix;
};
-
###### functions
static void gen_goto(FILE *f, struct grammar *g)
int i;
fprintf(f, "#line 0 \"gen_goto\"\n");
for (i = 0; i < g->states; i++) {
+ struct symset gt = g->statetab[i]->go_to;
int j;
+
+ if (gt.cnt == 0)
+ continue;
fprintf(f, "static const struct lookup goto_%d[] = {\n",
i);
- struct symset gt = g->statetab[i]->go_to;
for (j = 0; j < gt.cnt; j++)
fprintf(f, "\t{ %d, %d },\n",
gt.syms[j], gt.data[j]);
}
}
-###### functions
+ static void gen_reductions(FILE *f, struct grammar *g)
+ {
+ int i;
+ fprintf(f, "#line 0 \"gen_reductions\"\n");
+ fprintf(f, "static const struct reduction reductions[] = {\n");
+ for (i = 0; i < g->production_count; i++) {
+ struct production *pr = g->productions[i];
+ struct symbol *hd = pr->head;
+ fprintf(f, "\t{%d, %d, ", pr->body_size, hd->num);
+ if (hd->struct_name.txt == NULL)
+ fprintf(f, "0 },\n");
+ else
+ fprintf(f, "sizeof(struct %.*s%s) },\n",
+ hd->struct_name.len,
+ hd->struct_name.txt,
+ hd->isref ? "*" : "");
+ }
+ fprintf(f, "};\n\n");
+ }
static void gen_states(FILE *f, struct grammar *g)
{
for (i = 0; i < g->states; i++) {
struct itemset *is = g->statetab[i];
int j, prod = -1, prod_len;
- int shift_sym = -1;
- int shift_len = 0, shift_remain = 0;
+
for (j = 0; j < is->items.cnt; j++) {
int itm = is->items.syms[j];
int p = item_prod(itm);
- int bp = item_index(itm);
+ int bp = item_dot(itm);
struct production *pr = g->productions[p];
- if (bp < pr->body_size) {
- if (shift_sym < 0 ||
- (shift_len == bp && shift_remain > pr->body_size - bp)) {
- shift_sym = pr->body[bp]->num;
- shift_len = bp;
- shift_remain = pr->body_size - bp;
- }
+ if (bp < pr->body_size)
continue;
- }
- /* This is what we reduce */
+ /* This is what we reduce - choose longest */
if (prod < 0 || prod_len < pr->body_size) {
prod = p;
prod_len = pr->body_size;
}
}
-
- if (prod >= 0)
- fprintf(f, "\t[%d] = { %d, goto_%d, %d, %d, %d, 0, %d, %d },\n",
- i, is->go_to.cnt, i, prod,
- g->productions[prod]->body_size,
- g->productions[prod]->head->num,
- is->starts_line, is->min_prefix);
+ if (is->go_to.cnt)
+ fprintf(f, "\t[%d] = { %d, %d, goto_%d },\n",
+ i, prod, is->go_to.cnt, i);
else
- fprintf(f, "\t[%d] = { %d, goto_%d, -1, -1, -1, %d, %d, %d },\n",
- i, is->go_to.cnt, i, shift_sym,
- is->starts_line, is->min_prefix);
+ fprintf(f, "\t[%d] = { %d, 0, NULL },\n", i, prod);
}
fprintf(f, "};\n\n");
}
### The `do_reduce` function and the code
-When the parser engine decides to reduce a production, it calls `do_reduce`.
-This has two functions.
-
-Firstly, if a non-NULL `trace` file is passed, it prints out details of the
-production being reduced. Secondly it runs the code that was included with
-the production if any.
+When the parser engine decides to reduce a production, it calls
+`do_reduce` which runs the code that was included with the production,
+if any.
-This code needs to be able to store data somewhere. Rather than requiring
-`do_reduce` to `malloc` that "somewhere", we pass in a large buffer and have
-`do_reduce` return the size to be saved.
+This code needs to be able to store data somewhere so we record the size
+of the data expected with each state so it can be allocated before
+`do_reduce` is called.
In order for the code to access "global" context, we pass in the
-"config" pointer that was passed to parser function. If the `struct
+"config" pointer that was passed to the parser function. If the `struct
token_config` is embedded in some larger structure, the reducing code
-can access the larger structure using pointer manipulation.
-
-The code fragment requires translation when written out. Any `$N` needs to
-be converted to a reference either to that buffer (if `$0`) or to the
-structure returned by a previous reduction. These pointers need to be cast
-to the appropriate type for each access. All this is handling in
+can access the larger structure using pointer manipulation. Performing
+that pointer manipulation, and any other common code or variables for
+all reduce actions, can be provided in code node called "reduce" which
+is passed around in `pre_reduce` which you might have already noticed.
+
+The code fragments require translation when written out. Any `$N` needs
+to be converted to a reference either to that buffer (if `$0`) or to the
+structure returned by a previous reduction. These pointers need to be
+cast to the appropriate type for each access. All this is handled in
`gen_code`.
-`gen_code` also allows symbol references to contain a '`<`' as in '`$<2`'.
-This applied only to symbols with references (or pointers), not those with structures.
-The `<` implies that the reference it being moved out, so the object will not be
-automatically freed. This is equivalent to assigning `NULL` to the pointer.
+`gen_code` also allows symbol references to contain a '`<`' as in
+'`$<2`'. This is particularly useful for references (or pointers), but
+can be used with structures too. The `<` implies that the value is
+being moved out, so the object will not be automatically freed. It is
+equivalent to assigning `NULL` to the pointer or filling a structure
+with zeros.
+
+Instead of a number `N`, the `$` or `$<` can be followed by some letters
+and possibly a number. A number by itself (other than zero) selects a
+symbol from the body of the production. A sequence of letters selects
+the shortest symbol in the body which contains those letters in the
+given order. If a number follows the letters, then a later occurrence
+of that symbol is chosen. So "`$AB2`" will refer to the structure
+attached to the second occurrence of the shortest symbol which contains
+an `A` followed by a `B`. If there is no unique shortest system, or if
+the number given is too large, then the symbol reference is not
+transformed, and will cause an error when the code is compiled.
###### functions
+ static int textchr(struct text t, char c, int s)
+ {
+ int i;
+ for (i = s; i < t.len; i++)
+ if (t.txt[i] == c)
+ return i;
+ return -1;
+ }
+
+ static int subseq_match(char *seq, int slen, struct text name)
+ {
+ int st = 0;
+ while (slen > 0) {
+ st = textchr(name, *seq, st);
+ if (st < 0)
+ return 0;
+ slen -= 1;
+ seq += 1;
+ st += 1;
+ }
+ return 1;
+ }
+
+ static int choose_sym(char **namep, int len, struct production *p)
+ {
+ char *name = *namep;
+ char *nam = name;
+ int namlen;
+ int n = 0;
+ int i, s, slen;
+ char c;
+
+ c = *name;
+ while (len > 0 &&
+ ((c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'))) {
+ name += 1;
+ len -= 1;
+ c = *name;
+ }
+ namlen = name-nam;
+ while (len > 0 && (c >= '0' && c <= '9')) {
+ name += 1;
+ len -= 1;
+ n = n * 10 + (c - '0');
+ c = *name;
+ }
+ if (namlen == 0) {
+ if (name == *namep || n > p->body_size)
+ return -1;
+ *namep = name;
+ return n;
+ }
+ slen = 0; s = -1;
+ for (i = 0; i < p->body_size; i++) {
+ if (!subseq_match(nam, namlen, p->body[i]->name))
+ continue;
+ if (slen == 0 || p->body[i]->name.len < slen) {
+ s = i;
+ slen = p->body[i]->name.len;
+ }
+ if (s >= 0 && p->body[i] != p->body[s] &&
+ p->body[i]->name.len == p->body[s]->name.len)
+ /* not unique, so s cannot be used */
+ s = -1;
+ }
+ if (s < 0)
+ return -1;
+ if (n == 0)
+ n = 1;
+ for (i = 0; i < p->body_size; i++)
+ if (p->body[i] == p->body[s]) {
+ n -= 1;
+ if (n == 0)
+ break;
+ }
+ if (n > 0 || i == p->body_size)
+ return -1;
+ *namep = name;
+ return i + 1;
+ }
+
static void gen_code(struct production *p, FILE *f, struct grammar *g)
{
char *c;
use = 1;
c++;
}
- if (*c < '0' || *c > '9') {
+ n = choose_sym(&c, p->code.txt + p->code.len - c, p);
+ if (n < 0) {
+ fputc('$', f);
if (use)
fputc('<', f);
fputc(*c, f);
continue;
}
- n = *c - '0';
- while (c[1] >= '0' && c[1] <= '9') {
- c += 1;
- n = n * 10 + *c - '0';
- }
if (n == 0)
fprintf(f, "(*(struct %.*s*%s)ret)",
p->head->struct_name.len,
p->head->struct_name.txt,
p->head->isref ? "*":"");
- else if (n > p->body_size)
- fprintf(f, "$%d", n);
else if (p->body[n-1]->type == Terminal)
fprintf(f, "(*(struct token *)body[%d])",
n-1);
p->body[n-1]->isref ? "*":"", n-1);
used[n-1] = use;
}
+ c -= 1;
}
fputs("\n", f);
for (i = 0; i < p->body_size; i++) {
if (p->body[i]->struct_name.txt &&
- p->body[i]->isref &&
- used[i])
+ used[i]) {
// assume this has been copied out
- fprintf(f, "\t\t*(void**)body[%d] = NULL;\n", i);
+ if (p->body[i]->isref)
+ fprintf(f, "\t\t*(void**)body[%d] = NULL;\n", i);
+ else
+ fprintf(f, "\t\tmemset(body[%d], 0, sizeof(struct %.*s));\n", i, p->body[i]->struct_name.len, p->body[i]->struct_name.txt);
+ }
}
free(used);
}
###### functions
- static void gen_reduce(FILE *f, struct grammar *g, char *file)
+ static void gen_reduce(FILE *f, struct grammar *g, char *file,
+ struct code_node *pre_reduce)
{
int i;
- fprintf(f, "#line 0 \"gen_reduce\"\n");
+ fprintf(f, "#line 1 \"gen_reduce\"\n");
fprintf(f, "static int do_reduce(int prod, void **body, struct token_config *config, void *ret)\n");
fprintf(f, "{\n");
fprintf(f, "\tint ret_size = 0;\n");
+ if (pre_reduce)
+ code_node_print(f, pre_reduce, file);
+ fprintf(f, "#line 4 \"gen_reduce\"\n");
fprintf(f, "\tswitch(prod) {\n");
for (i = 0; i < g->production_count; i++) {
struct production *p = g->productions[i];
fprintf(f, "\tcase %d:\n", i);
- if (p->code.txt)
+ if (p->code.txt) {
+ fprintf(f, "#line %d \"%s\"\n", p->code_line, file);
gen_code(p, f, g);
+ }
if (p->head->struct_name.txt)
fprintf(f, "\t\tret_size = sizeof(struct %.*s%s);\n",
For this, the grammar author is required to defined a `free_XX` function for
each structure that is used by a non-terminal. `do_free` will call whichever
is appropriate given a symbol number, and will call `free` (as is
-appropriate for tokens on any terminal symbol.
+appropriate for tokens) on any terminal symbol.
###### functions
fprintf(f, "static void do_free(short sym, void *asn)\n");
fprintf(f, "{\n");
fprintf(f, "\tif (!asn) return;\n");
- fprintf(f, "\tif (sym < %d) {\n", g->first_nonterm);
+ fprintf(f, "\tif (sym < %d", g->first_nonterm);
+ /* Need to handle special terminals too */
+ for (i = 0; i < g->num_syms; i++) {
+ struct symbol *s = g->symtab[i];
+ if (i >= g->first_nonterm && s->type == Terminal &&
+ s->isspecial)
+ fprintf(f, " || sym == %d", s->num);
+ }
+ fprintf(f, ") {\n");
fprintf(f, "\t\tfree(asn);\n\t\treturn;\n\t}\n");
fprintf(f, "\tswitch(sym) {\n");
case 't':
tag = optarg; break;
default:
- fprintf(stderr, "Usage: parsergen ...\n");
+ fprintf(stderr, "Usage: parsergen -[05SL1R] [-t tag] [-o output] input\n");
exit(1);
}
}
To be able to run `mdcode` and `scanner` on the grammar we need to memory
map it.
-One we have extracted the code (with `mdcode`) we expect to find three
-sections: header, code, and grammar. Anything else that is not
-excluded by the `--tag` option is an error.
+Once we have extracted the code (with `mdcode`) we expect to find three
+or four sections: header, code, grammar, reduce.
+Anything else that is not excluded by the `--tag` option is an error.
-"header" and "code" are optional, though it is hard to build a working
-parser with neither. "grammar" must be provided.
+"header", "code", and "reduce" are optional, though it is hard to build
+a working parser without the first two. "grammar" must be provided.
###### includes
#include <fcntl.h>
struct code_node *hdr = NULL;
struct code_node *code = NULL;
struct code_node *gram = NULL;
+ struct code_node *pre_reduce = NULL;
for (s = table; s; s = s->next) {
struct text sec = s->section;
if (tag && !strip_tag(&sec, tag))
code = s->code;
else if (text_is(sec, "grammar"))
gram = s->code;
+ else if (text_is(sec, "reduce"))
+ pre_reduce = s->code;
else {
fprintf(stderr, "Unknown content section: %.*s\n",
s->section.len, s->section.txt);
rv |= 1;
}
-If a headers section is defined, we write it out and include a declaration
+If a "headers" section is defined, we write it out and include a declaration
for the `parse_XX` function so it can be used from separate code.
if (rv == 0 && hdr && outfile) {
if (f) {
if (code)
code_node_print(f, code, infile);
- gen_parser(f, g, infile, name);
+ gen_parser(f, g, infile, name, pre_reduce);
fclose(f);
} else {
fprintf(stderr, "Cannot create %s.c\n",
## The SHIFT/REDUCE parser
-Having analysed the grammar and generated all the tables, we only need the
-shift/reduce engine to bring it all together.
+Having analysed the grammar and generated all the tables, we only need
+the shift/reduce engine to bring it all together.
-### Goto table lookup
+### Go to table lookup
-The parser generator has nicely provided us with goto tables sorted by
+The parser generator has nicely provided us with go to tables sorted by
symbol number. We need a binary search function to find a symbol in the
table.
return -1;
}
-### The state stack.
-
-The core data structure for the parser is the stack. This tracks all the
-symbols that have been recognised or partially recognised.
+### Memory allocation
-The stack usually won't grow very large - maybe a few tens of entries. So
-we dynamically resize and array as required but never bother to shrink it
-down again.
+The `scanner` returns tokens in a local variable - we want them in allocated
+memory so they can live in the `asn_stack`. So we provide `tok_copy` to
+make an allocated copy as required.
-We keep the stack as two separate allocations. One, `asn_stack` stores the
-"abstract syntax nodes" which are created by each reduction. When we call
-`do_reduce` we need to pass an array of the `asn`s of the body of the
-production, and by keeping a separate `asn` stack, we can just pass a
-pointer into this stack.
+###### parser includes
+ #include <memory.h>
-The other allocation stores all other stack fields of which there are six.
-The `state` is the most important one and guides the parsing process. The
-`sym` is nearly unnecessary. However when we want to free entries from the
-`asn_stack`, it helps to know what type they are so we can call the right
-freeing function. The symbol leads us to the right free function through
-`do_free`.
+###### parser functions
-The `indents` count tracks the line indents with in the symbol or
-immediately follow it. These are used to allow indent information to
-guide parsing and error recovery.
+ static struct token *tok_copy(struct token tk)
+ {
+ struct token *new = malloc(sizeof(*new));
+ *new = tk;
+ return new;
+ }
-`since_newline` tracks how many stack frames since the last
-start-of-line (whether indented or not). So if `since_newline` is
-zero, then this symbol is at the start of a line. Similarly
-`since_indent` counts the number of states since an indent, it is zero
-precisely when `indents` is not zero.
+### The state stack.
-`newline_permitted` keeps track of whether newlines should be ignored
-or not.
+The core data structure for the parser is the stack. This tracks all
+the symbols that have been recognised or partially recognised.
+
+The stack usually won't grow very large - maybe a few tens of entries.
+So we dynamically grow an array as required but never bother to
+shrink it down again.
+
+We keep the stack as two separate allocations. One, `asn_stack`, stores
+the "abstract syntax nodes" which are created by each reduction. When
+we call `do_reduce` we need to pass an array of the `asn`s of the body
+of the production, and by keeping a separate `asn` stack, we can just
+pass a pointer into this stack.
+
+The other allocation stores all other stack fields of which there are
+two. The `state` is the most important one and guides the parsing
+process. The `sym` is nearly unnecessary as it is implicit in the
+state. However when we want to free entries from the `asn_stack`, it
+helps to know what type they are so we can call the right freeing
+function. The symbol leads us to the right free function through
+`do_free`.
The stack is most properly seen as alternating states and symbols -
states, like the 'DOT' in items, are between symbols. Each frame in
our stack holds a state and the symbol that was before it. The
bottom of stack holds the start state but no symbol, as nothing came
-before the beginning.
+before the beginning. As we need to store some value, `TK_eof` is used
+to mark the beginning of the file as well as the end.
###### parser functions
struct parser {
struct frame {
short state;
- short newline_permitted;
-
short sym;
- short indents;
- short since_newline;
- short since_indent;
} *stack;
void **asn_stack;
int stack_size;
int tos;
+
+ ## parser state
};
#### Shift and pop
Two operations are needed on the stack - shift (which is like push) and pop.
-Shift applies not only to terminals but also to non-terminals. When
-we reduce a production we will pop off entries corresponding to the
-body symbols, then push on an item for the head of the production.
-This last is exactly the same process as shifting in a terminal so we
-use the same function for both. In both cases we provide the symbol,
-the number of indents the symbol contains (which will be zero for a
-terminal symbol) and a flag indicating the the symbol was at (or was
-reduced from a symbol which was at) the start of a line. The state is
+Shift applies not only to terminals but also to non-terminals. When we
+reduce a production we will pop off frames corresponding to the body
+symbols, then push on a frame for the head of the production. This last
+is exactly the same process as shifting in a terminal so we use the same
+function for both. In both cases we provide the symbol. The state is
deduced from the current top-of-stack state and the new symbol.
-To simplify other code we arrange for `shift` to fail if there is no `goto`
+To simplify other code we arrange for `shift` to fail if there is no `go to`
state for the symbol. This is useful in basic parsing due to our design
that we shift when we can, and reduce when we cannot. So the `shift`
function reports if it could.
So `shift` finds the next state. If that succeeds it extends the
allocations if needed and pushes all the information onto the stacks.
-Newlines are permitted after a `starts_line` state until an internal
-indent. If the new frame has neither a `starts_line` state nor an
-indent, newlines are permitted if the previous stack frame permitted
-them.
-
###### parser functions
static int shift(struct parser *p,
- short sym, short indents, short start_of_line,
- void *asn,
+ short sym, void *asn,
const struct state states[])
{
- // Push an entry onto the stack
struct frame next = {0};
int newstate = p->tos
? search(&states[p->stack[p->tos-1].state],
: 0;
if (newstate < 0)
return 0;
+
if (p->tos >= p->stack_size) {
p->stack_size += 10;
p->stack = realloc(p->stack, p->stack_size
* sizeof(p->asn_stack[0]));
}
next.sym = sym;
- next.indents = indents;
next.state = newstate;
- if (states[newstate].starts_line)
- next.newline_permitted = 1;
- else if (indents)
- next.newline_permitted = 0;
- else if (p->tos)
- next.newline_permitted =
- p->stack[p->tos-1].newline_permitted;
- else
- next.newline_permitted = 0;
-
- if (!start_of_line) {
- if (p->tos)
- next.since_newline = p->stack[p->tos-1].since_newline + 1;
- else
- next.since_newline = 1;
- }
- if (indents)
- next.since_indent = 0;
- else if (p->tos)
- next.since_indent = p->stack[p->tos-1].since_indent + 1;
- else
- next.since_indent = 1;
p->stack[p->tos] = next;
p->asn_stack[p->tos] = asn;
}
`pop` primarily moves the top of stack (`tos`) back down the required
-amount and frees any `asn` entries that need to be freed. It also
-collects a summary of the indents and line starts in the symbols that
-are being removed. It is called _after_ we reduce a production, just
-before we `shift` the nonterminal in.
+amount and frees any `asn` entries that need to be freed. It is called
+_after_ we reduce a production, just before we `shift` the nonterminal
+in.
###### parser functions
- static int pop(struct parser *p, int num,
- short *start_of_line,
- void(*do_free)(short sym, void *asn))
+ static void pop(struct parser *p, int num,
+ void(*do_free)(short sym, void *asn))
{
int i;
- short indents = 0;
- int sol = 0;
p->tos -= num;
- for (i = 0; i < num; i++) {
- sol |= !p->stack[p->tos+1].since_newline;
- indents += p->stack[p->tos+i].indents;
- do_free(p->stack[p->tos+i].sym,
- p->asn_stack[p->tos+i]);
- }
- if (start_of_line)
- *start_of_line = sol;
- return indents;
+ for (i = 0; i < num; i++)
+ do_free(p->stack[p->tos+i].sym, p->asn_stack[p->tos+i]);
}
-### Memory allocation
+### The heart of the parser.
-The `scanner` returns tokens in a local variable - we want them in allocated
-memory so they can live in the `asn_stack`. Similarly the `asn` produced by
-a reduce is in a large buffer. Both of these require some allocation and
-copying, hence `memdup` and `tokcopy`.
+Now we have the parser. For each token we might shift it, trigger a
+reduction, or start error handling. 2D tokens (IN, OUT, NEWLINE, EOL)
+might also be ignored. Ignoring tokens is combined with shifting.
-###### parser includes
- #include <memory.h>
+###### parser vars
-###### parser functions
+ struct parser p = { 0 };
+ struct token *tk = NULL;
+ int accepted = 0;
- void *memdup(void *m, int len)
- {
- void *ret;
- if (len == 0)
- return NULL;
- ret = malloc(len);
- memcpy(ret, m, len);
- return ret;
+###### heart of parser
+
+ shift(&p, TK_eof, NULL, states);
+ while (!accepted && p.tos > 0) {
+ struct frame *tos = &p.stack[p.tos-1];
+ if (!tk)
+ tk = tok_copy(token_next(tokens));
+ parser_trace(trace, &p,
+ tk, states, non_term, config->known_count);
+
+ ## try shift or ignore
+ ## try reduce
+ ## handle error
}
- static struct token *tok_copy(struct token tk)
- {
- struct token *new = malloc(sizeof(*new));
- *new = tk;
- return new;
+Indents are ignored unless they can be shifted onto the stack
+immediately or nothing can be shifted (in which case we reduce, and try
+again). The end of an indented section - the OUT token - is ignored
+precisely when the indent was ignored. To keep track of this we need a
+small stack of flags, which is easily stored as bits in an `unsigned
+long`. This will never overflow and the scanner only allows 20 levels
+of indentation.
+
+###### parser state
+ unsigned long ignored_indents;
+
+NEWLINE is ignored when in an indented section of text which was not
+explicitly expected by the grammar. So if the most recent indent is
+ignored, so is any NEWLINE token.
+
+If a NEWLINE is seen but it cannot be shifted, we try to shift an EOL
+token instead. If that succeeds, we make a new copy of the NEWLINE
+token and continue. This allows a NEWLINE to appear to be preceded by
+an indefinite number of EOL tokens.
+
+The token number for `EOL` cannot be statically declared, so when the
+parser starts we need to look through the array of non-terminals to find
+the EOL.
+
+###### parser state
+ int tk_eol;
+
+###### find eol
+ p.tk_eol = 0;
+ while (strcmp(non_term[p.tk_eol], "EOL") != 0)
+ p.tk_eol += 1;
+ p.tk_eol += TK_reserved + config->known_count;
+
+For other tokens, we shift the next token if that is possible, otherwise
+we try to reduce a production.
+
+###### try shift or ignore
+
+ if ((tk->num == TK_newline || tk->num == TK_out) &&
+ (p.ignored_indents & 1)) {
+ /* indented, so ignore OUT and NEWLINE */
+ if (tk->num == TK_out)
+ p.ignored_indents >>= 1;
+ free(tk);
+ tk = NULL;
+ parser_trace_action(trace, "Ignore");
+ continue;
+ }
+
+ if (shift(&p, tk->num, tk, states)) {
+ if (tk->num == TK_out)
+ p.ignored_indents >>= 1;
+ if (tk->num == TK_in)
+ p.ignored_indents <<= 1;
+
+ parser_trace_action(trace, "Shift");
+ tk = NULL;
+ ## did shift
+ continue;
+ } else if (tk->num == TK_newline &&
+ shift(&p, p.tk_eol, tk, states)) {
+ tk = tok_copy(*tk);
+ parser_trace_action(trace, "ShiftEOL");
+ continue;
+ }
+
+ if (tk->num == TK_in && states[p.stack[p.tos-1].state].go_to_cnt > 0) {
+ /* No indent expected here and reduce is not mandatory, so ignore IN */
+ free(tk);
+ tk = NULL;
+ p.ignored_indents <<= 1;
+ p.ignored_indents |= 1;
+ parser_trace_action(trace, "Ignore");
+ continue;
}
-### The heart of the parser.
+We have already discussed the bulk of the handling of a "reduce" action,
+with the `pop()` and `shift()` functions doing much of the work. There
+is a little more complexity needed to manage storage for the asn (Abstract
+Syntax Node), and also a test of whether the reduction is permitted.
+
+When we try to shift the result of reducing production-zero, it will
+fail because there is no next state. In this case the asn will not have
+been stored on the stack, so it get stored in the `ret` variable, and we
+report that that input has been accepted.
+
+###### parser vars
+
+ void *ret = NULL;
+
+###### try reduce
+
+ if (states[tos->state].reduce_prod >= 0) {
+ void **body;
+ void *res;
+ const struct state *nextstate = &states[tos->state];
+ int prod = nextstate->reduce_prod;
+ int size = reductions[prod].size;
+ int res_size = reductions[prod].result_size;
+
+ body = p.asn_stack + (p.tos - size);
+ res = res_size ? calloc(1, res_size) : NULL;
+ res_size = do_reduce(prod, body, config, res);
+ if (res_size != reductions[prod].result_size)
+ abort();
+ pop(&p, size, do_free);
+ if (!shift(&p, reductions[prod].sym, res, states)) {
+ accepted = 1;
+ ret = res;
+ parser_trace_action(trace, "Accept");
+ } else
+ parser_trace_action(trace, "Reduce");
+ continue;
+ }
-Now we have the parser. If we can shift we do, though newlines and
-reducing indenting may block that. If not and we can reduce we do
-that. If the production we reduced was production zero, then we have
-accepted the input and can finish.
+If we can neither shift nor reduce we have an error to handle. There
+are two possible responses to an error: we can pop single frames off the
+stack until we find a frame that can shift `TK_error`, or we can discard
+the current look-ahead symbol.
-We return whatever `asn` was returned by reducing production zero.
+When we first see an error we do the first of these and set a flag to
+record that we are processing an error. If the normal shift/reduce
+tests fail to find that anything can be done from that state, we start
+dropping tokens until either we manage to shift one, or reach end-of-file.
-If we can neither shift nor reduce we have an error to handle. We pop
-single entries off the stack until we can shift the `TK_error` symbol, then
-drop input tokens until we find one we can shift into the new error state.
+###### parser vars
-When we find `TK_in` and `TK_out` tokens which report indents we need
-to handle them directly as the grammar cannot express what we want to
-do with them.
+ int in_err = 0;
-`TK_in` tokens are easy: we simply update indent count in the top stack frame to
-record how many indents there are following the previous token.
+###### did shift
-`TK_out` tokens must either be canceled against an indent count
-within the stack. If we can reduce some symbols that are all since
-the most recent indent, then we do that first. If the minimum prefix
-of the current state then extents back before the most recent indent,
-that indent can be cancelled. If the minimum prefix is shorter then
-the indent is premature and we must start error handling, which
-currently doesn't work at all.
+ in_err = 0;
-`TK_newline` tokens are ignored unless the top stack frame records
-that they are permitted. In that case they will not be considered for
-shifting if it is possible to reduce some symbols that are all since
-the most recent start of line. This is how a newline forcible
-terminates any line-like structure - we try to reduce down to at most
-one symbol for each line where newlines are allowed.
+###### handle error
+
+ if (in_err) {
+ parser_trace_action(trace, "DISCARD");
+ if (tk->num == TK_eof)
+ break;
+ free(tk);
+ tk = NULL;
+ } else {
+ struct token *err_tk;
+
+ parser_trace_action(trace, "ERROR");
+
+ err_tk = tok_copy(*tk);
+ while (p.tos > 0 && shift(&p, TK_error, err_tk, states) == 0)
+ // discard this state
+ pop(&p, 1, do_free);
+ if (p.tos == 0) {
+ free(err_tk);
+ // no state accepted TK_error
+ break;
+ }
+ in_err = 1;
+ }
###### parser includes
#include "parser.h"
+
###### parser_run
+
void *parser_run(struct token_state *tokens,
const struct state states[],
+ const struct reduction reductions[],
int (*do_reduce)(int, void**, struct token_config*, void*),
void (*do_free)(short, void*),
FILE *trace, const char *non_term[],
struct token_config *config)
{
- struct parser p = { 0 };
- struct token *tk = NULL;
- int accepted = 0;
- void *ret = NULL;
-
- shift(&p, TK_eof, 0, 1, NULL, states);
- while (!accepted) {
- struct token *err_tk;
- struct frame *tos = &p.stack[p.tos-1];
- if (!tk)
- tk = tok_copy(token_next(tokens));
- parser_trace(trace, &p,
- tk, states, non_term, config->known_count);
-
- if (tk->num == TK_in) {
- tos->indents += 1;
- tos->since_newline = 0;
- tos->since_indent = 0;
- if (!states[tos->state].starts_line)
- tos->newline_permitted = 0;
- free(tk);
- tk = NULL;
- parser_trace_action(trace, "Record");
- continue;
- }
- if (tk->num == TK_out) {
- if (states[tos->state].reduce_size >= 0 &&
- states[tos->state].reduce_size <= tos->since_indent)
- goto force_reduce;
- if (states[tos->state].min_prefix >= tos->since_indent) {
- // OK to cancel
- struct frame *in = tos - tos->since_indent;
- in->indents -= 1;
- if (in->indents == 0) {
- /* Reassess since_indent and newline_permitted */
- if (in > p.stack) {
- in->since_indent = in[-1].since_indent + 1;
- in->newline_permitted = in[-1].newline_permitted;
- } else {
- in->since_indent = 0;
- in->newline_permitted = 0;
- }
- if (states[in->state].starts_line)
- in->newline_permitted = 1;
- while (in < tos) {
- in += 1;
- in->since_indent = in[-1].since_indent + 1;
- if (states[in->state].starts_line)
- in->newline_permitted = 1;
- else
- in->newline_permitted = in[-1].newline_permitted;
- }
- }
- free(tk);
- tk = NULL;
- parser_trace_action(trace, "Cancel");
- continue;
- }
- // fall through and force a REDUCE (as 'shift'
- // will fail).
- }
- if (tk->num == TK_newline) {
- if (!tos->newline_permitted) {
- free(tk);
- tk = NULL;
- parser_trace_action(trace, "Discard");
- continue;
- }
- if (tos->since_newline > 1 &&
- states[tos->state].reduce_size >= 0 &&
- states[tos->state].reduce_size <= tos->since_newline)
- goto force_reduce;
- }
- if (shift(&p, tk->num, 0, tk->num == TK_newline, tk, states)) {
- tk = NULL;
- parser_trace_action(trace, "Shift");
- continue;
- }
- force_reduce:
- if (states[tos->state].reduce_prod >= 0) {
- void **body;
- void *res;
- const struct state *nextstate = &states[tos->state];
- int prod = nextstate->reduce_prod;
- int size = nextstate->reduce_size;
- int bufsize;
- static char buf[16*1024];
- short indents, start_of_line;
-
- body = p.asn_stack + (p.tos - size);
-
- bufsize = do_reduce(prod, body, config, buf);
-
- indents = pop(&p, size, &start_of_line,
- do_free);
- res = memdup(buf, bufsize);
- memset(buf, 0, bufsize);
- if (!shift(&p, nextstate->reduce_sym,
- indents, start_of_line,
- res, states)) {
- if (prod != 0) abort();
- accepted = 1;
- ret = res;
- }
- parser_trace_action(trace, "Reduce");
- continue;
- }
- if (tk->num == TK_out) {
- // Indent problem - synthesise tokens to get us
- // out of here.
- fprintf(stderr, "Synthesize %d to handle indent problem\n", states[tos->state].shift_sym);
- shift(&p, states[tos->state].shift_sym,
- 0, 1, tok_copy(*tk), states);
- // FIXME need to report this error somehow
- parser_trace_action(trace, "Synthesize");
- continue;
- }
- /* Error. We walk up the stack until we
- * find a state which will accept TK_error.
- * We then shift in TK_error and see what state
- * that takes us too.
- * Then we discard input tokens until
- * we find one that is acceptable.
- */
- parser_trace_action(trace, "ERROR");
- short indents = 0, start_of_line;
-
- err_tk = tok_copy(*tk);
- while (shift(&p, TK_error, 0, 0,
- err_tk, states) == 0
- && p.tos > 0)
- // discard this state
- indents += pop(&p, 1, &start_of_line, do_free);
- if (p.tos == 0) {
- free(err_tk);
- // no state accepted TK_error
- break;
- }
- tos = &p.stack[p.tos-1];
- while (search(&states[tos->state], tk->num) < 0 &&
- tk->num != TK_eof) {
- free(tk);
- tk = tok_copy(token_next(tokens));
- if (tk->num == TK_in)
- indents += 1;
- if (tk->num == TK_out) {
- if (indents == 0)
- break;
- indents -= 1;
- // FIXME update since_indent here
- }
- }
- if (p.tos == 0 && tk->num == TK_eof)
- break;
- tos = &p.stack[p.tos-1];
- tos->indents += indents;
- }
+ ## parser vars
+
+ ## find eol
+
+ ## heart of parser
+
free(tk);
- pop(&p, p.tos, NULL, do_free);
+ pop(&p, p.tos, do_free);
free(p.asn_stack);
free(p.stack);
return ret;
###### exported functions
void *parser_run(struct token_state *tokens,
const struct state states[],
+ const struct reduction reductions[],
int (*do_reduce)(int, void**, struct token_config*, void*),
void (*do_free)(short, void*),
FILE *trace, const char *non_term[],
[TK_newline] = "NEWLINE",
[TK_eof] = "$eof",
};
- static void parser_trace_state(FILE *trace, struct frame *f, const struct state states[])
- {
- fprintf(trace, "(%d", f->state);
- if (states[f->state].starts_line)
- fprintf(trace, "s");
- if (f->newline_permitted)
- fprintf(trace, "n%d", f->since_newline);
- fprintf(trace, ") ");
- }
void parser_trace(FILE *trace, struct parser *p,
struct token *tk, const struct state states[],
} else
fputs(non_term[sym - TK_reserved - knowns],
trace);
- if (f->indents)
- fprintf(trace, ".%d", f->indents);
- if (f->since_newline == 0)
- fputs("/", trace);
fputs(" ", trace);
}
- parser_trace_state(trace, f, states);
+ fprintf(trace, "(%d) ", f->state);
}
fprintf(trace, "[");
if (tk->num < TK_reserved &&
fputs(reserved_words[tk->num], trace);
else
text_dump(trace, tk->txt, 20);
- fputs("]", trace);
+ fprintf(trace, ":%d:%d]", tk->line, tk->col);
}
void parser_trace_action(FILE *trace, char *action)
The obvious example for a parser is a calculator.
-As `scanner` provides number parsing function using `libgmp` is it not much
+As `scanner` provides number parsing function using `libgmp` it is not much
work to perform arbitrary rational number calculations.
-This calculator takes one expression, or an equality test per line. The
-results are printed and if any equality test fails, the program exits with
-an error.
+This calculator takes one expression, or an equality test, per line.
+The results are printed and if any equality test fails, the program
+exits with an error.
###### File: parsergen.mk
calc.c calc.h : parsergen parsergen.mdc
./parsergen --tag calc -o calc parsergen.mdc
calc : calc.o libparser.o libscanner.o libmdcode.o libnumber.o
$(CC) $(CFLAGS) -o calc calc.o libparser.o libscanner.o libmdcode.o libnumber.o -licuuc -lgmp
+ calctest : calc
+ ./calc parsergen.mdc
+ demos :: calctest
# calc: header
- #include "number.h"
+ #include "parse_number.h"
// what do we use for a demo-grammar? A calculator of course.
struct number {
mpq_t val;
#include <stdio.h>
#include <malloc.h>
#include <gmp.h>
+ #include <string.h>
#include "mdcode.h"
#include "scanner.h"
- #include "number.h"
#include "parser.h"
#include "calc.h"
free(n);
}
+ static int text_is(struct text t, char *s)
+ {
+ return (strlen(s) == t.len &&
+ strncmp(s, t.txt, t.len) == 0);
+ }
+
int main(int argc, char *argv[])
{
int fd = open(argv[1], O_RDONLY);
int len = lseek(fd, 0, 2);
char *file = mmap(NULL, len, PROT_READ, MAP_SHARED, fd, 0);
- struct section *s = code_extract(file, file+len, NULL);
+ struct section *table = code_extract(file, file+len, NULL);
+ struct section *s;
struct token_config config = {
.ignored = (1 << TK_line_comment)
- | (1 << TK_block_comment)
| (1 << TK_in)
| (1 << TK_out),
.number_chars = ".,_+-",
.word_start = "",
.word_cont = "",
};
- parse_calc(s->code, &config, argc > 2 ? stderr : NULL);
- while (s) {
- struct section *t = s->next;
- code_free(s->code);
- free(s);
- s = t;
+ for (s = table; s; s = s->next)
+ if (text_is(s->section, "example: input"))
+ parse_calc(s->code, &config, argc > 2 ? stderr : NULL);
+ while (table) {
+ struct section *t = table->next;
+ code_free(table->code);
+ free(table);
+ table = t;
}
exit(0);
}
# calc: grammar
+ $LEFT + -
+ $LEFT * / //
+
Session -> Session Line
| Line
| ERROR NEWLINE ${ printf("Skipped a bad line\n"); }$
$number
- Expression -> Expression + Term ${ mpq_init($0.val); mpq_add($0.val, $1.val, $3.val); }$
- | Expression - Term ${ mpq_init($0.val); mpq_sub($0.val, $1.val, $3.val); }$
- | Term ${ mpq_init($0.val); mpq_set($0.val, $1.val); }$
+ Expression -> Expression + Expression ${ mpq_init($0.val); mpq_add($0.val, $1.val, $3.val); }$
+ | Expression - Expression ${ mpq_init($0.val); mpq_sub($0.val, $1.val, $3.val); }$
+ | Expression * Expression ${ mpq_init($0.val); mpq_mul($0.val, $1.val, $3.val); }$
+ | Expression / Expression ${ mpq_init($0.val); mpq_div($0.val, $1.val, $3.val); }$
+ | Expression // Expression ${ {
+ mpz_t z0, z1, z2;
+ mpq_init($0.val);
+ mpz_init(z0); mpz_init(z1); mpz_init(z2);
+ mpz_tdiv_q(z1, mpq_numref($1.val), mpq_denref($1.val));
+ mpz_tdiv_q(z2, mpq_numref($3.val), mpq_denref($3.val));
+ mpz_tdiv_q(z0, z1, z2);
+ mpq_set_z($0.val, z0);
+ mpz_clear(z0); mpz_clear(z1); mpz_clear(z2);
+ } }$
+ | NUMBER ${ if (number_parse($0.val, $0.tail, $1.txt) == 0) mpq_init($0.val); }$
+ | ( Expression ) ${ mpq_init($0.val); mpq_set($0.val, $2.val); }$
- Term -> Term * Factor ${ mpq_init($0.val); mpq_mul($0.val, $1.val, $3.val); }$
- | Term / Factor ${ mpq_init($0.val); mpq_div($0.val, $1.val, $3.val); }$
- | Factor ${ mpq_init($0.val); mpq_set($0.val, $1.val); }$
+# example: input
- Factor -> NUMBER ${ if (number_parse($0.val, $0.tail, $1.txt) == 0) mpq_init($0.val); }$
- | ( Expression ) ${ mpq_init($0.val); mpq_set($0.val, $2.val); }$
+ 355/113
+ 3.1415926535 - 355/113
+ 2 + 4 * 5
+ 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9
+ 10 * 9 / 2
+ 1 * 1000 + 2 * 100 + 3 * 10 + 4 * 1
+
+ 355//113
+
+ error
code / ocean / blobdiff