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

TinyCompiler: A compiler in a week-end

ssloy.github.io

Post reply on HN
Print view View original

11–20 of 120 posts

Re: TinyCompiler: A compiler in a week-end

#11

Post by sieve »

sitkack wrote: post #10
sieve wrote: post #8

Earlier quoted context omitted.

Compilers are some of the simplest "complicated" programs out there if you start by throwing yacc/bison/antlr/parser generators in the garbage. Production compilers are complicated because of the feature set of languages and performance requirements. You can write a lexer + parser + treewalk interpreter for a simple language in a day if you know what you are doing.

5 days if you don't, but have the right tutor.

If you know basic programming (js/python), a day is more than enough to get the concept across using a tiny language. Could probably be done in an hour.

The problem, always, is people are given terrible reading recommendations which makes the subject more complicated than it is.

Re: TinyCompiler: A compiler in a week-end

#12

Post by jcuenod »

sieve wrote: post #8
zvmaz wrote: post #3

I don't think one can understand compilers in a "week-end".

Compilers are some of the simplest "complicated" programs out there if you start by throwing yacc/bison/antlr/parser generators in the garbage. Production compilers are complicated because of the feature set of languages and performance requirements. You can write a lexer + parser + treewalk interpreter for a simple language in a day if you know what you are doing.

