5. `parser_run` is a library function intended to be linked together
with the generated parser tables to complete the implementation of
a parser.
-6. `calc.cgm` is a test grammar for a simple calculator.
+6. Finally `calc` is a test grammar for a simple calculator. The
+ `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>
## parser includes
## parser functions
## parser_run
-###### File: calc.cgm
- ## demo grammar
###### File: parsergen.mk
CFLAGS += -Wall -g
all :: parsergen calc
- parsergen.c parsergen.mk calc.cgm libparser.c parser.h : parsergen.mdc
+ parsergen.c parsergen.mk libparser.c parser.h : parsergen.mdc
./md2c parsergen.mdc
## Reading the grammar
literally copied into the generated `.c` and `.h`. files. The last
contains the grammar. This is tokenised with "[scanner][]".
+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`.
+
[mdcode]: mdcode.html
[scanner]: scanner.html
_ad hoc_ parsing as we don't have a parser generator yet.
The precedence and associativity can be set for each production, but
-can be inherited from symbols. The data type is potentially defined
-for each non-terminal and describes what C structure is used to store
-information about each symbol.
+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
+symbol.
###### declarations
enum assoc {Left, Right, Non};
struct symbol {
struct text struct_name;
+ int isref;
enum assoc assoc;
unsigned short precedence;
## symbol fields
`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.
+
###### functions
static int text_is(struct text t, char *s)
{
printf("%.*s", t.len, t.txt);
}
+ static int strip_tag(struct text *t, char *tag)
+ {
+ int skip = strlen(tag) + 1;
+ if (skip >= t->len ||
+ strncmp(t->txt, tag, skip-1) != 0 ||
+ t->txt[skip-1] != ':')
+ return 0;
+ while (skip < t->len && t->txt[skip] == ' ')
+ skip++;
+ t->len -= skip;
+ t->txt += skip;
+ return 1;
+ }
+
### Symbols
Productions are comprised primarily of symbols - terminal and
int num_syms;
###### functions
- static int text_cmp(struct text a, struct text b)
- {
- int len = a.len;
- if (a.len > b.len)
- len = b.len;
- int cmp = strncmp(a.txt, b.txt, len);
- if (cmp)
- return cmp;
- else
- return a.len - b.len;
- }
-
static struct symbol *sym_find(struct grammar *g, struct text s)
{
struct symbol **l = &g->syms;
precedence, otherwise it specifies a data type.
The data type name is simply stored and applied to the head of all
-subsequent productions. It must be the name of a structure, so `$expr`
-maps to `struct expr`.
-
-Any productions given before the first data type will have no data type
-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 non-terminals.
+subsequent productions. It must be the name of a structure optionally
+preceded by an asterisk which means a reference or "pointer". So
+`$expression` maps to `struct expression` and `$*statement` maps to
+`struct statement *`.
+
+Any productions given before the first data type declaration will have
+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
+non-terminals.
The precedence line must contain a list of symbols - typically
terminal symbols, but not necessarily. It can only contain symbols
###### grammar fields
struct text current_type;
+ int type_isref;
int prec_levels;
###### declarations
static const char *known[] = { "$$", "${", "}$" };
###### functions
- static char *dollar_line(struct token_state *ts, struct grammar *g)
+ static char *dollar_line(struct token_state *ts, struct grammar *g, int isref)
{
struct token t = token_next(ts);
char *err;
assoc = Non;
else {
g->current_type = t.txt;
+ g->type_isref = isref;
if (text_is(t.txt, "void"))
g->current_type.txt = NULL;
t = token_next(ts);
return NULL;
}
+ if (isref) {
+ err = "$* cannot be followed by a precedence";
+ goto abort;
+ }
+
// This is a precedence line, need some symbols.
found = 0;
g->prec_levels += 1;
be in one `code_node` of the literate code. The `}$` must be
at the end of a line.
-Text in the code fragment will undergo substitutions where `$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.
+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.
While building productions we will need to add to an array which needs to
grow dynamically.
struct production *p = calloc(1,sizeof(*p));
struct text start = {"$start",6};
struct text eof = {"$eof",4};
+ struct text code = {"$0 = $<1;", 9};
p->head = sym_find(g, start);
p->head->type = Nonterminal;
+ p->head->struct_name = g->current_type;
+ p->head->isref = g->type_isref;
+ if (g->current_type.txt)
+ p->code = code;
array_add(&p->body, &p->body_size, head);
array_add(&p->body, &p->body_size, sym_find(g, eof));
- g->start = p->head->num;
p->head->first_production = g->production_count;
array_add(&g->productions, &g->production_count, p);
Now we are ready to read in the grammar.
-###### grammar fields
- int start; // the 'start' symbol.
-
###### grammar_read
static struct grammar *grammar_read(struct code_node *code)
{
};
struct token_state *state = token_open(code, &conf);
- struct token tk = token_next(state);
+ struct token tk;
struct symbol *head = NULL;
struct grammar *g;
char *err = NULL;
else {
head->type = Nonterminal;
head->struct_name = g->current_type;
- if (g->start == 0) {
+ head->isref = g->type_isref;
+ if (g->production_count == 0) {
## create production zero
}
head->first_production = g->production_count;
err = "First production must have a head";
} else if (tk.num == TK_mark
&& text_is(tk.txt, "$")) {
- err = dollar_line(state, g);
+ err = dollar_line(state, g, 0);
+ } else if (tk.num == TK_mark
+ && text_is(tk.txt, "$*")) {
+ err = dollar_line(state, g, 1);
} else {
err = "Unrecognised token at start of line.";
}
}
}
-### Setting `can_eol`
+### 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 section.
+line-like symbol.
-To know what is line-like, we first need to know which symbols can end
-a line-like section, which is precisely those which can end with a
-newline token. These symbols don't necessarily alway end with a
-newline, but they can. Hence they are not described as "lines" but
-only "line-like".
+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 end with a newline. Any symbol
-which is the head of a production that contains a line-ending symbol
-followed only by nullable symbols is also a line-ending 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`.
+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)
if (pr->head->can_eol)
continue;
- for (s = pr->body_size - 1; s >= 0; s--) {
+ for (s = 0 ; s < pr->body_size; s++) {
if (pr->body[s]->can_eol) {
pr->head->can_eol = 1;
check_again = 1;
}
}
+ 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 an subsequent non-terminal might be. So
+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.
struct symset items;
struct symset go_to;
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 add symbol that weren't in the old LA set, we
+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.
#### The build
-To build all the itemsets, we first insert the initial itemset made from the
-start symbol, 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
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.
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 (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;
sn = save_set(g, LA);
LA = set_find(g, sn);
}
+
/* Add productions for this symbol */
for (p2 = s->first_production;
p2 < g->production_count &&
###### derive itemsets
// Now we have a completed itemset, so we need to
- // create all the 'next' itemset and create them
+ // compute all the 'next' itemsets and create them
// if they don't exist.
for (i = 0; i < done.cnt; i++) {
int j;
unsigned short state;
+ struct symbol *sym = g->symtab[done.syms[i]];
struct symset newitemset = INIT_SYMSET;
if (type >= LALR)
newitemset = INIT_DATASET;
if (bp == pr->body_size)
continue;
- if (pr->body[bp]->num != done.syms[i])
+ if (pr->body[bp] != sym)
continue;
if (type >= LALR)
la = is->items.data[j];
set_nullable(g);
set_can_eol(g);
+ set_line_like(g);
if (type >= SLR)
build_first(g);
The purpose of the report is to give the grammar developer insight into
how the grammar parser will work. It is basically a structured dump of
-all the tables that have been generated, plus an description of any conflicts.
+all the tables that have been generated, plus a description of any conflicts.
###### grammar_report
static int grammar_report(struct grammar *g, enum grammar_type type)
return report_conflicts(g, type);
}
-Firstly we have the complete list of symbols, together with the "FIRST"
-set if that was generated.
+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 implies the start of a
+line (`<`), or if it is nullable (`.`).
###### functions
if (!s)
continue;
- printf(" %c%c%3d%c: ",
+ printf(" %c%c%c%3d%c: ",
s->nullable ? '.':' ',
s->can_eol ? '>':' ',
+ s->line_like ? '<':' ',
s->num, symtypes[s->type]);
prtxt(s->name);
if (s->precedence)
}
}
-Then we have to follow sets if they were computed.
+Then we have the follow sets if they were computed.
static void report_follow(struct grammar *g)
{
for (s = 0; s < g->states; s++) {
int j;
struct itemset *is = g->statetab[s];
- printf(" Itemset %d:\n", s);
+ printf(" Itemset %d:%s min prefix=%d\n",
+ s, is->starts_line?" (startsline)":"", is->min_prefix);
for (j = 0; j < is->items.cnt; j++) {
report_item(g, is->items.syms[j]);
if (is->items.data != NO_DATA)
}
LR0 conflicts are any state which have both a reducible item and
-a shiftable item.
+a shiftable item, or two reducible items.
LR05 conflicts only occurs if two possibly reductions exist,
as shifts always over-ride reductions.
}
SLR, LALR, and LR1 conflicts happen if two reducible items have over-lapping
-look ahead, or if a symbol in a look-ahead can be shifted. The differ only
+look ahead, or if a symbol in a look-ahead can be shifted. They differ only
in the source of the look ahead set.
-We build a dataset mapping terminal to item for possible SHIFTs and then
-another for possible REDUCE operations. We report when we get conflicts
-between the two.
+We build two datasets to reflect the "action" table: one which maps
+terminals to items where that terminal could be shifted and another
+which maps terminals to items that could be reduced when the terminal
+is in look-ahead. We report when we get conflicts between the two.
static int conflicts_slr(struct grammar *g, enum grammar_type type)
{
## Generating the parser
-The export part of the parser is the `parse_XX` function, where the name
+The exported part of the parser is the `parse_XX` function, where the name
`XX` is based on the name of the parser files.
This takes a `code_node`, a partially initialized `token_config`, and an
known words added and then is used with the `code_node` to initialize the
scanner.
-`parse_XX` then call the library function `parser_run` to actually complete
+`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.
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->known_count);\n");
+ fprintf(f, "\tvoid *rv = parser_run(tokens, states, do_reduce, do_free, trace, non_term, config);\n");
fprintf(f, "\ttoken_close(tokens);\n");
fprintf(f, "\treturn rv;\n");
fprintf(f, "}\n\n");
}
-### Table words table
+### Known words table
-The know words is simply an array of terminal symbols.
+The known words table is simply an array of terminal symbols.
The table of nonterminals used for tracing is a similar array.
###### functions
short reduce_size;
short reduce_sym;
short shift_sym;
+ short starts_line;
+ short min_prefix;
};
}
if (prod >= 0)
- fprintf(f, "\t[%d] = { %d, goto_%d, %d, %d, %d, 0 },\n",
+ 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);
+ g->productions[prod]->head->num,
+ is->starts_line, is->min_prefix);
else
- fprintf(f, "\t[%d] = { %d, goto_%d, -1, -1, -1, %d },\n",
- i, is->go_to.cnt, i, shift_sym);
+ 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, "};\n\n");
}
`do_reduce` to `malloc` that "somewhere", we pass in a large buffer and have
`do_reduce` return the size to be saved.
+In order for the code to access "global" context, we pass in the
+"config" pointer that was passed to 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 pointer need to be cast
+structure returned by a previous reduction. These pointers need to be cast
to the appropriate type for each access. All this is handling 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.
###### functions
static void gen_code(struct production *p, FILE *f, struct grammar *g)
{
char *c;
+ char *used = calloc(1, p->body_size);
+ int i;
+
fprintf(f, "\t\t\t");
for (c = p->code.txt; c < p->code.txt + p->code.len; c++) {
int n;
+ int use = 0;
if (*c != '$') {
fputc(*c, f);
if (*c == '\n')
continue;
}
c++;
+ if (*c == '<') {
+ use = 1;
+ c++;
+ }
if (*c < '0' || *c > '9') {
+ if (use)
+ fputc('<', f);
fputc(*c, f);
continue;
}
n = n * 10 + *c - '0';
}
if (n == 0)
- fprintf(f, "(*(struct %.*s*)ret)",
+ fprintf(f, "(*(struct %.*s*%s)ret)",
p->head->struct_name.len,
- p->head->struct_name.txt);
+ 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)
n-1);
else if (p->body[n-1]->struct_name.txt == NULL)
fprintf(f, "$%d", n);
- else
- fprintf(f, "(*(struct %.*s*)body[%d])",
+ else {
+ fprintf(f, "(*(struct %.*s*%s)body[%d])",
p->body[n-1]->struct_name.len,
- p->body[n-1]->struct_name.txt, n-1);
+ p->body[n-1]->struct_name.txt,
+ p->body[n-1]->isref ? "*":"", n-1);
+ used[n-1] = use;
+ }
}
fputs("\n", f);
+ for (i = 0; i < p->body_size; i++) {
+ if (p->body[i]->struct_name.txt &&
+ p->body[i]->isref &&
+ used[i])
+ // assume this has been copied out
+ fprintf(f, "\t\t*(void**)body[%d] = NULL;\n", i);
+ }
+ free(used);
}
###### functions
{
int i;
fprintf(f, "#line 0 \"gen_reduce\"\n");
- fprintf(f, "static int do_reduce(int prod, void **body, void *ret)\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");
gen_code(p, f, g);
if (p->head->struct_name.txt)
- fprintf(f, "\t\tret_size = sizeof(struct %.*s);\n",
+ fprintf(f, "\t\tret_size = sizeof(struct %.*s%s);\n",
p->head->struct_name.len,
- p->head->struct_name.txt);
+ p->head->struct_name.txt,
+ p->head->isref ? "*":"");
fprintf(f, "\t\tbreak;\n");
}
It is particularly important to have fine control over freeing during error
recovery where individual stack frames might need to be freed.
-For this, the grammar author required to defined a `free_XX` function for
-each structure that is used by a non-terminal. `do_free` all call whichever
+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
continue;
fprintf(f, "\tcase %d:\n", s->num);
- fprintf(f, "\t\tfree_%.*s(asn);\n",
- s->struct_name.len,
- s->struct_name.txt);
+ if (s->isref) {
+ fprintf(f, "\t\tfree_%.*s(*(void**)asn);\n",
+ s->struct_name.len,
+ s->struct_name.txt);
+ fprintf(f, "\t\tfree(asn);\n");
+ } else
+ fprintf(f, "\t\tfree_%.*s(asn);\n",
+ s->struct_name.len,
+ s->struct_name.txt);
fprintf(f, "\t\tbreak;\n");
}
fprintf(f, "\t}\n}\n\n");
{ "SLR", 0, NULL, 'S' },
{ "LALR", 0, NULL, 'L' },
{ "LR1", 0, NULL, '1' },
+ { "tag", 1, NULL, 't' },
{ "report", 0, NULL, 'R' },
{ "output", 1, NULL, 'o' },
{ NULL, 0, NULL, 0 }
};
- const char *options = "05SL1Ro:";
+ const char *options = "05SL1t:Ro:";
###### process arguments
int opt;
char *outfile = NULL;
char *infile;
char *name;
+ char *tag = NULL;
int report = 1;
enum grammar_type type = LR05;
while ((opt = getopt_long(argc, argv, options,
report = 2; break;
case 'o':
outfile = optarg; break;
+ case 't':
+ tag = optarg; break;
default:
fprintf(stderr, "Usage: parsergen ...\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 file three
-sections: header, code, and grammar. Anything else is an error.
+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.
"header" and "code" are optional, though it is hard to build a working
parser with neither. "grammar" must be provided.
struct code_node *code = NULL;
struct code_node *gram = NULL;
for (s = table; s; s = s->next) {
- if (text_is(s->section, "header"))
+ struct text sec = s->section;
+ if (tag && !strip_tag(&sec, tag))
+ continue;
+ if (text_is(sec, "header"))
hdr = s->code;
- else if (text_is(s->section, "code"))
+ else if (text_is(sec, "code"))
code = s->code;
- else if (text_is(s->section, "grammar"))
+ else if (text_is(sec, "grammar"))
gram = s->code;
else {
fprintf(stderr, "Unknown content section: %.*s\n",
}
And that about wraps it up. We need to set the locale so that UTF-8 is
-recognised properly, and link with `libicuuc` is `libmdcode` requires that.
+recognised properly, and link with `libicuuc` as `libmdcode` requires that.
###### File: parsergen.mk
parsergen : parsergen.o libscanner.o libmdcode.o
## The SHIFT/REDUCE parser
-Having analysed the grammar and generated all the table, we only need the
+Having analysed the grammar and generated all the tables, we only need the
shift/reduce engine to bring it all together.
### Goto table lookup
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 four.
+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`.
-The `indents` count and the `starts_indented` flag track the line
-indents in the symbol. These are used to allow indent information to
-guide parsing and error recovery.
+The `indents` count tracks the line indents in the symbol. These are
+used to allow indent information to guide parsing and error recovery.
+
+`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.
-As well as the stack of frames we have a `next` frame which is
-assembled from the incoming token and other information prior to
-pushing it onto the stack.
+`newline_permitted` keeps track of whether newlines should be ignored
+or not, and `starts_line` records if this state stated on a newline.
+
+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.
###### parser functions
struct parser {
struct frame {
short state;
+ short newline_permitted;
+
short sym;
- short starts_indented;
short indents;
- } *stack, next;
+ short since_newline;
+ short since_indent;
+ } *stack;
void **asn_stack;
int stack_size;
int tos;
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.
+function for both. In both cases we provide a stack frame which
+contains the symbol to shift and related indent information.
To simplify other code we arrange for `shift` to fail if there is no `goto`
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.
+`shift` is also used to push state zero onto the stack, so if the
+stack is empty, it always chooses zero as the next state.
+
So `shift` finds the next state. If that succeed it extends the allocations
-if needed and pushed all the information onto the stacks.
+if needed and pushes all the information onto the stacks.
+
+Newlines are permitted after a starts_line state until an internal
+indent. So we need to find the topmost state which `starts_line` and
+see if there are any indents other than immediately after it.
+
+So we walk down:
+
+- if state starts_line, then newlines_permitted.
+- if any non-initial indents, newlines not permitted
###### parser functions
static int shift(struct parser *p,
+ short sym, short indents, short start_of_line,
void *asn,
const struct state states[])
{
// Push an entry onto the stack
- int newstate = search(&states[p->next.state], p->next.sym);
+ struct frame next = {0};
+ int newstate = p->tos
+ ? search(&states[p->stack[p->tos-1].state],
+ sym)
+ : 0;
if (newstate < 0)
return 0;
if (p->tos >= p->stack_size) {
p->asn_stack = realloc(p->asn_stack, p->stack_size
* sizeof(p->asn_stack[0]));
}
- p->stack[p->tos] = p->next;
+ 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;
p->tos++;
- p->next.state = newstate;
- p->next.indents = 0;
- p->next.starts_indented = 0;
return 1;
}
-`pop` simply moves the top of stack (`tos`) back down the required 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.
+`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 in the symbols that are being
+removed. It is called _after_ we reduce a production, just before we
+`shift` the nonterminal in.
+
+`pop` is only called if there are entries to remove, so `num` is never zero.
###### parser functions
- static void pop(struct parser *p, int num,
- void(*do_free)(short sym, void *asn))
+ static int pop(struct parser *p, int num,
+ short *start_of_line,
+ void(*do_free)(short sym, void *asn))
{
int i;
+ short indents;
p->tos -= num;
+ if (start_of_line)
+ *start_of_line =
+ !p->stack[p->tos].since_newline;
+ indents = 0;
for (i = 0; i < num; i++) {
- p->next.indents += p->stack[p->tos+i].indents;
+ indents += p->stack[p->tos+i].indents;
do_free(p->stack[p->tos+i].sym,
p->asn_stack[p->tos+i]);
}
-
- if (num) {
- p->next.state = p->stack[p->tos].state;
- p->next.starts_indented = p->stack[p->tos].starts_indented;
- }
+ return indents;
}
### Memory allocation
### The heart of the parser.
-Now we have the parser. If we can shift, we do. If not and we can reduce
-we do. If the production we reduced was production zero, then we have
+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.
+If the production we reduced was production zero, then we have
accepted the input and can finish.
We return whatever `asn` was returned by reducing production zero.
or must force reductions until there is a pending indent which isn't
at the start of a production.
+`TK_newline` tokens are ignored precisely if there has been an indent
+since the last state which could have been at the start of a line.
+
###### parser includes
#include "parser.h"
###### parser_run
void *parser_run(struct token_state *tokens,
const struct state states[],
- int (*do_reduce)(int, void**, void*),
+ int (*do_reduce)(int, void**, struct token_config*, void*),
void (*do_free)(short, void*),
- FILE *trace, const char *non_term[], int knowns)
+ FILE *trace, const char *non_term[],
+ struct token_config *config)
{
struct parser p = { 0 };
+ struct frame next = { 0 };
struct token *tk = NULL;
int accepted = 0;
- void *ret;
+ 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));
- p.next.sym = tk->num;
- if (trace)
- parser_trace(trace, &p, tk, states, non_term, knowns);
-
- if (p.next.sym == TK_in) {
- p.next.starts_indented = 1;
- p.next.indents = 1;
+ next.sym = tk->num;
+ parser_trace(trace, &p, next.indents, !next.since_newline,
+ tk, states, non_term, config->known_count);
+
+ if (next.sym == 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 (p.next.sym == TK_out) {
- if (p.stack[p.tos-1].indents > p.stack[p.tos-1].starts_indented ||
- (p.stack[p.tos-1].indents == 1 &&
- states[p.next.state].reduce_size > 1)) {
- p.stack[p.tos-1].indents -= 1;
+ if (next.sym == 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 = 0;
+ 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 (shift(&p, tk, states)) {
+ if (next.sym == TK_newline) {
+ if (!tos->newline_permitted) {
+ free(tk);
+ tk = NULL;
+ parser_trace_action(trace, "Discard");
+ continue;
+ }
+ if (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)) {
+ next.since_newline = !(tk->num == TK_newline);
+ next.indents = 0;
tk = NULL;
+ parser_trace_action(trace, "Shift");
continue;
}
- if (states[p.next.state].reduce_prod >= 0) {
+ force_reduce:
+ if (states[tos->state].reduce_prod >= 0) {
void **body;
- int prod = states[p.next.state].reduce_prod;
- int size = states[p.next.state].reduce_size;
+ 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];
- p.next.sym = states[p.next.state].reduce_sym;
+ short indents, start_of_line;
- body = p.asn_stack +
- (p.tos - states[p.next.state].reduce_size);
+ body = p.asn_stack + (p.tos - size);
- bufsize = do_reduce(prod, body, buf);
+ bufsize = do_reduce(prod, body, config, buf);
- pop(&p, size, do_free);
- shift(&p, memdup(buf, bufsize), states);
- if (prod == 0)
+ if (size)
+ indents = pop(&p, size, &start_of_line,
+ do_free);
+ else {
+ indents = next.indents;
+ start_of_line = 0;
+ next.indents = 0;
+ }
+ 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[p.next.state].shift_sym);
- p.next.sym = states[p.next.state].shift_sym;
- shift(&p, tok_copy(*tk), states);
+ 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
* 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);
- p.next.sym = TK_error;
- while (shift(&p, err_tk, states) == 0
+ next.sym = TK_error;
+ while (shift(&p, TK_error, next.indents, !next.since_newline,
+ err_tk, states) == 0
&& p.tos > 0)
// discard this state
- pop(&p, 1, do_free);
+ indents += pop(&p, 1, &start_of_line, do_free);
if (p.tos == 0) {
free(err_tk);
// no state accepted TK_error
break;
}
- while (search(&states[p.next.state], tk->num) < 0 &&
+ 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)
- p.next.indents += 1;
+ indents += 1;
if (tk->num == TK_out) {
- if (p.next.indents == 0)
+ if (indents == 0)
break;
- p.next.indents -= 1;
+ 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;
}
free(tk);
- if (accepted)
- ret = p.asn_stack[0];
- else
- pop(&p, p.tos, do_free);
+ if (p.tos)
+ pop(&p, p.tos, NULL, do_free);
free(p.asn_stack);
free(p.stack);
return ret;
###### exported functions
void *parser_run(struct token_state *tokens,
const struct state states[],
- int (*do_reduce)(int, void**, void*),
+ int (*do_reduce)(int, void**, struct token_config*, void*),
void (*do_free)(short, void*),
- FILE *trace, const char *non_term[], int knowns);
+ FILE *trace, const char *non_term[],
+ struct token_config *config);
### Tracing
[TK_newline] = "NEWLINE",
[TK_eof] = "$eof",
};
- void parser_trace(FILE *trace, struct parser *p,
+ 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->newline_permitted);
+ fprintf(trace, ") ");
+ }
+
+ void parser_trace(FILE *trace, struct parser *p, int indents, int start_of_line,
struct token *tk, const struct state states[],
const char *non_term[], int knowns)
{
int i;
+ if (!trace)
+ return;
for (i = 0; i < p->tos; i++) {
- int sym = p->stack[i].sym;
- fprintf(trace, "(%d) ", p->stack[i].state);
- if (sym < TK_reserved &&
- reserved_words[sym] != NULL)
- fputs(reserved_words[sym], trace);
- else if (sym < TK_reserved + knowns) {
- struct token *t = p->asn_stack[i];
- text_dump(trace, t->txt, 20);
- } else
- fputs(non_term[sym - TK_reserved - knowns],
- trace);
- fputs(" ", trace);
+ struct frame *f = &p->stack[i];
+ if (i) {
+ int sym = f->sym;
+ if (sym < TK_reserved &&
+ reserved_words[sym] != NULL)
+ fputs(reserved_words[sym], trace);
+ else if (sym < TK_reserved + knowns) {
+ struct token *t = p->asn_stack[i];
+ text_dump(trace, t->txt, 20);
+ } 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) [", p->next.state);
+ fprintf(trace, "[");
if (tk->num < TK_reserved &&
reserved_words[tk->num] != NULL)
fputs(reserved_words[tk->num], trace);
else
text_dump(trace, tk->txt, 20);
- fputs("]\n", trace);
+ if (indents)
+ fprintf(trace, ".%d", indents);
+ if (start_of_line)
+ fputs("/", trace);
+ fputs("]", trace);
+ }
+
+ void parser_trace_action(FILE *trace, char *action)
+ {
+ if (trace)
+ fprintf(trace, " - %s\n", action);
}
# A Worked Example
work to perform arbitrary rational number calculations.
This calculator takes one expression, or an equality test per line. The
-results are printed and in any equality test fails, the program exits with
+results are printed and if any equality test fails, the program exits with
an error.
-Embedding mdcode inside mdcode is rather horrible. I'd like to find a
-better approach, but as the grammar file must have 3 components I need
-something like this.
-
###### File: parsergen.mk
- calc.c : parsergen calc.cgm
- ./parsergen -o calc calc.cgm
+ 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
-###### demo grammar
-
- # header
- ~~~~~
+# calc: header
#include "number.h"
// what do we use for a demo-grammar? A calculator of course.
int err;
};
- ~~~~~
- # code
- ~~~~~
+# calc: code
#include <stdlib.h>
#include <unistd.h>
.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;
+ }
exit(0);
}
- ~~~~~
- # grammar
- ~~~~~
+# calc: grammar
Session -> Session Line
| Line
code / ocean / blobdiff