parse.h
Go to the documentation of this file.
// -*- C++ -*- (c) 2011 Petr Rockai
// (c) 2013 Jan Kriho
// Support code for writing backtracking recursive-descent parsers
#include <string>
#include <cassert>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <wibble/regexp.h>
#ifndef WIBBLE_PARSE_H
#define WIBBLE_PARSE_H
namespace wibble {
struct Position {
std::string source;
int line;
int column;
Position() : source("-"), line(1), column(1) {}
bool operator==( const Position &o ) const {
return o.source == source && o.line == line && o.column == column;
}
};
template< typename _Id >
struct Token {
typedef _Id Id;
Id id;
std::string data;
Position position;
bool _valid;
bool valid() { return _valid; }
Token( Id _id, char c ) : id( _id ), _valid( true ) {
data.push_back( c );
}
Token( Id _id, std::string d ) : id( _id ), data( d ), _valid( true ) {}
Token() : id( Id( 0 ) ), _valid( false ) {}
bool operator==( const Token &o ) const {
return o._valid == _valid && o.id == id && o.data == data && o.position == position;
}
};
template< typename X, typename Y >
inline std::ostream &operator<<( std::ostream &o, const std::pair< X, Y > &x ) {
return o << "(" << x.first << ", " << x.second << ")";
}
/*
* This is a SLOW lexer (at least compared to systems like lex/flex, which
* build a finite-state machine to make decisions per input character. We could
* do that in theory, but it would still be slow, since we would be in effect
* interpreting the FSM anyway, while (f)lex uses an optimising compiler like
* gcc. So while this is friendly and flexible, it won't give you a fast
* scanner.
*/
template< typename Token, typename Stream >
struct Lexer {
Stream &stream;
typedef std::deque< char > Window;
Window _window;
Position current;
Token _match;
void shift() {
assert( !stream.eof() );
std::string r = stream.remove();
std::copy( r.begin(), r.end(), std::back_inserter( _window ) );
}
bool eof() {
return _window.empty() && stream.eof();
}
std::string window( unsigned n ) {
bool valid = ensure_window( n );
assert( valid );
static_cast< void >( valid );
std::deque< char >::iterator b = _window.begin(), e = b;
e += n;
return std::string( b, e );
}
bool ensure_window( unsigned n ) {
while ( _window.size() < n && !stream.eof() )
shift();
return _window.size() >= n;
}
void consume( int n ) {
for( int i = 0; i < n; ++i ) {
if ( _window[i] == '\n' ) {
current.line ++;
current.column = 1;
} else
current.column ++;
}
std::deque< char >::iterator b = _window.begin(), e = b;
e += n;
_window.erase( b, e );
}
void consume( const std::string &s ) {
consume( s.length() );
}
void consume( const Token &t ) {
// std::cerr << "consuming " << t << std::endl;
consume( t.data );
}
void keep( typename Token::Id id, const std::string &data ) {
Token t( id, data );
t.position = current;
if ( t.data.length() > _match.data.length() )
_match = t;
}
template< typename I >
bool match( I begin, I end ) {
if ( !ensure_window( end - begin ) )
return false;
return std::equal( begin, end, _window.begin() );
}
void match( const std::string &data, typename Token::Id id ) {
if ( match( data.begin(), data.end() ) )
return keep( id, data );
}
void match( Regexp &r, typename Token::Id id ) {
unsigned n = 1, max = 0;
while ( r.match( window( n ) ) ) {
if ( max && max == r.matchLength( 0 ) )
return keep( id, window( max ) );
max = r.matchLength( 0 );
++ n;
}
}
void match( int (*first)(int), int (*rest)(int), typename Token::Id id )
{
unsigned n = 1;
if ( !ensure_window( 1 ) )
return;
if ( !first( _window[0] ) )
return;
while ( true ) {
++ n;
if ( ensure_window( n ) && rest( _window[ n - 1 ] ) )
continue;
return keep( id, window( n - 1 ) );
}
}
void match( const std::string &from, const std::string &to, typename Token::Id id ) {
if ( !match( from.begin(), from.end() ) )
return;
Window::iterator where = _window.begin();
int n = from.length();
where += n;
while ( true ) {
if ( !ensure_window( n + to.length() ) )
return;
if ( std::equal( to.begin(), to.end(), where ) )
return keep( id, window( n + to.length() ) );
++ where;
++ n;
}
}
void skipWhitespace() {
while ( !eof() && isspace( window( 1 )[ 0 ] ) )
consume( 1 );
}
Token decide() {
Token t;
std::swap( t, _match );
consume( t );
return t;
}
Lexer( Stream &s ) : stream( s ) {}
};
template< typename Token, typename Stream >
struct ParseContext
{
Stream *_stream;
Stream &stream() { assert( _stream ); return *_stream; }
std::deque< Token > window;
int window_pos;
int position;
std::string name;
typedef ParseContext< Token, Stream > This;
std::vector< This > children;
struct Fail {
enum Type { Syntax, Semantic };
int position;
const char *expected;
Type type;
bool operator<( const Fail &other ) const {
return position > other.position;
}
Fail( const char *err, int pos, Type t = Syntax) {
expected = err;
position = pos;
type = t;
}
~Fail() throw () {}
};
std::priority_queue< Fail > failures;
void clearErrors() {
failures = std::priority_queue< Fail >();
}
void error( std::ostream &o, std::string prefix, const Fail &fail ) {
Token t = window[ fail.position ];
switch ( fail.type ) {
case Fail::Syntax:
o << prefix
<< "expected " << fail.expected
<< " at line " << t.position.line
<< ", column " << t.position.column
<< ", but seen " << Token::tokenName[ t.id ] << " '" << t.data << "'"
<< std::endl;
return;
case Fail::Semantic:
o << prefix
<< fail.expected
<< " at line " << t.position.line
<< ", column " << t.position.column
<< std::endl;
return;
}
}
void errors( std::ostream &o ) {
for ( typename std::vector< This >::iterator pc = children.begin(); pc != children.end(); ++pc )
pc->errors( o );
if ( failures.empty() )
return;
std::string prefix;
switch ( failures.top().type ) {
case Fail::Syntax:
o << "parse";
break;
case Fail::Semantic:
o << "semantic";
break;
}
o << " error in context " << name << ": ";
if ( failures.size() > 1 ) {
o << failures.size() << " rightmost alternatives:" << std::endl;
prefix = " ";
}
while ( !failures.empty() ) {
error( o, prefix, failures.top() );
failures.pop();
}
}
Token remove() {
if ( int( window.size() ) <= window_pos ) {
Token t;
do {
t = stream().remove();
} while ( t.id == Token::Comment ); // XXX
window.push_back( t );
}
++ window_pos;
++ position;
return window[ window_pos - 1 ];
}
void rewind( int n ) {
assert( n >= 0 );
assert( n <= window_pos );
window_pos -= n;
position -= n;
}
This & createChild( Stream &s, std::string name ) {
children.push_back( This( s, name ) );
return children.back();
}
ParseContext( Stream &s, std::string name )
: _stream( &s ), window_pos( 0 ), position( 0 ), name( name )
{}
};
template< typename Token, typename Stream >
struct Parser {
typedef typename Token::Id TokenId;
typedef ParseContext< Token, Stream > Context;
Context *ctx;
typedef typename Context::Fail Fail;
typedef typename Fail::Type FailType;
int _position;
bool valid() const {
return ctx;
}
Context &context() {
assert( ctx );
return *ctx;
}
int position() {
return context().position;
}
void rewind( int i ) {
context().rewind( i );
_position = context().position;
}
void fail( const char *what, FailType type = FailType::Syntax ) __attribute__((noreturn))
{
Fail f( what, _position, type );
context().failures.push( f );
while ( context().failures.top().position < _position )
context().failures.pop();
throw f;
}
void semicolon() {
Token t = eat();
if ( t.id == Token::Punctuation && t.data == ";" )
return;
rewind( 1 );
fail( "semicolon" );
}
void colon() {
Token t = eat();
if ( t.id == Token::Punctuation && t.data == ":" )
return;
rewind( 1 );
fail( "colon" );
}
Token eat( TokenId id ) {
Token t = eat( false );
if ( t.id == id )
return t;
rewind( 1 );
fail( Token::tokenName[id].c_str() );
}
#if __cplusplus >= 201103L
template< typename F >
void either( void (F::*f)() ) {
(static_cast< F* >( this )->*f)();
}
template< typename F, typename... Args >
void either( F f, Args... args ) {
if ( maybe( f ) )
return;
either( args... );
}
#else
template< typename F, typename G >
void either( F f, void (G::*g)() ) {
if ( maybe( f ) )
return;
(static_cast< G* >( this )->*g)();
}
#endif
#if __cplusplus >= 201103L
template< typename F, typename... Args >
bool maybe( F f, Args... args ) {
if ( maybe( f ) )
return true;
return maybe( args... );
}
#else
template< typename F, typename G >
bool maybe( F f, G g ) {
if ( maybe( f ) )
return true;
return maybe( g );
}
template< typename F, typename G, typename H >
bool maybe( F f, G g, H h ) {
if ( maybe( f ) )
return true;
if ( maybe( g ) )
return true;
return maybe( h );
}
#endif
template< typename F >
bool maybe( void (F::*f)() ) {
int fallback = position();
try {
(static_cast< F* >( this )->*f)();
return true;
} catch ( Fail fail ) {
rewind( position() - fallback );
return false;
}
}
bool maybe( TokenId id ) {
int fallback = position();
try {
eat( id );
return true;
} catch (Fail) {
rewind( position() - fallback );
return false;
}
}
template< typename T, typename I >
void many( I i ) {
int fallback = 0;
try {
while ( true ) {
fallback = position();
*i++ = T( context() );
}
} catch (Fail) {
rewind( position() - fallback );
}
}
#if __cplusplus >= 201103L
template< typename F >
bool arbitrary( F f ) {
return maybe( f );
}
template< typename F, typename... Args >
bool arbitrary( F f, Args... args ) {
bool retval = arbitrary( args... );
retval |= maybe( f );
retval |= arbitrary( args... );
return retval;
}
#endif
template< typename T, typename I >
void list( I i, TokenId sep ) {
do {
*i++ = T( context() );
} while ( next( sep ) );
}
template< typename T, typename I, typename F >
void list( I i, void (F::*sep)() ) {
int fallback = position();
try {
while ( true ) {
*i++ = T( context() );
fallback = position();
(static_cast< F* >( this )->*sep)();
}
} catch(Fail) {
rewind( position() - fallback );
}
}
template< typename T, typename I >
void list( I i, TokenId first, TokenId sep, TokenId last ) {
eat( first );
list< T >( i, sep );
eat( last );
}
Token eat( bool _fail = true ) {
Token t = context().remove();
_position = context().position;
if ( _fail && !t.valid() ) {
rewind( 1 );
fail( "valid token" );
}
return t;
}
bool next( TokenId id ) {
Token t = eat( false );
if ( t.id == id )
return true;
rewind( 1 );
return false;
}
Parser( Context &c ) : ctx( &c ) {}
Parser() : ctx( 0 ) {}
};
}
#endif
wibble::Position::source
std::string source
Definition: parse.h:19
wibble::Lexer::match
void match(int(*first)(int), int(*rest)(int), typename Token::Id id)
Definition: parse.h:149
wibble::Token::data
std::string data
Definition: parse.h:32
wibble::Token::_valid
bool _valid
Definition: parse.h:34
wibble::iterator
Iterator< typename I::value_type > iterator(I i)
Definition: iterator.h:123
wibble::Lexer::_window
Window _window
Definition: parse.h:68
wibble::ParseContext::error
void error(std::ostream &o, std::string prefix, const Fail &fail)
Definition: parse.h:238
wibble::Lexer::match
void match(const std::string &from, const std::string &to, typename Token::Id id)
Definition: parse.h:167
wibble::Position::Position
Position()
Definition: parse.h:22
wibble::Lexer::eof
bool eof()
Definition: parse.h:79
wibble::Parser::list
void list(I i, void(F::*sep)())
Definition: parse.h:488
wibble::Lexer
Definition: parse.h:65
wibble::Position::operator==
bool operator==(const Position &o) const
Definition: parse.h:23
wibble::Parser::ctx
Context * ctx
Definition: parse.h:321
wibble::Parser::valid
bool valid() const
Definition: parse.h:326
wibble::Parser
Definition: parse.h:318
wibble::ParseContext::ParseContext
ParseContext(Stream &s, std::string name)
Definition: parse.h:312
wibble::Position::line
int line
Definition: parse.h:20
wibble::Lexer::match
void match(Regexp &r, typename Token::Id id)
Definition: parse.h:139
wibble::ParseContext::rewind
void rewind(int n)
Definition: parse.h:300
wibble::Lexer::Window
std::deque< char > Window
Definition: parse.h:67
wibble::Lexer::shift
void shift()
Definition: parse.h:73
wibble::Lexer::consume
void consume(int n)
Definition: parse.h:98
wibble::Token::Token
Token()
Definition: parse.h:43
wibble::ParseContext::position
int position
Definition: parse.h:208
wibble::Lexer::Lexer
Lexer(Stream &s)
Definition: parse.h:197
wibble::Lexer::skipWhitespace
void skipWhitespace()
Definition: parse.h:185
wibble::ParseContext::Fail::Fail
Fail(const char *err, int pos, Type t=Syntax)
Definition: parse.h:224
wibble::Parser::eat
Token eat(bool _fail=true)
Definition: parse.h:508
wibble::Parser::rewind
void rewind(int i)
Definition: parse.h:339
wibble::ParseContext::name
std::string name
Definition: parse.h:209
wibble::Token::valid
bool valid()
Definition: parse.h:36
wibble::Regexp::match
bool match(const std::string &str, int flags=0)
Definition: regexp.cpp:74
wibble::ParseContext::_stream
Stream * _stream
Definition: parse.h:203
wibble::ParseContext::createChild
This & createChild(Stream &s, std::string name)
Definition: parse.h:307
wibble::Parser::context
Context & context()
Definition: parse.h:330
wibble::ParseContext::Fail::operator<
bool operator<(const Fail &other) const
Definition: parse.h:220
wibble::Parser::next
bool next(TokenId id)
Definition: parse.h:518
wibble::list::begin
ListIterator< List > begin(List l)
Definition: list.h:420
wibble::Parser::eat
Token eat(TokenId id)
Definition: parse.h:371
wibble::Lexer::consume
void consume(const std::string &s)
Definition: parse.h:111
wibble::Lexer::consume
void consume(const Token &t)
Definition: parse.h:115
wibble::Parser::FailType
Fail::Type FailType
Definition: parse.h:323
wibble::Parser::semicolon
void semicolon()
Definition: parse.h:353
assert
#define assert(x)
Definition: test.h:30
wibble::Regexp
Definition: regexp.h:53
wibble::Token::position
Position position
Definition: parse.h:33
wibble::ParseContext::Fail::type
Type type
Definition: parse.h:218
wibble::ParseContext::Fail::~Fail
~Fail()
Definition: parse.h:229
wibble::ParseContext::failures
std::priority_queue< Fail > failures
Definition: parse.h:232
wibble::ParseContext::Fail::Type
Type
Definition: parse.h:214
wibble::ParseContext::Fail::expected
const char * expected
Definition: parse.h:217
wibble::Lexer::window
std::string window(unsigned n)
Definition: parse.h:83
wibble::ParseContext::Fail::position
int position
Definition: parse.h:216
wibble::Parser::Parser
Parser(Context &c)
Definition: parse.h:526
wibble::ParseContext::window
std::deque< Token > window
Definition: parse.h:206
wibble::Token::Token
Token(Id _id, std::string d)
Definition: parse.h:42
wibble::Lexer::decide
Token decide()
Definition: parse.h:190
wibble::ParseContext::window_pos
int window_pos
Definition: parse.h:207
wibble::ParseContext::This
ParseContext< Token, Stream > This
Definition: parse.h:210
wibble::Token::operator==
bool operator==(const Token &o) const
Definition: parse.h:45
wibble::Parser::Parser
Parser()
Definition: parse.h:527
wibble::Parser::Context
ParseContext< Token, Stream > Context
Definition: parse.h:320
wibble::Token::Id
_Id Id
Definition: parse.h:30
wibble::Parser::many
void many(I i)
Definition: parse.h:454
wibble::Parser::list
void list(I i, TokenId first, TokenId sep, TokenId last)
Definition: parse.h:502
wibble::Parser::_position
int _position
Definition: parse.h:324
wibble::Parser::maybe
bool maybe(TokenId id)
Definition: parse.h:442
wibble::ParseContext::children
std::vector< This > children
Definition: parse.h:211
wibble::Parser::either
void either(F f, void(G::*g)())
Definition: parse.h:394
wibble::Parser::maybe
bool maybe(F f, G g)
Definition: parse.h:412
wibble::Parser::TokenId
Token::Id TokenId
Definition: parse.h:319
wibble::Parser::maybe
bool maybe(void(F::*f)())
Definition: parse.h:431
wibble::Parser::colon
void colon()
Definition: parse.h:362
wibble::Lexer::_match
Token _match
Definition: parse.h:71
wibble::Position::column
int column
Definition: parse.h:21
regexp.h
wibble::Token
Definition: parse.h:29
wibble::Parser::position
int position()
Definition: parse.h:335
wibble::ParseContext::errors
void errors(std::ostream &o)
Definition: parse.h:259
wibble::Lexer::match
bool match(I begin, I end)
Definition: parse.h:128
wibble
Definition: amorph.h:17
wibble::Parser::list
void list(I i, TokenId sep)
Definition: parse.h:481
wibble::ParseContext
Definition: parse.h:201
wibble::Token::id
Id id
Definition: parse.h:31
wibble::Position
Definition: parse.h:18
wibble::Lexer::current
Position current
Definition: parse.h:69
wibble::ParseContext::Fail
Definition: parse.h:213
wibble::Lexer::stream
Stream & stream
Definition: parse.h:66
wibble::Lexer::ensure_window
bool ensure_window(unsigned n)
Definition: parse.h:92
wibble::Parser::fail
void fail(const char *what, FailType type=FailType::Syntax) __attribute__((noreturn))
Definition: parse.h:344
wibble::Parser::Fail
Context::Fail Fail
Definition: parse.h:322
wibble::Lexer::match
void match(const std::string &data, typename Token::Id id)
Definition: parse.h:134
wibble::ParseContext::stream
Stream & stream()
Definition: parse.h:204
wibble::Lexer::keep
void keep(typename Token::Id id, const std::string &data)
Definition: parse.h:120
wibble::Token::Token
Token(Id _id, char c)
Definition: parse.h:38
wibble::list::end
ListIterator< List > end(List)
Definition: list.h:425
wibble::ParseContext::clearErrors
void clearErrors()
Definition: parse.h:234
wibble::Parser::maybe
bool maybe(F f, G g, H h)
Definition: parse.h:420
wibble::Regexp::matchLength
size_t matchLength(int idx)
Definition: regexp.cpp:120