#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <stdbool.h>
#include <string.h>

/// scanner

// constants

enum {
	MAX_IDENT_LEN = 10,
	MAX_SYMBOLS = 101
};

// helpers

// djb2 hash
unsigned int hash( const char *s )
{
	unsigned int h = 5381;
	int c;

	while( ( c = *s++ ) ) {
		h = ((h << 5) + h) + c;
	}

	return h;
}

// token types

typedef enum {
	S_undef,
	S_token,
	S_number,
	S_ident,
	S_false,
	S_true,
	S_eof
} Sym;

typedef struct {
	Sym sym;
	union {
		char s[MAX_IDENT_LEN];
		int n;
		bool b;
	};
	int tag;
} Symbol;

char *symbol_tostr( Symbol s, char *buf, size_t buflen )
{
	switch( s.sym ) {
		case S_undef:
			snprintf( buf, buflen, "UNDEF" );
			break;

		case S_token:
			if( isprint( s.tag ) ) {
				snprintf( buf, buflen, "TOK(%c)", s.tag );
			} else {
				snprintf( buf, buflen, "TOK(0x%dx)", s.tag );
			}
			break;

		case S_number:
			snprintf( buf, buflen, "NUMBER(%d)", s.n );
			break;

		case S_ident:
			snprintf( buf, buflen, "IDENT(%s)", s.s );
			break;
				
		case S_false:
			snprintf( buf, buflen, "FALSE" );
			break;

		case S_true:
			snprintf( buf, buflen, "TRUE" );
			break;

		case S_eof:
			snprintf( buf, buflen, "EOF" );
			break;

		default:
			snprintf( buf, buflen, "ILLEGAL(%d)", s.sym );
			
	}

	return buf;
}

typedef struct {
	int peek;
	int row;
	int col;
	FILE *f;
	Symbol words[MAX_SYMBOLS];
} Scanner;

void scanner_word_insert( Scanner *s, const char *w, Sym sym )
{
	Symbol word;
	unsigned int h = hash( w ) % MAX_SYMBOLS;
	word.sym = sym;
	strncpy( word.s, w, MAX_IDENT_LEN );
	word.s[MAX_IDENT_LEN-1] = '\0';
	if( s->words[h].sym == S_undef ) {
		s->words[hash( w ) % MAX_SYMBOLS] = word;
	} else {
		fprintf( stderr, "Hashtable overflow\n" );
		exit( 1 );
	}
}

Symbol *scanner_word_get( Scanner *s, const char *w )
{
	unsigned int h = hash( w ) % MAX_SYMBOLS;
	if( s->words[h].sym != S_undef ) {
		return &s->words[h];
	}
	return NULL;
}

void scanner_init( Scanner *s, FILE *f )
{
	s->peek = ' ';
	s->row = 1;
	s->col = 1;
	s->f = f;
	
	memset( s->words, 0, sizeof( s->words ) );
	
	scanner_word_insert( s, "false", S_false );
	scanner_word_insert( s, "true", S_true );
}

void scanner_skip_whitespace( Scanner *s )
{
	for( ; ; s->peek = getc( s->f ) ) {
		s->col++;
		if( s->peek == ' ' || s->peek == '\t' ) {
			continue;
		} else if( s->peek == '\n' ) {
			s->row++;
			s->col = 1;
		} else if( s->peek == EOF ) {
			break;
		} else {
			break;
		}
	}
}

Symbol scanner_get_int( Scanner *s )
{
	Symbol sym;

	sym.sym = S_number;
	sym.n = 0;

	do {
		sym.n = sym.n * 10 + ( s->peek - '0' );
		s->peek = getc( s->f );
	} while( isdigit( s->peek ) && ( s->peek != EOF ) );

	return sym;
}

Symbol scanner_get_ident( Scanner *s )
{
	Symbol newSym;
	Symbol *sym;

	newSym.sym = S_ident;
	newSym.s[0] = '\0';
	char *p = newSym.s;

	do {
		*p++ = s->peek;
		s->peek = getc( s->f );
	} while( isalnum( s->peek ) && ( s->peek != EOF ) && ( p - newSym.s < MAX_IDENT_LEN ) );

	*p = '\0';

	sym = scanner_word_get( s, newSym.s );
	if( sym != NULL ) {
		return *sym;
	} else {
		scanner_word_insert( s, newSym.s, S_ident );
		return newSym;
	}
}

Symbol scanner_scan( Scanner *s )
{
	Symbol sym;

	if( s->peek == EOF ) {
		sym.sym = S_eof;
		return sym;
	}

	scanner_skip_whitespace( s );

	if( isdigit( s->peek ) ) {
		sym = scanner_get_int( s );
		return sym;
	} else if( isalpha( s->peek ) ) {
		sym = scanner_get_ident( s );
		return sym;
	} else if( s->peek == EOF ) {
		sym.sym = S_eof;
		return sym;
	} else {
		sym.sym = S_token;
		sym.tag = s->peek;
		s->peek = ' ';
	}
	
	return sym;
}

/// parser

typedef struct {
	Scanner *s;
} Parser;

void parser_init( Parser *p, Scanner *s )
{
	p->s = s;
}

void parser_error( Parser *p, const char *s, Symbol sym )
{
	char errbuf[255];
	fprintf( stderr, "\nERR: %s at symbol '%s' at line %d, column %d\n",
		s, symbol_tostr( sym, errbuf, 255 ), p->s->row, p->s->col );
	exit( 1 );
}

void parser_term( Parser *p )
{
	Symbol s = scanner_scan( p->s );
	
	if( s.sym == S_number ) {
		printf( "%d ", s.n );
	} else if( s.sym == S_ident ) {
		printf( "%s ", s.s );
	} else {
		parser_error( p, "expecting number", s );
	}
}

void parser_rest( Parser *p )
{
	Symbol s = scanner_scan( p->s );

	if( s.sym == S_token ) {
		switch( s.tag ) {
			case '+':
				parser_term( p );
				putchar( '+' ); putchar( ' ' );
				parser_rest( p );
				break;		

			case '-':
				parser_term( p );
				putchar( '-' ); putchar( ' ' );
				parser_rest( p );
				break;		
			default:
				parser_error( p, "expecting operator '+' or '-'", s );
		}
	} else if( s.sym == S_eof ) {
		return;
	} else {
		parser_error( p, "expecting an operator '+' or '-'", s );
	}
}

void parser_expr( Parser *p )
{
	parser_term( p );
	parser_rest( p );
}

void parser_parse( Parser *p )
{
	parser_expr( p );
}

/// main

int main( void )
{
	Scanner s;
	Parser p;

	scanner_init( &s, stdin );
	parser_init( &p, &s );

	parser_parse( &p );

	puts( "" );

	exit( 0 );
}