C++ 構文解析入門

はじめに

近年、組み込み環境でもスクリプト言語への関心が高まっていますが、そういった言語処理系を書く際に必要となってくるのが字句解析、構文解析です
ここでは簡単な再帰下降型のパーサを例に、実際に実装してみながら構文解析について学んでゆきましょう

再帰下降型の構文解析器は単純に実装するとスタックの消費が激しいことやスタック領域の枯渇の予測が難しいことなどであまり実用的なものにはならないのですが、構造が簡単なので構文解析の仕組みを理解するのには向いています

（「再帰降下」でも「再帰下降」でもどっちでもいいです。「recursive descent」の訳かな）

BNF

式の構造の定義としてＢＮＦ的な表記を用いていますが、別にＢＮＦを知らなくても問題ありません
空文字列（ε）は省略してあります
一部には正規表現的な表記も用いています
* は 0回以上の繰り返し、+ は 1回以上の繰り返しを表しています

予め用意するもの

include

Windows環境ならとりあえずこのくらい

#pragma	warning( push, 3 )
#include	<tchar.h>
#include	<windows.h>
#include	<mbctype.h>
#include	<string>
#include	<algorithm>
#pragma	warning( pop )
#pragma	warning( disable : 4100 )

stringprintf

数値と文字列の変換などが面倒なので stringprintf を作っておきましょう

#if	defined( _vsctprintf )
inline int	basic_string_vscprintf( const char*	format, va_list	ap ){
	return	_vscprintf( &format[0], ap );
}
inline int	basic_string_vscprintf( const wchar_t*	format, va_list	ap ){
	return	_vscwprintf( &format[0], ap );
}
inline int	basic_string_vscprintf( const std::string&	format, va_list	ap ){
	return	_vscprintf( &format[0], ap );
}
inline int	basic_string_vscprintf( const std::wstring&	format, va_list	ap ){
	return	_vscwprintf( &format[0], ap );
}
#else // _vsctprintf
template<class T> inline int	basic_string_vscprintf( T, va_list ){
	return	SHRT_MAX;
}
#endif // _vsctprintf
#if	defined( _vsntprintf )
inline int	basic_string_vsnprintf( char*	s, size_t	cch, const char*	format, va_list	ap ){
	return	::_vsnprintf( s, cch, &format[0], ap );
}
inline int	basic_string_vsnprintf( wchar_t*	s, size_t	cch, const wchar_t*	format, va_list	ap ){
	return	::_vsnwprintf( s, cch, &format[0], ap );
}
inline int	basic_string_vsnprintf( std::string::pointer	s, std::string::size_type	cch, const std::string&	format, va_list	ap ){
	return	::_vsnprintf( s, cch, &format[0], ap );
}
inline int	basic_string_vsnprintf( std::wstring::pointer	s, std::wstring::size_type	cch, const std::wstring&	format, va_list	ap ){
	return	::_vsnwprintf( s, cch, &format[0], ap );
}
#else // _vsntprintf
inline int	basic_string_vsnprintf( char*	s, size_t, const char*	format, va_list	ap ){
	return	::vsprintf( s, &format[0], ap );
}
inline int	basic_string_vsnprintf( wchar_t*	s, size_t, const wchar_t*	format, va_list	ap ){
	return	::vswprintf( s, &format[0], ap );
}
inline int	basic_string_vsnprintf( std::string::pointer	s, std::string::size_type, const std::string&	format, va_list	ap ){
	return	::vsprintf( s, &format[0], ap );
}
inline int	basic_string_vsnprintf( std::wstring::pointer	s, std::wstring::size_type, const std::wstring&	format, va_list	ap ){
	return	::vswprintf( s, &format[0], ap );
}
#endif // _vsntprintf
template<class T,class U> inline T	basic_string_sprintf( U	format,... ){
	va_list	ap;
	va_start( ap, format );
	int	cch = basic_string_vscprintf( format, ap );
	T	s;
	s.resize( cch+1 );
	basic_string_vsnprintf( &s[0], s.size(), format, ap );
	s.erase( std::find( s.begin(), s.end(), 0 ), s.end());
	va_end( ap );
	return	s;
}
template<class T,class U> inline T	basic_string_vsprintf( U	format, va_list	ap ){
	int	cch = basic_string_vscprintf( format, ap );
	T	s;
	s.resize( cch+1 );
	basic_string_vsnprintf( &s[0], s.size(), format, ap );
	s.erase( std::find( s.begin(), s.end(), 0 ), s.end());
	return	s;
}

