Live data from Hacker News

C4 – C in 4 functions

github.com

51–60 of 142 posts

Re: C4 – C in 4 functions

#51

On a first skim, this looks really nice; complaints that it's unreadable are unfounded. The background that makes it readable are Wirth's Compiler Construction http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf plus precedence climbing http://en.wikipedia.org/wiki/Operator-precedence_parser#Prec...

complaints that it's unreadable are unfounded

Not exactly. You have to remember that language and compiler design require a LOT of work and experience to understand, and that many programmers will only see this as, frankly, spaghetti.

I think it could have used some more block comments, but that's just me.

Re: C4 – C in 4 functions

#52
post #40

Earlier quoted context omitted.

Yes. This is the reason it is way easier to hand-build a parser for C than try to use any kind of parser generator.

Bison and Flex work fine - do they count as 'parser generators'?

Flex does not work fine, that's why you need the lexer hack: https://en.wikipedia.org/wiki/The_lexer_hack

Non-working (no lexer hack) Flex and Bison specification for C99: https://gist.github.com/codebrainz/2933703 653 lines

Hand-written recursive-descent C parser and pre-processor (something not handled by Lex/Yacc) that produces executable Common Lisp code: https://github.com/vsedach/Vacietis/blob/master/compiler/rea... 935 lines

Re: C4 – C in 4 functions

#53

On a first skim, this looks really nice; complaints that it's unreadable are unfounded. The background that makes it readable are Wirth's Compiler Construction http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf plus precedence climbing http://en.wikipedia.org/wiki/Operator-precedence_parser#Prec...

[deleted]

Re: C4 – C in 4 functions

#54

On a first skim, this looks really nice; complaints that it's unreadable are unfounded. The background that makes it readable are Wirth's Compiler Construction http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf plus precedence climbing http://en.wikipedia.org/wiki/Operator-precedence_parser#Prec...

complaints that it's unreadable are unfounded Not exactly. You have to remember that language and compiler design require a LOT of work and experience to understand, and that many programmers will only see this as, frankly, spaghetti. I think it could have used some more block comments, but that's just me.

I'm writing a chapter for AOSA on something like this: a self-hosting compiler of a subset of Python to Python bytecode. It'll present the full code (about the same length) and try to explain it well for people not into compilers yet, but in the meantime I recommend the Wirth book.

What's your favorite shorter intro? I'd especially like to reference other educational compilers that are self-hosting.

Re: C4 – C in 4 functions

#55
post #52

Earlier quoted context omitted.

Bison and Flex work fine - do they count as 'parser generators'?

Flex does not work fine, that's why you need the lexer hack: https://en.wikipedia.org/wiki/The_lexer_hack Non-working (no lexer hack) Flex and Bison specification for C99: https://gist.github.com/codebrainz/2933703 653 lines Hand-written recursive-descent C parser and pre-processor (something not handled by Lex/Yacc) that produces executable Common Lisp code: https://github.com/vsedach/Vacietis/blob/master/compiler/r…

You can put whatever code you want into the Flex phrase rules. The 'lexer hack' can be implemented there. That's what I do whenever I have to parse something like C.

Re: C4 – C in 4 functions

#56

From a cursory glance this appears to be a much-condensed recursive-descent parser with all of the usual parsing functions moved into one, so it's not all that difficult to understand. I think recursive-descent is one of the easiest to intuitively understand parsing algorithms, and it also makes for some concise code; it's also far easier to debug a recursive-descent parser than one of the traditional table-driven on…

It's an operator precedence parser, which is actually quite a bit faster than recursive descent for expressions when operator precedence is defined using grammar productions that would otherwise get turned into methods.

For example, a simplified expression operator precedence can be expressed like this (where {} denotes repetition, implemented with e.g. a while loop in a recursive descent parser (RDP)):

    expr ::= term { '+' term | '-' term } ;
    term ::= factor { '*' factor | '/' factor } ;
    factor ::= '-' factor |  | '(' expr ')' ;
Typically this would be parsed in RDP using expr(), term() and factor() functions, where expr() calls term(), term() calls factor(), and factor() calls expr() if it sees an opening parenthesis.

The trouble is that this means that every single expression parse needs to call through this deep code flow before it can see a single interesting bit of the expression being parsed. Parsing "2 + 3" will result in 5 function calls: expr, term, factor, then term and factor again.

The operator precedence parser presented avoids this deeply nested set of calls before it starts parsing interesting things.

This problem is far more acute in a language like C, which has lots of precedence levels, than it is in a language like Pascal, which only has a handful.

Re: C4 – C in 4 functions

#57

Earlier quoted context omitted.

I think generally an intepreter can refer to either a byte code interpreter (ie virtual machine) or an AST walking interpreter. This brings to mind how fuzzy "interpreter" is as terminology. What is a virtual machine that JIT compiles the byte code or the AST? Is it a JIT implementation of an interpreter? What of implementations that only JIT the most frequently used functions? Wouldn't those be half interpreter and…

Most interpreters (not all, but most) are actually a compiler and a VM, yes. The difference between a "compiler" and an "interpreter", in practise, seems to be that "compilers" lack a built-in interpreter.

Most static language compilers include an interpreter for constant expressions at a minimum, because otherwise statically allocating things like arrays is a bit tricky. Handily, this interpreter can be reused for constant folding.

C++ compilers nowadays necessarily include a Turing complete interpreter.

Re: C4 – C in 4 functions

#58

Earlier quoted context omitted.

Most interpreters (not all, but most) are actually a compiler and a VM, yes. The difference between a "compiler" and an "interpreter", in practise, seems to be that "compilers" lack a built-in interpreter.

That's another very good point. One can just as well think of the VisualWorks Smalltalk VM as a compiler (which is actually implemented in Smalltalk) with an interpreter+JIT which also functions as a linker. This means, one can also think of Smalltalk as a compiled language with lots of late binding that makes for a more complicated linker. (JIT) Then the part that's a byte code interpreter can be thought of as an "o…

Also, a linker is very similar to a simple garbage collector: it follows code references, marking blocks as it goes (physically allocated in the final output), and adding the references in those blocks to its current list of references to resolve, until it runs out of references to resolve (done) or fails to resolve a reference (link error). All the references then need to be patched up according to their final address, very similar to a GC fixing up memory references.

Re: C4 – C in 4 functions

#60
post #57

Earlier quoted context omitted.

Most interpreters (not all, but most) are actually a compiler and a VM, yes. The difference between a "compiler" and an "interpreter", in practise, seems to be that "compilers" lack a built-in interpreter.

Most static language compilers include an interpreter for constant expressions at a minimum, because otherwise statically allocating things like arrays is a bit tricky. Handily, this interpreter can be reused for constant folding. C++ compilers nowadays necessarily include a Turing complete interpreter.

C has one in the preprocessor, to do platform-independent conditionals.
Post reply on HN