v0.2.4

Added

• The printer in rucc-ast, which is what --emit=ast will write and what keeps the parser honest. It does not give the source back and it is not meant to: the comments are gone, the layout is the printer's own, and the parentheses are worked out again from the precedences rather than remembered. What it does give back is the tree, so parsing the output produces the same tree and printing that tree produces the same text, and the pair of them is then a check on each other rather than a check on nothing. Three things are written in a way that reads oddly and is exact for a reason. A floating constant comes out in hexadecimal, so 1.0 is 0x1p+0, because a decimal spelling that reads back unchanged needs a shortest round trip algorithm and printing one without such an algorithm quietly changes the program. A keyword comes out in the spelling that is a keyword in every dialect, so _Bool rather than bool and __asm__ rather than asm, since the tree does not record which dialect it was parsed in and the ugly spelling is the one that survives all of them. A declarator is assembled outward from its name, which is the only way int (*f[3])(char) comes back with its parentheses where the grammar needs them and nowhere else. The failures a printer has are the ones that read correctly and are not, so each of those has a test of its own: two tokens that would join into one get a space, so -(-a) is - -a and not the decrement; the declarators of one declaration stay in one declaration, so struct { int x; } a, b; does not turn into two anonymous structures that happen to look alike; an else gets braces around the if it is not attached to; the operand of sizeof is printed as a primary expression, so sizeof (T){0} cannot be read back as a sizeof of a type name; and an escape in a wide string closes the literal rather than swallowing what follows it, so L"\x1234" L"abc" stays four characters long. Nineteen round trip tests drive source through the lexer, phase 7, the parser and the printer twice over and compare both the texts and the tree sizes, which is how the parser bug they landed with was found: int x __attribute__((weak)); was read as an old style function definition, because __attribute__ is a specifier keyword and the question asked after the first declarator is whether a specifier follows it.

• The grammar itself in rucc-parse, so parse now takes the tokens phase 7 produced and gives back a tree: expressions, declaration specifiers, declarators, initializers, statements and declarations, in every dialect from C89 to C23 and with the GNU extensions that real headers cannot be read without. Expressions are a Pratt parser rather than a ladder of fifteen mutually recursive functions, because the precedences are then a table a reader can check against the standard's grammar in one sitting instead of a shape that has to be inferred from the call graph, and because the unary and postfix operators are the interesting part and they get the room. The three genuinely hard decisions each have one home. Whether (A)*b is a cast or a multiplication is asked of the scope stack and nowhere else. Whether int f(void) { is a definition or a declaration is decided on the single token after the first declarator, since the two share a prefix that can be arbitrarily long and no fixed lookahead settles it, and a { is a body while a declaration specifier is an old-style parameter list and anything else, an attribute or an asm label included, belongs to the declaration. Whether a block item is a declaration or a statement is asked after a __label__ and after an ident : label, because a label may be a typedef name and reading the two in the other order makes T: x; a declaration of nothing. A run of labels is collected in a loop and folded afterwards rather than parsed by recursion, because the grammar nests them and a generated dispatch table really does contain three hundred case labels on one statement, so the obvious parser is a stack overflow on real input and the test uses two thousand of them. The GNU shapes that headers depend on are here rather than deferred: statement expressions, case 1 ... 9, computed goto, __label__, the label address operator, __builtin_offsetof, __builtin_choose_expr, __builtin_types_compatible_p, __builtin_va_arg, the conditional with its middle left out, the assembler name on a declaration, and inline assembly with its four sections, where a :: skipping the output list is one token from the lexer and gets split back into two colons here rather than in the lexer, since that is the only place in the grammar where the distinction exists. C23 is a dialect rather than a mode: an old-style definition parses everywhere and is an error only from C23, a declaration may follow a label, an enumeration may name its underlying type, and a label may end a block. Forty integration tests drive the whole path from source text through the lexer and phase 7, so what they check is what a driver sees rather than a token stream written by hand to agree with the parser.

• The parser's spine in rucc-parse: the token buffer, the scopes and the error recovery, which is everything the productions rest on and none of the productions themselves. The lookahead is bounded and the bound is enforced, so peek refuses to look more than four tokens ahead and panics rather than quietly widening the window, because unbounded backtracking is how a C parser becomes quadratic on the input a fuzzer eventually finds. The scopes are where C's one real ambiguity is settled, since (A)*B is a cast when A is a type and a multiplication when it is not, and the answer comes from a scope stack the parser maintains itself rather than from a feedback channel back to the lexer, which is the traditional approach and which makes the lexer's state depend on how far the parser has got. The shape is one map from a name to the stack of bindings for that name, innermost last, plus a log of what each open scope bound, so a lookup costs one hash rather than the depth of the nesting and closing a scope costs what it declared rather than a walk of everything visible from it. Each of the hazards has a test, because each of them is a real bug in a real compiler: a declarator introduces its name at the end of the declarator rather than at the start, so typedef int T; void f(int T, T x); has T as a parameter name and T x is then an error while typedef int T; T T; reads the specifier as the type and then declares a variable of that name, tags are a namespace of their own so struct T leaves a bare T alone, and a typedef name shadowed by an inner declaration comes back when that scope closes. Recovery skips to the next ; or } at the current bracket depth for a statement and past the ; or the function body for a declaration, while an expression skips nothing at all, since expressions are short and skipping one costs the rest of the statement. What actually stops a cascade is that every recovery leaves a poisoned node behind and a diagnostic about a poisoned node is never reported, rather than an error count or a flag saying that something already went wrong here. The limit on errors is twenty and that number was measured rather than assumed: clang 23.1 stops there and says so, and gcc 13.3 has no default limit at all and prints every error the file produces.

• The tree itself in rucc-ast: the three arenas, the side tables, and a node for every expression, statement and declaration this compiler intends to parse. It is flat vectors and four byte indices rather than boxes and pointers, which is what makes it half the size, droppable in one go, Send for free, and serialisable without fixups. An expression is sixteen bytes, a statement twenty, a declaration twenty four, and every one of those numbers has a test asserting it, because the day a variant grows is a day somebody should have to say so out loud rather than a day the arena quietly gets a third larger. Spans are out of line in a vector beside each arena, since almost nothing that walks the tree reads them and eight bytes of source position in the node would make every scan pay for the diagnostics. Nothing is desugared: a subscript is a subscript and not pointer arithmetic, a compound assignment is one operator and not three nodes, a for loop is a for loop. Rewriting any of it here would make every message after this point describe a program nobody wrote, and the rewriting has exactly one home, which is where the IR is built. The declarator representation is the part that matters most: a name plus the list of steps that build its type outward from it, so int (*f[3])(char) is array, pointer, function in that order, folded from the end onto the type the specifiers named. It is one flat list rather than a tree and it is shared with the abstract declarators, because a compiler that writes those twice ends up accepting different things in a cast than in a parameter. The type keywords are kept as the multiset they were written in and turned into a type by a table with its own tests, which is how long on its own, long before int and long after long end up being the same keyword doing three different jobs without the parser needing to know it.

• Phase 7 in rucc-lex, which is the join between the preprocessor and the parser and the last place where a spelling means anything. convert walks a stream of preprocessing tokens and produces the tokens the parser reads: an identifier becomes a keyword when the dialect has that spelling, a preprocessing number becomes a typed value, a literal becomes elements, a run of adjacent string literals becomes the one literal it is, and a stray byte becomes the error it always was. Concatenation lives here rather than in the parser because the encoding rules are already here, and doing it anywhere else would be the second place that knows them. It is not a matter of joining the elements either, because the bodies are read in the encoding of the whole run: the accented letter in L"a" "e-acute" is one wide element and not the two bytes it would be on its own, and a run mixing two prefixes is refused in gcc's words, "unsupported non-standard concatenation of string literals". A token is sixteen bytes, the same budget a preprocessing token has and for the same reason, so a converted constant does not live in the token; the token holds an index and the values live in vectors beside it, which is also the shape the parser wants, since it reaches for a value at one node in a hundred and reads the kind at every one. This is also where a remark from a conversion becomes a diagnostic, because it is the first layer holding the span. Which remarks are warnings without a flag and which wait for -pedantic was measured on gcc 13.3 rather than guessed, and the split is not obvious: a multi-character constant, an escape out of range, an overflowing floating constant and a decimal constant that came out unsigned are warnings with no flag at all, while the GNU escape, the imaginary suffix, the d suffix, binary constants and everything the dialect does not have yet are quiet until -pedantic asks. A constant that will not convert produces one diagnostic and a token that stands in for it, so one bad literal does not cost the rest of the file its parse.

What's Changed

• Add phase 7, which turns pp-tokens into the tokens the parser reads by @tamnd in #63
• Add the AST: three arenas, the side tables, and the declarators by @tamnd in #64
• Add the parser's spine: the cursor, the scopes, and the recovery by @tamnd in #65
• Add the grammar: expressions, declarators, statements, declarations by @tamnd in #66
• Add the AST printer, which round-trips through the parser by @tamnd in #67
• Release 0.2.4 by @tamnd in #68

Full Changelog: v0.2.3...v0.2.4