4 ms·

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

8 points by LeSUTHU 5y ago

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 5y ago
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-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e... - How Desmos Uses Pratt Parsers (2018) - https://engineering.desmos.com/articles/pratt-parser/ https://engineering.desmos.com/articles/pratt-parser/ - Simple But Powerful Pratt Parsing (2020) - https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html https://matklad.github.io/2020/04/13/simple-but-powerful-pra...
skydhash 5y ago
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-Domain-Specific-Programming/dp/193435645X https://www.amazon.com/Language-Implementation-Patterns-Doma... [1]: https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811 https://www.amazon.com/Compilers-Principles-Techniques-Tools...
perfopt 5y ago
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 5y ago
  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 https://en.wikipedia.org/wiki/LALR_parser] or GLR (generalized Left-To-Right) [https://en.wikipedia.org/wiki/GLR_parser 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/0596155972 https://www.amazon.com/flex-bison-Text-Processing-Tools/dp/0...]
x0re4x 5y ago
@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/ https://www.antlr3.org/works/ * once you want to actually implement your language: https://cs3110.github.io/textbook/chapters/interp/intro.html https://cs3110.github.io/textbook/chapters/interp/intro.html * some older tutorials: https://web.archive.org/web/20051220013748/http://pllab.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamllex-tutorial/ https://web.archive.org/web/20051220013748/http://pllab.kais... https://web.archive.org/web/20051220043933/http://pllab.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamlyacc-tutorial/ https://web.archive.org/web/20051220043933/http://pllab.kais... NOTE: modern replacement for ocamlyacc: http://gallium.inria.fr/~fpottier/menhir/ http://gallium.inria.fr/~fpottier/menhir/
Akronymus 5y ago
I could see a parser combinator working out for you. https://hasura.io/blog/parser-combinators-walkthrough/ https://hasura.io/blog/parser-combinators-walkthrough/ https://www.youtube.com/watch?v=RDalzi7mhdY https://www.youtube.com/watch?v=RDalzi7mhdY https://devlog.hexops.com/2021/zig-parser-combinators-and-why-theyre-awesome https://devlog.hexops.com/2021/zig-parser-combinators-and-wh... https://www.youtube.com/watch?v=N9RUqGYuGfw https://www.youtube.com/watch?v=N9RUqGYuGfw https://lorgonblog.wordpress.com/2007/12/02/c-3-0-lambda-and-the-first-post-of-a-series-about-monadic-parser-combinators/ https://lorgonblog.wordpress.com/2007/12/02/c-3-0-lambda-and...
jimsmart 5y ago
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 5y ago
Here's a classic "Let's Build a Compiler" by Jack Crenshaw https://compilers.iecc.com/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.

8 points by LeSUTHU 5y ago

lioeters 5y ago

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-expression-parsing-made-easy/ http://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-e... - How Desmos Uses Pratt Parsers (2018) - https://engineering.desmos.com/articles/pratt-parser/ https://engineering.desmos.com/articles/pratt-parser/ - Simple But Powerful Pratt Parsing (2020) - https://matklad.github.io/2020/04/13/simple-but-powerful-pratt-parsing.html https://matklad.github.io/2020/04/13/simple-but-powerful-pra...

skydhash 5y ago

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-Domain-Specific-Programming/dp/193435645X https://www.amazon.com/Language-Implementation-Patterns-Doma... [1]: https://www.amazon.com/Compilers-Principles-Techniques-Tools-2nd/dp/0321486811 https://www.amazon.com/Compilers-Principles-Techniques-Tools...

perfopt 5y ago

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 5y ago
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 https://en.wikipedia.org/wiki/LALR_parser] or GLR (generalized Left-To-Right) [https://en.wikipedia.org/wiki/GLR_parser 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/0596155972 https://www.amazon.com/flex-bison-Text-Processing-Tools/dp/0...]

x0re4x 5y ago

@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/ https://www.antlr3.org/works/ * once you want to actually implement your language: https://cs3110.github.io/textbook/chapters/interp/intro.html https://cs3110.github.io/textbook/chapters/interp/intro.html * some older tutorials: https://web.archive.org/web/20051220013748/http://pllab.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamllex-tutorial/ https://web.archive.org/web/20051220013748/http://pllab.kais... https://web.archive.org/web/20051220043933/http://pllab.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamlyacc-tutorial/ https://web.archive.org/web/20051220043933/http://pllab.kais... NOTE: modern replacement for ocamlyacc: http://gallium.inria.fr/~fpottier/menhir/ http://gallium.inria.fr/~fpottier/menhir/

Akronymus 5y ago

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

jimsmart 5y ago

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 5y ago

Here's a classic "Let's Build a Compiler" by Jack Crenshaw https://compilers.iecc.com/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.