X-Git-Url: https://ocean-lang.org/code/?a=blobdiff_plain;f=csrc%2Fparsergen.mdc;h=80027aa74e49989428ea370172c3a783c8ebfd40;hb=e49b8c9295ce261db570ea62025b5dfa2a697b2b;hp=554e63c37c921faea604399f7a9dd1f968b7cc84;hpb=29614f479bd2539b7401dc2e5b0df649727a15d8;p=ocean diff --git a/csrc/parsergen.mdc b/csrc/parsergen.mdc index 554e63c..80027aa 100644 --- a/csrc/parsergen.mdc +++ b/csrc/parsergen.mdc @@ -5,6 +5,9 @@ fragments, analyses it, and can report details about the analysis and 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. @@ -149,11 +152,11 @@ because that is what we need to detect tags. 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 @@ -288,7 +291,7 @@ carry precedence information but are not included in the grammar. A 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. @@ -390,9 +393,10 @@ here is told which was found in the `isref` argument. found += 1; t = token_next(ts); } - if (found == 0) + if (found == 0) { err = "No symbols given on precedence/TERM line"; goto abort; + } return NULL; abort: while (t.num != TK_newline && t.num != TK_eof) @@ -511,10 +515,6 @@ Now we have all the bits we need to parse a full production. tk = token_next(state); while (tk.num == TK_ident || tk.num == TK_mark) { struct symbol *bs = sym_find(g, tk.txt); - if (bs->type == Unknown) { - if (!g->terminals_declared) - bs->type = Terminal; - } if (bs->type == Virtual) { err = "Virtual symbol not permitted in production"; goto abort; @@ -688,20 +688,22 @@ used as a terminal anywhere that a terminal is expected. goto abort; } token_close(state); - if (g->terminals_declared) { - struct symbol *s; - int errs = 0; - for (s = g->syms; s; s = s->next) { - if (s->type != Unknown) - continue; - errs += 1; - fprintf(stderr, "Token %.*s not declared\n", - s->name.len, s->name.txt); - } - if (errs) { - free(g); // FIXME free content - g = NULL; + + struct symbol *s; + for (s = g->syms; s; s = s->next) { + if (s->type != Unknown) + continue; + if (!g->terminals_declared) { + s->type = Terminal; + continue; } + err = "not declared"; + fprintf(stderr, "Token %.*s not declared\n", + s->name.len, s->name.txt); + } + if (err) { + free(g); // FIXME free content + g = NULL; } return g; abort: @@ -725,8 +727,8 @@ and to simplify some comparisons of sets, these sets will be stored in a 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. @@ -2039,9 +2041,9 @@ When the parser engine decides to reduce a production, it calls `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 @@ -2617,14 +2619,14 @@ The stack usually won't grow very large - maybe a few tens of entries. 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 @@ -2648,6 +2650,8 @@ to mark the beginning of the file as well as the end. void **asn_stack; int stack_size; int tos; + + ## parser state }; #### Shift and pop @@ -2672,6 +2676,25 @@ stack is empty, it always chooses zero as the next state. 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, @@ -2679,12 +2702,28 @@ allocations if needed and pushes all the information onto the stacks. 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 @@ -2698,7 +2737,7 @@ allocations if needed and pushes all the information onto the stacks. 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 @@ -2721,8 +2760,8 @@ in. ### 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. ###### parser vars @@ -2745,88 +2784,61 @@ to be handled. ## handle error } +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. -We return whatever `asn` was returned by reducing production zero. - -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 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. - -`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 - -###### Example: newlines - broken - - Newlines -> - | NEWLINE Newlines - IfStatement -> Newlines if .... - -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: - -###### Example: newlines - works - - If -> if - | NEWLINE If - IfStatement -> If .... - -Here the NEWLINE will be shifted because nothing can be reduced until -the `if` is seen. +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_in) { + 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, "Record"); + parser_trace_action(trace, "Ignore"); continue; } - if (tk->num == TK_out) { - if (1) { - // OK to cancel - 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)) { + + 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; + tk = NULL; - parser_trace_action(trace, "Shift"); + /* fallthrough */ + case 2: + parser_trace_action(trace, tk ? "ShiftEOL" : "Shift"); ## did shift continue; } + 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; + } + 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 @@ -2923,6 +2935,8 @@ dropping tokens until either we manage to shift one, or reach end-of-file. { ## parser vars + ## find eol + ## heart of parser free(tk);