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 (`.`).
+show if it can end in a newline (`>`), if it is considered to be
+"line-like" (`<`), or if it is nullable (`.`).
###### functions
freeing function. The symbol leads us to the right free function through
`do_free`.
-The `indents` count tracks the line indents in the symbol. These are
-used to allow indent information to guide parsing and error recovery.
+The `indents` count tracks the line indents with in the symbol or
+immediately follow it. These are used to allow indent information to
+guide parsing and error recovery.
`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.
+zero, then this symbol is at the start of a line. Similarly
+`since_indent` counts the number of states since an indent, it is zero
+precisely when `indents` is not zero.
`newline_permitted` keeps track of whether newlines should be ignored
-or not, and `starts_line` records if this state stated on a newline.
+or not.
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
+bottom of stack holds the start state but no symbol, as nothing came
before the beginning.
###### parser functions
Two operations are needed on the stack - shift (which is like push) and pop.
-Shift applies not only to terminals but also to non-terminals. When we
-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. In both cases we provide a stack frame which
-contains the symbol to shift and related indent information.
+Shift applies not only to terminals but also to non-terminals. When
+we 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. In both cases we provide the symbol,
+the number of indents the symbol contains (which will be zero for a
+terminal symbol) and a flag indicating the the symbol was at (or was
+reduced from a symbol which was at) the start of a line. The state is
+deduced from the current top-of-stack state and the new symbol.
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
`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.
+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. 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
+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
`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.
+collects a summary of the indents and line starts in the symbols that
+are being removed. It is called _after_ we reduce a production, just
+before we `shift` the nonterminal in.
###### parser functions
void(*do_free)(short sym, void *asn))
{
int i;
- short indents;
+ short indents = 0;
+ int sol = 0;
+
p->tos -= num;
- if (start_of_line)
- *start_of_line =
- !p->stack[p->tos].since_newline;
- indents = 0;
for (i = 0; i < num; i++) {
+ sol |= !p->stack[p->tos+i].since_newline;
indents += p->stack[p->tos+i].indents;
do_free(p->stack[p->tos+i].sym,
p->asn_stack[p->tos+i]);
}
+ if (start_of_line)
+ *start_of_line = sol;
return indents;
}
### The heart of the parser.
-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
+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
+that. 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.
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_in` tokens are easy: we simply update indent count in the top stack frame to
+record how many indents there are following the previous token.
-`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.
+`TK_out` tokens must either be canceled against an indent count
+within the stack. If we can reduce some symbols that are all since
+the most recent indent, then we do that first. If the minimum prefix
+of the current state then extents back before the most recent indent,
+that indent can be cancelled. If the minimum prefix is shorter then
+the indent is premature and we must start error handling, which
+currently doesn't work at all.
-`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.
+`TK_newline` tokens are ignored unless the top stack frame records
+that they are permitted. In that case they will not be considered for
+shifting if it is possible to reduce some symbols that are all since
+the most recent start of line. This is how a newline forcible
+terminates any line-like structure - we try to reduce down to at most
+one symbol for each line where newlines are allowed.
###### parser includes
#include "parser.h"
struct token_config *config)
{
struct parser p = { 0 };
- struct frame next = { 0 };
struct token *tk = NULL;
int accepted = 0;
void *ret = NULL;
struct frame *tos = &p.stack[p.tos-1];
if (!tk)
tk = tok_copy(token_next(tokens));
- next.sym = tk->num;
- parser_trace(trace, &p, &next, tk, states, non_term, config->known_count);
+ parser_trace(trace, &p,
+ tk, states, non_term, config->known_count);
- if (next.sym == TK_in) {
+ if (tk->num == TK_in) {
tos->indents += 1;
tos->since_newline = 0;
tos->since_indent = 0;
parser_trace_action(trace, "Record");
continue;
}
- if (next.sym == TK_out) {
+ if (tk->num == TK_out) {
if (states[tos->state].reduce_size >= 0 &&
states[tos->state].reduce_size <= tos->since_indent)
goto force_reduce;
in->newline_permitted = 0;
}
if (states[in->state].starts_line)
- in->newline_permitted = 0;
+ in->newline_permitted = 1;
while (in < tos) {
in += 1;
in->since_indent = in[-1].since_indent + 1;
// fall through and force a REDUCE (as 'shift'
// will fail).
}
- if (next.sym == TK_newline) {
+ if (tk->num == TK_newline) {
if (!tos->newline_permitted) {
free(tk);
tk = NULL;
parser_trace_action(trace, "Discard");
continue;
}
- if (states[tos->state].reduce_size >= 0 &&
+ if (tos->since_newline > 1 &&
+ states[tos->state].reduce_size >= 0 &&
states[tos->state].reduce_size <= tos->since_newline)
goto force_reduce;
}
if (shift(&p, tk->num, 0, tk->num == TK_newline, tk, states)) {
- next.since_newline = !(tk->num == TK_newline);
- next.indents = 0;
tk = NULL;
parser_trace_action(trace, "Shift");
continue;
bufsize = do_reduce(prod, body, config, buf);
- if (size)
- indents = pop(&p, size, &start_of_line,
- do_free);
- else {
- indents = next.indents;
- start_of_line = 0;
- next.indents = 0;
- }
+ indents = pop(&p, size, &start_of_line,
+ do_free);
res = memdup(buf, bufsize);
memset(buf, 0, bufsize);
if (!shift(&p, nextstate->reduce_sym,
short indents = 0, start_of_line;
err_tk = tok_copy(*tk);
- next.sym = TK_error;
- while (shift(&p, TK_error, next.indents, !next.since_newline,
+ while (shift(&p, TK_error, 0, 0,
err_tk, states) == 0
&& p.tos > 0)
// discard this state
tos->indents += indents;
}
free(tk);
- if (p.tos)
- pop(&p, p.tos, NULL, do_free);
+ pop(&p, p.tos, NULL, do_free);
free(p.asn_stack);
free(p.stack);
return ret;
if (states[f->state].starts_line)
fprintf(trace, "s");
if (f->newline_permitted)
- fprintf(trace, "n%d", f->newline_permitted);
+ fprintf(trace, "n%d", f->since_newline);
fprintf(trace, ") ");
}
- void parser_trace(FILE *trace, struct parser *p, struct frame *n,
+ void parser_trace(FILE *trace, struct parser *p,
struct token *tk, const struct state states[],
const char *non_term[], int knowns)
{
fputs(reserved_words[tk->num], trace);
else
text_dump(trace, tk->txt, 20);
- if (n->indents)
- fprintf(trace, ".%d", n->indents);
- if (n->since_newline == 0)
- fputs("/", trace);
fputs("]", trace);
}
code / ocean / blobdiff