#define	stringprintf	basic_string_sprintf<std::string>
#define	vstringprintf	basic_string_vsprintf<std::string>
#define	wstringprintf	basic_string_sprintf<std::wstring>
#define	vwstringprintf	basic_string_vsprintf<std::wstring>

OutputDebugString

OutputDebugString も面倒なので std::string をそのまま渡せるようにしておきます

inline void	OutputDebugStringW( const std::wstring&	s ){
	return	OutputDebugStringW( s.c_str());
}
inline void	OutputDebugStringA( const std::string&	s ){
	return	OutputDebugStringA( s.c_str());
}

istringstream

文字列バッファの操作も面倒なので予め下記のようなクラスを作っておきましょう
名前は何でもいいんですがここでは istringstream としておきます

template<class _value_type> class istringstream {
protected:
	typedef typename std::basic_string<_value_type>::size_type	size_type;
	
	std::basic_string<_value_type>	m_istr;
	size_type	m_offset;
public:
	static const size_type	npos = ( size_type )-1;
	
	size_type	size() const {
		return	m_istr.size();
	}
	bool	eof() const {
		return	( m_offset >= size());
	}
	size_type	tell() const {
		return	m_offset;
	}
	size_type	seek( size_type	offset_new, int	origin ){
		if( origin == SEEK_SET ){
			m_offset = offset_new;
		}
		else if( origin == SEEK_CUR ){
			m_offset += offset_new;
		}
		else if( origin == SEEK_END ){
			m_offset = offset_new + size();
		}
		return	m_offset;
	}
	_value_type	at( size_type	n, int	origin = SEEK_SET ){
		_value_type	c = 0;
		if( origin == SEEK_CUR ){
			n += m_offset;
		}
		else if( origin == SEEK_END ){
			n += size();
		}
		if( n < size()){
			c = m_istr[n];
		}
		return	c;
	}
	std::basic_string<_value_type>	substr( size_type	n, size_type	cch = npos, int	origin = SEEK_SET ){
		if( origin == SEEK_CUR ){
			n += m_offset;
		}
		else if( origin == SEEK_END ){
			n += size();
		}
		if( cch == npos ){
			cch = size();
		}
		std::basic_string<_value_type>	s;
		if( n < size()){
			s.reserve( cch );
			std::basic_string<_value_type>::iterator	p = m_istr.begin();
			std::advance( p, n );
			std::basic_string<_value_type>::iterator	q = m_istr.end();
			if( n+cch < size()){
				q = p;
				std::advance( q, cch );
			}
			while( p != q ){
				s.push_back( *p );
				++p;
			}
		}
		return	s;
	}
	_value_type	getch(){
		_value_type	c = at( 0, SEEK_CUR );
		if( c ){
			++m_offset;
		}
		return	c;
	}
	void	ungetch( _value_type	c ){
		if( c && m_offset ){
			--m_offset;
		}
	}
	const _value_type*	getp(){
		return	&m_istr[m_offset];
	}
	std::basic_string<_value_type>	gets( size_type	cch ){
		std::basic_string<_value_type>	s = substr( 0, cch, SEEK_CUR );
		m_offset += s.size();
		return	s;
	}
	void	ungets( const std::basic_string<_value_type>	s ){
		if( m_offset < s.size()){
			m_offset = 0;
		}
		else{
			m_offset -= s.size();
		}
	}
	void	assign( const std::basic_string<_value_type>&	s ){
		m_istr = s;
		m_offset = 0;
	}
	istringstream&	operator=( const istringstream&	rhs ){
		if( this != &rhs ){
			m_istr = rhs.m_istr;
			m_offset = rhs.m_offset;
		}
		return	*this;
	}
	istringstream():
	m_istr(),
	m_offset(0)
	{
	}
	istringstream( const istringstream&	rhs ):
	m_istr(rhs.m_istr),
	m_offset(rhs.m_offset)
	{
	}
	~istringstream(){
	}
};

