Stream-Based Parsing in C++

This paper shows how to implement general parsers as a family of streams. This allows for very readable, maintainable and flexible parsers. The method is illustrated with a parser for simple arithmetic expressions, but can easily be extended to a parser for a full-fledged programming language. Moreover, the same technique can be applied to the entire process from lexing to execution, since actions can be associated with each sub-parser.

The parsing of input is a very important problem appearing in many different parts of software development - parsing user input in the form of command-line options, the parsing of arithmetic expressions in a calculator, parsing values in a user-defined configuration file or compiling some programming language.

This makes it important to have different approaches. What we will present here in this paper, is a method of parsing inspired by what is done in functional programming (FP). The paper is not about functional programming in C++Moreover, the presence of too many parentheses makes the code harder to read and is hence also more error prone.^[1], rather it is about how to implement a particularly elegant idea from FP in an object oriented context.

The entire process, from lexical analysis to actual execution of a program can be divided into a number of individual steps:

source -> lexer -> parser -> optimiser
       -> execution -> output

In FP, this could be represented by a family of functions:

output = execution o optimiser o parser
         o lexer(source)

The advantage of this approach is flexibility: it is easy to omit or modify individual steps, which is important for playing around with different approaches in language design or compiler construction.

One could attempt to implement the different sub-parsers as functions or (better) function objects in C++. The disadvantage of doing so, however, is the proliferation of parentheses this would entail. In C++ there is no operator for function (or functor) composition corresponding to ^o above (which may be called many different things in a functional language - e.g. a period or simply the letter 'o'). Nor can such an operator be defined in a natural way - none of the overloadable operators are well suited for becoming composition operators^[2].

Moreover, the presence of too many parentheses makes the code harder to read and is hence also more error prone.

One can consider a function as a stream, however. Instead of writing x=f(y) one could try to write x << f << y. Here, we do have a natural operator for composition, namely the stream operator <<. This suggests considering the entire process as a collection of streams:

output << execution << optimiser
       << parser << lexer << source

This won't work, however, since << is left-associative. Hence, either one needs to introduce parentheses once more, e.g., write x << (f << y) and so on, or one will need to use another, right-associative operator. The former case will automatically suffer from the abovementioned problems with using function objects.

Consequently, we will have to use a right-associative operator instead. Unfortunately, C++ does not allow one to declare an operator to have a user-defined associativity, so instead we will have to replace << by one of the right-associative operators defined by C++. There are very, very few of these. In fact, the only binary rightassociative operators are the assignment operators +=, *=,.... Thus, the simplest possible change is to use operator<<=. This also has the added advantage of resembling an arrow, more showing the direction of the flow of data.

Now, even though strictly speaking the sub-parsers won't be stream objects, we will still refer to them as such by analogy to ordinary streams (I/O stream, file streams, string streams) present in C++. The reason being that the defining feature of a stream is its ability to process input and to be pipelined, which is precisely what our generalised stream will do.

In this paper, we will concentrate on the parsing step, but in such a way that the remaining steps of the process could be implemented in a similar fashion. In fact, we will see how to make a simple modification to our parser and turn it into an expression calculator. For concreteness, we will consider a particular example, which is simple enough not to introduce unnecessary complications yet complex enough to be non-trivial. The chosen example is the parsing of arithmetic expressions like 1+(2-3)*4. We will only consider integers^[3]. Furthermore, we will not worry about the precedence levels of the standard arithmetic operators - this could be done by slightly modifying the grammar as shown in for instance, [Martin]. It will be shown later how to accommodate this with very few changes to our framework.

Hence, the basic ingredients in our language are:

<digit>    ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 |
               7 | 8 | 9
<operator> ::= + | - | * | /
<lpar>     ::= (
<rpar>     ::= )

To this we add the definition of a number as a sequence of one or more digits:

<num> ::= <digit>+

Now, a simple expression is either a number on its own or it is two numbers separated by an operator:

<simexp> ::= <num> | <num> <operator> <num>

Such an expression is the smallest string composed from the symbols which makes sense in this simple language. A general expression can then be built like this:

<exp> ::= <simexp> | <lpar> <exp> <rpar>
                   | <exp> <operator> <exp>

Actually, the simple expression is redundant and could be omitted by replacing the first option in the production for <exp>. In any case, the set of rules above constitute the entire grammar.

