parselets.h

彩信浏览器

/*
 * This file is part of Ambulant Player, www.ambulantplayer.org.
 *
 * Copyright (C) 2003-2007 Stichting CWI, 
 * Kruislaan 413, 1098 SJ Amsterdam, The Netherlands.
 *
 * Ambulant Player is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * Ambulant Player is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with Ambulant Player; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

/* 
 * @$Id: parselets.h,v 1.20 2007/02/12 14:14:38 jackjansen Exp $ 
 */

#ifndef AMBULANT_LIB_PARSELETS_H
#define AMBULANT_LIB_PARSELETS_H

#include "ambulant/config/config.h"

// used by nfa_p
// support for nfa parsers may be removed
#include "ambulant/lib/nfa.h"

// used by and_p and options_p
#include <list>

// used by number_list_p
#include <vector>

#include <math.h>

// This module defines a set of simple parsers.
// All the parsers offer a common minimal interface 
// in order to simplify composition.
//
// Reserving the name "parser" for the final composition
// we call an atomic parser a "parselet".

namespace ambulant {

namespace lib {

template <class CharType>
class basic_parselet {
  public:
 	typedef CharType char_type;
 	typedef std::basic_string<char_type> string_type;
	typedef typename string_type::size_type size_type;   
	typedef typename string_type::iterator iterator;
	typedef typename string_type::const_iterator const_iterator;
	struct empty {};
	
	virtual ~basic_parselet() {}
	virtual std::ptrdiff_t parse(const_iterator& it, const const_iterator& end) = 0;
	
	bool matches(const string_type& s) {
		const_iterator b = s.begin(), e = s.end();
		return parse(b, e) == (std::ptrdiff_t)s.length();
	}
};

typedef basic_parselet<char> parselet;


//////////////////
// Generic parselets

template<char ch>
class literal_p : public parselet {
  public:
	typedef literal_p<ch> self_type;
	typedef char_type result_type;
	result_type m_result;
	std::ptrdiff_t parse(const_iterator& it, const const_iterator& end) {
		return (it == end || *it != ch)? -1 : (m_result = *it++, 1); 
	}
};

template<char ch1, char ch2>
class range_p : public parselet {
  public:
	typedef range_p<ch1, ch2> self_type;
	typedef char_type result_type;
	result_type m_result;
	std::ptrdiff_t parse(const_iterator& it, const const_iterator& end) {
		return (it == end || *it < ch1 || *it > ch2)?-1:(m_result = *it++, 1);
	}
};

class literal_cstr_p : public parselet {
   public:
	typedef literal_cstr_p self_type;
	typedef string_type result_type;
	result_type m_result;
	
	const char *m_psz;
	literal_cstr_p(const char *psz) : m_psz(psz) {}
	
	std::ptrdiff_t parse(const_iterator& it, const const_iterator& end) {
		const_iterator test_it = it;
		std::ptrdiff_t d = 0;
		const char *p = m_psz;
		while(test_it != end && *p && *test_it == *p) 
			{m_result+=*test_it;test_it++; p++; d++;}
		return *p?-1:(it = test_it, d);
	}
};

class delimiter_p : public parselet {
   public:
	typedef delimiter_p self_type;
	typedef char_type result_type;
	result_type m_result;
	string_type m_delims;
	
	delimiter_p(const string_type& delims)
	:	m_delims(delims) {}
	
	std::ptrdiff_t parse(const_iterator& it, const const_iterator& end) {
		if(it == end) return -1;
		size_type ix = m_delims.find_first_of(*it);
		if(ix != string_type::npos) {
			m_result = *it;
			it++;
			return 1;
		}
		return -1;
	}
};

class int_p : public parselet {
   public:
	typedef int_p self_type;
	typedef int result_type;
	result_type m_result;

	std::ptrdiff_t parse(const_iterator& it, const const_iterator& end) {
		if(it == end || *it < '0' || *it > '9') return -1; 	
		m_result = 0;
		std::ptrdiff_t len = 0;
		do {
			m_result = m_result*10 + int(*it - '0');
			len++;it++;
		} while(it != end && *it >= '0' && *it <= '9');
		return len;
	}
};

template <class CharType, class IsNameStartCh, class IsNameCh >
class name_p :  public basic_parselet<CharType> {
  public:
	typedef name_p<CharType, IsNameStartCh, IsNameCh> self_type;
	typedef typename basic_parselet<CharType>::string_type result_type;
	typedef typename basic_parselet<CharType>::const_iterator const_iterator;
	result_type m_result;
	std::ptrdiff_t parse(const_iterator& it, const const_iterator& end) {
		if(it == end || !IsNameStartCh()(*it)) return -1;
		m_result += *it;
		std::ptrdiff_t d = 1;
		const_iterator test_it = ++it;
		while(test_it != end && IsNameCh()(*test_it)) 
			{ m_result += *test_it++; d++;}
		return (it = test_it, d);
	}
};

class epsilon_p : public parselet {
  public:
	typedef epsilon_p self_type;
	typedef empty result_type;
	std::ptrdiff_t parse(const_iterator& it, 
		const const_iterator& end) { return 0;}
	result_type m_result;
};

class nfa_p : public parselet {
  public:
	typedef nfa_p self_type;
	typedef string_type result_type;
	
	nfa_p(const lib::nfa_expr& expr) 
	:	m_expr(expr) {}
	
