lexer.hpp

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

/*=============================================================================
    Boost.Wave: A Standard compliant C++ preprocessor library

    Spirit based lexer
    
    http://www.boost.org/

    Copyright (c) 2001, Daniel C. Nuffer.
    Copyright (c) 2001-2008 Hartmut Kaiser. 
    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)

    TODO List:
        X callback objects (called when a match is made.)
        X    callback passed first & last iterator, and
                a reference to a lexercontrol object that supports some
                operations on the lexer.
                    set state
                    terminate
                    state stack (push, pop, top)
                    set new token return value
                    ignore the current token
                    yymore
                    get length of matched token
                    get current lexer state
        X DFA serialization to save recomputing the DFA.

        lexer states.
        organize the file into hpp and ipp. arrange the classes in a logical order.
        use buffering - iterator only needs be an input iterator,
           lexer & callback are not templatized on iterator type, but char type.
           next_token is templatized on iterator type.
        beginning/ending contexts.
        ^ and $
        DFA minimization.
        DFA table compression.

=============================================================================*/
#ifndef BOOST_SPIRIT_LEXER_HPP
#define BOOST_SPIRIT_LEXER_HPP

///////////////////////////////////////////////////////////////////////////////
#include <boost/throw_exception.hpp>

#include <boost/spirit/include/classic_core.hpp>
#include <boost/spirit/include/classic_symbols.hpp>
#include <boost/spirit/include/classic_chset.hpp>
#include <boost/spirit/include/classic_escape_char.hpp>

#include <set>
#include <map>
#include <vector>
#include <stack>
#include <utility> // for pair
#include <iostream>
#include <fstream>
#include <boost/assert.hpp>
#include <boost/limits.hpp>

#if defined(BOOST_NO_STD_ITERATOR_TRAITS)
#define BOOST_SPIRIT_IT_NS impl
#else
#define BOOST_SPIRIT_IT_NS std
#endif

///////////////////////////////////////////////////////////////////////////////
namespace boost {
namespace spirit {
namespace classic {

typedef unsigned char uchar;
typedef unsigned int node_id_t;
const node_id_t invalid_node = node_id_t(-1);
typedef std::set<node_id_t> node_set;
typedef std::vector<uchar> uchar_vector;
typedef std::map<node_id_t, node_set> followpos_t;
typedef std::vector<uchar_vector> state_match_t;

template <typename TokenT>
class lexer_control;

class bad_regex : public std::exception
{
};

namespace lexerimpl
{

class node
{
public:

    virtual ~node() {}

    virtual node* clone() const = 0;
    virtual bool nullable() const = 0;
    virtual node_set firstpos() const = 0;
    virtual node_set lastpos() const = 0;
    virtual void compute_followpos(followpos_t& followpos) const = 0;
    virtual void compute_state_match(state_match_t& state_match) const = 0;
    virtual void get_eof_ids(node_set& eof_set) const = 0;
    virtual void assign_node_ids(node_id_t& node_count) = 0;
#if defined(BOOST_SPIRIT_DEBUG) && (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_SLEX)
    virtual void dump(std::ostream& out) const = 0;
#endif

};

class char_node : public node
{

public:

    char_node(const uchar c);
    char_node(const char_node& x);
    virtual ~char_node(){}

    virtual node* clone() const;
    virtual bool nullable() const;
    virtual node_set firstpos() const;
    virtual node_set lastpos() const;
    virtual void compute_followpos(followpos_t& followpos) const;
    virtual void compute_state_match(state_match_t& state_match ) const;
    virtual void get_eof_ids(node_set& eof_set) const;
    virtual void assign_node_ids(node_id_t& node_count);
#if defined(BOOST_SPIRIT_DEBUG) && (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_SLEX)
    virtual void dump(std::ostream& out) const;
#endif

private:

