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

Discussion in 'C++' started by Phlip, Aug 2, 2004.

  1. Phlip

    Phlip Guest

    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(); }
     
    Phlip, Aug 2, 2004
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Phlip
    Replies:
    6
    Views:
    435
    Phlip
    Aug 5, 2004
  2. Phlip
    Replies:
    0
    Views:
    427
    Phlip
    Aug 2, 2004
  3. Replies:
    4
    Views:
    459
    Ben Sizer
    Oct 2, 2006
  4. Just Another Victim of the Ambient Morality

    Is pyparsing really a recursive descent parser?

    Just Another Victim of the Ambient Morality, Nov 2, 2007, in forum: Python
    Replies:
    39
    Views:
    1,405
    Kay Schluehr
    Nov 9, 2007
  5. Robert
    Replies:
    1
    Views:
    582
    Puppet_Sock
    Apr 14, 2008
Loading...

Share This Page