News for hackers. Stuff that matters.

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

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 | 8 points | on HN )
Re:Ask HN: Good Resources to Learn and Implement a Parser (C... by lioeters on Monday February 14, 2022 @09:52PM (#30342088)
I'd suggest looking into Pratt parsers.

- Pratt Parsers: Expression Parsing Made Easy (2011) by Bob Nystrom - http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e...

- How Desmos Uses Pratt Parsers (2018) - https://engineering.desmos.com/articles/pratt-parser/

- Simple But Powerful Pratt Parsing (2020) - https://matklad.github.io/2020/04/13/simple-but-powerful-pra...

Re:Ask HN: Good Resources to Learn and Implement a Parser (C... by skydhash on Monday February 14, 2022 @09:56PM (#30342117)
I'm starting with Language Implementation Patterns [0], which is more practice focused than the Dragon's book [1]. Most of the examples are in Java, which you can then convert into your current implementation language.

[0]: https://www.amazon.com/Language-Implementation-Patterns-Doma...

[1]: https://www.amazon.com/Compilers-Principles-Techniques-Tools...

Re:Ask HN: Good Resources to Learn and Implement a Parser (C... by x0re4x on Tuesday February 15, 2022 @12:50AM (#30343268)
@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/

Re:Ask HN: Good Resources to Learn and Implement a Parser (C... by jimsmart on Tuesday February 15, 2022 @10:31AM (#30347748)
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).

Re:Ask HN: Good Resources to Learn and Implement a Parser (C... by mikewarot on Tuesday February 15, 2022 @11:33AM (#30348718)
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.

Re:Ask HN: Good Resources to Learn and Implement a Parser (C... by perfopt on Monday February 14, 2022 @11:39PM (#30342872)
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.

Re:Ask HN: Good Resources to Learn and Implement a Parser (C... by massinstall on Monday February 14, 2022 @11:59PM (#30342968)
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...]