	std::ptrdiff_t parse(const_iterator& it, const const_iterator& end) {
		const_iterator it_test = it;
		std::ptrdiff_t d = m_expr.parse(it_test, end);
		if(d != -1) {
			m_result = std::string(it, it_test);
			it = it_test;
		}
		return d;
	}
	result_type m_result;
	const lib::nfa_expr& m_expr;
};


// Parses: FirstType SecondType
template<class FirstType, class SecondType>
class cat_pair_p  : public parselet {
  public:
	typedef FirstType first_type;
	typedef SecondType second_type;
	typedef typename FirstType::result_type first_result_type;
	typedef typename SecondType::result_type second_result_type;
	//typedef typename cat_pair_p<FirstType, SecondType> self_type;
	typedef std::pair<typename FirstType::result_type,
		typename SecondType::result_type> result_type;

	cat_pair_p(const FirstType& f, const SecondType& s) : m_first(f), m_second(s) {}
	
	std::ptrdiff_t parse(const_iterator& it, const const_iterator& end) {
		const_iterator it_test = it;
		std::ptrdiff_t fd = m_first.parse(it_test, end);
		if(fd == -1) return -1;
		std::ptrdiff_t sd = m_second.parse(it_test, end);
		if(sd == -1) return -1;
		it = it_test;
		m_result = std::make_pair(m_first.m_result, m_second.m_result);
		return fd + sd;
	}
	
	first_result_type get_first_result() const { return m_result.first;}
	second_result_type get_second_result() const { return m_result.second;}
	
	first_type m_first;
	second_type m_second;
	result_type m_result;
};

// Parses: FirstType | SecondType
template<class FirstType, class SecondType>
class or_pair_p : public parselet {
  public:
	typedef FirstType first_type;
	typedef SecondType second_type;
	typedef or_pair_p<FirstType, SecondType> self_type;
	typedef typename FirstType::result_type first_result_type;
	typedef typename SecondType::result_type second_result_type;
	typedef std::pair< 
		std::pair<bool, first_result_type>, 
		std::pair<bool, second_result_type>
		> result_type; 
	result_type m_result;
	
	first_type m_first;
	second_type m_second;	
	or_pair_p(const first_type& f, const second_type& s) : m_first(f), m_second(s) {}
	
	std::ptrdiff_t parse(const_iterator& it, const const_iterator& end) {
		const_iterator fit = it;
		std::ptrdiff_t fd = m_first.parse(fit, end);		
		
		const_iterator sit = it;
		std::ptrdiff_t sd = m_second.parse(sit, end);
		
		if( (fd == -1 && sd != -1) || (fd != -1 && sd != -1 && fd<sd)) {
			it = sit;
			m_result.first = std::make_pair(false, m_first.m_result);
			m_result.second = std::make_pair(true, m_second.m_result);
			return sd;
		} else if( (fd != -1 && sd == -1) || (fd != -1 && sd != -1 && fd>=sd)) {
			it = fit;
			m_result.first = std::make_pair(true, m_first.m_result);
			m_result.second = std::make_pair(false, m_second.m_result);
			return fd;
		} 
		return -1;
	}
	
	bool matched_first() const { return m_result.first.first;}
	bool matched_second() const { return m_result.second.first;}
	first_result_type get_first_result() const { return m_result.first.second;}
	second_result_type get_second_result() const { return m_result.second.second;}
};

template<class FirstType, class SecondType>
cat_pair_p<FirstType, SecondType> make_cat_p(const FirstType& f, const SecondType& s) {
	return cat_pair_p<FirstType, SecondType>(f, s);
}
template<class FirstType, class SecondType>
or_pair_p<FirstType, SecondType> make_or_p(const FirstType& f, const SecondType& s) {
	return or_pair_p<FirstType, SecondType>(f, s);
}

// Parses: P?
template<class P>
class optional_p : public or_pair_p<P, epsilon_p> {
  public:
	typedef typename or_pair_p<P, epsilon_p>::first_result_type first_result_type;
	optional_p(const P& p) : or_pair_p<P, epsilon_p>(p, epsilon_p()) {}
	bool occured() const { return or_pair_p<P, epsilon_p>::matched_first();}
	first_result_type get_result() const { return or_pair_p<P, epsilon_p>::get_first_result();}
};

template<class P>
optional_p<P> make_optional(const P& p) {
	return optional_p<P>(p);
}

// Parses: P+
template<class P>
class plus_p : public parselet {
  public:
	typedef plus_p<P> self_type;
	typedef typename P::result_type atom_result_type;
	typedef std::list<atom_result_type> result_type;
	result_type m_result;
	P m_p;
	plus_p(const P& p) : m_p(p) {}
	std::ptrdiff_t parse(const_iterator& it, const const_iterator& end) {
		const_iterator test_it = it;
		std::ptrdiff_t rd = m_p.parse(test_it, end);
		if(rd == -1) return -1;
		it = test_it;
		m_result.push_back(m_p.m_result);
		while(test_it != end) {
			std::ptrdiff_t d = m_p.parse(test_it, end);
			if(d == -1) break;
			rd += d;
			it = test_it;
			m_result.push_back(m_p.m_result);		
		}
		return rd;
	}
};

template<class P>
plus_p<P> make_plus(const P& p) {
	return plus_p<P>(p);
}

// Parses: P*
template<class P>
class star_p : public parselet {
  public:
	typedef star_p<P> self_type;
	typedef typename P::result_type atom_result_type;
	typedef std::list<atom_result_type> result_type;
	result_type m_result;
	P m_p;
	star_p(const P& p) : m_p(p) {}
	std::ptrdiff_t parse(const_iterator& it, const const_iterator& end) {
		const_iterator test_it = it;
		std::ptrdiff_t rd = m_p.parse(test_it, end);
		if(rd == -1) return 0;
		it = test_it;
		m_result.push_back(m_p.m_result);
		while(test_it != end) {