Anatomy of.. installment: extended terminals

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

Anatomy of.. installment: extended terminals

Joel de Guzman-2
Hi,

We had an example of a terminal, the int parser. next, well
investigate extended terminals, those that accept parameters.

First, we'll have another example of a simple terminal, the
bare eps parser. Like before, we start of by enabling our place holder.
But wait, we haven't really seen how we define our place holders.
It's actually quite simple. For the int_ (and friends) we
have this code:

     BOOST_SPIRIT_DEFINE_TERMINALS(
     /*...*/

         ( short_ )
         ( long_ )
         ( int_ )
         ( ulong_long )
         ( long_long )

     /*...*/
     )

Placed in support/common_terminals.hpp. Each of these is a call
to the macro, BOOST_SPIRIT_TERMINAL. Example:

     BOOST_SPIRIT_TERMINAL(int_)

which expands to:

     namespace tag { struct int_{};  }
     typedef boost::proto::terminal<tag::name>::type int__type;
     int__type const int_ = {{}};

Our eps parser also has its eps placeholder. Unlike the int_
placeholder, however, eps can stand in its own, or can accept
a parameter. eps basicallly has two forms:

     eps     // as is
     eps(c)  // with a condition

the condition can be an immediate boolean, or a function or function
object (typically phoenix expressions) that return a bool. Some
samples:

     eps
     eps(true)
     eps(f)

The parameterized forms are called semantic predicates. The parser
fails or succeeds depending on the bool condition or the result of
the function f, in the last example. The function f is evaluated not
at grammar defintion time, but at parse time. In other words, it
is lazy. All function-like parsers, that take in functions as its
arguments, like the eps(f), char_(f), lit(f), etc., are lazily
evaluated at parse time.

For terminals with function-like forms, we use a related macro:

     BOOST_SPIRIT_TERMINAL_EX(name)

Hence, for eps:

     BOOST_SPIRIT_TERMINAL_EX(eps)

Similarly, you'll see in support/common_terminals.hpp a macro
call to BOOST_SPIRIT_DEFINE_TERMINALS_EX which lists all the
extended terminals used by Spirit:

     // Our extended terminals
     BOOST_SPIRIT_DEFINE_TERMINALS_EX(
     /*...*/

         ( repeat )
         ( eps )

     /*...*/
     )

Ok, let's proceed. As before, we enable the eps terminal:

     template <>
     struct use_terminal<qi::domain, tag::eps>       // enables eps
       : mpl::true_ {};

Note again that this is in namespace boost::spirit.

Now, the actual parser (in boost::spirit::qi namespace):

     struct eps_parser : primitive_parser<eps_parser>
     {
         template <typename Context>
         struct attribute
         {
             typedef unused_type type;
         };

         template <typename Iterator, typename Context
           , typename Skipper, typename Attribute>
         bool parse(Iterator& first, Iterator const& last
           , Context& context, Skipper const& skipper
           , Attribute& attr) const
         {
             qi::skip(first, last, skipper);
             return true;
         }

         template <typename OStream, typename Context>
         void what(OStream& out, Context const& context) const
         {
             out << "eps";
         }
     };

No need to explain, I presume? It's even simpler than the int
parser. eps always returns true, but eats nothing. Well, ok,
it does a pre-skip, as all terminals do.

Then, our generator (in namespace boost::spirit::qi):

     template <typename Modifiers>
     struct make_primitive<tag::eps, Modifiers>
     {
         typedef eps_parser result_type;
         result_type operator()(unused_type, unused_type) const
         {
             return result_type();
         }
     };

Ok, there you go. But we're not done yet. We have so far dealt
with the unparameterized form of eps. For the parameterized form,
we present the semantic_predicate:

     struct semantic_predicate : primitive_parser<semantic_predicate>
     {
         template <typename Context>
         struct attribute
         {
             typedef unused_type type;
         };

         semantic_predicate(bool predicate)
           : predicate(predicate) {}

         template <typename Iterator, typename Context
           , typename Skipper, typename Attribute>
         bool parse(Iterator& first, Iterator const& last
           , Context& context, Skipper const& skipper
           , Attribute& attr) const
         {
             qi::skip(first, last, skipper);
             return predicate;
         }

         template <typename OStream, typename Context>
         void what(OStream& out, Context const& context) const
         {
             out << "semantic-predicate";
         }

         bool predicate;
     };

