Best practices for writing a programming language parser

c++ parsing programming-languages conventions
Vinay picture Vinay · Feb 20, 2009 · Viewed 12.6k times · Source

Are there any best practices that I should follow while writing a parser?

Answer

mike g picture mike g · Feb 20, 2009

The received wisdom is to use parser generators + grammars and it seems like good advice, because you are using a rigorous tool and presumably reducing effort and potential for bugs in doing so.

To use a parser generator the grammar has to be context free. If you are designing the languauge to be parsed then you can control this. If you are not sure then it could cost you a lot of effort if you start down the grammar route. Even if it is context free in practice, unless the grammar is enormous, it can be simpler to hand code a recursive decent parser.

Being context free does not only make the parser generator possible, but it also makes hand coded parsers a lot simpler. What you end up with is one (or two) functions per phrase. Which is if you organise and name the code cleanly is not much harder to see than a grammar (if your IDE can show you call hierachies then you can pretty much see what the grammar is).

The advantages:-

  • Simpler build
  • Better performance
  • Better control of output
  • Can cope with small deviations, e.g. work with a grammar that is not 100% context free

I am not saying grammars are always unsuitable, but often the benefits are minimal and are often out weighed by the costs and risks.

(I believe the arguments for them are speciously appealing and that there is a general bias for them as it is a way of signaling that one is more computer-science literate.)

Related questions

Parse (split) a string in C++ using string delimiter (standard C++)

I am parsing a string in C++ using the following: using namespace std; string parsed,input="text to be parsed"; stringstream input_stringstream(input); if (getline(input_stringstream,parsed,' ')) { // do some processing. } Parsing with a single char delimiter …

Read More
How can I read and parse CSV files in C++?

I need to load and use CSV file data in C++. At this point it can really just be a comma-delimited parser (ie don't worry about escaping new lines and commas). The main need is a line-by-line parser that will …

Read More
How do I check if a C++ std::string starts with a certain string, and convert a substring to an int?

How do I implement the following (Python pseudocode) in C++? if argv[1].startswith('--foo='): foo_value = int(argv[1][len('--foo='):]) (For example, if argv[1] is --foo=98, then foo_value is 98.) Update: I'm hesitant to look into Boost, since …

Read More