struct production {
unsigned short precedence;
enum assoc assoc;
- char line_like;
## production fields
};
struct grammar {
goto abort;
}
vs = sym_find(g, tk.txt);
- if (vs->num == TK_newline)
- p.line_like = 1;
- else if (vs->num == TK_out)
- p.line_like = 2;
- else if (vs->precedence == 0) {
+ if (vs->precedence == 0) {
err = "symbol after $$ must have precedence";
goto abort;
} else {
}
}
-### Setting `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.
-
-A "line_like" symbol is simply any symbol that can derive a NEWLINE.
-If a symbol cannot derive a NEWLINE, then it is only part of a line -
-so is word-like. If it can derive a NEWLINE, then we consider it to
-be like a line.
-
-Clearly the `TK_newline` token can derive a NEWLINE. Any symbol which
-is the head of a production that contains a line_like symbol is also a
-line-like symbol. We use a new field `line_like` to record this
-attribute of symbols, and compute it in a repetitive manner similar to
-`set_nullable`.
-
-###### symbol fields
- int line_like;
-
-###### functions
- static void set_line_like(struct grammar *g)
- {
- int check_again = 1;
- g->symtab[TK_newline]->line_like = 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->line_like)
- continue;
-
- for (s = 0 ; s < pr->body_size; s++) {
- if (pr->body[s]->line_like) {
- pr->head->line_like = 1;
- check_again = 1;
- break;
- }
- }
- }
- }
- }
-
### Building the `first` sets
When calculating what can follow a particular non-terminal, we will need
need to be consider for completion again. So a `completed` flag is
needed.
-For correct handling of `TK_newline` when parsing, we will need to
-know which states (itemsets) can occur at the start of a line, so we
-will record a `starts_line` flag too whenever DOT is at the start of a
-`line_like` symbol.
-
-Finally, for handling `TK_out` we need to know whether productions in the
-current state started *before* the most recent indent. A state
-doesn't usually keep details of individual productions, so we need to
-add one extra detail. `min_prefix` is the smallest non-zero number of
-symbols *before* DOT in any production in an itemset. This will allow
-us to determine if the the most recent indent is sufficiently recent
-to cancel it against a `TK_out`. If it was seen longer ago than the
-`min_prefix`, and if the current state cannot be reduced, then the
-indented section must have ended in the middle of a syntactic unit, so
-an error must be signaled.
-
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.
enum assoc assoc;
unsigned short precedence;
char completed;
- char starts_line;
- int min_prefix;
};
###### grammar fields
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
-`line_like`, then this state must be a `starts_line` state so now is a
-good time to record that.
+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
struct symbol *s;
struct symset LA = INIT_SYMSET;
unsigned short sn = 0;
- struct symset LAnl = INIT_SYMSET;
- unsigned short snnl = 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];
* not Right-associative, so we mustn't shift it.
*/
continue;
- if (symset_find(&done, s->num) < 0) {
+ if (symset_find(&done, s->num) < 0)
symset_add(&done, s->num, 0);
- }
+
if (s->type != Nonterminal)
continue;
- if (s->line_like)
- is->starts_line = 1;
check_again = 1;
if (type >= LALR) {
// Need the LA set.
}
sn = save_set(g, LA);
LA = set_find(g, sn);
- if (symset_find(&LA, TK_newline))
- symset_add(&LAnl, TK_newline, 0);
- snnl = save_set(g, LAnl);
- LAnl = set_find(g, snnl);
}
/* Add productions for this symbol */
int itm = item_num(p2, 0);
int pos = symset_find(&is->items, itm);
if (pos < 0) {
- if (g->productions[p2]->line_like)
- symset_add(&is->items, itm, snnl);
- else
- symset_add(&is->items, itm, sn);
+ symset_add(&is->items, itm, sn);
/* Will have re-ordered, so start
* from beginning again */
i = -1;
struct symset tmp = INIT_SYMSET;
struct symset *la = &LA;
- if (g->productions[p2]->line_like)
- la = &LAnl;
symset_union(&tmp, &ss);
if (symset_union(&tmp, la)) {
is->items.data[pos] = save_set(g, tmp);
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 + 1 == pr->body_size &&
+ 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];
g->symtab[s->num] = s;
set_nullable(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 is considered to be "line-like" (`<`), or if it is nullable (`.`).
+show if it is nullable (`.`).
###### functions
if (!s)
continue;
- printf(" %c%c%3d%c: ",
+ printf(" %c%3d%c: ",
s->nullable ? '.':' ',
- s->line_like ? '<':' ',
s->num, symtypes[s->type]);
prtxt(s->name);
if (s->precedence)
printf(" [%d%s]", s->precedence,
assoc_names[s->assoc]);
}
- if (pr->line_like == 1)
- printf(" $$NEWLINE");
- else if (pr->line_like)
- printf(" $$OUT");
printf("\n");
}
for (s = 0; s < g->states; s++) {
int j;
struct itemset *is = g->statetab[s];
- printf(" Itemset %d:%s min prefix=%d",
- 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");
short reduce_prod;
short reduce_size;
short reduce_sym;
- char starts_line;
- char newline_only;
- short min_prefix;
+ short result_size;
};
###### functions
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]);
prod_len = pr->body_size;
}
}
-
- if (prod >= 0)
- fprintf(f, "\t[%d] = { %d, goto_%d, %d, %d, %d, %d, %d, %d },\n",
- i, is->go_to.cnt, i, prod,
- g->productions[prod]->body_size,
- g->productions[prod]->head->num,
- is->starts_line,
- g->productions[prod]->line_like,
- is->min_prefix);
+ if (is->go_to.cnt)
+ fprintf(f, "\t[%d] = { %d, goto_%d, ",
+ i, is->go_to.cnt, i);
else
- fprintf(f, "\t[%d] = { %d, goto_%d, -1, -1, -1, %d, 0, %d },\n",
- i, is->go_to.cnt, i,
- is->starts_line, is->min_prefix);
+ fprintf(f, "\t[%d] = { 0, NULL, ", i);
+ if (prod >= 0) {
+ struct production *pr = g->productions[prod];
+ struct symbol *hd = pr->head;
+ fprintf(f, "%d, %d, %d, ",
+ prod, pr->body_size, pr->head->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 ? "*" : "");
+ } else
+ fprintf(f, "-1, -1, -1, -1 },\n");
}
fprintf(f, "};\n\n");
}
### Memory allocation
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 `tok_copy`.
+memory so they can live in the `asn_stack`. So we provide `tok_copy` to
+make an allocated copy as required.
###### parser includes
#include <memory.h>
###### parser functions
- void *memdup(void *m, int len)
- {
- void *ret;
- if (len == 0)
- return NULL;
- ret = malloc(len);
- memcpy(ret, m, len);
- return ret;
- }
-
static struct token *tok_copy(struct token tk)
{
struct token *new = malloc(sizeof(*new));
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,
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)
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");
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) {
+ if (1) {
// OK to cancel
struct frame *in = tos - tos->since_indent;
in->indents -= 1;
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);
}
force_reduce:
if (states[tos->state].reduce_prod >= 0 &&
- states[tos->state].newline_only &&
!(tk->num == TK_newline ||
tk->num == TK_eof ||
tk->num == TK_out ||
const struct state *nextstate = &states[tos->state];
int prod = nextstate->reduce_prod;
int size = nextstate->reduce_size;
- int bufsize;
- static char buf[16*1024];
+ int res_size = nextstate->result_size;
short indents, start_of_line;
body = p.asn_stack + (p.tos - size);
-
- bufsize = do_reduce(prod, body, config, buf);
+ res = res_size ? calloc(1, res_size) : NULL;
+ res_size = do_reduce(prod, body, config, res);
+ if (res_size != nextstate->result_size)
+ abort();
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)) {
[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[],
fputs("/", trace);
fputs(" ", trace);
}
- parser_trace_state(trace, f, states);
+ fprintf(trace, "(%d) ", f->state);
}
fprintf(trace, "[");
if (tk->num < TK_reserved &&