A compiler generator. It rests on the claim that a compiler is a grammar plus a sequence of tree walks, and that both halves can be written down instead of programmed.
cc.Why not lex and yacc
After the parser you still hand-write forward-declaration collection, type checking, optimisation and code generation — four large modules that are mostly traversal boilerplate and a little content, written again for every language.
Phoenix's claim is that a compiler is a grammar plus a sequence of tree walks, and that both halves can be written down instead of programmed.
The name belongs to Brooker and Morris, whose Compiler Compiler ran at Manchester around 1960 and meant something larger than a parser: their system had a notation for what constructs meant. Yet Another Compiler-Compiler borrowed the name and delivered a fraction of it.
One — the tree
-> after an alternative names the node it
means. Everything else — the brackets, the semicolons, the chain of rules
that each pass one thing along — is never built in the first place.
program = { statement } -> Program(body: $1) .
statement = "print" e:expression ";"
-> Print(value: $e)
| "let" n:name ":=" e:expression ";"
-> Let(name: $n, value: $e) .
(* $$ is what has been built so far, which
makes this a left fold -- and is why
associativity is said once. *)
expression = term { ( "+" | "-" ) term
-> Binary(op: $1, left: $$, right: $2) } .Program
`- body: [3]
|- Let
| |- name: "width"
| `- value: Binary
| |- op: "+"
| |- left: Number
| | `- text: "3"
| `- right: Number
| `- text: "4"
|- Let
| |- name: "height"
| `- value: Binary
| |- op: "*"
| |- left: Variable
| | `- name: "width"
| `- right: Number
| `- text: "2"
`- Print
`- value: Binary ...Interior nodes are never built. One rule, no exceptions: a body that produced one value answers that value, and a body that produced any other number answers a node named after the rule. The useless nodes every hand-written tree-builder exists to strip are not stripped — they never exist.
Two — the walks
There is no visitor class and no recursion to write.
$left.out reads a child's attribute; over a list it means
that of each, which is why there is no map either.
%pass emit-c
Number : out = "{}" of $text .
Variable : out = "{}" of $name .
Binary : out = "({} {} {})"
of $left.out, $op, $right.out .
Let : out = "{}long {} = {};"
of $indent, $name, $value.out .
Print : out = "{}printf(\"%ld\\n\", (long)({}));"
of $indent, $value.out .
(* indentation flows downward: an inherited
attribute is the one thing a synthesised
or a threaded one cannot say *)
Block : down indent = "{} " of $indent
: out = join($body.out, "\n") .
%driver c = show, typecheck, emit-c -> out .#include <stdio.h>
int main(void)
{
long width = (3 + 4);
long height = (width * 2);
printf("%ld\n", (long)(((width * height) - 1)));
return 0;
}$ phx --driver check calc-c.phx bad.calc
bad.calc:3:3: error: print wants an int,
and (n < 2) is bool
print n < 2;
^A driver is a claim about order, and it is checked.
That message reads $value.show, which a different pass
computed. If a driver forgets to run it, Phoenix names the driver and the
pass that would have supplied it — when the description is read, not when
somebody's program hits it.
Three — the compiler
$ phx calc-c.phx -o calcc.c
$ cc calcc.c -o calcc
$ ./calcc sum.calc
#include <stdio.h>
int main(void)
{
long width = (3 + 4);
long height = (width * 2);
printf("%ld\n", (long)(((width * height) - 1)));
return 0;
}A generator can emit code — a recursive-descent function per rule, a switch per pass — which is faster and is what most of the yacc family does. Or it can emit the description as data and ship the machine that already runs it.
Phoenix emits data, because the alternative is a second implementation of everything: a second matcher with the same ordered-choice rules, a second evaluator with the same floored division. Two implementations of one notation have to agree.
A generated compiler runs the same scanner, matcher and
evaluator that phx runs, over a grammar frozen into
static tables. There is nothing for the two to disagree about,
because there is only one of them.
The conformance rule: the same
.phx, interpreted and through every backend, produces identical output — and that is a test on every build.
What you get that a parser generator does not
An emit pass builds a string and nothing anywhere cares what is in
it. C, SVG, another language — or bytes: Solveig's .sob
bytecode is emitted by a description, not by Phoenix.
$3 going stale after somebody inserts a factor before it
is yacc's most famous silent failure — the grammar still builds and
the tree is quietly wrong. Both $n and named factors are
checked when the description is read.
A %driver names the walks and their sequence, and
Phoenix refuses one whose passes read attributes nothing before them
defines — naming the pass that would have supplied it.
Integers that trap rather than wrap, floored division, no implicit
conversion, structural equality. Every claim on that page is a check
the test suite runs, through phx and through a compiler
phx wrote.
A line, a column and a caret in the file somebody wrote — not in the description, and not at the place a PEG happened to give up. When a match fails at the top, the position reported is the one it got furthest.
The .phx notation is written in .phx, and
it parses itself along with every other description in the
repository. Wirth's own argument for the notation, carried out rather
than asserted.
Evidence
Pascal came with Wirth's grammar and Solveig with its own BNF, both vendored and read unmodified. There is no awk grammar on this machine, so awk is the POSIX definition transcribed — and what checks it is not a grammar at all.
fpc -Miso's does. The first eight found six bugs at
once.
solas's does — byte for byte, tracebacks included.
/usr/bin/awk prints.
et_c.awk is 269 lines of awk that e2fsprogs uses to generate
C error tables. Compiled by a Phoenix description it becomes 1,149 lines
of C and prints the same 56 lines that /usr/bin/awk does.
Nobody involved in writing it had heard of this project.
That matters because the cheaper test lies. Three tests agreed with each other for months while a miscounted spread built a wrong tree, wrote it back out wrongly in the same way, and re-parsed to an identical tree. Running the program saw it at once.
176 checks on every build, 174 of which need nothing outside the repository.
Get started
$ git clone https://github.com/hansolovkarlsson/Phoenix
$ cd Phoenix
$ make
$ make test
176 passed, 0 failed$ bin/phx languages/calc/calc-c.phx \
languages/calc/programs/sum.calcA picture language takes you from an empty file to a language, a compiler to SVG, and a standalone C compiler — in about half an hour. Every command and every piece of output in it was run.
Two passes, and a forward reference is the mechanism the first one did not need: a threaded attribute, an inherited one, and why a symbol table is two walks and not one.
Documentation