Subject: [Boost-commit] svn:boost r61578 - trunk/libs/spirit/example/scheme/test/qi
From: joel_at_[hidden]
Date: 2010-04-26 12:22:27
Author: djowel
Date: 2010-04-26 12:22:26 EDT (Mon, 26 Apr 2010)
New Revision: 61578
URL: http://svn.boost.org/trac/boost/changeset/61578
Log:
calculator working. memoization saved the day.
Text files modified:
trunk/libs/spirit/example/scheme/test/qi/calc.scm | 43 +++-----
trunk/libs/spirit/example/scheme/test/qi/qi_interpreter.cpp | 184 ++++++++++++++++++++++++++-------------
2 files changed, 141 insertions(+), 86 deletions(-)
Modified: trunk/libs/spirit/example/scheme/test/qi/calc.scm
==============================================================================
--- trunk/libs/spirit/example/scheme/test/qi/calc.scm (original)
+++ trunk/libs/spirit/example/scheme/test/qi/calc.scm 2010-04-26 12:22:26 EDT (Mon, 26 Apr 2010)
@@ -2,32 +2,23 @@
(define expression) ; forward declaration
-(define expression
- (qi:>> (qi:int_)
+(define factor
+ (qi:|
+ (qi:int_)
+ (qi:>> (qi:char_ "(") (expression) (qi:char_ ")"))
+ (qi:>> (qi:char_ "-") (factor))
+ (qi:>> (qi:char_ "+") (factor))))
+
+(define term
+ (qi:>> (factor)
(qi:*
(qi:|
- (qi:>> (qi:char_ "+") (qi:int_))
- (qi:>> (qi:char_ "-") (qi:int_))))))
-
-; (define expression)
-
-; (define factor
- ; (qi:|
- ; (qi:int_)
- ; (qi:>> (qi:char_ "(") (expression) (qi:char_ ")"))
- ; (qi:>> (qi:char_ "-") (factor))
- ; (qi:>> (qi:char_ "+") (factor))))
+ (qi:>> (qi:char_ "*") (factor))
+ (qi:>> (qi:char_ "/") (factor))))))
-; (define term
- ; (qi:>> (factor)
- ; (qi:*
- ; (qi:|
- ; (qi:>> (qi:char_ "*") (factor))
- ; (qi:>> (qi:char_ "/") (factor))))))
-
-; (define expression
- ; (qi:>> (term)
- ; (qi:*
- ; (qi:|
- ; (qi:>> (qi:char_ "+") (term))
- ; (qi:>> (qi:char_ "-") (term))))))
\ No newline at end of file
+(define expression
+ (qi:>> (term)
+ (qi:*
+ (qi:|
+ (qi:>> (qi:char_ "+") (term))
+ (qi:>> (qi:char_ "-") (term))))))
\ No newline at end of file
Modified: trunk/libs/spirit/example/scheme/test/qi/qi_interpreter.cpp
==============================================================================
--- trunk/libs/spirit/example/scheme/test/qi/qi_interpreter.cpp (original)
+++ trunk/libs/spirit/example/scheme/test/qi/qi_interpreter.cpp 2010-04-26 12:22:26 EDT (Mon, 26 Apr 2010)
@@ -30,7 +30,7 @@
namespace spirit = boost::spirit;
typedef qi::rule<char const*> skipper_type;
- typedef qi::rule<char const*, utree(), skipper_type> rule_type;
+ typedef qi::rule<char const*, skipper_type> rule_type;
///////////////////////////////////////////////////////////////////////////
// All rule are stored here. Rules are held in the utree by its id;
@@ -46,13 +46,18 @@
{
};
- template <typename Expr>
- int new_rule(Expr const& expr)
+ int new_rule()
{
- rules[index] = expr;
+ rules[index];
return index++;
}
+ template <typename Expr>
+ void define_rule(int id, Expr const& expr)
+ {
+ rules[id] = expr;
+ }
+
Rule const& operator[](int id) const
{
typename std::map<int, Rule>::const_iterator
@@ -95,7 +100,9 @@
inline primitive_parser_composite
make_primitive_parser_composite(Fragments& fragments, Expr const& expr)
{
- return primitive_parser_composite(fragments.new_rule(expr));
+ int id = fragments.new_rule();
+ fragments.define_rule(id, expr);
+ return primitive_parser_composite(id);
}
///////////////////////////////////////////////////////////////////////////
@@ -104,22 +111,23 @@
template <typename Fragments>
struct char_function : actor<char_function<Fragments> >
{
- Fragments& fragments;
+ mutable int id;
function a;
function b;
+ Fragments& fragments;
char_function(
Fragments& fragments, function const& a, function const& b)
- : a(a), b(b), fragments(fragments)
+ : id(-1), a(a), b(b), fragments(fragments)
{
}
- utree eval() const
+ void define() const
{
// char_
- return fragments.new_rule(qi::char_);
+ fragments.define_rule(id, qi::char_);
}
- utree eval(utree const& a) const
+ void define(utree const& a) const
{
// $$$ use exceptions here $$$.
BOOST_ASSERT(a.which() == utree_type::string_type);
@@ -128,17 +136,17 @@
if (a_.size() == 1)
{
// char_('x')
- return fragments.new_rule(qi::char_(a_[0]));
+ fragments.define_rule(id, qi::char_(a_[0]));
}
else
{
// char_("some-regex")
- return fragments.new_rule(
+ fragments.define_rule(id,
qi::char_(std::string(a_.begin(), a_.end())));
}
}
- utree eval(utree const& a, utree const& b) const
+ void define(utree const& a, utree const& b) const
{
// $$$ use exceptions here $$$.
BOOST_ASSERT(a.which() == utree_type::string_type);
@@ -151,17 +159,23 @@
BOOST_ASSERT(b_.size() == 1);
// char_('x', 'y')
- return fragments.new_rule(qi::char_(a_[0], b_[0]));
+ fragments.define_rule(id, qi::char_(a_[0], b_[0]));
}
utree eval(scope const& env) const
{
+ if (id != -1)
+ return id;
+ id = fragments.new_rule();
+
if (a.empty())
- return eval();
+ define();
else if (b.empty())
- return eval(a(env));
+ define(a(env));
else
- return eval(a(env), b(env));
+ define(a(env), b(env));
+
+ return id;
}
};
@@ -191,22 +205,27 @@
template <typename Fragments>
struct kleene_function : actor<kleene_function<Fragments> >
{
- Fragments& fragments;
+ mutable int id;
function a;
+ Fragments& fragments;
kleene_function(
Fragments& fragments, function const& a)
- : a(a), fragments(fragments)
+ : id(-1), a(a), fragments(fragments)
{
}
- utree eval(utree const& a) const
+ void define(utree const& a) const
{
- return fragments.new_rule(*fragments[a]); // *a
+ fragments.define_rule(id, *fragments[a]); // *a
}
utree eval(scope const& env) const
{
- return eval(a(env));
+ if (id != -1)
+ return id;
+ id = fragments.new_rule();
+ define(a(env));
+ return id;
}
};
@@ -231,24 +250,29 @@
template <typename Fragments>
struct difference_function : actor<difference_function<Fragments> >
{
- Fragments& fragments;
+ mutable int id;
function a;
function b;
+ Fragments& fragments;
difference_function(
Fragments& fragments, function const& a, function const& b)
- : a(a), b(b), fragments(fragments)
+ : id(-1), a(a), b(b), fragments(fragments)
{
}
- utree eval(utree const& a, utree const& b) const
+ void define(utree const& a, utree const& b) const
{
- return fragments.new_rule(
+ fragments.define_rule(id,
fragments[a] - fragments[b]); // a - b
}
utree eval(scope const& env) const
{
- return eval(a(env), b(env));
+ if (id != -1)
+ return id;
+ id = fragments.new_rule();
+ define(a(env), b(env));
+ return id;
}
};
@@ -277,48 +301,53 @@
template <typename Fragments>
struct sequence_function : actor<sequence_function<Fragments> >
{
- Fragments& fragments;
+ mutable int id;
actor_list elements;
+ Fragments& fragments;
sequence_function(
Fragments& fragments, actor_list const& elements)
- : elements(elements), fragments(fragments)
+ : id(-1), elements(elements), fragments(fragments)
{
}
- utree eval(utree const& a, utree const& b) const
+ void define(utree const& a, utree const& b) const
{
// a >> b
- return fragments.new_rule(
+ fragments.define_rule(id,
fragments[a] >> fragments[b]);
}
- utree eval(utree const& a, utree const& b, utree const& c) const
+ void define(utree const& a, utree const& b, utree const& c) const
{
// a >> b >> c
- return fragments.new_rule(
+ fragments.define_rule(id,
fragments[a] >> fragments[b] >> fragments[c]);
}
- utree eval(utree const& a, utree const& b, utree const& c,
+ void define(utree const& a, utree const& b, utree const& c,
utree const& d) const
{
// a >> b >> c >> d
- return fragments.new_rule(
+ fragments.define_rule(id,
fragments[a] >> fragments[b] >> fragments[c] >>
fragments[d]);
}
- utree eval(utree const& a, utree const& b, utree const& c,
+ void define(utree const& a, utree const& b, utree const& c,
utree const& d, utree const& e) const
{
// a >> b >> c >> d >> e
- return fragments.new_rule(
+ fragments.define_rule(id,
fragments[a] >> fragments[b] >> fragments[c] >>
fragments[d] >> fragments[e]);
}
utree eval(scope const& env) const
{
+ if (id != -1)
+ return id;
+ id = fragments.new_rule();
+
actor_list::const_iterator i = elements.begin();
switch (elements.size())
{
@@ -326,14 +355,16 @@
{
function const& a = *i++;
function const& b = *i;
- return eval(a(env), b(env));
+ define(a(env), b(env));
+ break;
}
case 3:
{
function const& a = *i++;
function const& b = *i++;
function const& c = *i;
- return eval(a(env), b(env), c(env));
+ define(a(env), b(env), c(env));
+ break;
}
case 4:
{
@@ -341,7 +372,8 @@
function const& b = *i++;
function const& c = *i++;
function const& d = *i;
- return eval(a(env), b(env), c(env), d(env));
+ define(a(env), b(env), c(env), d(env));
+ break;
}
case 5:
{
@@ -350,12 +382,13 @@
function const& c = *i++;
function const& d = *i++;
function const& e = *i;
- return eval(a(env), b(env), c(env), d(env), e(env));
+ define(a(env), b(env), c(env), d(env), e(env));
+ break;
}
// $$$ Use Boost PP using SCHEME_QI_COMPILER_LIMIT $$$
}
- return utree();
+ return id;
}
};
@@ -380,48 +413,53 @@
template <typename Fragments>
struct alternative_function : actor<alternative_function<Fragments> >
{
- Fragments& fragments;
+ mutable int id;
actor_list elements;
+ Fragments& fragments;
alternative_function(
Fragments& fragments, actor_list const& elements)
- : elements(elements), fragments(fragments)
+ : id(-1), elements(elements), fragments(fragments)
{
}
- utree eval(utree const& a, utree const& b) const
+ void define(utree const& a, utree const& b) const
{
// a | b
- return fragments.new_rule(
+ fragments.define_rule(id,
fragments[a] | fragments[b]);
}
- utree eval(utree const& a, utree const& b, utree const& c) const
+ void define(utree const& a, utree const& b, utree const& c) const
{
// a | b | c
- return fragments.new_rule(
+ fragments.define_rule(id,
fragments[a] | fragments[b] | fragments[c]);
}
- utree eval(utree const& a, utree const& b, utree const& c,
+ void define(utree const& a, utree const& b, utree const& c,
utree const& d) const
{
// a | b | c | d
- return fragments.new_rule(
+ fragments.define_rule(id,
fragments[a] | fragments[b] | fragments[c] |
fragments[d]);
}
- utree eval(utree const& a, utree const& b, utree const& c,
+ void define(utree const& a, utree const& b, utree const& c,
utree const& d, utree const& e) const
{
// a | b | c | d | e
- return fragments.new_rule(
+ fragments.define_rule(id,
fragments[a] | fragments[b] | fragments[c] |
fragments[d] | fragments[e]);
}
utree eval(scope const& env) const
{
+ if (id != -1)
+ return id;
+ id = fragments.new_rule();
+
actor_list::const_iterator i = elements.begin();
switch (elements.size())
{
@@ -429,14 +467,16 @@
{
function const& a = *i++;
function const& b = *i;
- return eval(a(env), b(env));
+ define(a(env), b(env));
+ break;
}
case 3:
{
function const& a = *i++;
function const& b = *i++;
function const& c = *i;
- return eval(a(env), b(env), c(env));
+ define(a(env), b(env), c(env));
+ break;
}
case 4:
{
@@ -444,7 +484,8 @@
function const& b = *i++;
function const& c = *i++;
function const& d = *i;
- return eval(a(env), b(env), c(env), d(env));
+ define(a(env), b(env), c(env), d(env));
+ break;
}
case 5:
{
@@ -453,12 +494,13 @@
function const& c = *i++;
function const& d = *i++;
function const& e = *i;
- return eval(a(env), b(env), c(env), d(env), e(env));
+ define(a(env), b(env), c(env), d(env), e(env));
+ break;
}
// $$$ Use Boost PP using SCHEME_QI_COMPILER_LIMIT $$$
}
- return utree();
+ return id;
}
};
@@ -574,11 +616,33 @@
}
interpreter parser(in, filename, &env);
+ rule_type calc = fragments[parser["expression"]()].alias();
+ std::string str;
+
+ while (std::getline(std::cin, str))
+ {
+ if (str.empty() || str[0] == 'q' || str[0] == 'Q')
+ break;
- //~ fragments[parser["expression"]()];
+ char const* iter = str.c_str();
+ char const* end = iter + strlen(iter);
+ bool r = phrase_parse(iter, end, calc, space);
- BOOST_TEST(!test("1 + 1",
- fragments[parser["expression"]()], space));
+ if (r && iter == end)
+ {
+ std::cout << "-------------------------\n";
+ std::cout << "Parsing succeeded\n";
+ std::cout << "-------------------------\n";
+ }
+ else
+ {
+ std::string rest(iter, end);
+ std::cout << "-------------------------\n";
+ std::cout << "Parsing failed\n";
+ std::cout << "stopped at: \": " << rest << "\"\n";
+ std::cout << "-------------------------\n";
+ }
+ }
}