    uchar m_char;
    node_id_t m_node_num;
};

inline
char_node::char_node(const uchar c)
    : node()
    , m_char(c)
    , m_node_num(0)
{
}

inline
char_node::char_node(const char_node& x)
    : node(x)
    , m_char(x.m_char)
    , m_node_num(x.m_node_num)
{
}

inline node *
char_node::clone() const
{
    return new char_node(*this);
}

inline bool
char_node::nullable() const
{
    return false;
}

inline node_set
char_node::firstpos() const
{
    node_set rval;
    rval.insert(m_node_num);
    return rval;
}

inline node_set
char_node::lastpos() const
{
    return firstpos();
}

inline void
char_node::compute_followpos(followpos_t&) const
{
    return;
}

inline void
char_node::compute_state_match(state_match_t& state_match) const
{
    if (state_match.size() < m_node_num + 1)
        state_match.resize(m_node_num + 1);
    state_match[m_node_num].resize(256);
    state_match[m_node_num][m_char] = 1;
}

inline void
char_node::get_eof_ids(node_set&) const
{
    return;
}

inline void
char_node::assign_node_ids(node_id_t& node_count)
{
    m_node_num = node_count++;
}

#if defined(BOOST_SPIRIT_DEBUG) && (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_SLEX)
inline void
char_node::dump(std::ostream& out) const
{
    out << "\nchar_node m_char = " << m_char;
    out << " m_node_num = " << m_node_num;
    out << " nullable() = " << (nullable() ? "true" : "false");
    out << " firstpos() = ";
    node_set fp = firstpos();
    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


class epsilon_node : public node
{

public:

    epsilon_node();
    epsilon_node(const epsilon_node& x);
    virtual ~epsilon_node(){}

    virtual node* clone() const;
    virtual bool nullable() const;
    virtual node_set firstpos() const;
    virtual node_set lastpos() const;
    virtual void compute_followpos(followpos_t& followpos) const;
    virtual void compute_state_match(state_match_t& state_match ) const;
    virtual void get_eof_ids(node_set& eof_set) const;
    virtual void assign_node_ids(node_id_t& node_count);
#if defined(BOOST_SPIRIT_DEBUG) && (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_SLEX)
    virtual void dump(std::ostream& out) const;
#endif

private:

    node_id_t m_node_num;
};

inline
epsilon_node::epsilon_node()
    : node()
    , m_node_num(0)
{
}

inline
epsilon_node::epsilon_node(const epsilon_node& x)
    : node(x)
    , m_node_num(x.m_node_num)
{
}

inline node *
epsilon_node::clone() const
{
    return new epsilon_node(*this);
}

inline bool
epsilon_node::nullable() const
{
    return true;
}

inline node_set
epsilon_node::firstpos() const
{
    return node_set();
}

inline node_set
epsilon_node::lastpos() const
{
    return node_set();
}

inline void
epsilon_node::compute_followpos(followpos_t&) const
{
    return;
}

inline void
epsilon_node::compute_state_match(state_match_t& state_match) const
{
    if (state_match.size() < m_node_num + 1)
        state_match.resize(m_node_num + 1);
    state_match[m_node_num].resize(256, 1);
}

inline void
epsilon_node::get_eof_ids(node_set&) const
{
    return;
}

inline void
epsilon_node::assign_node_ids(node_id_t& node_count)
{
    m_node_num = node_count++;
}

#if defined(BOOST_SPIRIT_DEBUG) && (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_SLEX)
inline void
epsilon_node::dump(std::ostream& out) const
{
    out << "\nepsilon_node";
    out << " m_node_num = " << m_node_num;
    out << " nullable() = " << (nullable() ? "true" : "false");
    out << " firstpos() = ";
    node_set fp = firstpos();
    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


class or_node : public node
{

public:

    or_node(node* left, node* right);
    or_node(const or_node& x);
    virtual ~or_node(){}

    virtual node* clone() const;
    virtual bool nullable() const;
    virtual node_set firstpos() const;
    virtual node_set lastpos() const;
    virtual void compute_followpos(followpos_t& followpos) const;
    virtual void compute_state_match(state_match_t& state_match ) const;
    virtual void get_eof_ids(node_set& eof_set) const;
    virtual void assign_node_ids(node_id_t& node_count);
#if defined(BOOST_SPIRIT_DEBUG) && (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_SLEX)
    virtual void dump(std::ostream& out) const;
#endif

private:

    std::auto_ptr<node> m_left;
    std::auto_ptr<node> m_right;
};

inline
or_node::or_node(node* left, node* right)
    : node()
    , m_left(left)
    , m_right(right)
{
}

inline
or_node::or_node(const or_node& x)
    : node(x)
    , m_left(x.m_left->clone())
    , m_right(x.m_right->clone())
{
}

inline node *
or_node::clone() const
{
    return new or_node(m_left->clone(), m_right->clone());
}

inline bool
or_node::nullable() const
{
    return m_left->nullable() || m_right->nullable();
}

inline node_set
or_node::firstpos() const
{
    node_set rval;
    node_set l = m_left->firstpos();
    node_set r = m_right->firstpos();
    std::set_union(l.begin(), l.end(), r.begin(), r.end(),
            std::inserter(rval, rval.begin()));
    return rval;
}

inline node_set
or_node::lastpos() const
{
    node_set rval;
    node_set l = m_left->lastpos();
    node_set r = m_right->lastpos();
    std::set_union(l.begin(), l.end(), r.begin(), r.end(),
            std::inserter(rval, rval.begin()));
    return rval;
}

inline void
or_node::compute_followpos(followpos_t& followpos) const
{
    m_left->compute_followpos(followpos);
    m_right->compute_followpos(followpos);
}

inline void
or_node::compute_state_match(state_match_t& state_match) const
{
    m_left->compute_state_match(state_match);
    m_right->compute_state_match(state_match);
}

inline void
or_node::get_eof_ids(node_set& eof_nodes) const
{
    m_left->get_eof_ids(eof_nodes);
    m_right->get_eof_ids(eof_nodes);
}

inline void
or_node::assign_node_ids(node_id_t& node_count)
{
    m_left->assign_node_ids(node_count);
    m_right->assign_node_ids(node_count);
}

#if defined(BOOST_SPIRIT_DEBUG) && (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_SLEX)
inline void
or_node::dump(std::ostream& out) const
{
    m_left->dump(out);

    out << "\nor_node";
    out << " nullable() = " << (nullable() ? "true" : "false");
    out << " firstpos() = ";
    node_set fp = firstpos();
    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, ","));

    m_right->dump(out);
}
#endif


class cat_node : public node
{

public:

    cat_node(node* left, node* right);
    cat_node(const cat_node& x);
    virtual ~cat_node(){}

    virtual node* clone() const;
    virtual bool nullable() const;
    virtual node_set firstpos() const;
    virtual node_set lastpos() const;
    virtual void compute_followpos(followpos_t& followpos) const;
    virtual void compute_state_match(state_match_t& state_match ) const;
    virtual void get_eof_ids(node_set& eof_set) const;
    virtual void assign_node_ids(node_id_t& node_count);
#if defined(BOOST_SPIRIT_DEBUG) && (BOOST_SPIRIT_DEBUG_FLAGS & BOOST_SPIRIT_DEBUG_FLAGS_SLEX)
    virtual void dump(std::ostream& out) const;
#endif

private:

    std::auto_ptr<node> m_left;
    std::auto_ptr<node> m_right;
};

inline
cat_node::cat_node(node* left, node* right)
    : node()
    , m_left(left)
    , m_right(right)
{
}

inline
cat_node::cat_node(const cat_node& x)