shithub: pprolog

Info  •  Files  •  Log

Add a term parser.

--- a/dat.h

+++ b/dat.h

@@ -1,1 +1,28 @@

+typedef struct Term Term;

+struct Term

+{

+	int tag;

+

+	Rune *text;

+	int arity;

+	Term *next;

+	Term *children;

+	int numbertype;

+	vlong ival;

+	double dval;

+};

+

+enum {

+	CompoundTerm,

+	AtomTerm,

+	VariableTerm,

+	NumberTerm,

+	StringTerm,

+};

+

+enum {

+	NumberInt,

+	NumberFloat,

+};

+

 int debug;

\ No newline at end of file

--- /dev/null

+++ b/example.pl

@@ -1,0 +1,5 @@

+:- dynamic(math/4).

+

+math(A,B,C,D) :- D is A + B + C * A.

+

+true :- 1 = 1.

--- a/fns.h

+++ b/fns.h

@@ -1,0 +1,13 @@

+/* parser.c */

+void parse(int);

+

+/* prettyprint.c */

+Rune *prettyprint(Term *);

+

+/* misc.c */

+Term *appendterm(Term *, Term *);

+int termslength(Term *);

+Term *mkatom(Rune *);

+Term *mkvariable(Rune *);

+Term *mkcompound(Rune *, int, Term *);

+Term *mknumber(int, vlong, double);

\ No newline at end of file

--- a/main.c

+++ b/main.c

@@ -9,10 +9,15 @@

 void

 main(int argc, char *argv[])

 {

+	char *parsetestfile = nil;

+

 	ARGBEGIN{

 	case 'd':

 		debug = 1;

 		break;

+	case 'f':

+		parsetestfile = EARGF(usage());

+		break;

 	default:

 		usage();

 	}ARGEND

@@ -19,6 +24,13 @@

 	if(argc != 0)

 		usage();

+

+	if(parsetestfile){

+		int fd = open(parsetestfile, OREAD);

+		if(fd < 0)

+			exits("open");

+		parse(fd);

+	}

 	exits(nil);

 }

--- /dev/null

+++ b/misc.c

@@ -1,0 +1,72 @@

+#include <u.h>

+#include <libc.h>

+

+#include "dat.h"

+#include "fns.h"

+

+Term *

+appendterm(Term *a, Term *b)

+{

+	if(a == nil)

+		return b;

+

+	Term *tmp;

+	for(tmp = a; tmp->next != nil; tmp = tmp->next);

+	tmp->next = b;

+	return a;

+}

+

+int

+termslength(Term *list)

+{

+	int len;

+	for(len = 0; list != nil; len++, list = list->next);

+	return len;

+}

+

+Term *

+mkterm(int tag)

+{

+	Term *t = malloc(sizeof(Term));

+	t->tag = tag;

+	t->next = nil;

+	t->children = nil;

+	t->text = nil;

+	return t;

+}

+

+Term *

+mkatom(Rune *name)

+{

+	Term *t = mkterm(AtomTerm);

+	t->text = name;

+	return t;

+}

+

+Term *

+mkvariable(Rune *name)

+{

+	Term *t = mkterm(VariableTerm);

+	t->text = name;

+	return t;

+}

+

+Term *

+mkcompound(Rune *name, int arity, Term *args)

+{

+	Term *t = mkterm(CompoundTerm);

+	t->text = name;

+	t->arity = arity;

+	t->children = args;

+	return t;

+}

+

+Term *

+mknumber(int type, vlong ival, double dval)

+{

+	Term *t = mkterm(NumberTerm);

+	t->numbertype = type;

+	t->ival = ival;

+	t->dval = dval;

+	return t;

+}

--- a/mkfile

+++ b/mkfile

@@ -2,7 +2,7 @@

 TARG=pprolog

-OFILES=main.$O parser.$O

+OFILES=main.$O parser.$O prettyprint.$O misc.$O

 HFILES=dat.h fns.h

--- a/parser.c

+++ b/parser.c

@@ -1,5 +1,561 @@

 #include <u.h>

 #include <libc.h>

+#include <bio.h>

 #include "dat.h"

 #include "fns.h"

+

+#define PrecedenceLevels 1200

+

+/* The parser doesn't produce an ast for now, it only acts like a recognizer,

+   printing errors if it fails */

+

+typedef struct Token Token;

+typedef struct Operator Operator;

+typedef struct OpInfo OpInfo;

+struct Token

