}
}
+### Setting `can_eol`
+
+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.
+
+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".
+
+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`.
+
+###### symbol fields
+ int can_eol;
+
+###### functions
+ static void set_can_eol(struct grammar *g)
+ {
+ int check_again = 1;
+ g->symtab[TK_newline]->can_eol = 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->can_eol)
+ continue;
+
+ for (s = pr->body_size - 1; s >= 0; s--) {
+ if (pr->body[s]->can_eol) {
+ pr->head->can_eol = 1;
+ check_again = 1;
+ break;
+ }
+ if (!pr->body[s]->nullable)
+ break;
+ }
+ }
+ }
+ }
+
### Building the `first` sets
When calculating what can follow a particular non-terminal, we will need to
for (s = g->syms; s; s = s->next)
g->symtab[s->num] = s;
- if (type >= SLR) {
- set_nullable(g);
+ set_nullable(g);
+ set_can_eol(g);
+ if (type >= SLR)
build_first(g);
- }
+
if (type == SLR)
build_follow(g);
if (!s)
continue;
- printf(" %c%3d%c: ",
- s->nullable ? '*':' ',
+ printf(" %c%c%3d%c: ",
+ s->nullable ? '.':' ',
+ s->can_eol ? '>':' ',
s->num, symtypes[s->type]);
prtxt(s->name);
if (s->precedence)
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 two.
+The other allocation stores all other stack fields of which there are four.
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.
+
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.
struct frame {
short state;
short sym;
+ short starts_indented;
+ short indents;
} *stack, next;
void **asn_stack;
int stack_size;
p->asn_stack[p->tos] = asn;
p->tos++;
p->next.state = newstate;
+ p->next.indents = 0;
+ p->next.starts_indented = 0;
return 1;
}
{
int i;
p->tos -= num;
- for (i = 0; i < num; i++)
+ for (i = 0; i < num; i++) {
+ p->next.indents += p->stack[p->tos+i].indents;
do_free(p->stack[p->tos+i].sym,
p->asn_stack[p->tos+i]);
+ }
- if (num)
+ if (num) {
p->next.state = p->stack[p->tos].state;
+ p->next.starts_indented = p->stack[p->tos].starts_indented;
+ }
}
### Memory allocation
single entries off the stack until we can shift the `TK_error` symbol, then
drop input tokens until we find one we can shift into the new error state.
+When we find `TK_in` and `TK_out` tokens which report indents we need
+to handle them directly as the grammar cannot express what we want to
+do with them.
+
+`TK_in` tokens are easy: we simply update the `next` stack frame to
+record how many indents there are and that the next token started with
+an indent.
+
+`TK_out` tokens must either be counted off against any pending indent,
+or must force reductions until there is a pending indent which isn't
+at the start of a production.
###### parser includes
#include "parser.h"
FILE *trace, const char *non_term[], int knowns)
{
struct parser p = { 0 };
- struct token *tk;
+ struct token *tk = NULL;
int accepted = 0;
void *ret;
- tk = tok_copy(token_next(tokens));
while (!accepted) {
+ struct token *err_tk;
+ 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;
+ free(tk);
+ tk = NULL;
+ 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;
+ free(tk);
+ tk = NULL;
+ continue;
+ }
+ // fall through and force a REDUCE (as 'shift'
+ // will fail).
+ }
if (shift(&p, tk, states)) {
- tk = tok_copy(token_next(tokens));
+ tk = NULL;
continue;
}
if (states[p.next.state].reduce_prod >= 0) {
accepted = 1;
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);
+ // FIXME need to report this error somehow
+ continue;
+ }
/* Error. We walk up the stack until we
* find a state which will accept TK_error.
* We then shift in TK_error and see what state
* Then we discard input tokens until
* we find one that is acceptable.
*/
+
+ err_tk = tok_copy(*tk);
p.next.sym = TK_error;
- while (shift(&p, tk, states) == 0
+ while (shift(&p, err_tk, states) == 0
&& p.tos > 0)
// discard this state
pop(&p, 1, do_free);
- tk = tok_copy(*tk);
+ if (p.tos == 0) {
+ free(err_tk);
+ // no state accepted TK_error
+ break;
+ }
while (search(&states[p.next.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;
+ if (tk->num == TK_out) {
+ if (p.next.indents == 0)
+ break;
+ p.next.indents -= 1;
+ }
}
if (p.tos == 0 && tk->num == TK_eof)
break;