lexer.hpp

C++的一个好库。。。现在很流行

    std::copy(fp.begin(), fp.end(),
            std::ostream_iterator<node_id_t>(out, ","));

    out << " lastpos() = ";
    node_set lp = lastpos();
    std::copy(lp.begin(), lp.end(),
            std::ostream_iterator<node_id_t>(out, ","));
}
#endif

template <typename ScannerT>
class make_concat
{
    typedef typename ScannerT::iterator_t iterator_type;

public:

    make_concat(std::stack<node*>& the_stack)
        : m_stack(the_stack)
        {}

    void operator()(iterator_type const &, iterator_type const &) const
    {
        node* right = m_stack.top();
        m_stack.pop();
        node* left = m_stack.top();
        m_stack.pop();
        node* newnode = new cat_node(left, right);
        m_stack.push(newnode);
    }

    std::stack<node*>& m_stack;
};

template <int CharTSize>
struct get_byte_aux;

template<>
struct get_byte_aux<1>
{
    template <typename CharT>
    unsigned char operator()(CharT c, unsigned int byte)
    {
        BOOST_ASSERT(byte == 0);
        return c;
    }
};

template<>
struct get_byte_aux<2>
{
    template <typename CharT>
    unsigned char operator()(CharT c, unsigned int byte)
    {
        static unsigned long mask[] =
        {
            0xFF00,
            0x00FF
        };

        BOOST_ASSERT(byte < 2);
        return (c & mask[byte]) >> ((sizeof(c) - 1 - byte) * 8);
    }
};

template<>
struct get_byte_aux<4>
{
    template <typename CharT>
    unsigned char operator()(CharT c, unsigned int byte)
    {
        static unsigned long mask[] =
        {
            0xFF000000,
            0x00FF0000,
            0x0000FF00,
            0x000000FF
        };

        BOOST_ASSERT(byte < 4);
        return (c & mask[byte]) >> ((sizeof(c) - 1 - byte) * 8);
    }
};

template <typename CharT>
inline unsigned char
get_byte(CharT c, unsigned int byte)
{
    return get_byte_aux<sizeof(c)>()(c, byte);
}

template <typename ScannerT>
class make_star
{
    typedef typename ScannerT::iterator_t iterator_type;

public:
    typedef
        typename BOOST_SPIRIT_IT_NS::iterator_traits<iterator_type>::value_type
        char_t;

    make_star(std::stack<node*>& the_stack)
        : m_stack(the_stack)
        {}

    void operator()(const char_t) const
    {
        node* left = m_stack.top();
        m_stack.pop();
        node* newnode = new star_node(left);
        m_stack.push(newnode);
    }

    std::stack<node*>& m_stack;
};

template <typename ScannerT>
class make_or
{
    typedef typename ScannerT::iterator_t iterator_type;

public:

    make_or(std::stack<node*>& the_stack)
        : m_stack(the_stack)
        {}

    void operator()(iterator_type const&, iterator_type const&) const
    {
        node* right = m_stack.top();
        m_stack.pop();
        node* left = m_stack.top();
        m_stack.pop();
        node* newnode = new or_node(left, right);
        m_stack.push(newnode);
    }

    std::stack<node*>& m_stack;
};

template <typename ScannerT>
class make_plus
{
    typedef typename ScannerT::iterator_t iterator_type;

public:
    typedef
        typename BOOST_SPIRIT_IT_NS::iterator_traits<iterator_type>::value_type
        char_t;

    make_plus(std::stack<node*>& the_stack)
        : m_stack(the_stack)
        {}

    void operator()(const char_t) const
    {
        node* left = m_stack.top();
        m_stack.pop();

        node* copy = left->clone();

        node* new_star = new star_node(copy);
        node* new_cat = new cat_node(left, new_star);
        m_stack.push(new_cat);
    }

    std::stack<node*>& m_stack;
};

template <typename ScannerT>
class make_optional
{
    typedef typename ScannerT::iterator_t iterator_type;

public:
    typedef
        typename BOOST_SPIRIT_IT_NS::iterator_traits<iterator_type>::value_type
        char_t;

    make_optional(std::stack<node*>& the_stack)
        : m_stack(the_stack)
        {}