+{

+	int	tag;

+	Rune	*text;

+	double	dval;

+	vlong	ival;

+};

+

+struct Operator

+{

+	int type;

+	int level;

+	Rune *spelling;

+	Operator *next;

+};

+

+struct OpInfo

+{

+	int level;

+	int type;

+};

+

+enum {

+	Xf	= 1<<0, /* 1 */

+	Yf	= 1<<1, /* 2 */

+	Xfx	= 1<<2, /* 4 */

+	Xfy	= 1<<3, /* 8 */

+	Yfx	= 1<<4, /* 16 */

+	Fy	= 1<<5, /* 32 */

+	Fx	= 1<<6, /* 64 */

+};

+

+enum {

+	AtomTok			= 1<<0, /* 1 */

+	FunctorTok		= 1<<1, /* 2 */

+	VarTok			= 1<<2, /* 4 */

+	StringTok		= 1<<3, /* 8 */

+	IntTok			= 1<<4, /* 16 */

+	FloatTok		= 1<<5, /* 32 */

+	ParenLeftTok		= 1<<6, /* 64 */

+	ParenRightTok		= 1<<7, /* 128 */

+	SquareBracketLeftTok	= 1<<8, /* 256 */

+	SquareBracketRightTok	= 1<<9, /* 512 */

+	CurlyBracketLeftTok	= 1<<10, /* 1024 */

+	CurlyBracketRightTok	= 1<<11, /* 2048 */

+	CommaTok		= 1<<12, /* 4096 */

+	EofTok			= 1<<13, /* 8192 */

+};

+

+static Biobuf *parsein;

+static Token lookahead;

+static Operator *operators[PrecedenceLevels];

+

+void initoperators(void);

+void addoperator(int, int, Rune *);

+Operator *getoperator(Rune *);

+void nexttoken(void);

+Term *fullterm(int, Rune *, Term *);

+Term *term(void);

+Term *compound(void);

+Term *parseoperators(Term *);

+void match(int);

+void syntaxerror(char *);

+void prologtext(void);

+

+void

+parse(int fd)

+{

+	parsein = Bfdopen(fd, OREAD);

+	if(parsein == nil){

+		print("Could not open file\n");

+		return;

+	}

+	initoperators();

+	nexttoken();

+

+	prologtext();

+}

+

+void

+prologtext(void)

+{

+	if(lookahead.tag == EofTok)

+		return;

+

+	Term *t = fullterm(AtomTok, L".", nil);

+	if(t->tag != CompoundTerm || runestrcmp(t->text, L":-") != 0 || !(t->arity == 1 || t->arity == 2)){

+		print("Expected directive or clause as toplevel\n");

+		print("Got %S\n", prettyprint(t));

+		print("Tag=%d arity=%d text=\"%S\"\n", t->tag, t->arity, t->text);

+		syntaxerror("prologtext");

+	}

+

+	if(t->arity == 1){

+		/* A directive */

+		print("Got directive: %S\n", prettyprint(t));

+	}else{

+		/* A clause */

+		print("Got clause: %S\n", prettyprint(t));

+	}

+

+	if(lookahead.tag == AtomTok && runestrcmp(lookahead.text, L".") == 0)

+		match(AtomTok);

+	else

+		syntaxerror("prologtext");

+

+	prologtext();

+}

+

+Term *

+fullterm(int stoptag, Rune *stoptext, Term *list)

+{

+	if((lookahead.tag & stoptag) && (stoptext == nil || runestrcmp(stoptext, lookahead.text) == 0))

+		return parseoperators(list);

+

+	Term *t = term();

+	list = appendterm(list, t);

+	return fullterm(stoptag, stoptext, list);

+}

+

+Term *

+term(void)

+{

+	Term *result;

+

+	switch(lookahead.tag){

+	case AtomTok:

+		result = mkatom(lookahead.text);

+		match(AtomTok);

+		break;

+	case FunctorTok:

+		result = compound();

+		break;

+	case VarTok:

+		result = mkvariable(lookahead.text);

+		match(VarTok);

+		break;

+	case IntTok:

+		result = mknumber(NumberInt, lookahead.ival, 0);

+		match(IntTok);

+		break;

+	case FloatTok:

+		result = mknumber(NumberFloat, 0, lookahead.dval);

+		match(FloatTok);

+		break;

+	default:

+		print("Cant parse term of token type %d\n", lookahead.tag);

+		syntaxerror("term");

+		result = nil;

+	}

+

+	return result;

+}

+

+Term *

+compound(void)