Honestly, antlr made this pretty straightforward to me. I didn't want to work in java, but they have a ton of targets. You can definitely write it all yourself, and that's a great learning exercise. But I wanted to get a parser for a language idea I had in mind and it took a couple of days with antlr (https://github.com/chicory-lang/chicory)

Re: TinyCompiler: A compiler in a week-end

#14

Post by sieve »

jcuenod wrote: post #12
sieve wrote: post #8

Earlier quoted context omitted.

Compilers are some of the simplest "complicated" programs out there if you start by throwing yacc/bison/antlr/parser generators in the garbage. Production compilers are complicated because of the feature set of languages and performance requirements. You can write a lexer + parser + treewalk interpreter for a simple language in a day if you know what you are doing.

Honestly, antlr made this pretty straightforward to me. I didn't want to work in java, but they have a ton of targets. You can definitely write it all yourself, and that's a great learning exercise. But I wanted to get a parser for a language idea I had in mind and it took a couple of days with antlr ( https://github.com/chicory-lang/chicory )

Problem with these tools is, you have to spend time wrangling them instead of learning to write a lexer/parser yourself.

A recursive-descent parser is a beautiful thing and can be implemented very quickly.

Re: TinyCompiler: A compiler in a week-end

#15

Post by glouwbug »

keyle wrote: post #7

Funnily enough, wend looks like what fun programming means to me. C like (prefixed types) syntax, strongly typed but without heartaches of pointers, and simple types. Every features on top of that has either leaky abstractions and/or nightmare scenarios. That said I'm not claiming the world should run on this type of code. Or should it.

I think OP is just trying to demystify the complexity of compliers for the sake of an educational resource. It's high quality work, compressed to a very small line count

Re: TinyCompiler: A compiler in a week-end

#16

Post by whartung »

sieve wrote: post #8
zvmaz wrote: post #3

I don't think one can understand compilers in a "week-end".

Compilers are some of the simplest "complicated" programs out there if you start by throwing yacc/bison/antlr/parser generators in the garbage. Production compilers are complicated because of the feature set of languages and performance requirements. You can write a lexer + parser + treewalk interpreter for a simple language in a day if you know what you are doing.

The hardest part (IMHO) about getting a simple language running, particularly for beginners, is the “expression”. Mostly for your typical algebraic style infix expressions with precedence.

Just getting the grammar straight on the naturally recursive structures can be a trick. They also touch a large portion of the code generation and run time.

Get:

  (a + c/2) * sqrt(b)
working and you’re 80% there.

Re: TinyCompiler: A compiler in a week-end

#17

Post by andai »

glouwbug wrote: post #15
keyle wrote: post #7

Funnily enough, wend looks like what fun programming means to me. C like (prefixed types) syntax, strongly typed but without heartaches of pointers, and simple types. Every features on top of that has either leaky abstractions and/or nightmare scenarios. That said I'm not claiming the world should run on this type of code. Or should it.

I think OP is just trying to demystify the complexity of compliers for the sake of an educational resource. It's high quality work, compressed to a very small line count

Well, Python and Pascal were designed as a teaching language, and ended up being remarkably good for actual programming.

Re: TinyCompiler: A compiler in a week-end

#18

Post by andai »

whartung wrote: post #16
sieve wrote: post #8

Earlier quoted context omitted.

Compilers are some of the simplest "complicated" programs out there if you start by throwing yacc/bison/antlr/parser generators in the garbage. Production compilers are complicated because of the feature set of languages and performance requirements. You can write a lexer + parser + treewalk interpreter for a simple language in a day if you know what you are doing.

The hardest part (IMHO) about getting a simple language running, particularly for beginners, is the “expression”. Mostly for your typical algebraic style infix expressions with precedence. Just getting the grammar straight on the naturally recursive structures can be a trick. They also touch a large portion of the code generation and run time. Get: (a + c/2) * sqrt(b) working and you’re 80% there.

Is that really the hard part? I figured that part out before I knew much programming: made a simple Excel type formula parser. (A horrible, horrible solution based around replacing strings and manually counting parentheses... but it worked!)

I never got much farther than that though, I've looked into making a compiler many times and got overwhelmed every time.

Re: TinyCompiler: A compiler in a week-end

#19

Post by sieve »

whartung wrote: post #16
sieve wrote: post #8

Earlier quoted context omitted.

Compilers are some of the simplest "complicated" programs out there if you start by throwing yacc/bison/antlr/parser generators in the garbage. Production compilers are complicated because of the feature set of languages and performance requirements. You can write a lexer + parser + treewalk interpreter for a simple language in a day if you know what you are doing.

The hardest part (IMHO) about getting a simple language running, particularly for beginners, is the “expression”. Mostly for your typical algebraic style infix expressions with precedence. Just getting the grammar straight on the naturally recursive structures can be a trick. They also touch a large portion of the code generation and run time. Get: (a + c/2) * sqrt(b) working and you’re 80% there.

> The hardest part (IMHO) about getting a simple language running, particularly for beginners, is the “expression”

This is why teaching material should be tailored towards teaching rather than implementing demented stuff from the real world just because it is "there." You can easily implement a parser that ignores precedence and tell the reader that we are using brackets to force precedence instead.

In a real-word parser, you might use something like this[1] or some other home-grown algorithm if you didn't know about it. Doesn't matter as long as the parser works.

[1] Top-Down operator precedence (Pratt) parsing https://eli.thegreenplace.net/2010/01/02/top-down-operator-p...

Re: TinyCompiler: A compiler in a week-end

#20

Post by RossBencina »

sieve wrote: post #8
zvmaz wrote: post #3

I don't think one can understand compilers in a "week-end".

Compilers are some of the simplest "complicated" programs out there if you start by throwing yacc/bison/antlr/parser generators in the garbage. Production compilers are complicated because of the feature set of languages and performance requirements. You can write a lexer + parser + treewalk interpreter for a simple language in a day if you know what you are doing.

> lexer + parser + treewalk interpreter

If all you do is construct an AST and interpret it it's not really a compiler is it. It doesn't compile from source to target. At most you're describing a compiler front end (arguably), or an interpreter.

I would expect:

lexer + parser + AST definition and construction + semantic analysis/type checking + X + codegen to ASM/WASM/C

where X includes

  - definition of an intermediate representation (IR)
  - lowering AST to IR
  - static analysis
  - improvers/optimisation passes (at least some simple stuff)
  - code gen including register allocation
This can still be a simple "complicated" program, but there's more to a compiler than an AST interpreter.

EDIT: I notice that the author of the original article has also started work on an optimizing compiler: https://ssloy.github.io/tinyoptimizer/

Post reply on HN