    void operator()(const char_t) const
    {
        node* left = m_stack.top();
        m_stack.pop();

        node* new_or = new or_node(left, new epsilon_node());
        m_stack.push(new_or);
    }

    std::stack<node*>& m_stack;
};

///////////////////////////////////////////////////////////////////////////////
//  utility function
template <typename CharT>
inline utility::impl::range<CharT> const&
full_range()
{
    static utility::impl::range<CharT> full((std::numeric_limits<CharT>::min)(),
        (std::numeric_limits<CharT>::max)());
    return full;
}

namespace ccl_utils
{
    template <typename char_t>
    inline utility::impl::range_run<char_t>
    negate_range_run(
            const utility::impl::range_run<char_t>& rr)
    {
        utility::impl::range_run<char_t> newrr;
        newrr.set(full_range<char_t>());
        for (typename utility::impl::range_run<char_t>::const_iterator iter = rr.begin();
                iter != rr.end(); ++iter)
            newrr.clear(*iter);
        return newrr;
    }

    template <typename char_t>
    inline node*
    create_mb_node_seq(char_t c)
    {
        node* newnode = new char_node(get_byte(c, 0));
        for (unsigned int i = 1; i < sizeof(c); ++i)
        {
            node* cnode = new char_node(get_byte(c, i));
            node* top_node = new cat_node(newnode, cnode);
            newnode = top_node;
        }
        return newnode;
    }

    template <typename char_t>
    inline void
    handle_mb_char(char_t c, bool first_time,
            std::stack<node*>& stack)
    {
        node* newnode = create_mb_node_seq(c);

        if (first_time)
        {
            stack.push(newnode);
        }
        else
        {
            node* top = stack.top();
            stack.pop();

            node* newtop = new or_node(top, newnode);
            stack.push(newtop);
        }
    }

    // forward decl only
    template <typename char_t>
    inline void
    handle_mb_range(char_t c1, char_t c2, bool first_time,
            std::stack<node*>& stack);

    template <typename char_t>
    inline void
    create_nodes(const utility::impl::range_run<char_t>& rr,
            std::stack<node*>& stack)
    {

        if (sizeof(char_t) == 1)
        {
            std::vector<uchar> ccl;
            ccl.resize(256);
            for (typename utility::impl::range_run<char_t>::const_iterator iter = rr.begin();
                    iter != rr.end(); ++iter)
            {
                for (int i = iter->first; i <= iter->last; ++i)
                {
//                  this is always true because of the limited datatype
//                  BOOST_ASSERT(uchar(i) < 256 && ccl.size() == 256);
                    ccl[uchar(i)] = 1;
                }
            }

            node* new_ccl = new ccl_node(ccl);
            stack.push(new_ccl);
        }
        else
        {
            bool mb_first_time = true;
            for (typename utility::impl::range_run<char_t>::const_iterator iter = rr.begin();
                    iter != rr.end(); ++iter)
            {
                if (iter->first == iter->last)
                {
                    handle_mb_char(iter->first, mb_first_time, stack);
                }
                else
                {
                    handle_mb_range(iter->first, iter->last, mb_first_time, stack);
                }
                mb_first_time = false;
            }
        }
    }

    template <typename char_t>
    inline std::size_t
    compute_differing_byte(char_t c1, char_t c2)
    {
        std::size_t rval = 0;
        while (rval < sizeof(c1) && 
               get_byte(c1, (unsigned int)rval) == get_byte(c2, (unsigned int)rval))
        {
           ++rval;
        }
        return rval;
    }

    template <typename char_t>
    inline node*
    create_mb_node_type1(std::size_t j, char_t c1, char_t c2)
    {
        std::size_t diff = get_byte(c2, (unsigned int)j) - 
            get_byte(c1, (unsigned int)j);
        if (diff == 1) {
            return 0;
        }
        else if (diff == 2) {
            return new char_node(get_byte(c1, (unsigned int)j)+1);
        }
        else {
            return new ccl_node(get_byte(c1, (unsigned int)j)+1, 
                get_byte(c2, (unsigned int)j)-1);
        }
    }