+{

+	Rune *name = lookahead.text;

+	Term *args = nil;

+	int arity = 0;

+

+	match(FunctorTok);

+	match(ParenLeftTok);

+

+	while(lookahead.tag != ParenRightTok){

+		Term *t = fullterm(CommaTok|ParenRightTok, nil, nil);

+		if(lookahead.tag == CommaTok)

+			match(CommaTok);

+		args = appendterm(args, t);

+		arity++;

+	}

+

+	match(ParenRightTok);

+	return mkcompound(name, arity, args);

+}

+

+Term *

+parseoperators(Term *list)

+{

+	int i;

+	int length = termslength(list);

+	Term *t;

+	Term **terms = malloc(sizeof(Term *) * length);

+	OpInfo *infos = malloc(sizeof(OpInfo) * length);

+

+	for(i = 0, t = list; i < length; i++){

+		Operator *op = getoperator(t->text);

+		if(op){

+			infos[i].type = op->type;

+			infos[i].level = op->level;

+		}else{

+			infos[i].type = 0;

+			infos[i].level = 0;

+		}

+		terms[i] = t;

+		Term *tmp = t;

+		t = t->next;

+		tmp->next = nil;

+	}

+

+	while(length > 1){

+		int index = -1;

+		int lowest = PrecedenceLevels + 1;

+		for(i = 0; i < length; i++){

+			if(infos[i].type == 0)

+				continue;

+			if(infos[i].level == lowest && infos[i].type == Xfy && i == index+1)

+				index = i;

+			else if(infos[i].level < lowest){

+				index = i;

+				lowest = infos[i].level;

+			}

+		}

+

+		if(index == -1){

+			print("Can't parse, list contains no operators");

+			syntaxerror("parseoperators");

+		}

+

+		int infixlevel = infos[index].level & (Xfx|Xfy|Yfx);

+		int prefixlevel = infos[index].level & (Fx|Fy);

+		int postfixlevel = infos[index].level & (Xf|Yf);

+

+		if(infixlevel && index != 0 && index != length-1 && infos[index-1].type == 0 && infos[index-1].type == 0){

+			infos[index-1].type = 0;

+			infos[index-1].level = infos[index].level;

+			Term *args = terms[index-1];

+			args->next = terms[index+1];

+			terms[index-1] = mkcompound(terms[index]->text, 2, args);

+			length -= 2;

+			for(i = index; i < length; i++){

+				infos[i].level = infos[i+2].level;

+				infos[i].type = infos[i+2].type;

+				terms[i] = terms[i+2];

+			}

+		}else if(prefixlevel && index != length-1 && infos[index+1].type == 0){

+			infos[index].type = 0;

+			terms[index] = mkcompound(terms[index]->text, 1, terms[index+1]);

+			length--;

+			for(i = index+1; i < length; i++){

+				infos[i].level = infos[i+1].level;

+				infos[i].type = infos[i+1].type;

+				terms[i] = terms[i+1];

+			}

+		}else if(postfixlevel && index != 0 && infos[index-1].type == 0){

+			infos[index-1].type = 0;

+			infos[index-1].level = infos[index].level;

+			terms[index-1] = mkcompound(terms[index]->text, 1, terms[index-1]);

+			length--;

+			for(i = index; i < length; i++){

+				infos[i].level = infos[i+1].level;

+				infos[i].type = infos[i+1].type;

+				terms[i] = terms[i+1];

+			}

+		}else{

+			print("Parse error when parsing operators\n");

+			syntaxerror("parseoperators");

+		}

+	}

+

+	Term *result = terms[0];

+	free(infos);

+	free(terms);

+	return result;

+}

+

+void

+initoperators(void)

+{

+	Operator *op;

+	int i;

+	for(i = 0; i < PrecedenceLevels; i++){

+		while(operators[i]){

+			op = operators[i];

+			operators[i] = op->next;

+			free(op);

+		}

+	}

+

+	addoperator(1200, Xfx, L":-");

+	addoperator(1200, Fx,  L":-");

+	addoperator(1100, Xfy, L";");

+	addoperator(1000, Xfy, L",");

+	addoperator(700,  Xfx, L"=");

+	addoperator(700,  Xfx, L"is");

+	addoperator(500,  Yfx, L"+");

+	addoperator(400,  Yfx, L"*");

+	addoperator(400,  Yfx, L"/");

+}

+

+void

+addoperator(int level, int type, Rune *spelling)

