Hacker News Reader

Comment by chrisdotcode | Hacker News Reader

Most "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?

View on HN

Writing 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.

Thank you for the recommendation!

I'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.

There is not much point in writing a parser without using a parser generator. Now, if you want to know how to make a parser generator, I recommend starting here:

https://en.wikipedia.org/wiki/Shift-reduce_parsing

https://en.wikipedia.org/wiki/LALR_parser

If you want lots of detail, there is always this:

http://www.amazon.com/Compilers-Principles-Techniques-Tools-...

I couldn't disagree more. Parser generators are ok for trivial grammars with limited error handling. They're generally horrible for writing compilers.

Also, this wonderful page too: http://compilers.iecc.com/crenshaw/ It exactly what you're looking for. No automated tool, library etc; In fact, you will need to have a automated tool: the Pascal compiler for compile your compiler. But I guess it is not a problem, right? :p the tutorial is really nice I’m at tutor6 right now and the guy really teaches step-by-step each little thing about we are going to working on. The toturial is unfinished but don’t worry, you can learn a lot with the contents he has provided so far. (sorry english, not my native language)

I would advise "Compiler Construction" from Niklaus Wirth book over that tutorial.

http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf

Of course, the best is to do both. :)

Thanks very much for that book. Of course I'm going to read it too. :)

This was some of my motivation for my series, though it needs a rewrite/tightening up some day if/when I complete it. I started with code-generation, and worked my way up from that, partly because I've always been very annoyed that so many compiler texts are so focused on parser theory (especially because most production compilers ends up with hand-written recursive descent parsers because they are easy to write and easy to add error handling to, unlike most of the ones generated with fancy tools, yet lots of texts insists on trying to teach tons of parsing theory that most people will never, ever use before touching on any of the other parts).

My series is here: http://www.hokstad.com/compiler/

(I just finished part 34 last night, and the next part goes up on my site in a week or so; I'll shorten my buffer quite a bit over the next two months, I think - I currently have a lead time of about 5 months... )

It starts out fairly generic in terms of code generation, but I then got the stupid or brilliant (you choose) idea of writing a Ruby compiler, which on one hand is very interesting, on the other hand is exceedingly frustrating, and which I think lost me some focus - I really should extract the simple/non-Ruby specific sections into a separate text and clean it up.

In terms of other peoples series, look up Crenshaws "Let's write a compiler" and Niklaus Wirths "Compiler Construction". Bother are available for free online. Frankly, if you google 'How to write a compiler' the results are actually very useful (both books show up on the first page for me).

I would also recommend looking at the code generated by Lex and Yacc as well as hand-written code to parse a Lisp or Scheme. That might give an idea of how to organize a hand-written parser.

Though, without reading Modern Compiler Implementation or something similar the use of shift-reduce tables in generated code might not make sense. Also, my computer science curriculum included a course where we wrote a top-down LL(1) parser which is organized very differently with a function call for parsing each rule which calls other functions for parsing sub-rules etc.

I've hand-written a few mangled char-by-char state machines as well, which served as lexers for various DSLs.

The reason you see people using yacc instead of hand coding it is that its really annoying to hand-write a bottom up parser for an LR grammar. If you are going to be writing things by hand then its more intuitive to use a top-down recursive-descent parser instead. However, top-down parsing requires more "tricks" to parse usual languages (for example, you need to rewrite the grammar to an equivalent one without left-recursion) so most introductions you see use bottom-up parsing instead.

Check out the Coursera courses:

https://www.coursera.org/course/automata https://www.coursera.org/course/compilers

Reply on news.ycombinator.com