9 ms·
Join the Compiler Creation Club
- lennel 13y agoNitpicking certainly but I would say use something like antlr rather than peg.js antlr "schemas" are extremely close to ebnf's (some exceptions obviously) and the compiler creation club could benefit from that. Antlr 3 is usable in a variaty of languages (although 4 is a hellavalot simpler and solves a fair bit around left recursive grammers, but non jvm support is non existent still I suspect)
- computer 13y agoFor an advanced version: The C++ Grandmaster Certification MOOC where participants build their own complete C++11 compiler in C++11 is still going strong: http://cppgm.org/ http://cppgm.org/
- octo_t 13y agoHas literally anyone actually completed that certification?
- madhusudancs 13y agoWell, I would extend that and ask. Has anybody completed implementing the Lexer/Parser phase? Once you get the Syntax tree or IR, the complexity is more or less (if not exactly the same) similar to other languages.
- WalterBright 13y agoI've written a complete C++98 compiler, front to back.
- pkaye 13y agoHow long did something like that take you to do?
- WalterBright 13y ago10 years
- arcft 13y agoMr. Bright, you're my hero. Really. Not only because you have made a C++ compiler using recusive descent parser and it's was the first ever to generate native code and the first comercial too and you don't even do generate assembly on dmd. You still made the D language and dmd compiler. A world saving tool from C and C++. It will rock the world. Could you imagine one of the next world's famous software like Windows or *BSD written in D? Also, I'm on the way on compiler business too (joke :-)). (sorry english, not my native language)
- madhusudancs 13y agoI am going to second arcft now. You are now my hero too! Wow, 10 years!
- beagle3 13y agoWalterBright[0] wrote the first native code C++ compiler, Zortech C++, (later called Symantec C++ and recently DigitalMars C++) and is the man behind the D programming language. [0] http://en.wikipedia.org/wiki/Walter_Bright http://en.wikipedia.org/wiki/Walter_Bright
- deleted 13y ago[deleted]
- rayiner 13y agoWriting a C++ compiler is something I wouldn't wish on my worst enemy. My Google SoC project (ages ago) involved generating code to be ABI compatible with C++ virtual table layouts. This spec gave me nightmares: http://mentorembedded.github.io/cxx-abi/abi.html#vtable http://mentorembedded.github.io/cxx-abi/abi.html#vtable. My favorite part is this sentence: "The rules for constructing virtual tables of the class are a combination of the rules from Categories 2 and 3, and can generally be determined inductively." Ah yes, very comforting. The rules can be generally determined inductively (except of course, when they can't be!)
- caissy 13y agoI am currently following a compiler class, and I must say that I am really amazed and impressed. For an assignment, we of course had to write an interpreter for our own mini language. The fealing you have after creating this interpreter was overwhelming. For the lexer and parser, we used SableCC, an object oriented framework that generates a compiler in Java. I've never used anything else (yacc, lex, etc), so I can't compare the tool, but it provides a rich, useful and easy interface to use.
- pjmlp 13y agoSableCC is quite good. yacc and lex are handy to have around, but feel like Jurassic tools when compared to more modern parser generators tooling like ANTLR.
- Taniwha 13y agokids these days, when I wrote my first compiler I had to write my own yacc equivalent, and parser FYI: My generator allowed for dynamic resolution of shift/reduce conflicts which allows you to compile some languages yacc wont let you (languages that let you change the priority of operators for example)
- pjmlp 13y agoGiven that one of my CS specialization areas was compiler design, me too. I implemented a left recursive parser in x86 Assembly for MS-DOS systems. As I said, yacc and lex are nice to have, but nowadays there is little incentive to keep using them. Specially as you say, they are not able to parse all types of languages.
- Taniwha 13y agoDid something similar in 6800 assembly, left recursion of course limits you even more - but it helps fit that tiny tiny compiler into 2k. I actually like yacc/bison - they're good for most purposes and deliberately designing a non-LALR (or more a non-LR) language on purpose (rather than because you don't know any better) is usually silly - you do need to 'get' the concept of building a parse tree from bottom up - assembling it from larger and larger snippets as you go Oh and yacc/bison run about 10 times faster than equivalent I wrote 10 years before they existed so I'm not complaining I tend to use the same bespoke lexical analyser I've used for years and hack it to suit - it includes support for symbol tables/etc and runs really fast, no need to reinvent the wheel
- pjmlp 13y agoAdvice to anyone jumping into writing compilers, just pick a functional language, specially ML family. Symbolic manipulation of data structures is plain joy, compared to what is required in C or Pascal family of languages.
- rayiner 13y agoMy recommendation would be to compile a Lisp. See: http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf. Easy to follow tutorial for compiling Scheme to x86. This advice is especially true if you think syntax and parsing are the boring parts of writing a compiler.
- pjmlp 13y agoYes, that tutorial is quite good.
- cjh_ 13y agoI have been working on a small r7rs scheme interperter [1] and it has been extremely educational. I had never used scheme previously but learning it from sicp [2] has been rather enlightening, it surprisingly lived up to expectations. I haven't considered if I will go down the compiler route, but either way that resource looks very interesting; especially the coverage on tail call optimisation at the assembly level. Does anyone have any further resources discussing tail call optimisation? I would like something a bit more in depth. The other topic I would like to read more on is continuations, as a still newbie-schemer I find the idea of implementing them to be quite daunting. [1] https://github.com/mkfifo/plot https://github.com/mkfifo/plot [2] https://mitpress.mit.edu/sicp/ https://mitpress.mit.edu/sicp/
- jfoutz 13y agoGood old 3imp might be interesting to you, http://www.cs.indiana.edu/~dyb/papers/3imp.pdf http://www.cs.indiana.edu/~dyb/papers/3imp.pdf Dybvig himself, you might recognize him as the author of the Scheme specification.
- edtechdev 13y agoYou can also learn a lot by studying (and even contributing to) other open source compilers. Here are about 100 javascript-based compilers, including tools for compiler writers at the bottom: https://github.com/jashkenas/coffee-script/wiki/List-of-languages-that-compile-to-JS https://github.com/jashkenas/coffee-script/wiki/List-of-lang...
- cocoflunchy 13y agoI started writing my own compile-to-JS language a while back after reading this book: http://createyourproglang.com/ http://createyourproglang.com/ and I'm loving it! However I'm having a bit of trouble right now with my grammar, I'm using Jison (http://jison.org http://jison.org) and the error messages are kind of confusing (I didn't even know they were error messages at first, I thought they were some kind of logging). I apparently have shift-reduce conflicts just about everywhere, but I didn't bother solving them as I was building the rest of the language since everything is working fine! (well I'm sure there are edge cases that I haven't ran into yet) So if anyone here has a good link on the basics of parsing, grammars, LR(1) and whatnot, I'd like to understand what I'm doing ;)
- pjmlp 13y agoAlthough a bit out of date, the Dragon book is always worth a read. http://dragonbook.stanford.edu/ http://dragonbook.stanford.edu/
- j_baker 13y agoNit: Not all languages have a separation between statements and expressions. Most lisps just have expressions.
- chrisdotcode 13y agoMost "tutorials" I've seen as of late (including this one) seem to walk through creating the grammar, and then just hand wave the actual creation of the AST (and the rest of the steps) to "yacc magic" or some other friends. I would not call that building a compiler. Are there any modern tutorials/references of hand-generating the grammar, hand-coding the parser, and hand-coding whatever comes next (because I have no idea, thanks to these new-age tutorials) - without a toolchain, so that the entire process can be seen from start to finish?
- mcpherrinm 13y agoWriting a parser isn't a terribly interesting or difficult part of writing a compiler. You can describe a simple one in a page of pseudocode. If you really are interested in writing a compiler, I wouldn't get hung up on this point. If you want more depth, you probably want to pick up a compiler textbook. I liked "Modern Compiler Implementation" (I've used both the C and ML versions) in my undergrad.
- chrisdotcode 13y agoThank you for the recommendation!
- mcpherrinm 13y agoI've been thinking about what I've said in this post and I want to reword slightly. Writing a parser can be very interesting, and there's a lot of neat techniques, and since we're talking about learning here and not making production compilers, it's certainly a worthwhile endeavor. What I really mean to say is that your parser doesn't have a lot of effect on the rest of your compiler design. In the end, it's a function that takes input text to an AST. You can go back and replace a YACC generated one later, if you want to know more. Of course if you choose a simple to parse input language (like lisp) then you can write a simple handwritten parser off the bat.
- bcheung 13y agoCheck out the Coursera courses: https://www.coursera.org/course/automata https://www.coursera.org/course/automata https://www.coursera.org/course/compilers https://www.coursera.org/course/compilers
- cjh_ 13y agoI have been writing a scheme interpreter in c, and for me the most interesting aspect so far has been the level at which I am programming. At the beginning it was very traditional c; symbol and AST manipulation were a PITA (at that point it was a malloc'd arrays of `expressions`). After I had a base language working I started to use the language I had implemented so far to further the implementation, this finally peaked where this weekend I did a large refactor to remove most of my c arrays and instead replace them with scheme pairs and lists. For example, here [1] I implement define function form in terms of lambda, specifically new_lambda(env, cons(args, cons(body, null))). In hindsight this seems so obvious, but I have found the whole process extremely interesting, specifically looking at how the implemented languages starts to influence the implementation language. I really cannot stress enough how enjoyable the process of writing my interpreter has been, I thoroughly recommend it to anyone who is interesting in programming languages. [1] https://github.com/mkfifo/plot/commit/07272bd69e51979ab71fa08f6415978f46a3b4ee#diff-e2f93fafd9051a63d4bd310620ebd261R105 https://github.com/mkfifo/plot/commit/07272bd69e51979ab71fa0...
- chewxy 13y agoUgh, Hacker News you are better than this. THIS was posted yesterday: http://news.ycombinator.com/item?id=6792225 http://news.ycombinator.com/item?id=6792225. It links to the original source. Why are we not giving the original author credit, instead of linking to blog spam on tech.pro?