HN Explorer

Ask HN: Good Resources to Learn and Implement a Parser (Compiler)

8 points by LeSUTHU ↗ HN
Hello, I am interested in compilers and have been trying to build my own compiler.

To make things little easier for me, I have defined my grammar and tokens to resemble Algol, which made tokenizing easier and I have a near complete tokenizer.

So I was able to get an input stream and transform it into an array of tokens, but I was having a hard time parsing, turning the array into a tree (AST).

After I wish to try try different parsing techniques to learn more about parsing and hopefully attempt at writing a semantic analyzer.

I was hoping to get some recommendation on where to start and good resources that I can use to achieve my goal.

Thanks

8 comments

[ 0.26 ms ] story [ 28.0 ms ] thread
perfopt
My knowledge in this area is very dated. But is Lex (Flex) & Yacc (Bison) not the standard way to parse?

Many years ago when I was trying parsing for something else I was informed that these tools generally do as good if not a better job than hand written parsers.

Does that not hold any more?

Though, Flex+Bison is not the easiest of tools to learn.

massinstall
Going by OP's description, Flex and Bison appear to be well suited for what he/she intends to do. There is a bit of a learning curve, but I think it's well worth it. I have been working with both for a few years now and find them very flexible.

FYI, Bison supports parsers using either LALR(1) (Look-Ahead Left-to-Right with 1 token lookahead) [https://en.wikipedia.org/wiki/LALR_parser] or GLR (generalized Left-To-Right) [https://en.wikipedia.org/wiki/GLR_parser].

O'Reilly's book "flex & bison" by John Levine is a helpful reference. [https://www.amazon.com/flex-bison-Text-Processing-Tools/dp/0...]

x0re4x
@LeSUTHU:

* if you want to design and play around with your grammar (builtin interpreter is very nice to try things out):

https://www.antlr3.org/works/

* once you want to actually implement your language:

https://cs3110.github.io/textbook/chapters/interp/intro.html

* some older tutorials:

https://web.archive.org/web/20051220013748/http://pllab.kais...

https://web.archive.org/web/20051220043933/http://pllab.kais...

NOTE: modern replacement for ocamlyacc: http://gallium.inria.fr/~fpottier/menhir/

jimsmart
I learnt a lot from the book 'Writing Compilers and Interpreters' by Ronald Mak.

I have the original edition of the book, which is C++ based (building a language that compiles to x86 assembly), but I see on googling that there is a newer edition that is Java-based, I can't comment upon that, but assume the overall theory and mechanics are just as good (but from the overview it seems it is not only Java-language based in implementation, but also targets the Java VM).

mikewarot
Here's a classic "Let's Build a Compiler" by Jack Crenshaw

https://compilers.iecc.com/crenshaw/

He goes step by step through making a single pass compiler for Pascal, in Pascal. It's easy to follow, and written for a wider audience.