The basic idea in the FP-style of parsing is to split-up the parser into a family of sub-parsers each corresponding to a term in the grammar, with special combinators corresponding to ways of combining these sub-parsers (there will be one for combining them - often just standard function composition in an FP-language - and one for representing options in the BNF grammar), see [Hutton, Fokker, Peyton-Jones-]. For a way to implement part of this in another multi-paradigm language, Perl, see [Antonsen].

In the functional language Miranda, for instance, one could write a parser for this simple language like this (following [Hutton] and ignoring problems with left-recursive grammars for sake of illustration):

exp = (exp $then operator $xthen exp) $alt
      (literal '(' $then exp $xthen
      literal ')') $alt simexp

Here, exp, then, xthen, alt, literal and simexp are all sub-parsers (the prefix '$' turns any function into an infix operator in Miranda, and brackets around arguments are optional in Miranda as well as in Haskell and ML). The sub-parser operator simply parses operators, while the sub-parser literal parses the literal string given as the argument, and alt is a sub-parser representing alternatives as given by the symbol '|' in the BNF grammar. We won't be able to reach the same level of conciseness in this C++ implementation though, but we will try to get as close as possible.

Such parsers may not be as efficient as the ones generated by general high-quality parser-writing tools such as lex and yacc (and their various relatives such as flex and bison from GNU), but they have other advantages:

For simplicity, we will assume that the lexing has been done and resulted in an array of single characters. This is of course a rather trivial lexing (which, moreover, is easy to implement) - most lexers would return not a list of characters but a list of tokens. In order to show the power of the technique, however, it is advantageous to consider such trivial lexers. Such a lexer, for instance, could be implemented by simply reading from a file, one character at a time, returning a list of characters read when done.

This paper will be structured as follows: First, the abstract base class is defined. This is a very basic class skeleton, but will form the foundation of all the richer sub-parsers to be defined later. At the same time we define the basic parse tree class and other related datatypes. Secondly, we introduce some simple general utilities (a Boolean function for testing for digits and two list processing functions found in all functional languages). Next, we define our first generic sub-parsers for numbers and operators. The fourth step is to define general parser combinators, allowing us to combine subparsers to generate new types of sub-parsers.

All of these steps are completely general and form a basic parsing library. We then turn to using these general tools to actually parse integer arithmetic expressions. This turns out to be very easy and there is a very, very close relationship between the BNF grammar and the actual implementation of the sub-parsers as promised.

Finally, we discuss various ways to refine the framework.

We will begin by defining a general parse stream or pstream. The various sub-parsers will then all be derived from this base class. The parser will need to keep track of a list which is passed on between consecutive parses. Even though, we will only consider lists of single characters here, it is worthwhile to work with a more general set-up, namely that of lists of strings.

Our pstreams will have a state, containing the parse tree constructed so far. In order to be able to pipe pstreams together, thereby building more complex parsers from simple sub-parsers, we will also need the pstream to keep track of the remaining tokens.

Hence, we define a new data type:

typedef std::pair<Ptree, List> Presult;

where Ptree is the class defining parse trees and where List is defined by:

typedef std::list<std::string> List;

which will be our basic data structure. Similarly, Ptree is a specialisation of a more general parse tree:

typedef ParseTree<std::string> Ptree;

The ParseTree class is a simple binary tree:

template <class T>
class ParseTree {
private:
  ParseTree *left; // left sub tree
  ParseTree *right; // right sub tree
  T root;
public:
  ... // constructors & destructor
  bool isEmpty() const { return root==T(); }
  bool isLeaf() const
               { return left==0 && right==0; }
  T getRoot() const { return root; }
  ParseTree* getLeft() const { return left; }
  ParseTree* getRight() const
               { return right; }
  void setLeft(ParseTree& lft) { left = &lft; }
  void setRight(ParseTree& rgh)
               { right = &rgh; }
  void setRoot(T rt) { root = rt; }
  void update(T); // used for operators
  void insert(T); // used for numbers
  void insert(ParseTree&);
               // used for parentheses
};

The member functions update and insert are there to allow parsers to manipulate the parse tree. The former adds a node as the root, copying the old tree to the left sub-tree, this is to be used when parsing binary operators. The latter inserts a node at the first empty sub-tree it finds. This is used for parsing either numbers or parentheses.

Using just recursion these methods could be implemented simply like this:

template<class T>
void ParseTree<T>::update(T val) {
  if(isEmpty())
    throw std::logic_error(
           "Syntax error: Missing operand");
  ParseTree* newLeftSubtree
           = new ParseTree(*this);
  root = val;
  left = newLeftSubtree;
  right = 0;
}