Again, I guess there's no need to explain how this parser
functions. It's a very trivial parser. What's interesting
is how this is hooked up. First, we enable the parameterized
form of eps:

     template <typename A0>
     struct use_terminal<qi::domain
       , terminal_ex<tag::eps, fusion::vector1<A0> >
     > : is_convertible<A0, bool> {};

This fella enables the eps form:

     eps(bool-condition)

Notice that we are picking up the:

     terminal_ex<tag::eps, fusion::vector1<A0> >

(terminal_ex is the one used for "extended" terminals when
we use the macro BOOST_SPIRIT_TERMINAL_EX)

and we enable the use_terminal only if A0 is convertible to
a bool. The fusion::vector holds the arguments passed into our
eps terminal. Here, we care only for single arguments. eps
only accepts a single argument.

Likewise, we provide its generator:

     template <typename Modifiers, typename A0>
     struct make_primitive<
         terminal_ex<tag::eps, fusion::vector1<A0> >
       , Modifiers>
     {
         typedef semantic_predicate result_type;
         template <typename Terminal>
         result_type operator()(Terminal const& term, unused_type) const
         {
             return result_type(fusion::at_c<0>(term.args));
         }
     };

We create a semantic_predicate passing in the boolean predicate
we obtained from the argument to eps (contained in the fusion
vector).

We're almost done. But we have to take care of one last detail.
So far, we've handled the /immediate/ form of eps. For eps, what's
more important is the lazy form:

     eps(f)

For that to happen, we simply need to enable the lazy form:

     template <>                       // enables eps(f)
     struct use_lazy_terminal<
         qi::domain, tag::eps, 1 /*arity*/
     > : mpl::true_ {};

Then all the lazy magic happens. use_lazy_terminal is only
concerned about 1) the domain 2) the terminal tag and 3) the
arity. The code above reads as: use lazy terminal in qi::domain
with tag eps and an arity of 1.

At parser construction time, this is all that's needed. At
parse time, the function f, passed to the eps terminal, will
be converted to a semantic_predicate. Again, take note, this
happens at parse time. The actual creation of the semantic_predicate
is delayed. Only at parse time can we truly know the boolean
predicate. For example, this may be a rule local variable, a
rule inherited attribute, and so on.

-----------------------

Attached is the full eps.hpp file. Peruse the code. Try to see how it
compares to the one in "classic' spirit. You'll be amazed :-)

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

/*=============================================================================
    Copyright (c) 2001-2008 Joel de Guzman

    Distributed under the Boost Software License, Version 1.0. (See accompanying
    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
==============================================================================*/
#if !defined(BOOST_SPIRIT_EPS_MARCH_23_2007_0454PM)
#define BOOST_SPIRIT_EPS_MARCH_23_2007_0454PM

#include <boost/spirit/home/qi/domain.hpp>
#include <boost/spirit/home/qi/skip.hpp>
#include <boost/spirit/home/qi/meta_compiler.hpp>
#include <boost/spirit/home/support/unused.hpp>
#include <boost/spirit/home/support/common_terminals.hpp>
#include <boost/fusion/include/at.hpp>
#include <boost/type_traits/is_convertible.hpp>

namespace boost { namespace spirit
{
    ///////////////////////////////////////////////////////////////////////////
    // Enablers
    ///////////////////////////////////////////////////////////////////////////
    template <>
    struct use_terminal<qi::domain, tag::eps>       // enables eps
      : mpl::true_ {};

    template <typename A0>
    struct use_terminal<qi::domain
      , terminal_ex<tag::eps, fusion::vector1<A0> > // enables eps(bool-condition)
    > : is_convertible<A0, bool> {};

