Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Writing a C compiler in 500 lines of Python

vgel.me

Post reply on HN
Print view View original

171–180 of 183 posts

Re: Writing a C compiler in 500 lines of Python

#171

Post by Gibbon1 »

pragma_x wrote: post #167
brundolf wrote: post #6

> Instead, we'll be single-pass: code generation happens during parsing IIRC, C was specifically designed to allow single-pass compilation, right? I.e. in many languages you don't know what needs to be output without parsing the full AST, but in C, syntax directly implies semantics. I think I remember hearing this was because early computers couldn't necessarily fit the AST for an entire code file in memory at once

I can't say if that was a design goal, but it sure looks like it. That's also the way to avoid scaling compiler memory use to program size. At first I thought that it wasn't possible for C. After I thought about it, as long as you disallow forward references, and rely on a single source file as input, it's possible to compile a complete C program in one pass. Anything else requires a preprocessor (e.g "#include") and…

I think one thing some early compilers did was read the source serially in one pass and write the output serially in one pass. If you were doing multiple passes you had do that for each pass. That means your compiler speed is IO bound. So one pass is faster.

My cousins ex had a workflow in the late 70's that involved two floppy drives and a little dance to compile and link. Later he got a 5M hard drive which improved things a lot.

Re: Writing a C compiler in 500 lines of Python

#172

Post by bsder »

fodkodrasz wrote: post #140
bsder wrote: post #93

Earlier quoted context omitted.

Infix parsing chews up a remarkable amount code and memory. It's scary just how much easier it is to parse languages without infix parsing.

where it takes up the memory in the human brain, where we have more limited working set, than in computers. That is probably why postfix notation is mostly a thing of the past by now in languages intended to be used by humans.

But creates a habit of having exactly two individual items for an operation.

Which led us to imperative programming and object oriented programming. Which everybody now recognizes as limited in various artificial ways.

Which we are now struggling to shake off given that the majority of chips have a whopping number of parallel cores.

Programming languages restrain your thinking about your solution space.

Re: Writing a C compiler in 500 lines of Python

#173

Post by WalterBright »

andrewmcwatters wrote: post #170
WalterBright wrote: post #43

This looks a lot like the Tiny Pascal compiler that BYTE published a listing of back in 1978. http://www.trs-80.org/tiny-pascal/ I figured out the basics of how a compiler works by going through it line by line.

Thanks for sharing this, Walter. I'm always curious where language developers get their experience from.

Figuring out how recursive descent worked was just magical.

Re: Writing a C compiler in 500 lines of Python

#174

Post by glouwbug »

Waterluvian wrote: post #77
glouwbug wrote: post #74

Earlier quoted context omitted.

Took me seven years to do my own dynamic one that ended up being very similar to python2 with curly braces. Every programmer should try it

“Crafting Interpreters” is a phenomenal place to start. It’s very accessible. If you think you’re “not good enough” to write a programming language, it will show you just how wrong you are. Really boosted my confidence. (Hi Bob!)

Yeah that's where I started

Re: Writing a C compiler in 500 lines of Python

#175

Post by laurencerowe »

59nadir wrote: post #134
laurencerowe wrote: post #70

Earlier quoted context omitted.

As an experienced developer who did not do a compilers course at university I was able to write a SQL/JSONPath evaluator in TypeScript in a week or so. I don’t expect a minimal C compiler would be that much more complex. Essentially all you need is a grammar, parser library and a couple of tree walkers to convert the AST first to expand macros and then convert to assembly. A production compiler with all its optimisat…

You don't need a parser library; writing the tokenizer + parsing logic isn't a very time consuming endeavor and the code doesn't suffer from it either. The upside is also that you're not taking on some monstrosity of a library for something you can implement in a tenth of the lines yourself. You'll also end up with something you actually fully understand yourself as well, which should be a big plus.

While I suspect I would learn more writing a tokenizer and parsing logic myself I find grammars much easier to read and maintain.

ANTLR is pretty good and is supported across several languages and something I had previously used for some quick Elasticsearch query syntax munging in Python. It also means you can often start from an already existing grammar.

The JS version of ANTLR didn't seem to work for me so for the SQL/JSONPath stuff ended up using the Moo lever and Nearly parser which was rather pleasant. https://nearley.js.org

Re: Writing a C compiler in 500 lines of Python

#177

Post by thr0w__4w4y »

coldtea wrote: post #117
bee_rider wrote: post #48

Earlier quoted context omitted.

I wonder why =+ is so obviously a mistake. It does look vaguely wrong for some reason, but I’m prejudiced by current languages.

> I wonder why =+ is so obviously a mistake Consider x = -5 now how about: x =- 5 One makes x negative 5, the other subtracts 5 from it. And under this design of the operator the only difference is a space. It's the same with +, just that we're not used to seeing unary plus in the wild.

>> x =- 5

I think you mean: x -= 5, which indeed is different.

Re: Writing a C compiler in 500 lines of Python

#178

Post by cnity »

rcarmo wrote: post #159
cnity wrote: post #144

Earlier quoted context omitted.

Have you seen Guile Hoot? https://gitlab.com/spritely/guile-hoot

No, thanks! Had a look, doesn’t seem to be ready to support WASI, but it’s active.

WASI support is more a property of the host, no? If I compile some guile to WASM and it imports things from WASI, the compiler doesn't need to do anything to support it. The WASM host simply has to provide those imports according to the WASI spec. Unless I'm misunderstanding you.

Re: Writing a C compiler in 500 lines of Python

#179

Post by coldtea »

thr0w__4w4y wrote: post #177
coldtea wrote: post #117

Earlier quoted context omitted.

> I wonder why =+ is so obviously a mistake Consider x = -5 now how about: x =- 5 One makes x negative 5, the other subtracts 5 from it. And under this design of the operator the only difference is a space. It's the same with +, just that we're not used to seeing unary plus in the wild.

>> x =- 5 I think you mean: x -= 5, which indeed is different.

I'm showing how it would be under the original operator design which was reverted, which was "=-".

Re: Writing a C compiler in 500 lines of Python

#180

Post by Shocka1 »

These kinds of posts are one of the things that keeps me coming back to HN. Right when I start thinking I'm a professional badass for implementing several features with great well tested code in record time, I stumble along posts like this that set me in my place.
Post reply on HN