    template <typename char_t>
    inline node *
    create_mb_node_for_byte(std::size_t i, std::size_t j, std::size_t sizem1,
            std::size_t differing_byte, char_t c1, char_t c2, node* newnode)
    {
        node* cnode;
        if (i == sizem1 && j == differing_byte && j != sizem1)
        {
            node* tmp = create_mb_node_type1(j, c1, c2);
            if (tmp == 0)
            {
                delete newnode;
                return 0;
            }
            else
                cnode = tmp;
        }
        else if (i == differing_byte && j == sizem1)
        {
            if (i != sizem1) {
                cnode = new ccl_node(get_byte(c1, (unsigned int)j), 0xFF);
            }
            else {
                cnode = new ccl_node(get_byte(c1, (unsigned int)j), 
                    get_byte(c2, (unsigned int)j));
            }
        }
        else if (i != differing_byte && i != sizem1 &&
                j == (sizem1 - i + differing_byte))
        {
            cnode = new ccl_node(get_byte(c1, (unsigned int)j)+1, 0xFF);
        }
        else if (i + j - differing_byte > sizem1) {
            cnode = new ccl_node(0, 0xFF);
        }
        else {//if (is plain)
            cnode = new char_node(get_byte(c1, (unsigned int)j));
        }

        node* top_node = new cat_node(newnode, cnode);
        return top_node;
    }

// On platforms, where wchar_t is a typedef for unsigned short, the
// comparision for a negative value is pointless
    template <bool is_signed>
    struct correct_char_aux {
    };

    template <>
    struct correct_char_aux<true> {

        template <typename char_t>
        static char_t correct(char_t c) { if (c < 0) c = 0; return c; }
    };

    template <>
    struct correct_char_aux<false> {

        template <typename char_t>
        static char_t correct(char_t c) { return c; }
    };

    template <typename char_t>
    struct correct_char
    {
        static char_t correct(char_t c)
        {
            return correct_char_aux<std::numeric_limits<char_t>::is_signed >::
                correct(c);
        }
    };

    template <typename char_t>
    inline void
    handle_mb_range(char_t c1, char_t c2, bool first_time,
            std::stack<node*>& stack)
    {
        // The algorithm can't handle negative value chars, which don't make
        // much sense anyway. This comparision is pointless for wchar_t's on
        // platforms, where wchar_t is a typedef for unsigned short

        c1 = correct_char<char_t>::correct(c1);
        //if (c1 < 0)
        //    c1 = 0;

        BOOST_ASSERT(c1 < c2);
        node* newnode = 0;
        node* savednode = 0;
        const std::size_t differing_byte = compute_differing_byte(c1, c2);
        const std::size_t sizem1 = sizeof(c1) - 1;
        const std::size_t ndb = sizem1 - differing_byte;
        for (std::size_t i = differing_byte; i < sizeof(c1); ++i)
        {
            // generate node for the first byte
            if (differing_byte == 0 && i == ndb)
            {
                node* tmp = create_mb_node_type1(0, c1, c2);
                if (tmp == 0)
                    continue;
                else
                    newnode = tmp;
            }
            else
            {
                newnode = new char_node(get_byte(c1, 0));
            }
            for (std::size_t j = 1; j < sizeof(c1); ++j)
            {
                newnode = create_mb_node_for_byte(i, j, sizem1, differing_byte,
                        c1, c2, newnode);
                if (newnode == 0)
                    goto end_outer_for;
            }

            // or together the various parts
            if (savednode)
            {
                node* top_node = new or_node(savednode, newnode);
                savednode = top_node;
            }
            else
            {
                savednode = newnode;
            }
end_outer_for:
            continue;
        }

        for (std::size_t k = 0; k < ndb; ++k)
        {
            newnode = new char_node(get_byte(c2, 0));
            for (std::size_t j = 1; j < sizeof(c2); ++j)
            {
                node* cnode;
                if (k == differing_byte && j == sizem1 && k != sizem1)
                    cnode = new ccl_node(0, get_byte(c2, (unsigned int)j));

                else if (k != differing_byte && k != sizem1 &&
                        j == (sizem1 - k + differing_byte))
                    cnode = new ccl_node(0, get_byte(c2, (unsigned int)j)-1);

                else if (k + j - differing_byte > sizem1)
                    cnode = new ccl_node(0, 0xFF);

                else //if (is plain)
                    cnode = new char_node(get_byte(c2, (unsigned int)j));