Recursive Descent Parser Cpp

I wrote a parser to solve math expressions like "3.0 ^(4 - 5)", or "3 / 8". Below my sig is recursiveDescentParser.cpp, the test suite that drove the implementation of the expression solver found in RecursiveDescentParserHpp. The tests use a NanoCppUnit implementation in RecursiveDescentParserTest.

Test-Driven Development works by accumulating assertions. Before the very first assertion existed...

CPPUNIT_ASSERT_CLOSE( 3.0, parse("3") );

...the parse() function could not parse anything. After I got that assertion to pass (and before writing any other assertions), parse() contained only the simplest code possible to parse a "3.0". Naturally, I used strtod().

I added the assertions, one by one, and got each to pass. Whenever the design of parse() became poor, I refactored it to improve its design. This migrated the call to strtod() from parse() to its current site, parseTerminal().

TDD can rapidly produce a robust and extensible design. When the time came to add parentheses, then exponentiation, I did not need to refactor the current design at all - I only extended it.

--PhlIp

  //  a recursive descent parser,
  //  written test-first

#include "recursiveDescentParser.h"
#include "test.h"


bool TestCase::all_tests_passed = true;
TestCase::TestCases_t TestCase::cases;


using namespace parser;

#define ASSERT_BEEF(function, beef)   \
        CPPUNIT_ASSERT_EQUAL(false, function.getValid());   \
        CPPUNIT_ASSERT_EQUAL(beef, function.m_beef);


TEST_(TestCase, term)
{
    CPPUNIT_ASSERT_CLOSE( 3.0, parse("3") );
    CPPUNIT_ASSERT_CLOSE( 2.0, parse("2") );
    CPPUNIT_ASSERT_CLOSE( 2.8, parse("2.8") );
    CPPUNIT_ASSERT_CLOSE( 2.8, parse("  2.8") );
    CPPUNIT_ASSERT_CLOSE(-2.8, parse("-2.8") );
    ASSERT_BEEF( parse(".q")   , "syntax error" );
    ASSERT_BEEF( parse("- 1.0"), "syntax error" );

}


TEST_(TestCase, sum)
{
    CPPUNIT_ASSERT_CLOSE( 5.0, parse("3 + 2") );
    CPPUNIT_ASSERT_CLOSE( 1.0, parse("3 + -2") );
    CPPUNIT_ASSERT_CLOSE(11.0, parse("3 + 8") );
    CPPUNIT_ASSERT_CLOSE(11.0, parse("3 + 4 + 4") );
    CPPUNIT_ASSERT_CLOSE( 5.0, parse("-3 + 4 + 4") );
    ASSERT_BEEF( parse("3 + .q")  , "syntax error" );
    ASSERT_BEEF( parse("3 + 12 +"), "syntax error" );
}


TEST_(TestCase, subtraction)
{
    CPPUNIT_ASSERT_CLOSE(  1.0, parse("3 - 2") );
    CPPUNIT_ASSERT_CLOSE(  5.0, parse("3 - -2") );
    CPPUNIT_ASSERT_CLOSE( -5.0, parse("3 - 8") );
    CPPUNIT_ASSERT_CLOSE( -5.0, parse("3 - 4 - 4") );
    CPPUNIT_ASSERT_CLOSE(-11.0, parse("-3 - 4 - 4") );
    CPPUNIT_ASSERT_CLOSE( -3.0, parse("-3 + 4 - 4") );
    CPPUNIT_ASSERT_CLOSE( -3.0, parse("-3 - 4 + 4") );
    ASSERT_BEEF( parse("3 - .q")  , "syntax error" );
    ASSERT_BEEF( parse("3 + 12 -"), "syntax error" );
}


TEST_(TestCase, multiplication)
{
    CPPUNIT_ASSERT_CLOSE(  6.0, parse("3 * 2") );
    CPPUNIT_ASSERT_CLOSE( -6.0, parse("3 * -2") );
    CPPUNIT_ASSERT_CLOSE( 24.0, parse("3 * 8") );
    CPPUNIT_ASSERT_CLOSE(  8.0, parse("3 * 4 - 4") );
    CPPUNIT_ASSERT_CLOSE(-19.0, parse("-3 - 4 * 4") );
    ASSERT_BEEF( parse("3 * .q")  , "syntax error" );
    ASSERT_BEEF( parse("3 - 12 *"), "syntax error" );
}


