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;
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));
p->head->first_production = g->production_count;
}
}
-### Setting `can_eol`
+### Setting `can_eol` and `starts_line`
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
###### symbol fields
int can_eol;
+ int starts_line;
###### functions
static void set_can_eol(struct grammar *g)
}
}
+ static void set_starts_line(struct grammar *g)
+ {
+ int p;
+ for (p = 0; p < g->production_count; p++) {
+ struct production *pr = g->productions[p];
+ int s;
+
+ for (s = 0; s < pr->body_size - 1; s++)
+ if (pr->body[s]->can_eol)
+ pr->body[s+1]->starts_line = 1;
+ }
+ }
+
### Building the `first` sets
When calculating what can follow a particular non-terminal, we will need to
}
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.
them to a data structure, of freeing them.
static int add_itemset(struct grammar *g, struct symset ss,
- enum grammar_type type, int starts_line)
+ enum grammar_type type)
{
struct itemset **where, *is;
int i;
is->items = ss;
is->next = *where;
is->go_to = INIT_DATASET;
- is->starts_line = starts_line;
*where = is;
return is->state;
}
#### 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.
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->starts_line)
+ is->starts_line = 1;
+ }
if (s->type != Nonterminal)
continue;
again = 1;
for (i = 0; i < done.cnt; i++) {
int j;
unsigned short state;
- int starts_line = 0;
struct symbol *sym = g->symtab[done.syms[i]];
struct symset newitemset = INIT_SYMSET;
if (type >= LALR)
newitemset = INIT_DATASET;
- if (sym->can_eol ||
- (sym->nullable && is->starts_line))
- starts_line = 1;
for (j = 0; j < is->items.cnt; j++) {
int itm = is->items.syms[j];
int p = item_prod(itm);
}
}
}
- state = add_itemset(g, newitemset, type, starts_line);
+ state = add_itemset(g, newitemset, type);
if (symset_find(&is->go_to, done.syms[i]) < 0)
symset_add(&is->go_to, done.syms[i], state);
}
}
// production 0, offset 0 (with no data)
symset_add(&first, item_num(0, 0), la);
- add_itemset(g, first, type, g->productions[0]->body[0]->can_eol);
+ add_itemset(g, first, type);
for (again = 0, is = g->items;
is;
is = is->next ?: again ? (again = 0, g->items) : NULL) {
set_nullable(g);
set_can_eol(g);
+ set_starts_line(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->starts_line ? '<':' ',
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)
{
}
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
`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-1);
else if (p->body[n-1]->struct_name.txt == NULL)
fprintf(f, "$%d", n);
- else
+ else {
fprintf(f, "(*(struct %.*s*%s)body[%d])",
p->body[n-1]->struct_name.len,
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");
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);
- if (s->isref)
+ if (s->isref) {
fprintf(f, "\t\tfree_%.*s(*(void**)asn);\n",
s->struct_name.len,
s->struct_name.txt);
- else
+ fprintf(f, "\t\tfree(asn);\n");
+ } else
fprintf(f, "\t\tfree_%.*s(asn);\n",
s->struct_name.len,
s->struct_name.txt);
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.
}
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
indents in the symbol. These are used to allow indent information to
guide parsing and error recovery.
-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.
+`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.
+
+`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;
- short newline_permitted;
- } *stack, next;
+ short starts_newline;
+ } *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 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,
+ static int shift(struct parser *p, struct frame *next,
void *asn,
const struct state states[])
{
// Push an entry onto the stack
- int newstate = search(&states[p->next.state], p->next.sym);
+ int newstate = p->tos
+ ? search(&states[p->stack[p->tos-1].state],
+ next->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->state = newstate;
+ next->newline_permitted = 0;
+ if (p->tos)
+ next->newline_permitted =
+ (p->stack[p->tos-1].newline_permitted?:-1)+1;
+ if (next->indents > next->starts_indented)
+ next->newline_permitted = 0;
+ if (next->indents && next->newline_permitted > 2)
+ next->newline_permitted = 0;
+ if (states[newstate].starts_line)
+ next->newline_permitted = 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;
- // if new state doesn't start a line, we inherit newline_permitted status
- if (states[newstate].starts_line)
- p->next.newline_permitted = 1;
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,
+ static void pop(struct parser *p, int num, struct frame *next,
void(*do_free)(short sym, void *asn))
{
int i;
p->tos -= num;
+ next->starts_indented =
+ p->stack[p->tos].starts_indented;
+ next->starts_newline =
+ p->stack[p->tos].starts_newline;
+ next->indents = 0;
for (i = 0; i < num; i++) {
- p->next.indents += p->stack[p->tos+i].indents;
+ next->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;
- p->next.newline_permitted = p->stack[p->tos].newline_permitted;
- if (p->next.indents > p->next.starts_indented)
- p->next.newline_permitted = 0;
- }
}
### 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;
- p.next.newline_permitted = states[0].starts_line;
+ next.starts_newline = 1;
+ shift(&p, &next, 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);
+ next.sym = tk->num;
+ parser_trace(trace, &p, &next, tk, states, non_term, config->known_count);
- if (p.next.sym == TK_in) {
- p.next.starts_indented = 1;
- p.next.indents = 1;
+ if (next.sym == TK_in) {
+ next.starts_indented = 1;
+ next.indents = 1;
+ next.starts_newline = 1;
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 (p.stack[p.tos-1].indents == p.stack[p.tos-1].starts_indented) {
+ if (next.sym == TK_out) {
+ if (tos->indents > tos->starts_indented ||
+ (tos->indents == 1 &&
+ states[tos->state].reduce_size != 1)) {
+ tos->indents -= 1;
+ if (tos->indents <= tos->starts_indented) {
// no internal indent any more, reassess 'newline_permitted'
- if (states[p.stack[p.tos-1].state].starts_line)
- p.stack[p.tos-1].newline_permitted = 1;
+ if (states[tos->state].starts_line)
+ tos->newline_permitted = 1;
else if (p.tos > 1)
- p.stack[p.tos-1].newline_permitted = p.stack[p.tos-2].newline_permitted;
+ tos->newline_permitted = (p.stack[p.tos-2].newline_permitted ?:-1)+1;
}
free(tk);
tk = NULL;
+ parser_trace_action(trace, "Cancel");
continue;
}
// fall through and force a REDUCE (as 'shift'
// will fail).
}
- if (p.next.sym == TK_newline) {
- if (!p.tos || ! p.stack[p.tos-1].newline_permitted) {
+ if (next.sym == TK_newline) {
+ if (! tos->newline_permitted) {
free(tk);
tk = NULL;
+ parser_trace_action(trace, "Discard");
continue;
}
}
- if (shift(&p, tk, states)) {
+ if (shift(&p, &next, tk, states)) {
+ next.starts_newline =
+ tk->num == TK_newline;
+ next.starts_indented = 0;
+ next.indents = 0;
tk = NULL;
+ parser_trace_action(trace, "Shift");
continue;
}
- if (states[p.next.state].reduce_prod >= 0) {
+ 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;
+ struct frame frame;
+ frame.sym = nextstate->reduce_sym;
- 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)
+ pop(&p, size, &frame, do_free);
+ else {
+ frame.indents = next.indents;
+ frame.starts_indented = frame.indents;
+ frame.starts_newline = 0;
+ next.indents = 0;
+ next.starts_indented = 0;
+ }
+ res = memdup(buf, bufsize);
+ memset(buf, 0, bufsize);
+ if (!shift(&p, &frame, 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);
+ struct frame frame = { 0 };
+ fprintf(stderr, "Synthesize %d to handle indent problem\n", states[tos->state].shift_sym);
+ frame.sym = states[tos->state].shift_sym;
+ shift(&p, &frame, 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");
err_tk = tok_copy(*tk);
- p.next.sym = TK_error;
- while (shift(&p, err_tk, states) == 0
+ next.sym = TK_error;
+ while (shift(&p, &next, err_tk, states) == 0
&& p.tos > 0)
// discard this state
- pop(&p, 1, do_free);
+ pop(&p, 1, &next, 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;
+ next.indents += 1;
if (tk->num == TK_out) {
- if (p.next.indents == 0)
+ if (next.indents == 0)
break;
- p.next.indents -= 1;
+ next.indents -= 1;
}
}
if (p.tos == 0 && tk->num == TK_eof)
break;
}
free(tk);
- if (accepted)
- ret = p.asn_stack[0];
- else
- pop(&p, p.tos, do_free);
+ if (p.tos)
+ pop(&p, p.tos, &next, 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
static void parser_trace_state(FILE *trace, struct frame *f, const struct state states[])
{
fprintf(trace, "(%d", f->state);
- if (f->indents)
- fprintf(trace, "%c%d", f->starts_indented?':':'.',
- f->indents);
if (states[f->state].starts_line)
fprintf(trace, "s");
if (f->newline_permitted)
- fprintf(trace, "n");
+ fprintf(trace, "n%d", f->newline_permitted);
fprintf(trace, ") ");
}
- void parser_trace(FILE *trace, struct parser *p,
+ void parser_trace(FILE *trace, struct parser *p, struct frame *n,
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;
- parser_trace_state(trace, &p->stack[i], states);
- 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, "%c%d", f->starts_indented?':':'.',
+ f->indents);
+ if (f->starts_newline)
+ fputs("/", trace);
+ fputs(" ", trace);
+ }
+ parser_trace_state(trace, f, states);
}
- parser_trace_state(trace, &p->next, states);
- fprintf(trace, " [");
+ 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 (n->indents)
+ fprintf(trace, "%c%d", n->starts_indented?':':'.',
+ n->indents);
+ if (n->starts_newline)
+ 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 calc.h : parsergen parsergen.mdc
./parsergen --tag calc -o calc parsergen.mdc
.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);
}
code / ocean / blobdiff