initial checkin

2 files changed, 328 insertions, 0 deletions

diff --git a/test3/Makefile b/test3/Makefile
new file mode 100644
index 0000000..ee3f68c
--- /dev/null
+++ b/test3/Makefile
@@ -0,0 +1,16 @@
+CFLAGS=-std=c99 -Wall -Werror -g
+
+all: parse
+
+test: parse
+	printf "9-5+2" | ./parse
+	printf "9 - 5 + 2" | ./parse
+	printf "91 - 35 + 23" | ./parse
+	-printf "91-" | ./parse
+	-printf "+22" | ./parse
+	-printf "x+y-22" | ./parse
+	-printf "hello" | ./parse
+	-printf "false+true" | ./parse
+
+clean:
+	-rm -f parse
diff --git a/test3/parse.c b/test3/parse.c
new file mode 100644
index 0000000..cba854e
--- /dev/null
+++ b/test3/parse.c
@@ -0,0 +1,312 @@
+#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 );
+}