Good Resources to Learn and Implement a Parser (Compiler)

Question

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

lioeters · Accepted Answer

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

skydhash · Answer

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

x0re4x · Answer

@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/

Akronymus · Answer

I could see a parser combinator working out for you.
https://hasura.io/blog/parser-combinators-walkthrough/
https://www.youtube.com/watch?v=RDalzi7mhdY
https://devlog.hexops.com/2021/zig-parser-combinators-and-wh...
https://www.youtube.com/watch?v=N9RUqGYuGfw
https://lorgonblog.wordpress.com/2007/12/02/c-3-0-lambda-and...

jimsmart · Answer

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 · Answer

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.

perfopt · Answer

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.

Good Resources to Learn and Implement a Parser (Compiler)

Here's a classic "Let's Build a Compiler" by Jack Crenshawhttps://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.

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.