Parsing a set of things

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Parsing a set of things

braden
I need to parse a set of things; for example {foo, bar, baz}. They can
appear in any order, but each one can occur only once. Can anyone
suggest a technique to facilitate this?

--
Braden McDaniel                           e-mail: <[hidden email]>
<http://endoframe.com>                    Jabber: <[hidden email]>




-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Braden McDaniel
braden@endoframe.com
Reply | Threaded
Open this post in threaded view
|

Re: Parsing a set of things

Joel de Guzman-2
Braden McDaniel wrote:
> I need to parse a set of things; for example {foo, bar, baz}. They can
> appear in any order, but each one can occur only once. Can anyone
> suggest a technique to facilitate this?

Ah! A permutation parser. Such a beast was suggested once but it was
not implemented (yet). See: http://tinyurl.com/8et2h.

Ok... anyone here knowledgeable in Haskell? Perhaps someone can
port this:

http://www.cs.uu.nl/groups/ST/Software/UU_Parsing/Perms2.pdf

to Spirit?

Regards,
--
Joel de Guzman
http://www.boost-consulting.com
http://spirit.sf.net



-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Parsing a set of things

Carl Barron
In reply to this post by braden

On Sep 7, 2005, at 1:14 AM, Braden McDaniel wrote:

> I need to parse a set of things; for example {foo, bar, baz}. They can
> appear in any order, but each one can occur only once. Can anyone
> suggest a technique to facilitate this?
>

Does this help?
//Cut here
#include <iostream>
#include <boost/spirit/core.hpp>
#include <boost/spirit/actor.hpp>
#include <boost/spirit/utility.hpp>

#include <set>
#include <string>

typedef std::set<std::string> Set;

namespace SP = boost::spirit;

struct test_empty
{
        Set  &not_found;
        test_empty( Set &a):not_found(a){}
        typedef SP::nil_t result_t;
        template <class Scan>
        std::ptrdiff_t operator () (const Scan &,result_t &)const
        {
                return not_found.empty()?0:-1;
        }
};

struct test_empty_p:SP::functor_parser<test_empty>
{
        test_empty_p( Set &a)
                :SP::functor_parser<test_empty>(test_empty(a)){}
};

struct in_set_impl
{
        Set &not_found;
        std::string &item;
        typedef SP::nil_t result_t;
        in_set_impl(Set &a,std::string &b):not_found(a),item(b){}
        template <class Scan>
        std::ptrdiff_t operator ()(const Scan &,SP::nil_t &)const
        {
                if(not_found.count(item))
                {
                        not_found.erase(item);
                        return 0;
                }
                return -1;
        }
};

struct in_set_p:SP::functor_parser<in_set_impl>
{
        in_set_p(Set &a,std::string &b)
        :SP::functor_parser<in_set_impl>(in_set_impl(a,b)){}
};

struct perm_g:SP::grammar<perm_g>
{
        Set the_symbols;
        perm_g(const Set &a):the_symbols(a){}

        template <class Scan>
        struct definition
        {
               
                definition(const perm_g &s)
                {
                        top = SP::eps_p
                                [SP::assign_a(not_found,s.the_symbols)]
                                >> +name
                                >> SP::end_p
                                >> test_empty_p(not_found);
                                ;
                        name = SP::lexeme_d[+SP::alpha_p]
                                [SP::assign_a(item)]
                                >> in_set_p(not_found,item)
                                ;
                }
                Set not_found;
                std::string item;
                SP::rule<Scan> top,name;
                SP::rule<Scan> const &start() const
                { return top;}
        };
};

void test_code(const Set &symbols,const char *s)
{
        perm_g g(symbols);
        std::cout << "Parse of \"" << s << '"';
       
        if(SP::parse(s,g,SP::space_p).full)
        {
                std::cout << "succeeded\n";
        }
        else
        {
                std::cout << "failed\n";
        }
}
int main()
{
        Set symbols;
        symbols.insert("foo");
        symbols.insert("bar");
        symbols.insert("baz");
        // etc.
        test_code(symbols,"foo bar bar");
        test_code(symbols,"bar foo baz");
        test_code(symbols,"baz bar foo");
}

       




-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Re: Parsing a set of things

