Parser generators : ANTLR, SableCC, JavaCC, bison at a glance.

One looks towards parser generators (or compiler compilers) when there is a need to translate something in one language to other language. Basically you need to read a sequence of characters, make a data structure which represents the same. For many interesting problems, you want to build a tree. Using this, one can generate a new sequence of character, which is translation of input or just do things on that data structure.

A grammar (context free grammar, technically speaking) says what type of children a node can have. The leaves of tree cannot have any nodes under them and they directly correspond to the characters in the input. Looking at the input, we try to construct a tree which complies with the rules declared by grammar. If only one such tree can be made for any valid input, then the grammar is called unambiguous.

To construct the tree, we have many choices for selecting nodes, which can lead to the leaves to correspond to the input sequence seen so far. If we try to construct it from leaves, it is called bottom up approach. This approach usually uses a method of construction called LR parsing. If we attempt to build the tree top-down, the method usually used is called LL parsing.

Now let us discuss about the free tools that we have at our hand. Given a grammar and instructions on what to do with various nodes, these tools generate a parser.

ANTLR is derived from good old C/C++ PCCTS tool. Antlr has lots of features and can generate the parser in Java or C/C++. It uses top down approach to parsing.

JavaCC is a tool used in many applications, which is much like antlr, with few features different here and there. However, it just generates Java code.

The top down parser generators mentioned also support predicates, using which you can try to 'peep' in upcoming input. This is against the rules of game of context free parsing, but convenient in practice.

SableCC is a bottom up parser, which takes an unconventional and interesting approach of using object oriented methodology for constructing parsers. This results in easy to maintain code for generated parser. However, there are some performance issues at this point of time. It generates output in both C++ and Java

GNU Bison is classical bottom up parser. It generates C language output. It has been the standard tool on many unix operating system distributions. Now, it has also acquired the capability of parsing grammars with GLR method. It's implementation of it is not the best around, but we may have a look at lesser used parsing methods some other time.

There is a plethora of such tools. refer to Wikipedia - compiler compilers for details.

Parsing C++ Source Code: An overview of available tools

C++ is a popular programming language. On the other hand, compared to Java, there are few good programming tools available for C++. My favorite example is refactoring. Why should it be like that?

It happens to be the case that C++ was not designed with these issues in mind and also, it carries some legacy from it's ancestor, C. Technically speaking, C++ cannot be accurately specified using a context free grammar. A context free grammar is a grammar in which you can look at only a part of the whole document, and can give a name to that part without looking at other parts. An unambiguous grammar is one in which you can give exactly one name to that part.

Due to this, much hand-tinkering is required to write a C++ parser. However, many parsers take approach of accepting some source code which are not written in C++ and sort it out later in a second try called semantic pass. C++ has many dialects due to it's evolution and various compiler providers. These dialects differ from each other significantly.

If one can spend some money, there is a respected product which can parse C++ very accurately and also help you building tools on it. It can be found at: http://www.edg.com/

For free options, there are basically three approaches. First is to start from scratch and write a grammar (or use someone elses). There is a C++ grammar written by Edward D. Willink for his FOG . The thesis also contains good account of issues in the C++ grammar. The popular antlr parser generator also claims a C++ grammar which is updated from old PCCTS based grammar.

The second option is to use a parser tool that generates some type of intermediate representation which is easy to process programmatically. The noteworthy here is elsa. It is a C++ parser built using a special parser generator called elkhound. It can be found at Elkhound and Elsa site.

The last approach is to let compiler do the job! Prominent example is the modified C++ frontend for LLVM project, which translates the C++ code to bytecode and then provides infrastructure to write processing of this bytecode.

Apart from these, there are parsers coded for IDEs like Eclipse KDevelop, Anjuta etc. These are usually heuristics-driven, meaning that they would make some educated guesses when required to make analysis efficient.

One often forgotten pragmatic difficulty is the pre-processing of source. The first two approaches most of the time takes for granted preprocessed code.

These issues make parsing C++ code difficult and hinder the development of tools for C++ source code.