    template <>                                     // enables eps(f)
    struct use_lazy_terminal<
        qi::domain, tag::eps, 1 /*arity*/
    > : mpl::true_ {};
}}

namespace boost { namespace spirit { namespace qi
{
    struct eps_parser : primitive_parser<eps_parser>
    {
        template <typename Context>
        struct attribute
        {
            typedef unused_type type;
        };

        template <typename Iterator, typename Context
          , typename Skipper, typename Attribute>
        bool parse(Iterator& first, Iterator const& last
          , Context& context, Skipper const& skipper
          , Attribute& attr) const
        {
            qi::skip(first, last, skipper);
            return true;
        }

        template <typename OStream, typename Context>
        void what(OStream& out, Context const& context) const
        {
            out << "eps";
        }
    };

    struct semantic_predicate : primitive_parser<semantic_predicate>
    {
        template <typename Context>
        struct attribute
        {
            typedef unused_type type;
        };

        semantic_predicate(bool predicate)
          : predicate(predicate) {}

        template <typename Iterator, typename Context
          , typename Skipper, typename Attribute>
        bool parse(Iterator& first, Iterator const& last
          , Context& context, Skipper const& skipper
          , Attribute& attr) const
        {
            qi::skip(first, last, skipper);
            return predicate;
        }

        template <typename OStream, typename Context>
        void what(OStream& out, Context const& context) const
        {
            out << "semantic-predicate";
        }

        bool predicate;
    };

    ///////////////////////////////////////////////////////////////////////////
    // Parser generators: make_xxx function (objects)
    ///////////////////////////////////////////////////////////////////////////
    template <typename Modifiers>
    struct make_primitive<tag::eps, Modifiers>
    {
        typedef eps_parser result_type;
        result_type operator()(unused_type, unused_type) const
        {
            return result_type();
        }
    };

    template <typename Modifiers, typename A0>
    struct make_primitive<
        terminal_ex<tag::eps, fusion::vector1<A0> >
      , Modifiers>
    {
        typedef semantic_predicate result_type;
        template <typename Terminal>
        result_type operator()(Terminal const& term, unused_type) const
        {
            return result_type(fusion::at_c<0>(term.args));
        }
    };
}}}

#endif

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
Spirit-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-devel
Reply | Threaded
Open this post in threaded view
|

Re: Anatomy of.. installment: extended terminals

Joel de Guzman-2
Hi! here's an (important) update...

So far, I've been writng code with the attribute metafunction
writen as (example):

>    template <typename Context>
>    struct attribute
>    {
>        typedef unused_type type;
>    };

This will have to be changed to:

    template <typename Iterator, typename Context>
    struct attribute;

The iterator type is needed in certain (rare) occasions.
An example is the raw[p] directive which creates an
iterator range as its attribute. There might be more
in karma.

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


-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
Spirit-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-devel
Reply | Threaded
Open this post in threaded view
|

Re: Anatomy of.. installment: extended terminals

OvermindDL1
Definitely nicely done.  Cannot wait till the next installment.

On Sun, Nov 16, 2008 at 10:11 PM, Joel de Guzman
<[hidden email]> wrote:

> Hi! here's an (important) update...
>
> So far, I've been writng code with the attribute metafunction
> writen as (example):
>
>>    template <typename Context>
>>    struct attribute
>>    {
>>        typedef unused_type type;
>>    };
>
> This will have to be changed to:
>
>    template <typename Iterator, typename Context>
>    struct attribute;
>
> The iterator type is needed in certain (rare) occasions.
> An example is the raw[p] directive which creates an
> iterator range as its attribute. There might be more
> in karma.
>
> Regards,
> --
> Joel de Guzman
> http://www.boostpro.com
> http://spirit.sf.net
>
>
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
> Build the coolest Linux based applications with Moblin SDK & win great prizes
> Grand prize is a trip for two to an Open Source event anywhere in the world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> Spirit-devel mailing list
> [hidden email]
> https://lists.sourceforge.net/lists/listinfo/spirit-devel
>

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
Spirit-devel mailing list
[hidden email]
https://lists.sourceforge.net/lists/listinfo/spirit-devel