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

One-pass Compiler

keleshev.com

Post reply on HN
Print view View original

31–40 of 44 posts

Re: One-pass Compiler

#31

Post by Someone »

azhenley wrote: post #12

I'm currently working on a 3-part blog series on writing a one-pass compiler in Python that emits C. It is quite a bit longer though because we make the lexer and parser from scratch. I started it because my students were having trouble with other tutorials because of all the jargon, theory, and libraries required. http://web.eecs.utk.edu/~azh/blog/teenytinycompiler1.html

Good text, but let’s nitpick. I’m too lazy/confident/arrogant to verify, so let’s potentially embarrass myself here.

    def getToken(self):
        self.skipWhitespace()
        self.skipComment()
How does that handle multiple consecutive comments? Whitespace following a comment?

(returning ‘comment’ and ‘whitespace’ tokens would fix this, and would make it possible to reuse the lexer for pretty-printing/syntax coloring)

Re: One-pass Compiler

#32

Post by azhenley »

Someone wrote: post #31
azhenley wrote: post #12

I'm currently working on a 3-part blog series on writing a one-pass compiler in Python that emits C. It is quite a bit longer though because we make the lexer and parser from scratch. I started it because my students were having trouble with other tutorials because of all the jargon, theory, and libraries required. http://web.eecs.utk.edu/~azh/blog/teenytinycompiler1.html

Good text, but let’s nitpick. I’m too lazy/confident/arrogant to verify, so let’s potentially embarrass myself here. def getToken(self): self.skipWhitespace() self.skipComment() How does that handle multiple consecutive comments? Whitespace following a comment? (returning ‘comment’ and ‘whitespace’ tokens would fix this, and would make it possible to reuse the lexer for pretty-printing/syntax coloring)

It works because a comment by definition goes until a newline, so you can’t have consecutive comments without a newline token in between.

I’ll look into if there’s a better way to do it than this based on your suggestion, thanks!

Re: One-pass Compiler

#33

Post by saagarjha »

rcgorton wrote: post #25

A one pass compiler is going to generate code which is slower than a modern JIT/interpreter. Why is a one pass compiler interesting?

Because they're really fast. Actually, the lower tiers of modern JITs actually need speed, so being able to do code generation in one pass there is a huge boon.

Re: One-pass Compiler

#34

Post by timClicks »

nonsince wrote: post #20

I’ve been writing a one-pass optimising compiler for Wasm. It’s not perfect, but the code it outputs currently outperforms Cranelift's by a factor of 2-10x for many of the files in the Wasm specification testsuite.

Wow, that sounds incredible. Is that a .wasm -> .wasm compiler?

Re: One-pass Compiler

#35

Post by userbinator »

I remember some of the old DOS compilers would generate similar code, using the stack as an actual expression evaluation stack when registers weren't sufficient. It's not a bad idea even now, since x86 has an internal cache of the top of the stack so operations on it are specifically optimised, and the opcodes are very small: push/pop reg is 1 byte, push s8 is 2.

Re: One-pass Compiler

#36

Post by benibela »

tom_mellior wrote: post #3
foobar_ wrote: post #2

That was a short and epic read. > This limited both the language features that were possible and the quality of the produced code. What are the limitations ?

Older versions of C had the restriction that variables could only be declared at the start of a block. Supposedly this was due to the original C compiler being one-pass. It's easier to keep track of the size of the stack frame if you see all declarations in one place. Though I think with a frame pointer you could make it work anyway. You have essentially the same complications if you allow programmers to open a block…

>Older versions of C had the restriction that variables could only be declared at the start of a block.

Pascal also has that restriction

Although Delphi does not have it anymore. But FreePascal still has it, even in Delphi compatible mode. The FreePascal developers have also said, they will keep that restriction to improve readability. The code could not be read anymore if variables were placed willy-nilly everywhere

Re: One-pass Compiler

#37

Post by jashmatthews »

nonsince wrote: post #20

I’ve been writing a one-pass optimising compiler for Wasm. It’s not perfect, but the code it outputs currently outperforms Cranelift's by a factor of 2-10x for many of the files in the Wasm specification testsuite.

Is that due to SIMD or something? I got about 80% of LLVM performance when I was using CraneLift.

Re: One-pass Compiler

#38

Post by Iwan-Zotow »

rcgorton wrote: post #25

A one pass compiler is going to generate code which is slower than a modern JIT/interpreter. Why is a one pass compiler interesting?

How so?

Say, F# compiler is close to single-pass, I believe, producing CIL, which goes to JIT/AOT compiler later

Re: One-pass Compiler

#39

Post by userbinator »

stevekemp wrote: post #18

I wrote something very similar recently, also a single-pass, but with a trivial internal representation: https://github.com/skx/math-compiler The real difference between the compiler in the example, and mine, is that I handle floating-point operations and also explicitly use printf to show the output. (Because otherwise your return value is limited to an 8bit number.)

Because otherwise your return value is limited to an 8bit number

Only on Linux; Windows lets you use the full 32 bits.

Re: One-pass Compiler

#40

Post by tom_mellior »

stevekemp wrote: post #18

I wrote something very similar recently, also a single-pass, but with a trivial internal representation: https://github.com/skx/math-compiler The real difference between the compiler in the example, and mine, is that I handle floating-point operations and also explicitly use printf to show the output. (Because otherwise your return value is limited to an 8bit number.)

This is nice. The -debug flag is a cool feature. But if you first build a representation of the whole program in memory, then traverse that representation to generate code, it's not really single-pass.
Post reply on HN