How can I get my act together on the backend of this compiler?

43 views
Skip to first unread message

luser droog

unread,
Oct 22, 2021, 9:43:04 PM10/22/21
to
I've been working (playing) off and on with code for doing
parser combinators in C. And I filled it out with a K&R C
tokenizer and syntax analyzer so it produces as CST.
Some extra tree trimming and other gyrations to smooth
it out into something more like a usable AST.

And then I don't know what I'm doing anymore. I don't know
where best to study up to figure out how to write a
super amazing code generation backend that's fancy and
cryptic and short like I like.

Since the code itself is kinda stealing from FP literature,
I've been advised to look into "pattern matching" as an
appropriate FP technology to power my "middle end".
(My last question here was asking about how to power
my middle end.) And that has led to this article, which
kinda looks like exactly what I want...

https://arxiv.org/pdf/1210.3593.pdf
Ondˇrej B ́ılka, Pattern matching in compilers. Prague 2012

And I've also put down the Forth books and picked up
good old Budge, /Recursive Programming Techniques/ 1975,
for my lunch breaks. A sort of proto-SICP AFAICT.

Is there anywhere else I should be looking for inspiration
for a really concise and elegant way to write and organise
the tree-walking code-generation code? Or is this paper
the thing, and I'm just not seeing it yet?

I hope this is technical enough for the forum, despite being
somewhat vague and unconstructive. Hoping the experts
here can give me a kick in the right direction.

-- droog

Hans-Peter Diettrich

unread,
Oct 24, 2021, 5:26:51 PM10/24/21
to
On 10/23/21 2:58 AM, luser droog wrote:

> And then I don't know what I'm doing anymore. I don't know
> where best to study up to figure out how to write a
> super amazing code generation backend that's fancy and
> cryptic and short like I like.

A look at the Lua interpreter may be helpful.

DoDi

luser droog

unread,
Nov 12, 2021, 10:27:30 PM11/12/21
to
Thanks. I read up on some "internals" documents and it does look really
interesting. A sliding register window over the more basic stack. 3-address
opcodes eliminating a lot MOV and LOAD instructions. A lot of this may
be directly applicable if I target something like Forth.

But it may be that I'm not ready for the backend because of the lingering
unsolved issues with the frontend. So, I've been making some progress
on a new prototype that may ease the backend effort later on. At least,
the new one will be able to give error messages instead of simply not
producing output. And that feels very important and useful.

At the same time, Budge seems like exactly what I was after. All the tricks
from SICP (probably) with less jibber jabber. If you squint through the SKI
stuff you can see that simple "ideal" compiler I was trying to imagine.
This dude explains control structures by showing how to compile them.
He doesn't even get to parsing input for 2 more chapters. All lambdas all
the way down.

With any luck I'll have the prototype fleshed out with a few examples and
then rewritten in C in a few weeks/months. *Then*, maybe I'll be able to
do a backend. At least a draft to iterate on. Wish me luck. (A silent
luckwishing is acceptable.) Thanks for your patience, everyone. I'll be back
with actual interesting content when it's ready.

droog

Reply all
Reply to author
Forward
0 new messages