Carl Barron
In reply to this post by Joel de Guzman-2

On Sep 7, 2005, at 9:20 PM, Joel de Guzman wrote:

> Braden McDaniel wrote:
>> I need to parse a set of things; for example {foo, bar, baz}. They can
>> appear in any order, but each one can occur only once. Can anyone
>> suggest a technique to facilitate this?
>
> Ah! A permutation parser. Such a beast was suggested once but it was
> not implemented (yet). See: http://tinyurl.com/8et2h.
>
> Ok... anyone here knowledgeable in Haskell? Perhaps someone can
> port this:
>
> http://www.cs.uu.nl/groups/ST/Software/UU_Parsing/Perms2.pdf
>
> to Spirit?
>
> Regards,
> --

   Don't know haskell, but if symbols<> hand a remove and test if empty
and a copy ctr assignment operator [probably does, did not check this]
operations the code in my other reply could use a boost::symbols<....>
instead of std::set<std::string> and probably would be more efficient.
basicly create a symbol table of all the strings in the permuted set.
and remove them if they are in the found.

in pseudo spirit.
modified_symbol<> the_symbols,not_found

        rule<Scan>    perm_test = eps_p
[SP::assign_a(not_found,the_symbols)] >>  +(not_found [erase entry
found])
                                >> SP::end_p
                                 >> if_p(not_found is empty) [SP::eps_p]
                                        .else_p[SP::nothing_p]
                                ;
that is what the posted code in another message in this thread does
with a set of strings.





-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Re: Parsing a set of things

Carl Barron

On Sep 8, 2005, at 12:16 AM, Carl Barron wrote:

>
> On Sep 7, 2005, at 9:20 PM, Joel de Guzman wrote:
>
>> Braden McDaniel wrote:
>>> I need to parse a set of things; for example {foo, bar, baz}. They
>>> can
>>> appear in any order, but each one can occur only once. Can anyone
>>> suggest a technique to facilitate this?
>>
>> Ah! A permutation parser. Such a beast was suggested once but it was
>> not implemented (yet). See: http://tinyurl.com/8et2h.
>>
>> Ok... anyone here knowledgeable in Haskell? Perhaps someone can
>> port this:
>>
>> http://www.cs.uu.nl/groups/ST/Software/UU_Parsing/Perms2.pdf
>>
>> to Spirit?
>>
>> Regards,
>> --
>
>   Don't know haskell, but if symbols<> hand a remove and test if empty
> and a copy ctr assignment operator [probably does, did not check this]
> operations the code in my other reply could use a boost::symbols<....>
> instead of std::set<std::string> and probably would be more efficient.
> basicly create a symbol table of all the strings in the permuted set.
> and remove them if they are in the found.
>
> in pseudo spirit.
> modified_symbol<> the_symbols,not_found
>
> rule<Scan>    perm_test = eps_p
> [SP::assign_a(not_found,the_symbols)] >>  +(not_found [erase entry
> found])
> >> SP::end_p
> >> if_p(not_found is empty) [SP::eps_p]
> .else_p[SP::nothing_p]
> ;
> that is what the posted code in another message in this thread does
> with a set of strings.
>
>
   This will work using boost::symbols as is:

#include <boost/spirit/core.hpp>
#include <boost/spirit/utility.hpp>
#include <boost/spirit/symbols.hpp>

#include <string>

namespace SP = boost::spirit;

struct create_table
{
        SP::symbols<> &found;
        create_table(SP::symbols<> &a)
                :found(a){}
        template <class I>
        void operator () (I,I) const
        {
                found = SP::symbols<>();
        }
};

struct test_parser_impl
{
        bool &test;
        test_parser_impl(bool &a):test(a){}
        typedef SP::nil_t result_t;
        template <class Scan>
        std::ptrdiff_t operator () (const Scan &,result_t &)const
        {
                return test ?0:-1;
        }
};

struct test_parser:SP::functor_parser<test_parser_impl>
{
        test_parser(bool &a)
                :SP::functor_parser<test_parser_impl>(test_parser_impl(a))
                {}
};

struct store_data
{
        SP::symbols<> &found;
        bool &tester;
        store_data(SP::symbols<> &a,bool &b):found(a),tester(b){}
       
