[Snippet] a Recursive Descent Parser via TDD - recursiveDescentParser.cpp

[Phlip]

C++ newsgroupies:

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 recursiveDescentParser.h,
in a parallel post.

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
http://industrialxp.org/community/bin/view/Main/TestFirstUserInterfaces


// 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(); }