How to turn type-labeled tokens into a parse-tree?

Question

So I'm writing a programming language in C++. I've written pretty much all of it except for one little bit where I need to turn my tokens into a parse tree.

The tokens are already type labeled and ready to go, but I don't want to go through the effort of making my own parse tree generator. I've been looking around for apps to do this but always run into very complicating or overzealous apps, and all I want to turn a list of token types into a parse tree, nothing more, nothing less. Thanks in advance!

Answer 1

The simplest parser generator is yacc (or bison).

Bison is just a harry yacc (ie it has more options).

One of these is too generate a C++ parser object (rather than a C function).
Just add the following to the yacc file:

%skeleton "lalr1.cc"

Answer 2

The canonical parser generator is called yacc. There's a gnu version of it called bison. These are both C based tools, so they should integrate nicely with your C++ code. There is a tool for java called ANTLR which I've heard very good things about (i.e. it's easy to use and powerful). Keep in mind that with yacc or bison you will have to write a grammar in their language. This is most certainly doable, but not always easy. It's important to have a theoretical background in LR(k) parsing so you can understand that it means when it tells you to fix your ambiguous grammar.

Answer 3

Depending on what exactly your requirements are, Boost.Spirit might be an alternative. Its modular, so you should be able to use only components of it as well.