        template <class I>
        void operator ()(I begin,I end) const
        {
                std::string str(begin,end);
                tester = SP::add(found,str.c_str(),0);
        }
};
               

struct perm_g:SP::grammar<perm_g>
{
        SP::symbols<> &the_symbols;
       
        perm_g(SP::symbols<> &a):the_symbols(a){}
       
        template <class Scan>
        struct definition
        {
                SP::symbols<> found;
                bool tester;
                definition(const perm_g &s)
                {
                        item = (s.the_symbols >> SP::eps_p) // get beginning and ending
iterators of match
                                        [store_data(found,tester)]  // if not found and a symbol add set
tester
                                >> test_parser(tester) // succeed if tester is true.
                                ;
                        terms = SP::eps_p[create_table(found)]
                                >> +item
                                ;
                }
                SP::rule<Scan> item,terms;
                SP::rule<Scan> const &start() const
                { return terms;}
        };
};

#include <iostream>

namespace
{
        struct symbols:SP::symbols<>
        {
                symbols()
                {
                        add("foo",0);
                        add("bar",0);
                        add("baz",0);
                }
        };
       
        void do_parse(const char *s)
        {
                symbols the_symbols;
                perm_g g(the_symbols);
                std::cout << "Parse of \"" << s << '"';
                if(SP::parse(s,g,SP::space_p).full)
                {
                        std::cout << " succeeded\n";
                }
                else
                        std::cout << " failed\n";
        }
}

int main()
{
        do_parse("foo baz bar");
        do_parse("abs foo bar");
        do_parse("foo baz baz");
};



-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general
Reply | Threaded
Open this post in threaded view
|

Re: Re: Parsing a set of things

Carl Barron

On Sep 10, 2005, at 6:01 AM, Carl Barron wrote:

>
> On Sep 8, 2005, at 12:16 AM, Carl Barron wrote:
>
>>
>> On Sep 7, 2005, at 9:20 PM, Joel de Guzman wrote:
>>
>>> Braden McDaniel wrote:
>>>> I need to parse a set of things; for example {foo, bar, baz}. They
>>>> can
>>>> appear in any order, but each one can occur only once. Can anyone
>>>> suggest a technique to facilitate this?
>>>
>>> Ah! A permutation parser. Such a beast was suggested once but it was
>>> not implemented (yet). See: http://tinyurl.com/8et2h.
>>>
>>> Ok... anyone here knowledgeable in Haskell? Perhaps someone can
>>> port this:
>>>
>>> http://www.cs.uu.nl/groups/ST/Software/UU_Parsing/Perms2.pdf
>>>
>>> to Spirit?
>>>
>>> Regards,
>>> --
>>
>>   Don't know haskell, but if symbols<> hand a remove and test if empty
>> and a copy ctr assignment operator [probably does, did not check this]
>> operations the code in my other reply could use a boost::symbols<....>
>> instead of std::set<std::string> and probably would be more efficient.
>> basicly create a symbol table of all the strings in the permuted set.
>> and remove them if they are in the found.
>>
>> in pseudo spirit.
>> modified_symbol<> the_symbols,not_found
>>
>> rule<Scan>    perm_test = eps_p
>> [SP::assign_a(not_found,the_symbols)] >>  +(not_found [erase entry
>> found])
>> >> SP::end_p
>> >> if_p(not_found is empty) [SP::eps_p]
>> .else_p[SP::nothing_p]
>> ;
>> that is what the posted code in another message in this thread does
>> with a set of strings.
>>
>>
>   This will work using boost::symbols as is:
>
> #include <boost/spirit/core.hpp>
> #include <boost/spirit/utility.hpp>
> #include <boost/spirit/symbols.hpp>
> {
>
   Opps must also count entries found and compare against the number of
items, but this
code contains the ideas.



-------------------------------------------------------
SF.Net email is Sponsored by the Better Software Conference & EXPO
September 19-22, 2005 * San Francisco, CA * Development Lifecycle Practices
Agile & Plan-Driven Development * Managing Projects & Teams * Testing & QA
Security * Process Improvement & Measurement * http://www.sqe.com/bsce5sf
_______________________________________________
Spirit-general mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-general