OOP Recursive Decent Parsing I

First off we need to define what our parser is going to do; we need to a construct a set of terminals and non-terminals to work with, in other words a “grammar.” Let’s look at the following grammar.

expr -> term ‘+’ term
expr -> term ‘-‘ term
exor -> term
term -> unary ‘*’ unary
term -> unary ‘/’ unary
term -> unary
unary -> ‘-‘ factor
unary -> ‘+’ factor
unary -> factor
factor -> '(' expr ')'
factor -> number

In this case a factor is either a number or an expression enclosed by parenthesis, a factor could be a symbol or string literal, as well. For the purpose of this tutorial we will just use numbers. Also we are using a fairly limited set of operators

Let’s get down to business. First we want to set things up a bit; we want to predefine our classes and create some building blocks.

#ifndef PARSER_H_INCLUDED
#define PARSER_H_INCLUDED

#include <istream>
#include <deque>
#include <exception>

//pre-declare are classes so they can be used in a non-discriminate order
class Production;
class Expr;
class Term;
class Unary;
class Number;
class Factor;
class ParseError;

/**
* the base class for all of our productions
*/
class Production {
public:
 virtual ~Production(); //dose nothing, if we don't need to override it we don't want to
 virtual double getValue()=0; //pure virtual, all children MUST implmnet this function
};

/**
* a simple class to handle parsing errors
*/
class ParseError : public std::exception {
 const char* what() const throw();
};

Artikel Terkait: