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 {
abort:
while (tk.num != TK_newline && tk.num != TK_eof)
tk = token_next(state);
+ free(p.body);
return err;
}
s->name.len, s->name.txt);
}
if (errs) {
- free(g);
+ free(g); // FIXME free content
g = NULL;
}
}
fprintf(stderr, "Error at line %d: %s\n",
tk.line, err);
token_close(state);
- free(g);
+ free(g); // FIXME free content
return NULL;
}
}
}
-### 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
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
for (p = 0; p < g->production_count; p++) {
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)
{
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]);
}
}
-###### functions
-
static void gen_states(FILE *f, struct grammar *g)
{
int i;
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");
}
c = *name;
}
if (namlen == 0) {
- if (name == *namep)
+ if (name == *namep || n > p->body_size)
return -1;
*namep = name;
return n;
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)
+ 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 */
}
if (s < 0)
return -1;
- if (n == 0);
+ if (n == 0)
n = 1;
for (i = 0; i < p->body_size; i++)
if (p->body[i] == p->body[s]) {
if (n == 0)
break;
}
- if (n > 1)
+ if (n > 0 || i == p->body_size)
return -1;
*namep = name;
return i + 1;
###### functions
static void gen_reduce(FILE *f, struct grammar *g, char *file,
- struct code_node *code)
+ struct code_node *pre_reduce)
{
int i;
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 (code)
- code_node_print(f, code, file);
+ if (pre_reduce)
+ code_node_print(f, pre_reduce, file);
fprintf(f, "#line 4 \"gen_reduce\"\n");
fprintf(f, "\tswitch(prod) {\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);
}
}
return -1;
}
+### Memory allocation
+
+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.
+
+###### parser includes
+ #include <memory.h>
+
+###### parser functions
+
+ static struct token *tok_copy(struct token tk)
+ {
+ struct token *new = malloc(sizeof(*new));
+ *new = tk;
+ return new;
+ }
+
### The state stack.
The core data structure for the parser is the stack. This tracks all
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)
return indents;
}
-### 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 `tokcopy`.
-
-###### 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));
- *new = tk;
- return new;
- }
-
### The heart of the parser.
Now we have the parser. For each token we might shift it, trigger a
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 &&