template<class T>
void ParseTree<T>::insert(T val) {
  if(isEmpty()) {
    setRoot(val);
    return;
  }
  if(getLeft() == 0) {
    setLeft(*new ParseTree(val));
    return;
  }
  else {
    if(getRight() == 0) {
      setRight(*new ParseTree(val));
      return;
    }
    getRight()->insert(val);
               // use right recursion
  }
}

template<class T>
void ParseTree<T>::insert(ParseTree<T> &pt) {
  if(isEmpty()) {
    setRoot(pt.getRoot());
    setLeft(*pt.getLeft());
    setRight(*pt.getRight());
    return;
  }
  if(getLeft() == 0) {
    setLeft(pt);
    return;
  }
  else {
    if(getRight() == 0) {
      setRight(pt);
      return;
    }
    getRight()->insert(pt);
               // use right recursion
  }
}

The if-statements in the above implementations are the C++ analogue of the argument pattern matching of functional languages^[4], they are needed to control the recursive steps and to ensure termination. The code above can be shortened a little bit and most of the return-statements can be omitted if on instead uses nested if-clauses. While this will make the code a few lines shorter, I think the present coding style has the advantage of clearly showing the reader that the function returns after having handled each special case.

Both methods first handle the case of an empty tree. For insert, the value passed simply becomes the new root, whereas for update an exception is thrown. Next comes the case of a leaf, i.e., a node without children. Here, update inserts the passed value as a new root moving the leaf to the left subtree, while insert merely inserts its value as the left subtree rooted at the original leaf node. If the left subtree is occupied, insert first tries the right one, if this is also non-empty it uses recursion to find the first empty subtree.

The abstract base class, pstream is now:

class pstream {
protected:
  Presult pres; // contents so far
public:
  ... // constructors & virtual destructor
  List const& getList() const
           { return pres.second; } // accessor method
  Presult const& getPres() const
           { return pres; } // accessor method
  virtual Presult operator<<=
           (const List &) = 0;
  virtual Presult operator<<=
           (const Presult&) = 0;
};

Notice that only the accessor methods, getList and getPres, are non-trivial and that the streaming operator, operator<<= is a pure virtual function.

We will now turn to the question of actually writing the parser by splitting it up into a number of sub-parsers as stated in the introduction.

bool isDigit(std::string c) {
  return c == "0" || c == "1" || c == "2"
         || c == "3" || c == "4" || c == "5"
         || c == "6" || c == "7" || c == "8"
         || c == "9";
}

string head(List ls) {
  return ls.front();
}

List tail(List ls) {
  ls2.pop_front(); // remove head
  return ls2;
}

class pNum : public pstream {
public:
  pNum() {};
  pNum(const List & ls)
         { pres = make_pair(Ptree(),ls); };
  pNum(const Presult &pt) { pres = pt; };
  pNum() {};
  inline Presult operator<<=(const List &);
  inline Presult operator<<=(const Presult &);
};

inline Presult pNum::operator<<=(
                           const List &ls) {
  return operator<<=(make_pair(Ptree(),ls));
}

inline Presult pNum::operator<<=(
                           const Presult &pr) {
  List ls = pr.second;
  if(ls.empty())
    return pr; // nothing to parse
  std::string c = head(ls);
  if(!isDigit(c)) {
    return pr; // not a number, do nothing
  }
  else {
    std::string val(c);
    ls = tail(ls);
    while(isDigit(c=head(ls)) && !ls.empty()) {
      val += c; // construct number
      ls = tail(ls);
    }
    Ptree pt(pr.first);
    pt.insert(val);
    return make_pair(pt,ls);
  }
}

inline Presult pOp::operator<<=
                    (const Presult &pt) {
  List ls = pt.second;
  if(ls.empty())
    return pt; // nothing to parse
  std::string c = head(ls);
  if(!isOperator(c))
    return pt;
  Ptree ptt(pt.first);
  ptt.update(c);
  return make_pair(ptt,tail(ls));
}

template <class T, class S>
class pAlt : public pstream {
private:
  T p1;
  S p2; // component pstreams
public:
  ... // constructors & destructor
      // & accessors & operator<<=
};

template<class T, class S>
inline pAlt<T, S> operator||
                (const T& p1, const S& p2) {
  return pAlt<T, S>(p1,p2);
            // alternative way of creating pAlt objects
}
// definition of how pAlt works is given
// by operator<<=
template<class T, class S>
inline Presult pAlt<T, S>::operator<<=
                (const Presult& pr) {
  Presult lp1(p1 <<= pr), lp2(p2 <<= pr);
            // use component parsers
  List l1=lp1.second, l2=lp2.second;
  return (l1.size() <= l2.size())? lp1 : lp2;
            // return best parse
}