any_value_t

このパーサで使う「値」のための型を用意しましょう
名前は何でもいいんですがここでは any_value_t としておきます
このクラスはパーサの機能に応じて適宜拡張されます

#define	TYPEOF_INTEGER	"Integer"

class any_value_t {
	std::string	m_name;
	std::string	m_value;
public:
	std::string	get_value() const {
		return	m_value;
	}
	void	put_value( const std::string&	value_new ){
		m_value = value_new;
	}
	std::string	get_name() const {
		return	m_name;
	}
	void	put_name( const std::string&	name_new ){
		m_name = name_new;
	}
	bool	defined() const {
		return	!m_name.empty();
	}
	any_value_t&	assign( const std::string&	name, const std::string&	value ){
		m_name = name;
		m_value = value;
		return	*this;
	}
	void	undef(){
		m_name.clear();
		m_value.clear();
	}
	unsigned long	operator_typecast_to_ulong() const {
		const char*	p = &m_value[0];
		char*	endp = const_cast<char*>(p);
		unsigned long	result = strtoul( p, &endp, 0 );
		return	result;
	}
	long	operator_typecast_to_long() const {
		const char*	p = &m_value[0];
		char*	endp = const_cast<char*>(p);
		long	result = strtol( p, &endp, 0 );
		return	result;
	}
	bool	operator_typecast_to_bool() const {
		return	!!operator_typecast_to_long();
	}
	any_value_t&	operator_assign( const any_value_t&	rhs ){
		return	operator=( rhs );
	}
	any_value_t&	operator_assign_add( const any_value_t&	rhs ){
		long	l = operator_typecast_to_long();
		long	r = rhs.operator_typecast_to_long();
		l += r;
		return	assign( TYPEOF_INTEGER, stringprintf( "%d", l ));
	}
	any_value_t&	operator_assign_sub( const any_value_t&	rhs ){
		long	l = operator_typecast_to_long();
		long	r = rhs.operator_typecast_to_long();
		l -= r;
		return	assign( TYPEOF_INTEGER, stringprintf( "%d", l ));
	}
	any_value_t	operator_add( const any_value_t&	rhs ) const {
		any_value_t	result = *this;
		return	result.operator_assign_add( rhs );
	}
	any_value_t	operator_sub( const any_value_t&	rhs ) const {
		any_value_t	result = *this;
		return	result.operator_assign_sub( rhs );
	}
	any_value_t	operator_unary_plus() const {
		any_value_t	result = *this;
		return	result.assign( TYPEOF_INTEGER, stringprintf( "%d", +result.operator_typecast_to_long()));
	}
	any_value_t	operator_unary_minus() const {
		any_value_t	result = *this;
		return	result.assign( TYPEOF_INTEGER, stringprintf( "%d", -result.operator_typecast_to_long()));
	}
	
	operator bool() const {
		return	operator_typecast_to_bool();
	}
	any_value_t&	operator=( const any_value_t&	rhs ){
		if( this != &rhs ){
			m_name = rhs.m_name;
			m_value = rhs.m_value;
		}
		return	*this;
	}
	any_value_t():
	m_name(),
	m_value()
	{
	}
	any_value_t( const any_value_t&	rhs ):
	m_name(rhs.m_name),
	m_value(rhs.m_value)
	{
	}
	any_value_t( const std::string&	name, const std::string&	value ):
	m_name(name),
	m_value(value)
	{
	}
};