generator.hpp

Boost provides free peer-reviewed portable C++ source libraries. We emphasize libraries that work

            if (!end_state_)
            {
                end_state_ = true;
                id_ = node_->id ();
                state_ = node_->lexer_state ();
            }
        }

        if (set_ptr_->insert (node_).second)
        {
            vector_ptr_->push_back (node_);
            hash_ += reinterpret_cast<std::size_t> (node_);
        }
    }

    static void partition_tokens (const token_map &map_,
        charset_list &lhs_)
    {
        charset_list rhs_;

        fill_rhs_list (map_, rhs_);

        if (!rhs_->empty ())
        {
            typename charset_list::list::iterator iter_;
            typename charset_list::list::iterator end_;
            charset_ptr overlap_ (new charset);

            lhs_->push_back (0);
            lhs_->back () = rhs_->front ();
            rhs_->pop_front ();

            while (!rhs_->empty ())
            {
                charset_ptr r_ (rhs_->front ());

                rhs_->pop_front ();
                iter_ = lhs_->begin ();
                end_ = lhs_->end ();

                while (!r_->empty () && iter_ != end_)
                {
                    typename charset_list::list::iterator l_iter_ = iter_;

                    (*l_iter_)->intersect (*r_.get (), *overlap_.get ());

                    if (overlap_->empty ())
                    {
                        ++iter_;
                    }
                    else if ((*l_iter_)->empty ())
                    {
                        delete *l_iter_;
                        *l_iter_ = overlap_.release ();

                        // VC++ 6 Hack:
                        charset_ptr temp_overlap_ (new charset);

                        overlap_ = temp_overlap_;
                        ++iter_;
                    }
                    else if (r_->empty ())
                    {
                        delete r_.release ();
                        r_ = overlap_;

                        // VC++ 6 Hack:
                        charset_ptr temp_overlap_ (new charset);

                        overlap_ = temp_overlap_;
                        break;
                    }
                    else
                    {
                        iter_ = lhs_->insert (++iter_, 0);
                        *iter_ = overlap_.release ();

                        // VC++ 6 Hack:
                        charset_ptr temp_overlap_ (new charset);

                        overlap_ = temp_overlap_;
                        ++iter_;
                        end_ = lhs_->end ();
                    }
                }

                if (!r_->empty ())
                {
                    lhs_->push_back (0);
                    lhs_->back () = r_.release ();
                }
            }
        }
    }

    static void fill_rhs_list (const token_map &map_,
        charset_list &list_)
    {
        typename parser::tokeniser::token_map::const_iterator iter_ =
            map_.begin ();
        typename parser::tokeniser::token_map::const_iterator end_ =
            map_.end ();

        for (; iter_ != end_; ++iter_)
        {
            list_->push_back (0);
            list_->back () = new charset (iter_->first, iter_->second);
        }
    }

    static void fill_lookup (const string_token &token_,
        size_t_vector *lookup_, const std::size_t index_)
    {
        const CharT *curr_ = token_._charset.c_str ();
        const CharT *chars_end_ = curr_ + token_._charset.size ();
        std::size_t *ptr_ = &lookup_->front ();
        const std::size_t max_ = sizeof (CharT) == 1 ?
            num_chars : num_wchar_ts;

        if (token_._negated)
        {
            CharT curr_char_ = sizeof (CharT) == 1 ? -128 : 0;
            std::size_t i_ = 0;

            while (curr_ < chars_end_)
            {
                while (*curr_ > curr_char_)
                {
                    ptr_[static_cast<typename Traits::index_type>
                        (curr_char_)] = index_ + dfa_offset;
                    ++curr_char_;
                    ++i_;
                }

                ++curr_char_;
                ++curr_;
                ++i_;
            }

            for (; i_ < max_; ++i_)
            {
                ptr_[static_cast<typename Traits::index_type>(curr_char_)] =
                    index_ + dfa_offset;
                ++curr_char_;
            }
        }
        else
        {
            while (curr_ < chars_end_)
            {
                ptr_[static_cast<typename Traits::index_type>(*curr_)] =
                    index_ + dfa_offset;
                ++curr_;
            }
        }
    }

    static void build_equiv_list (const node_vector *vector_,
        const index_set_vector &set_mapping_, equivset_list &lhs_)
    {
        equivset_list rhs_;

        fill_rhs_list (vector_, set_mapping_, rhs_);

        if (!rhs_->empty ())
        {
            typename equivset_list::list::iterator iter_;
            typename equivset_list::list::iterator end_;
            equivset_ptr overlap_ (new equivset);

            lhs_->push_back (0);
            lhs_->back () = rhs_->front ();
            rhs_->pop_front ();

            while (!rhs_->empty ())
            {
                equivset_ptr r_ (rhs_->front ());

                rhs_->pop_front ();
                iter_ = lhs_->begin ();
                end_ = lhs_->end ();

                while (!r_->empty () && iter_ != end_)
                {
                    typename equivset_list::list::iterator l_iter_ = iter_;

                    (*l_iter_)->intersect (*r_.get (), *overlap_.get ());

                    if (overlap_->empty ())
                    {
                        ++iter_;
                    }
                    else if ((*l_iter_)->empty ())
                    {
                        delete *l_iter_;
                        *l_iter_ = overlap_.release ();

                        // VC++ 6 Hack:
                        equivset_ptr temp_overlap_ (new equivset);

                        overlap_ = temp_overlap_;
                        ++iter_;
                    }
                    else if (r_->empty ())
                    {
                        delete r_.release ();
                        r_ = overlap_;

                        // VC++ 6 Hack:
                        equivset_ptr temp_overlap_ (new equivset);

                        overlap_ = temp_overlap_;
                        break;
                    }
                    else
                    {
                        iter_ = lhs_->insert (++iter_, 0);
                        *iter_ = overlap_.release ();

                        // VC++ 6 Hack:
                        equivset_ptr temp_overlap_ (new equivset);

                        overlap_ = temp_overlap_;
                        ++iter_;
                        end_ = lhs_->end ();
                    }
                }

                if (!r_->empty ())
                {
                    lhs_->push_back (0);
                    lhs_->back () = r_.release ();
                }
            }
        }
    }

    static void fill_rhs_list (const node_vector *vector_,
        const index_set_vector &set_mapping_, equivset_list &list_)
    {
        typename node_vector::const_iterator iter_ =
            vector_->begin ();
        typename node_vector::const_iterator end_ =
            vector_->end ();

        for (; iter_ != end_; ++iter_)
        {
            const detail::node *node_ = *iter_;

            if (!node_->end_state ())
            {
                std::size_t token_ = node_->token ();

                if (token_ != null_token)
                {
                    list_->push_back (0);

                    if (token_ == bol_token || token_ == eol_token)
                    {
                        std::set<std::size_t> index_set_;

                        index_set_.insert (token_);
                        list_->back () = new equivset (index_set_,
                            node_->greedy (), node_->token (), node_->followpos ());
                    }
                    else
                    {
                        list_->back () = new equivset (set_mapping_[token_],
                            node_->greedy (), node_->token (), node_->followpos ());
                    }
                }
            }
        }
    }

    static void fixup_bol (detail::node * &root_,
        node_ptr_vector &node_ptr_vector_)
    {
        typename detail::node::node_vector *first_ = &root_->firstpos ();
        bool found_ = false;
        typename detail::node::node_vector::const_iterator iter_ =
            first_->begin ();
        typename detail::node::node_vector::const_iterator end_ =
            first_->end ();

        for (; iter_ != end_; ++iter_)
        {
            const detail::node *node_ = *iter_;

            found_ = !node_->end_state () && node_->token () == bol_token;

            if (found_) break;
        }

        if (!found_)
        {
            node_ptr_vector_->push_back (0);
            node_ptr_vector_->back () = new detail::leaf_node (bol_token, true);

            detail::node *lhs_ = node_ptr_vector_->back ();

            node_ptr_vector_->push_back (0);
            node_ptr_vector_->back () = new detail::leaf_node (null_token, true);

            detail::node *rhs_ = node_ptr_vector_->back ();

            node_ptr_vector_->push_back (0);
            node_ptr_vector_->back () =
                new detail::selection_node (lhs_, rhs_);
            lhs_ = node_ptr_vector_->back ();

            node_ptr_vector_->push_back (0);
            node_ptr_vector_->back () =
                new detail::sequence_node (lhs_, root_);
            root_ = node_ptr_vector_->back ();
        }
    }

    static void minimise_dfa (const std::size_t dfa_alphabet_,
        size_t_vector &dfa_, std::size_t size_)
    {
        const std::size_t *first_ = &dfa_.front ();
        const std::size_t *second_ = 0;
        const std::size_t *end_ = first_ + size_;
        std::size_t index_ = 1;
        std::size_t new_index_ = 1;
        std::size_t curr_index_ = 0;
        index_set index_set_;
        size_t_vector lookup_;
        std::size_t *lookup_ptr_ = 0;

        lookup_.resize (size_ / dfa_alphabet_, null_token);
        lookup_ptr_ = &lookup_.front ();
        *lookup_ptr_ = 0;
        // Only one 'jam' state, so skip it.
        first_ += dfa_alphabet_;

        for (; first_ < end_; first_ += dfa_alphabet_, ++index_)
        {
            for (second_ = first_ + dfa_alphabet_, curr_index_ = index_ + 1;
                second_ < end_; second_ += dfa_alphabet_, ++curr_index_)
            {
                if (index_set_.find (curr_index_) != index_set_.end ())
                {
                    continue;
                }

                // Some systems have memcmp in namespace std.
                using namespace std;

                if (memcmp (first_, second_, sizeof (std::size_t) *
                    dfa_alphabet_) == 0)
                {
                    index_set_.insert (curr_index_);
                    lookup_ptr_[curr_index_] = new_index_;
                }
            }

            if (lookup_ptr_[index_] == null_token)
            {
                lookup_ptr_[index_] = new_index_;
                ++new_index_;
            }
        }

        if (!index_set_.empty ())
        {
            const std::size_t *front_ = &dfa_.front ();
            size_t_vector new_dfa_ (front_, front_ + dfa_alphabet_);
            typename index_set::iterator set_end_ =
                index_set_.end ();
            const std::size_t *ptr_ = front_ + dfa_alphabet_;
            std::size_t *new_ptr_ = 0;

            new_dfa_.resize (size_ - index_set_.size () * dfa_alphabet_, 0);
            new_ptr_ = &new_dfa_.front () + dfa_alphabet_;
            size_ /= dfa_alphabet_;

            for (index_ = 1; index_ < size_; ++index_)
            {
                if (index_set_.find (index_) != set_end_)
                {
                    ptr_ += dfa_alphabet_;
                    continue;
                }

                new_ptr_[end_state_index] = ptr_[end_state_index];
                new_ptr_[id_index] = ptr_[id_index];
                new_ptr_[state_index] = ptr_[state_index];
                new_ptr_[bol_index] = lookup_ptr_[ptr_[bol_index]];
                new_ptr_[eol_index] = lookup_ptr_[ptr_[eol_index]];
                new_ptr_ += dfa_offset;
                ptr_ += dfa_offset;

                for (std::size_t i_ = dfa_offset; i_ < dfa_alphabet_; ++i_)
                {
                    *new_ptr_++ = lookup_ptr_[*ptr_++];
                }
            }

            dfa_.swap (new_dfa_);
        }
    }
};

typedef basic_generator<char> generator;
typedef basic_generator<wchar_t> wgenerator;
}
}

#endif