template<class T, class S>
class pThen : public pstream {
private:
  T p1;
  S p2; // component parsers
public:
  ... // usual stuff
};

template<class T, class S>
inline pThen<T, S> operator&&
                 (const T& p1, const S& p2) {
  return pThen<T,S>(p1,p2);
    // alternative syntax
}
template<class T, class S>
inline Presult pThen<T, S>::operator<<=
                 (const Presult& pr) {
  return p2 <<= p1 <<= pr;
}

template<class T>
class pMore : public pstream {
private:
  T p; // component parser
public:
  ... // usual stuff
};

template<class T>
inline Presult pMore<T>::operator<<=
                   (const Presult& pr) {
  Presult pr2(p <<= pr);
  List ls = pr.second;
  List ls2 = pr2.second;
  while(!ls2.empty() && (ls2.size()
                 < ls.size())) { // something was parsed
    pr2 = (p <<= pr2); // continue parsing
    ls = ls2;
    ls2 = pr2.second;
  } 
  return pr2;
}
template<class T>
inline pMore<T> operator++(const T pp) {
  return pMore<T>(pp);
}

pNum = ++(pLit("0") || pLit("1") || pLit("2")
       || pLit("3") || pLit("4") || pLit("5")
       || pLit("6") || pLit("7") || pLit("8")
       || pLit("9"));

template<class T>
class pBrack : public pstream {
private:
  T p; // internal sub-parser
  Presult pr2;
public:
  ... // usual stuff
};

template<class T>
inline Presult pBrack<T>::operator<<=
                   (const Presult &pr) {
  if( (pr.second).empty() )
    throw logic_error("Syntax error.
                      Closing bracket expected!");
  std::string c = head(pr.second);
  if(c == "(") {
    Presult prr( p <<= make_pair
                   (pr.first, tail(pr.second)) );
    // apply internal parser
    (pr2.first).insert(prr.first);
    // update internal parse tree
    return operator<<=
                  (make_pair(pr.first, prr.second));
  }
  if(c == ")") {
    Ptree pt(pr.first);
    pt.insert(pr2.first);
    // insert parsed subtree
    return make_pair(pt,tail(pr.second));
    //skip closing bracket & terminate recursion
  }
  return pr; // do nothing
}

We now have all the ingredients needed for parsing integer arithmetic expressions. One could put the previous classes and functions into general header files to be used for all parsers, and then proceed to write parsers for the specific language at hand, which is what we will turn to now.

Now, the grammar is recursive and while C++ is certainly capable of handling recursion (in fact, we have used it frequently in this paper), the language is not really capable of handling recursive definitions such as the grammar in its present state. Hence, we will have to introduce an extra layer of indirection. Rewrite the grammar as:

<aexp> ::= <num> | <num> <op> <num>
<sexp> ::= <aexp> | <lpar> <aexp> <rpar>
<exp>  ::= <sexp> | <lpar> <sexp> <rpar>
           | <sexp> <op> <sexp>

The idea is now simply to write three parsers pAExp, pSExp and pExp. These classes are completely trivial, with all the work being done in operator<<= as usual.

The first sub-parser is:

inline Presult pAExp::operator<<=
                     (const Presult &pr) {
  pOp po;
  pNum pn;
  return pn || (pn && po && pn) <<= pr;
}

Notice the simple expression in the last line. It is a simple, faithful reflection of the definition of the corresponding term in the BNF grammar.

The remaining sub-parser, pSExp, and final parser, pExp, are very simple and only their non-trivial operator<<= function will be given.

For pSExp the code is simply:

inline Presult pSExp::operator<<=
                    (const Presult &pr) {
  pAExp pa;
  return pa || pBrack<pAExp>(pa) <<= pr;
}

Which, once more, is a faithful representation of the corresponding definition in the BNF grammar.

Finally, the full parser, parsing general integer arithmetic expressions is simply:

inline Presult pExp::operator<<=
                   (const Presult &pr) {
  pSExp ps;
  pOp po;
  return ps || pBrack<pSExp>(ps)
            || (ps && po && ps) <<= pr;
}

Hence, with the generic sub-parser tools defined, writing a functional style parser using pstreams is an easy task, which makes it well suited for language experiments and for rapid prototyping.

With these definitions in place, to parse a list of characters, ls, using this parser, one simply writes:

pExp pe;
result = pe <<= ls;

where result is of type Presult. For a complete parse, this would contain a parse tree as first component and an empty list as second.

The previous sections have shown one way to implement functional-style parsing in C++ using a generalisation of streams together with operator overloading. Incidentally, the heavy usage of operator overloading shows one advantage of C++ over a language like Java that does not support the overloading of operators. Most of the above could also be carried out in Java, but one would then have to use functions instead of operators resulting in harder to read code. Java also lacks C++'s features for generic programming (the templates), although a library providing some of this support is available. Some of the same effects could be mimicked in Java, however, by judicious use of the universal base class Object and frequent casting. Such an approach will not be as easy to read and will, moreover, be more error prone than the one presented here. Although a direct translation of the above C++ code into Java would not be satisfactory, one could instead use Java Beans - in some sense, these are able to model a behaviour similar to that of functions in a functional language.

On the other hand, C++ is not perfect in this respect either, since it lacks the possibility of user defined operators as well as a method to specify the associativity of an operator and whether it is to be applied as infix, postfix or prefix. Such possibilities are often available in FP languages, e.g. in ML and Haskell, and they are also likely to be available in future versions of existing languages such as Perl6.

The necessity of writing the execution from right to left lies in the standard OO-convention that y<<=f is really short for y.operator<<=(f) and hence treats the left hand operand differently from the right hand one. This is a consequence of OOP's dispatching rules. If one wanted to make left-to-right parsing work instead, one would have to define, inside all classes, methods for handling the different parsestreams. For instance, one would have to define List::operator>>=(T &p), where the typename T can be any valid parsestream subclass. This could of course be done with templates much the same way as was done for the combinators, but it would also necessitate the writing of a wrapper class for the List-object in order to be able to extend it this way. A much cleaner solution would be to use multi-methods. However, unlike Lisp's CLOS, these are not directly available in C++. There are ways around this, of course, C++ being after all a very flexible language, [Alexandrescu].

A problem not addressed at all in this paper is the problem of optimisation. Clearly, the parsestreams as developed here are optimised neither for speed of execution nor for space, but rather for speed of definition. By this phrase, it is to be understood that the method is intended for rapid prototyping and for experimenting with language features. Although the program isn't slow, it would certainly be advantageous to have the parsestreams run faster in real-life applications. One simple way of doing this is to pass a tree-iterator around keeping track of where the last insert/update of the parsetree occurred, for instance by pointing to the first empty subtree. This would speed up the insert and update operations.

<expr>     ::= <term> + <term> | <term> - <term>
               | <term>
<term>     ::= <factor> * <factor>
               | <factor> / <factor> | <factor>
<factor>   ::= <number> | ( <expr> )

typedef std::list< Presult > LPresult;

template<class T, class S>
class pUse : public pstream {
private:
  T p; // component parser
  S f; // function to apply
public:
  ... // usual stuff
};
template<class T, class S>
inline Presult pUse<T,S>::operator<<=(const
                 Presult& pr) {
  Presult pr2(p <<= pr); // apply parser
  return f(pr2); // apply function - MUST return Presult
}
template<class T, class S>
inline pUse<T,S> operator>>=
                 (const T &pp, const S &ff) {
  return pUse<T,S>(pp,ff);
                     // alternative syntax
}

class printer {
public:
  Presult operator() (Presult &pr) const {
    std::cout << "Parse tree: ";
    (pr.first).print();
    std::cout << std::endl << " and ";
    prList(pr.second);
    return pr;
  }
};

pUse<pExp,printer> pu(pe,prn);
pu <<= ls;

(pe >>= prn) <<= ls;

We were able to extend the functional-style parsing using subparsers to C++ by defining a generalised class of streams, called pstreams. With this, we could define combinators allowing us to build new sub-parsers by combining old ones. With these general tools out of the way, it turned out to be very easy, once recursion had been handled properly, to implement the BNF grammar for integer arithmetic expressions. Moreover, similarly to the situation in FP, there was a very intimate relationship, in fact more or less an isomorphism, between the actual BNF production rule and the corresponding sub-parser, making it very easy to write such sub-parsers - it would even be feasible to write a general sub-parser generator to do so automatically.

It was also shown how to handle operator precedence and, perhaps even more importantly, ambiguous grammars. None of this involved major changes to the framework, thus the proposed framework scales well to more complicated grammars such as those of typical programming languages.

Moreover, we showed how one could associate actions to individual sub-parsers thereby dramatically extending the possibilities of stream-based parsing. The associated actions could be used to create a pretty printer, or even to translate or execute the code.