Recursive Descent Parser Hpp (Last Edit: Aug 02 2004 18:04:57)
RecentChanges Edit Search GoodStyle
Referenced By: RecursiveDescentParser, RecursiveDescentParserCpp, RecursiveDescentParserTest

I wrote a parser to solve math expressions like "3.0 ^(4 - 5)", or "3 / 8".

It's bad luck to name an interface after its implementation. This file could have been "expressionSolver.h". But naturally, if I set out to implement recursive descent parsing, that tainted my filename selection.

Below my sig is recursiveDescentParser.h, a math expression solver. Using the test framework, and test suite appearing in RecursiveDescentParserTest and RecursiveDescentParserCpp, and TestDrivenDevelopment?, I produced this little parser. Extending it to use variables, or your favorite math notation, should be relatively easy.

The primary interface is parse("1 + 3"). This returns a type that can contain either a double or a beef, which is an error message string.

The code is 'inline' due to laziness; no speed gain is implied.

--PhlIp

#ifndef RECURSIVE_DESCENT_PARSER_H_
#   define RECURSIVE_DESCENT_PARSER_H_

#   include <ctype.h>
#   include <stdexcept>
#   include <string>
#   include <assert.h>
#   include <math.h>

namespace parser {

    using std::string;

    class
Fallible_double_t
{

  //  contains either a double or a beef

    double       m_value;
  public:
    const string m_beef;

    Fallible_double_t(string beef):  m_value(0.0), m_beef(beef)  {}
    Fallible_double_t(double value):  m_value(value)  {}

    bool getValid()  {  return m_beef.size() == 0;  }

    operator double()
        {
        assert(getValid());
        return m_value;
        }
};  //  named after Barton & Nackman's Fallible type


    inline void
eatBlanks(char const * &z)
{
    while (isspace(*z))
        ++z;
}


    inline Fallible_double_t
parseTerminal(char const * &z)
{
    eatBlanks(z);
    char * end = NULL;
    double result = strtod(z, &end);

    if (z == end)
        return Fallible_double_t("syntax error");

    z = end;
    eatBlanks(z);
    return result;
}

    inline Fallible_double_t parseTerms(char const * &z);

#   define bounce_(x_) if (!x_.getValid())  return x_;


    inline Fallible_double_t
parseParentheses(char const * &z)
{
    eatBlanks(z);

    if (*z == '(')
        {
        ++z;
        Fallible_double_t contents = parseTerms(z);
        bounce_(contents);

        if (*z != ')')
            return Fallible_double_t("");

        ++z;
        eatBlanks(z);
        return contents;
        }
    return parseTerminal(z);
}



    inline Fallible_double_t
parseExponentiation(char const * &z)
{
    Fallible_double_t arg_ = parseParentheses(z);
    bounce_(arg_);
    double arg (arg_);

    while (*z == '^')
        {
        char op (*z++);
        Fallible_double_t factor = parseParentheses(z);
        bounce_(factor);
        return pow(arg, factor);
        }

    return arg;
}


    inline Fallible_double_t
parseFactors(char const * &z)
{
    Fallible_double_t arg_ = parseExponentiation(z);
    bounce_(arg_);
    double arg (arg_);

    while (*z == '*' || *z == '/')
        {
        char op (*z++);
        Fallible_double_t factor = parseExponentiation(z);
        bounce_(factor);

        switch(op)
            {
            case '*':  arg *= factor;  break;
            case '/':
                if (factor == 0.0)
                    return Fallible_double_t("division by zero error");

                arg /= factor;
                break;
            }
        }

    return arg;
}


    inline Fallible_double_t
parseTerms(char const * &z)
{
    Fallible_double_t arg_ = parseFactors(z);
    bounce_(arg_);
    double arg (arg_);

    while (*z == '+' || *z == '-')
        {
        char op (*z);
        Fallible_double_t factor = parseFactors(++z);
        bounce_(factor);

        switch(op)
            {
            case '+':  arg += factor;  break;
            case '-':  arg -= factor;  break;
            }
        }
    return arg;
}


    inline Fallible_double_t
parse(char const * input)
{
    char const * end = input;
    Fallible_double_t got = parseTerms(end);

    if (got.getValid() && input + strlen(input) != end)
        return Fallible_double_t("incomplete expression");  //  oh, you were
so close!

    return got;
}

} // namespace parser

#endif // ndef RECURSIVE_DESCENT_PARSER_H_