write out C code files which can be compiled to make a parser.
"2D support" means that indentation and line breaks can be significant.
+Indent tokens (IN and OUT) and end-of-line tokens (EOL and NEWLINE) can
+be used to describe the grammar and the parser can selectively ignore
+these where they aren't relevant.
There are several distinct sections.
Productions are comprised primarily of symbols - terminal and
non-terminal. We do not make a syntactic distinction between the two,
-though non-terminals must be identifiers. Non-terminal symbols are
-those which appear in the head of a production, terminal symbols are
-those which don't. There are also "virtual" symbols used for precedence
-marking discussed later, and sometimes we won't know what type a symbol
-is yet.
+though non-terminals must be identifiers while terminals can also be
+marks. Non-terminal symbols are those which appear in the head of a
+production, terminal symbols are those which don't. There are also
+"virtual" symbols used for precedence marking discussed later, and
+sometimes we won't know what type a symbol is yet.
To help with code safety it is possible to declare the terminal symbols.
If this is done, then any symbol used in a production that does not
production can declare that it inherits the precedence of a given
virtual symbol.
-This use for `$$` precludes it from being used as a symbol in the
+This use of `$$` precludes it from being used as a symbol in the
described language. Two other symbols: `${` and `}$` are also
unavailable.
list of unique sets, each assigned a number.
Once we have the data structures in hand to manage these sets and lists,
-we can start setting the 'nullable' flag, build the 'FIRST' sets, and
-then create the item sets which define the various states.
+we can start setting the 'nullable' flag, build the 'FIRST' and 'FOLLOW'
+sets, and then create the item sets which define the various states.
### Symbol sets.
`do_reduce` which runs the code that was included with the production,
if any.
-This code needs to be able to store data somewhere. Rather than
-requiring `do_reduce` to `malloc` that "somewhere", we pass in a large
-buffer and have `do_reduce` return the size to be saved.
+This code needs to be able to store data somewhere so we record the size
+of the data expected with each state so it can be allocated before
+`do_reduce` is called.
In order for the code to access "global" context, we pass in the
"config" pointer that was passed to the parser function. If the `struct
So we dynamically grow an array as required but never bother to
shrink it down again.
-We keep the stack as two separate allocations. One, `asn_stack` stores
+We keep the stack as two separate allocations. One, `asn_stack`, stores
the "abstract syntax nodes" which are created by each reduction. When
we call `do_reduce` we need to pass an array of the `asn`s of the body
of the 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
-several. The `state` is the most important one and guides the parsing
+two. The `state` is the most important one and guides the parsing
process. The `sym` is nearly unnecessary as it is implicit in the
state. 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
void **asn_stack;
int stack_size;
int tos;
+
+ ## parser state
};
#### Shift and pop
So `shift` finds the next state. If that succeeds it extends the
allocations if needed and pushes all the information onto the stacks.
+An extra complication is added to `shift` by the `EOL` token. This
+token must be generated when a `NEWLINE` is seen, but an `EOL` is
+expected. When this happens, the `NEWLINE` is NOT consumed, so multiple
+EOL can appear before a NEWLINE. To indicate that the token was shifted
+by not consumed, `shift` can return the special value `2`. The token
+number for `EOL` cannot be statically declared, so when the parser
+starts we need to look through the array of non-terminals to find the
+EOL.
+
+###### parser state
+ int tk_eol;
+
+###### find eol
+ p.tk_eol = 0;
+ while (strcmp(non_term[p.tk_eol], "EOL") != 0)
+ p.tk_eol += 1;
+ p.tk_eol += TK_reserved + config->known_count;
+
+
###### parser functions
static int shift(struct parser *p,
const struct state states[])
{
struct frame next = {0};
+ int ret;
int newstate = p->tos
? search(&states[p->stack[p->tos-1].state],
sym)
: 0;
- if (newstate < 0)
+ if (newstate >= 0)
+ ret = 1;
+ else if (sym != TK_newline)
return 0;
+ else {
+ // have a NEWLINE, might need an EOL
+ sym = p->tk_eol;
+ newstate = p->tos
+ ? search(&states[p->stack[p->tos-1].state],
+ sym)
+ : 0;
+ if (newstate < 0)
+ return 0;
+ ret = 2;
+ asn = tok_copy(*(struct token*)asn);
+ }
+
if (p->tos >= p->stack_size) {
p->stack_size += 10;
p->stack = realloc(p->stack, p->stack_size
p->stack[p->tos] = next;
p->asn_stack[p->tos] = asn;
p->tos++;
- return 1;
+ return ret;
}
`pop` primarily moves the top of stack (`tos`) back down the required
### The heart of the parser.
Now we have the parser. For each token we might shift it, trigger a
-reduction, or start error handling. 2D tokens (IN, OUT, EOL) also need
-to be handled.
+reduction, or start error handling. 2D tokens (IN, OUT, NEWLINE, EOL)
+might also be ignored. Ignoring tokens is combined with shifting.
-We return whatever `asn` was returned by reducing production zero.
+###### parser vars
+
+ struct parser p = { 0 };
+ struct token *tk = NULL;
+ int accepted = 0;
+
+###### heart of parser
+
+ shift(&p, TK_eof, NULL, states);
+ while (!accepted && p.tos > 0) {
+ struct frame *tos = &p.stack[p.tos-1];
+ if (!tk)
+ tk = tok_copy(token_next(tokens));
+ parser_trace(trace, &p,
+ tk, states, non_term, config->known_count);
+
+ ## try shift or ignore
+ ## try reduce
+ ## handle error
+ }
-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.
+Indents are ignored unless they can be shifted onto the stack
+immediately. The end of an indented section - the OUT token - is
+ignored precisely when the indent was ignored. To keep track of this we
+need a small stack of flags, which is easily stored as bits in an
+`unsigned long`. This will never overflow and the scanner only allows
+20 levels of indentation.
-`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.
+###### parser state
+ unsigned long ignored_indents;
-`TK_out` tokens must 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 extends back before the most recent indent,
-that indent can be cancelled. If the minimum prefix is shorter then
-the indent had ended prematurely and we must start error handling, which
-is still a work-in-progress.
+NEWLINE/EOL is ignored when in an indented section of text which was not
+explicitly expected by the grammar. So if the most recent indent is
+ignored, so is any EOL token.
+
+For other tokens, we shift the next token if that is possible, otherwise
+we try to reduce a production.
+
+###### try shift or ignore
+
+ if ((tk->num == TK_newline || tk->num == TK_out) &&
+ (p.ignored_indents & 1)) {
+ /* indented, so ignore OUT and NEWLINE */
+ if (tk->num == TK_out)
+ p.ignored_indents >>= 1;
+ free(tk);
+ tk = NULL;
+ parser_trace_action(trace, "Ignore");
+ continue;
+ }
-`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 forcibly
-terminates any line-like structure - we try to reduce down to at most
-one symbol for each line where newlines are allowed.
-A consequence of this is that a rule like
+ switch (shift(&p, tk->num, tk, states)) {
+ case 1:
+ if (tk->num == TK_out)
+ p.ignored_indents >>= 1;
+ if (tk->num == TK_in)
+ p.ignored_indents <<= 1;
-###### Example: newlines - broken
+ tk = NULL;
+ /* fallthrough */
+ case 2:
+ parser_trace_action(trace, tk ? "ShiftEOL" : "Shift");
+ ## did shift
+ continue;
+ }
- Newlines ->
- | NEWLINE Newlines
- IfStatement -> Newlines if ....
+ if (tk->num == TK_in) {
+ /* No indent expected here, so ignore IN */
+ free(tk);
+ tk = NULL;
+ p.ignored_indents <<= 1;
+ p.ignored_indents |= 1;
+ parser_trace_action(trace, "Ignore");
+ continue;
+ }
-cannot work, as the NEWLINE will never be shifted as the empty string
-will be reduced first. Optional sets of newlines need to be include
-in the thing that preceed:
+We have already discussed the bulk of the handling of a "reduce" action,
+with the `pop()` and `shift()` functions doing much of the work. There
+is a little more complexity needed to manage storage for the asn (Abstract
+Syntax Node), and also a test of whether the reduction is permitted.
-###### Example: newlines - works
+When we try to shift the result of reducing production-zero, it will
+fail because there is no next state. In this case the asn will not have
+been stored on the stack, so it get stored in the `ret` variable, and we
+report that that input has been accepted.
- If -> if
- | NEWLINE If
- IfStatement -> If ....
+###### parser vars
-Here the NEWLINE will be shifted because nothing can be reduced until
-the `if` is seen.
+ void *ret = NULL;
+
+###### try reduce
+
+ if (states[tos->state].reduce_prod >= 0) {
+ void **body;
+ void *res;
+ const struct state *nextstate = &states[tos->state];
+ int prod = nextstate->reduce_prod;
+ int size = nextstate->reduce_size;
+ int res_size = nextstate->result_size;
+
+ body = p.asn_stack + (p.tos - size);
+ res = res_size ? calloc(1, res_size) : NULL;
+ res_size = do_reduce(prod, body, config, res);
+ if (res_size != nextstate->result_size)
+ abort();
+ pop(&p, size, do_free);
+ if (!shift(&p, nextstate->reduce_sym, res, states)) {
+ accepted = 1;
+ ret = res;
+ parser_trace_action(trace, "Accept");
+ } else
+ parser_trace_action(trace, "Reduce");
+ continue;
+ }
If we can neither shift nor reduce we have an error to handle. There
are two possible responses to an error: we can pop single frames off the
FILE *trace, const char *non_term[],
struct token_config *config)
{
- struct parser p = { 0 };
- struct token *tk = NULL;
- int accepted = 0;
- void *ret = NULL;
## parser vars
- shift(&p, TK_eof, NULL, states);
- while (!accepted && p.tos > 0) {
- struct frame *tos = &p.stack[p.tos-1];
- if (!tk)
- tk = tok_copy(token_next(tokens));
- parser_trace(trace, &p,
- tk, states, non_term, config->known_count);
-
- if (tk->num == TK_in) {
- free(tk);
- tk = NULL;
- parser_trace_action(trace, "Record");
- continue;
- }
- if (tk->num == TK_out) {
- if (1) {
- // OK to cancel
+ ## find eol
- free(tk);
- tk = NULL;
- parser_trace_action(trace, "Cancel");
- continue;
- }
- // fall through to error handling as both SHIFT and REDUCE
- // will fail.
- }
- if (tk->num == TK_newline) {
- if (1) {
- free(tk);
- tk = NULL;
- parser_trace_action(trace, "Discard");
- continue;
- }
- }
- if (shift(&p, tk->num, tk, states)) {
- tk = NULL;
- parser_trace_action(trace, "Shift");
- ## did shift
- continue;
- }
+ ## heart of parser
- if (states[tos->state].reduce_prod >= 0) {
- void **body;
- void *res;
- const struct state *nextstate = &states[tos->state];
- int prod = nextstate->reduce_prod;
- int size = nextstate->reduce_size;
- int res_size = nextstate->result_size;
-
- body = p.asn_stack + (p.tos - size);
- res = res_size ? calloc(1, res_size) : NULL;
- res_size = do_reduce(prod, body, config, res);
- if (res_size != nextstate->result_size)
- abort();
-
- pop(&p, size, do_free);
-
- if (!shift(&p, nextstate->reduce_sym,
- res, states)) {
- if (prod != 0) abort();
- accepted = 1;
- ret = res;
- }
- parser_trace_action(trace, "Reduce");
- continue;
- }
- ## handle error
- }
free(tk);
pop(&p, p.tos, do_free);
free(p.asn_stack);
code / ocean / blobdiff