TEST_(TestCase, division)
{
    CPPUNIT_ASSERT_CLOSE(  1.5  , parse("3 / 2") );
    CPPUNIT_ASSERT_CLOSE( -1.5  , parse("3 / -2") );
    CPPUNIT_ASSERT_CLOSE(  0.375, parse("3 / 8") );
    CPPUNIT_ASSERT_CLOSE( -3.25 , parse("3 / 4 - 4") );
    CPPUNIT_ASSERT_CLOSE( -3.0  , parse("-3 / 4 * 4") );
    ASSERT_BEEF( parse("3 / .q")  , "syntax error" );
    ASSERT_BEEF( parse("3 + 12 /"), "syntax error" );
}


TEST_(TestCase, parens)
{
    CPPUNIT_ASSERT_CLOSE(  1.5  , parse("(3) / 2") );
    CPPUNIT_ASSERT_CLOSE( -1.5  , parse("(3 / -2)") );
    CPPUNIT_ASSERT_CLOSE(  0.375, parse("3 / (8)") );
    CPPUNIT_ASSERT_CLOSE( -3.0  , parse("3.0 / (4-5)") );
    CPPUNIT_ASSERT_CLOSE( -3.0  , parse("(-3.0 / 4) * 4") );
    CPPUNIT_ASSERT_CLOSE( -3.0  , parse("(-3.0 / 4)*4") );
    CPPUNIT_ASSERT_CLOSE( -3.0  , parse("3.0 / ((((4 - 5) )) )") );
    ASSERT_BEEF( parse("3.0 / (4 - 4)") , "division by zero error" );
    ASSERT_BEEF( parse("(3 / .q"), "syntax error" );
    ASSERT_BEEF( parse("3 + 12)"), "incomplete expression" );
}


TEST_(TestCase, exponentiation)
{
    CPPUNIT_ASSERT_CLOSE(   9.0     , parse("3 ^ 2") );
    CPPUNIT_ASSERT_CLOSE(   0.111111, parse("3 ^ -2") );
    CPPUNIT_ASSERT_CLOSE(6561.0     , parse("3 ^ 8") );
    CPPUNIT_ASSERT_CLOSE(  77.0     , parse("3 ^ 4 - 4") );
    CPPUNIT_ASSERT_CLOSE( 324.0     , parse("-3 ^ 4 * 4") );
    CPPUNIT_ASSERT_CLOSE(   9.0     , parse("(3) ^ 2") );
    CPPUNIT_ASSERT_CLOSE(   0.111111, parse("(3^-2)") );
    CPPUNIT_ASSERT_CLOSE(6561.0     , parse("3^(8)") );
}


TEST_(TestCase, exponentiationAndParens)
{
    CPPUNIT_ASSERT_CLOSE(   0.333333, parse("3.0 ^(4 - 5)") );
    CPPUNIT_ASSERT_CLOSE(   1.0     , parse("3.0 ^ (4-4)") );
    CPPUNIT_ASSERT_CLOSE( 324.0     , parse("(-3.0 ^ 4) * 4") );
    CPPUNIT_ASSERT_CLOSE(   0.333333, parse("3.0 ^ ((((4 - 5) )) )") );
    ASSERT_BEEF( parse("3 ^ .q")  , "syntax error" );
    ASSERT_BEEF( parse("3 + 12 ^"), "syntax error" );
}


    bool
runTests()
{
    bool result = TestCase::runTests();
    char const * determination = "";

    if (result)
        determination = "All tests passed!\n";
    else
        determination = "Tests failed...\n";

    cout << determination;
    OutputDebugString("\n");
    OutputDebugString(determination);
    OutputDebugString("\n");

    return result;
}


int main() {  return ! runTests();  }