+{

+	Operator *op = malloc(sizeof(Operator));

+	op->type = type;

+	op->level = level;

+	op->spelling = spelling;

+	op->next = operators[level-1];

+	operators[level-1] = op;

+}

+

+Operator *

+getoperator(Rune *spelling)

+{

+	Operator *op = nil;

+	int level;

+

+	if(spelling == nil)

+		return nil;

+

+	for(level = 0; level < PrecedenceLevels && op == nil; level++){

+		Operator *tmp;

+		for(tmp = operators[level]; tmp != nil; tmp = tmp->next){

+			if(runestrcmp(tmp->spelling, spelling) == 0){

+				if(op == nil){

+					op = malloc(sizeof(Operator));

+					memcpy(op, tmp, sizeof(Operator));

+				}else

+					op->type |= tmp->type;

+			}

+		}

+	}

+	return op;

+}

+

+void

+nexttoken(void)

+{

+	Rune buf[1024];

+	Rune peek;

+	int i = 0;

+	double numD;

+	vlong numI = 0;

+	int negative = 0;

+	static long replaypeek = -1;

+

+	if(replaypeek == -1)

+		peek = Bgetrune(parsein);

+	else{

+		peek = replaypeek;

+		replaypeek = -1;

+	}

+

+	/* Skip whitespace */

+	while(isspacerune(peek))

+		peek = Bgetrune(parsein);

+

+	/* Skip single line comments */

+	if(peek == L'%'){

+		while(peek != L'\n')

+			peek = Bgetrune(parsein);

+		peek = Bgetrune(parsein);

+	}

+

+	/* Variables */

+	if(peek == L'_' || isupperrune(peek)){

+		while(peek == L'_' || isalpharune(peek) || isdigitrune(peek)){

+			/* FIXME Should handle input length, also elsewhere in this function */

+			buf[i++] = peek;

+			peek = Bgetrune(parsein);

+		}

+		buf[i] = '\0';

+		Bungetrune(parsein);

+

+		lookahead.tag = VarTok;

+		lookahead.text = runestrdup(buf);

+		return;

+	}

+

+	/* Strings */

+	if(peek == L'"'){

+		peek = Bgetrune(parsein);

+		while(peek != L'"'){

+			buf[i++] = peek;

+			peek = Bgetrune(parsein);

+		}

+		buf[i] = '\0';

+		lookahead.tag = StringTok;

+		lookahead.text = runestrdup(buf);

+		return;

+	}

+

+	/* Numbers */

+	if(peek == L'-'){

+		peek = Bgetrune(parsein);

+		if(isdigitrune(peek))

+			negative = 1;

+		else{

+			Bungetrune(parsein);

+			peek = L'-';

+		}

+	}

+	if(isdigitrune(peek)){

+		if(peek == L'0'){

+			peek = Bgetrune(parsein);

+			switch(peek){

+			case L'o': /* Octal */

+			case L'x': /* Hexadecimal */

+			case L'b': /* Binary */

+				print("Cant lex numbers in other bases than base 10 right now\n");

+				exits("lexer");

+			}

+		}

+		while(isdigitrune(peek)){

+			numI *= 10;

+			numI += peek - L'0';

+			peek = Bgetrune(parsein);

+		}

+		if(peek == L'.'){

+			int place = 1;

+			numD = numI;

+			peek = Bgetrune(parsein);

+			if(!isdigitrune(peek)){

+				Bungetrune(parsein);

+				replaypeek = L'.';

+				goto Integer;

+			}

+			while(isdigitrune(peek)){

+				numD += (peek - L'0') / (10 * place);

+				peek = Bgetrune(parsein);

+			}

+			/* Should also lex 123.45E10 */

+			lookahead.tag = FloatTok;

+			lookahead.dval = negative ? -numD : numD;

+		}else{

+			Bungetrune(parsein);

+Integer:

+			lookahead.tag = IntTok;

+			lookahead.ival = negative ? -numI : numI;

+		}

+		return;

+	}

+

+	/* Atoms */

+	/* Atoms in single quotes */

+	if(peek == L'\''){

+		peek = Bgetrune(parsein);

+		while(peek != L'\''){

+			buf[i++] = peek;

+			peek = Bgetrune(parsein);

+		}

+		buf[i] = '\0';

+		lookahead.tag = AtomTok;

+		lookahead.text = runestrdup(buf);

+		goto Functor;

+	}

+

+	/* Special atom [] */

+	if(peek == L'['){

+		peek = Bgetrune(parsein);

+		if(peek == L']'){

+			lookahead.tag = AtomTok;

+			lookahead.text = runestrdup(L"[]");

+			goto Functor;

+		}else{

+			Bungetrune(parsein);

+			lookahead.tag = SquareBracketLeftTok;

+			return;

+		}

+	}

+

+	/* Special atom {} */

+	if(peek == L'{'){

+		peek = Bgetrune(parsein);

+		if(peek == L'}'){

+			lookahead.tag = AtomTok;

+			lookahead.text = runestrdup(L"{}");

+			goto Functor;

+		}else{

+			Bungetrune(parsein);

+			lookahead.tag = CurlyBracketLeftTok;

+			return;

+		}

+	}

+

+	/* Graphic atom */

+	Rune *graphics = L"#$&*+-./:<=>?@^~\\";

+	if(runestrchr(graphics, peek)){

+		while(runestrchr(graphics, peek)){

+			buf[i++] = peek;

+			peek = Bgetrune(parsein);

+		}

+		buf[i] = '\0';

+		Bungetrune(parsein);

+		lookahead.tag = AtomTok;

+		lookahead.text = runestrdup(buf);

+		goto Functor;

+	}

+

+	/* simple atom */

+	if(islowerrune(peek)){

+		while(isalpharune(peek) || isdigitrune(peek) || peek == L'_'){

+			buf[i++] = peek;

+			peek = Bgetrune(parsein);

+		}

+		buf[i] = '\0';

+		Bungetrune(parsein);

+		lookahead.tag = AtomTok;

+		lookahead.text = runestrdup(buf);

+		goto Functor;

+	}

+

+	/* Other */

+	if(runestrchr(L",.()]}", peek)){

+		switch(peek){

+		case L',': lookahead.tag = CommaTok; break;

+		case L'(': lookahead.tag = ParenLeftTok; break;

+		case L')': lookahead.tag = ParenRightTok; break;

+		case L']': lookahead.tag = SquareBracketRightTok; break;

+		case L'}': lookahead.tag = CurlyBracketRightTok; break;

+		}

+		return;

+	}

+

+	/* EOF */

+	if(peek == Beof){

+		lookahead.tag = EofTok;

+		return;

+	}

+

+	print("Could not lex rune %C (%ud)\n", peek, peek);

+	exits("lexer");

+

+Functor:

+	peek = Bgetrune(parsein);

+	if(peek == L'(')

+		lookahead.tag = FunctorTok;

+	Bungetrune(parsein);

+	return;

+}

