13 #ifndef WIBBLE_PARSE_H 14 #define WIBBLE_PARSE_H 22 Position() : source(
"-"), line(1), column(1) {}
28 template<
typename _Id >
38 Token( Id _id,
char c ) : id( _id ), _valid( true ) {
42 Token( Id _id, std::string d ) : id( _id ), data( d ), _valid( true ) {}
43 Token() : id( Id( 0 ) ), _valid( false ) {}
51 template<
typename X,
typename Y >
52 inline std::ostream &operator<<( std::ostream &o, const std::pair< X, Y > &x ) {
53 return o <<
"(" << x.first <<
", " << x.second <<
")";
64 template<
typename Token,
typename Stream >
75 std::string r = stream.remove();
76 std::copy( r.begin(), r.end(), std::back_inserter( _window ) );
80 return _window.empty() && stream.eof();
84 bool valid = ensure_window( n );
86 static_cast< void >( valid );
89 return std::string( b, e );
93 while ( _window.size() < n && !stream.eof() )
95 return _window.size() >= n;
99 for(
int i = 0; i < n; ++i ) {
100 if ( _window[i] ==
'\n' ) {
108 _window.erase( b, e );
112 consume( s.length() );
123 if ( t.
data.length() > _match.
data.length() )
127 template<
typename I >
129 if ( !ensure_window( end - begin ) )
131 return std::equal( begin, end, _window.begin() );
135 if ( match( data.begin(), data.end() ) )
136 return keep(
id, data );
140 unsigned n = 1, max = 0;
141 while ( r.
match( window( n ) ) ) {
143 return keep(
id, window( max ) );
153 if ( !ensure_window( 1 ) )
156 if ( !first( _window[0] ) )
161 if ( ensure_window( n ) && rest( _window[ n - 1 ] ) )
163 return keep(
id, window( n - 1 ) );
167 void match(
const std::string &from,
const std::string &to,
typename Token::Id id ) {
168 if ( !match( from.begin(), from.end() ) )
172 int n = from.length();
175 if ( !ensure_window( n + to.length() ) )
178 if ( std::equal( to.begin(), to.end(), where ) )
179 return keep(
id, window( n + to.length() ) );
186 while ( !eof() && isspace( window( 1 )[ 0 ] ) )
192 std::swap( t, _match );
200 template<
typename Token,
typename Stream >
214 enum Type { Syntax, Semantic };
235 failures = std::priority_queue< Fail >();
238 void error( std::ostream &o, std::string prefix,
const Fail &fail ) {
240 switch ( fail.
type ) {
246 <<
", but seen " << Token::tokenName[ t.
id ] <<
" '" << t.
data <<
"'" 263 if ( failures.empty() )
267 switch ( failures.top().type ) {
275 o <<
" error in context " << name <<
": ";
276 if ( failures.size() > 1 ) {
277 o << failures.size() <<
" rightmost alternatives:" << std::endl;
280 while ( !failures.empty() ) {
281 error( o, prefix, failures.top() );
287 if (
int( window.size() ) <= window_pos ) {
290 t = stream().remove();
291 }
while ( t.
id == Token::Comment );
292 window.push_back( t );
297 return window[ window_pos - 1 ];
302 assert( n <= window_pos );
308 children.push_back( This( s, name ) );
309 return children.back();
313 : _stream( &s ), window_pos( 0 ), position( 0 ), name( name )
317 template<
typename Token,
typename Stream >
336 return context().position;
340 context().rewind( i );
341 _position = context().position;
344 void fail(
const char *what, FailType type = FailType::Syntax ) __attribute__((noreturn))
346 Fail f( what, _position, type );
347 context().failures.push( f );
348 while ( context().failures.top().position < _position )
349 context().failures.pop();
355 if ( t.
id == Token::Punctuation && t.
data ==
";" )
364 if ( t.
id == Token::Punctuation && t.
data ==
":" )
372 Token t = eat(
false );
376 fail( Token::tokenName[
id].c_str() );
380 #if __cplusplus >= 201103L 381 template<
typename F >
382 void either(
void (F::*f)() ) {
383 (
static_cast< F*
>( this )->*f)();
386 template<
typename F,
typename... Args >
387 void either( F f, Args... args ) {
393 template<
typename F,
typename G >
397 (
static_cast< G*
>( this )->*g)();
402 #if __cplusplus >= 201103L 403 template<
typename F,
typename... Args >
404 bool maybe( F f, Args... args ) {
407 return maybe( args... );
411 template<
typename F,
typename G >
419 template<
typename F,
typename G,
typename H >
430 template<
typename F >
432 int fallback = position();
434 (
static_cast< F*
>( this )->*f)();
436 }
catch ( Fail fail ) {
437 rewind( position() - fallback );
443 int fallback = position();
448 rewind( position() - fallback );
453 template<
typename T,
typename I >
458 fallback = position();
459 *i++ = T( context() );
462 rewind( position() - fallback );
465 #if __cplusplus >= 201103L 466 template<
typename F >
467 bool arbitrary( F f ) {
471 template<
typename F,
typename... Args >
472 bool arbitrary( F f, Args... args ) {
473 bool retval = arbitrary( args... );
474 retval |= maybe( f );
475 retval |= arbitrary( args... );
480 template<
typename T,
typename I >
481 void list( I i, TokenId sep ) {
483 *i++ = T( context() );
484 }
while ( next( sep ) );
487 template<
typename T,
typename I,
typename F >
488 void list( I i,
void (F::*sep)() ) {
489 int fallback = position();
492 *i++ = T( context() );
493 fallback = position();
494 (
static_cast< F*
>( this )->*sep)();
497 rewind( position() - fallback );
501 template<
typename T,
typename I >
502 void list( I i, TokenId first, TokenId sep, TokenId last ) {
509 Token t = context().remove();
511 if ( _fail && !t.
valid() ) {
513 fail(
"valid token" );
519 Token t = eat(
false );
std::string source
Definition: parse.h:19
void match(int(*first)(int), int(*rest)(int), typename Token::Id id)
Definition: parse.h:149
std::string data
Definition: parse.h:32
bool _valid
Definition: parse.h:34
Iterator< typename I::value_type > iterator(I i)
Definition: iterator.h:123
Window _window
Definition: parse.h:68
void error(std::ostream &o, std::string prefix, const Fail &fail)
Definition: parse.h:238
void match(const std::string &from, const std::string &to, typename Token::Id id)
Definition: parse.h:167
Position()
Definition: parse.h:22
bool eof()
Definition: parse.h:79
void list(I i, void(F::*sep)())
Definition: parse.h:488
bool operator==(const Position &o) const
Definition: parse.h:23
Context * ctx
Definition: parse.h:321
bool valid() const
Definition: parse.h:326
ParseContext(Stream &s, std::string name)
Definition: parse.h:312
int line
Definition: parse.h:20
void match(Regexp &r, typename Token::Id id)
Definition: parse.h:139
void rewind(int n)
Definition: parse.h:300
std::deque< char > Window
Definition: parse.h:67
void shift()
Definition: parse.h:73
void consume(int n)
Definition: parse.h:98
Token()
Definition: parse.h:43
int position
Definition: parse.h:208
Lexer(Stream &s)
Definition: parse.h:197
void skipWhitespace()
Definition: parse.h:185
Fail(const char *err, int pos, Type t=Syntax)
Definition: parse.h:224
Token eat(bool _fail=true)
Definition: parse.h:508
void rewind(int i)
Definition: parse.h:339
std::string name
Definition: parse.h:209
bool valid()
Definition: parse.h:36
bool match(const std::string &str, int flags=0)
Definition: regexp.cpp:74
Stream * _stream
Definition: parse.h:203
This & createChild(Stream &s, std::string name)
Definition: parse.h:307
Context & context()
Definition: parse.h:330
bool operator<(const Fail &other) const
Definition: parse.h:220
bool next(TokenId id)
Definition: parse.h:518
ListIterator< List > begin(List l)
Definition: list.h:420
Token eat(TokenId id)
Definition: parse.h:371
void consume(const std::string &s)
Definition: parse.h:111
void consume(const Token &t)
Definition: parse.h:115
Fail::Type FailType
Definition: parse.h:323
void semicolon()
Definition: parse.h:353
#define assert(x)
Definition: test.h:30
Position position
Definition: parse.h:33
Type type
Definition: parse.h:218
~Fail()
Definition: parse.h:229
std::priority_queue< Fail > failures
Definition: parse.h:232
Type
Definition: parse.h:214
const char * expected
Definition: parse.h:217
std::string window(unsigned n)
Definition: parse.h:83
int position
Definition: parse.h:216
Parser(Context &c)
Definition: parse.h:526
std::deque< Token > window
Definition: parse.h:206
Token(Id _id, std::string d)
Definition: parse.h:42
Token decide()
Definition: parse.h:190
int window_pos
Definition: parse.h:207
ParseContext< Token, Stream > This
Definition: parse.h:210
bool operator==(const Token &o) const
Definition: parse.h:45
Parser()
Definition: parse.h:527
ParseContext< Token, Stream > Context
Definition: parse.h:320
_Id Id
Definition: parse.h:30
void many(I i)
Definition: parse.h:454
void list(I i, TokenId first, TokenId sep, TokenId last)
Definition: parse.h:502
int _position
Definition: parse.h:324
bool maybe(TokenId id)
Definition: parse.h:442
std::vector< This > children
Definition: parse.h:211
void either(F f, void(G::*g)())
Definition: parse.h:394
bool maybe(F f, G g)
Definition: parse.h:412
Token::Id TokenId
Definition: parse.h:319
bool maybe(void(F::*f)())
Definition: parse.h:431
void colon()
Definition: parse.h:362
Token _match
Definition: parse.h:71
int column
Definition: parse.h:21
int position()
Definition: parse.h:335
void errors(std::ostream &o)
Definition: parse.h:259
bool match(I begin, I end)
Definition: parse.h:128
void list(I i, TokenId sep)
Definition: parse.h:481
Id id
Definition: parse.h:31
Position current
Definition: parse.h:69
Stream & stream
Definition: parse.h:66
bool ensure_window(unsigned n)
Definition: parse.h:92
void fail(const char *what, FailType type=FailType::Syntax) __attribute__((noreturn))
Definition: parse.h:344
Context::Fail Fail
Definition: parse.h:322
void match(const std::string &data, typename Token::Id id)
Definition: parse.h:134
Stream & stream()
Definition: parse.h:204
void keep(typename Token::Id id, const std::string &data)
Definition: parse.h:120
Token(Id _id, char c)
Definition: parse.h:38
ListIterator< List > end(List)
Definition: list.h:425
void clearErrors()
Definition: parse.h:234
bool maybe(F f, G g, H h)
Definition: parse.h:420
size_t matchLength(int idx)
Definition: regexp.cpp:120