I wrote a C++ PEG packrat parser generator and would love to get some feedback on the code and/or syntax. I currently use the << operator for defining grammar expressions and linking the handler functions that are called when a rule is matched. These functions can then store a value of an arbitrary C++ type in the corresponding node of the parse tree using the value<type>() function.

For example, a very simple math parser can be generated through the following source code:

#include "IO.h"
#include "parserTools.h"
#include <cmath> //pow

using namespace llib;

std::map<std::string, double> variables;

void op(parser::info &lhs,parser::info &rhs,parser::info &r,const std::string &op){
  if(op[0]=='+')      r.value() =     lhs.value<double>() + rhs.value<double>() ;
  else if(op[0]=='-') r.value() =     lhs.value<double>() - rhs.value<double>() ;
  else if(op[0]=='*') r.value() =     lhs.value<double>() * rhs.value<double>() ;
  else if(op[0]=='/') r.value() =     lhs.value<double>() / rhs.value<double>() ;
  else if(op[0]=='^') r.value() = pow(lhs.value<double>() , rhs.value<double>());

void variable(parser::info &s){ s.value<double>()=variables[s.string()];             }
void negate(parser::info &s)  { s.value()=-s[0].value<double>();                     }
void set(parser::info &s)     { variables[s[0].string()]=s[1].value<double>();       }

int main(){
  peg::grammar math("Math");

  math << "Math"        << "Set | Expression"                           << parserTools::show("%v0\n");
  math << "Set"         << "Variable '=' Sum"                           << set << parserTools::pass(1);
  math << "Expression"  << "Sum"                                        << parserTools::pass();
  math << "Sum"         << "Product  ([+-] Product )*"                  << parserTools::leftbinary(op);
  math << "Product"     << "Exponent ([*/] Exponent)*"                  << parserTools::leftbinary(op);
  math << "Exponent"    << "Atomic   ('^'  Atomic  )*"                  << parserTools::leftbinary(op);
  math << "Atomic"      << "Parentheses | Number | Negate | Variable"   << parserTools::pass();
  math << "Parentheses" << "'(' Expression ')'"                         << parserTools::pass();
  math << "Negate"      << "'-' Atomic"                                 << negate;
  math << "Variable"    << "[a-zA-Z] [a-zA-Z0-9]*"                      << variable;
  math << "Number"      << parserTools::doubleGrammar()                 << parserTools::pass();

  math.ignored=" \t";

  parser p(math);


  while (1) {
    std::string str;
    IO << "> " >> str << str << " -> ";
    if(str=="q") break;
    else if(str!="") p.parse(str);
    else IO << clearline << endl;

  return 0;

The full code and documentation is available on GitHub (though LParser is probably pretty boring name).

So any thoughts on the project? Is it something you would actually use?

void op(parser::info &lhs,parser::info &rhs,parser::info &r,const std::string &op){

I think I'd prefer a more descriptive name than r here. I'm guessing it's intended to stand for "result", in which case I think I'd prefer to just name it result.

  peg::grammar math("Math");

  math << "Math" << "Set | Expression" << parserTools::show("%v0\n");

It's not immediately clear why you specify Math both when you create the grammar object and when you specify rules. I think the second is naming the top-level rule Math, but it's not clear what the parameter to the constructor accomplishes.

  math << "Set" << "Variable '=' Sum" << set << parserTools::pass(1);

At least without some documentation on your parserTools, the meaning of the pass(1) isn't immediately obvious. Presumably this is (at least roughly equivalent to) a semantic rule that's executed when the associated pattern is matched. I can think of a couple of different things pass(1) might be intended to mean, but lac, context to even guess at which is likely to be accurate. Sufficient study of your documentation would undoubtedly make the meaning clear, but it wasn't immediately obvious.

This is kind of a difficult situation: you're basically defining an EDSL, which means understanding the code pretty much requires learning the language you've defined. In other words, no matter how carefully or well written the code is, it's likely to be at least somewhat difficult to understand in isolation.

Summary: looking at the code in isolation, the grammar rules are highly readable, but the (presumed) associated actions much less so.

math << "Exponent" << "Atomic   ('^'  Atomic  )*" << parserTools::leftbinary(op);

At first glance, I'd have assumed that leftbinary was intended to signify a left-associative binary operator--but exponentiation is normally right-associative. I'm left uncertain whether:

  1. it's a bug,
  2. you intentionally changed it from right- to left-associative, or
  3. I've completely misinterpreted what leftbinary really means.

  while (1) {
    std::string str;
    IO << "> " >> str << str << " -> ";

I have mixed feelings about this mixture of input and output in the same expression. It does lead to relatively terse code, but requires unusual care in reading to keep track of which parts are input vs. output.

Ultimately, I think it would probably be better to review the parser generator and the IO library separately. Here I'm really concentrating on the parser generator, but the design if the I/O library might well be worth examination and review in its own right.

|improve this answer|||||
  • \$\begingroup\$ Completely right, I forgot about the right-associativeness of the exponentiation operator. I have re-written the project with your input in mind (and ditched the ParserTools concept). I've submitted a new codereview question here. \$\endgroup\$ – Lars Melchior Dec 8 '14 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.