+

+void

+match(int tag)

+{

+	if(lookahead.tag == tag)

+		nexttoken();

+	else

+		syntaxerror("match");

+}

+

+void

+syntaxerror(char *where)

+{

+	print("Syntax error: Unexpected %d token in %s\n", lookahead.tag, where);

+	exits("syntax error");

+}

\ No newline at end of file

--- /dev/null

+++ b/prettyprint.c

@@ -1,0 +1,61 @@

+#include <u.h>

+#include <libc.h>

+

+#include "dat.h"

+#include "fns.h"

+

+Rune *prettyprintlist(Term *, Rune *, int);

+

+Rune *

+prettyprint(Term *t)

+{

+	Rune *result;

+	Rune *args;

+

+	switch(t->tag){

+	case CompoundTerm:

+		args = prettyprintlist(t->children, L", ", 0);

+		result = runesmprint("%S(%S)", t->text, args);

+		free(args);

+		break;

+	case AtomTerm:

+	case VariableTerm:

+		result = runesmprint("%S", t->text);

+		break;

+	case NumberTerm:

+		if(t->numbertype == NumberInt)

+			result = runesmprint("%lld", t->ival);

+		else

+			result = runesmprint("%f", t->dval);

+		break;

+	default:

+		result = runesmprint("cant print term with tag %d", t->tag);

+		break;

+	}

+

+	return result;

+}

+

+Rune *

+prettyprintlist(Term *t, Rune *sep, int end)

+{

+	if(t == nil){

+		if(end)

+			return runesmprint("%S", sep);

+		else

+			return runesmprint("");

+	}

+

+	Rune *str = prettyprint(t);

+	Rune *rest = prettyprintlist(t->next, sep, end);

+	Rune *result;

+

+	if(t->next != nil)

+		result = runesmprint("%S%S%S", str, sep, rest);

+	else

+		result = runesmprint("%S%S", str, end ? rest : L"");

+

+	free(str);

+	free(rest);

+	return result;

+}

\ No newline at end of file