4 ms·
Pretty damn impressive. Though I must wonder: how complete is it? What does it and does it not support? It's at least complete enough to be self-hosting, but b
by TazeTSchnitzel 12y ago
Pretty damn impressive.
Though I must wonder: how complete is it? What does it and does it not support? It's at least complete enough to be self-hosting, but beyond that? The code doesn't use that much of C.
- cbhl 12y agoJudging from the comments in c4.cpp, it probably only supports enough of a subset to compile itself. Granted, while building a parser that can parse (let alone compiling) the full C language is nontrivial, any undergrad should be able to build a parser and compiler for a sufficiently simple subset of it. (In my undergrad, we used this subset to build a "compiler" in second year: https://www.student.cs.uwaterloo.ca/~cs241/wlp4/WLP4.html https://www.student.cs.uwaterloo.ca/~cs241/wlp4/WLP4.html)
- JoeAltmaier 12y agoYou can build a C parser in an afternoon. It only has a few language constructs. Declarations are the hardest. Scanners are readily available for expressions and constants.
- cbhl 12y agoI would be worried about handling the not-context-free parts of the language: http://trevorjim.com/c-and-cplusplus-are-not-context-free/ http://trevorjim.com/c-and-cplusplus-are-not-context-free/ How would you handle these?
- JoeAltmaier 12y agoScanner has to have access to the symbol table, emit 'ident' or 'type' as appropriate. So not a pure context-free parser.
- sedachv 12y agoYes. This is the reason it is way easier to hand-build a parser for C than try to use any kind of parser generator.
- JoeAltmaier 12y agoBison and Flex work fine - do they count as 'parser generators'?
- sedachv 12y agoFlex does not work fine, that's why you need the lexer hack: https://en.wikipedia.org/wiki/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 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/reader.lisp https://github.com/vsedach/Vacietis/blob/master/compiler/rea... 935 lines
- JoeAltmaier 12y agoYou 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.
- sedachv 12y agoExactly. You have to drop hooks into the lexer from the parser, and by the time you're done you end up with just as much code. Only it's slower than a recursive-descent parser would be, and a lot of the time parsing speed really matters because it shows up as user-visible latency.
- vidarh 12y ago
- rui314 12y agoC is not a simple language as a CIL guy says [1]. I wrote my own C compiler [2] and I can say that writing a parser was harder than I thought. It would take more than half a day at least. [1] http://www.cs.berkeley.edu/~necula/cil/cil016.html http://www.cs.berkeley.edu/~necula/cil/cil016.html [2] https://github.com/rui314/8cc https://github.com/rui314/8cc
- zik 12y agoYes, I also wrote my own C interpreter and the parser was a lot more than a day's work.
- vidarh 12y agoThat first link is almost all about language semantics, not parsing issues. As for your example, I'll be solomonic and say that you and Joe are right, of sorts (though I do think it'd be more than an afternoon). It's certainly far more than a days work if you handwrite a lexer and parser that does the amount of additional work that yours do (AST construction; a lot of error reporting and sanity checking). But you can get very far with C very quickly if you use parser generation tools and have prior experience writing compilers and your goal is "just" to get something to parse it as quickly as possible - it's a tiny language. Of course, in practice most real compilers don't use these parser-generation tools exactly because things like proper error reporting etc. is far harder, and a simple recursive descent parser is so much easier to work with.
- verytrivial 12y agoIndeed. The lack of a case statement in the run loop is a bit of a giveaway. Excellent work nonetheless.
- Lerc 12y agoIt's clear from the huge number of 'else if' statements that it doesn't support switch statements. This is also a bit of a clue p = "char else enum if int return while " "open read close printf malloc memset memcmp exit main";
- TazeTSchnitzel 12y agoAh, the lack of struct explains why the compiler doesn't use any structs.