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
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))
* 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");
}
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,
+ if (is->go_to.cnt)
+ fprintf(f, "\t[%d] = { %d, goto_",
+ i, is->go_to.cnt, i);
+ else
+ 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, %d, %d, %d, ", prod,
+ pr->body_size,
+ pr->head->num,
is->starts_line,
- g->productions[prod]->line_like,
is->min_prefix);
- else
- fprintf(f, "\t[%d] = { %d, goto_%d, -1, -1, -1, %d, 0, %d },\n",
- i, is->go_to.cnt, i,
+ 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, %d, %d, -1 },\n",
is->starts_line, is->min_prefix);
}
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));
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)) {