Anonymous avatar Anonymous committed f41de62

Initial import of Kangaroo Iceberg version 0.5 revision 2007.0406.

Comments (0)

Files changed (16)

+KangarooIceberg	::= {TopLevelNode}.
+TopLevelNode	::= NodeName NodeLit.
+NodeLit		::= "{" {ArcDefn} ["/" RuleSets] "}".
+
+ArcDefn		::= NodeRef ":" WeightDefn.
+NodeRef		::= NodeLit | "^" NodeName | NodeName NodeLit.
+WeightDefn	::= <<literal integer>>.
+
+RuleSets	::= RuleSet {";" RuleSet}.
+RuleSet		::= Rule {"," Rule}.
+Rule		::= {ArcApp} "->" {ArcApp}.
+
+ArcApp		::= NodeApp ":" WeightApp.
+NodeApp		::= NodeRefn | Var<Node>.
+WieghtApp	::= WeightDefn | Var<Weight>.
+
+Var		::= "$" Name.
+A { ^A:0 / ^A:0 -> ^A:1 }
+B { / ^B:0 -> ^B:1, ^B:1 -> ^B:2 }
+C { {}:0 / ^K:0 -> ^K:1, ^K:1 -> ^K:2; ^A:1 -> ^A:0 }
+A { ^A:0 ^B:1 }
+B { ^C:1 { ^C:1 }:9 }
+C { ^A:1 D { ^B:1 ^B:1 ^B:1 ^B:1 ^B:1 }:3 }
+E { ^E:0 }
+# BSD Makefile for kiceberg.
+# $Id$
+
+CC=	gcc
+CFLAGS=	-Wall
+LIBS=	
+
+.ifdef DEBUG
+CFLAGS+= -g
+.endif
+
+OBJS=	graph.o rule.o \
+	symbol.o \
+	scan.o parse.o \
+	main.o
+
+all: kiceberg
+
+kiceberg: $(OBJS)
+	$(CC) $(CFLAGS) $(OBJS) -o kiceberg $(LIBS)
+
+rule.o: rule.c rule.h symbol.h mem.h
+	$(CC) $(CFLAGS) -c rule.c -o rule.o
+
+graph.o: graph.c graph.h symbol.h mem.h
+	$(CC) $(CFLAGS) -c graph.c -o graph.o
+
+symbol.o: symbol.c symbol.h mem.h
+	$(CC) $(CFLAGS) -c symbol.c -o symbol.o
+
+scan.o: scan.c scan.h mem.h
+	$(CC) $(CFLAGS) -c scan.c -o scan.o
+
+parse.o: parse.c parse.h scan.h symbol.h
+	$(CC) $(CFLAGS) -c parse.c -o parse.o
+
+main.o: main.c scan.h parse.h
+	$(CC) $(CFLAGS) -c main.c -o main.o
+
+clean:
+	rm -f *.o *.core kiceberg
+/*
+ * Copyright (c)2004 Cat's Eye Technologies.  All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ *   Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * 
+ *   Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * 
+ *   Neither the name of Cat's Eye Technologies nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission. 
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+/*
+ * graph.h
+ * Graph housekeeping and manipulation for kiceberg.
+ * $Id$
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "graph.h"
+#include "symbol.h"
+#include "mem.h"
+
+struct node *
+node_new(struct symbol *sym)
+{
+	struct node *n;
+
+	MALLOC(n, node, "graph node");
+
+	n->head = NULL;
+	n->name = sym;
+
+	if (sym != NULL)
+		sym->dest = n;
+
+	return(n);
+}
+
+void
+node_free(struct node *n)
+{
+	struct arc *a, *a_last = NULL;
+
+	a = n->head;
+	while (a != NULL) {
+		a_last = a;
+		a = a->next;
+		FREE(a_last, "arc");
+	}
+	FREE(n, "graph node");
+}
+
+void
+graph_free(struct node *n)
+{
+	/* struct arc *a; */
+
+	/* free all nodes connected to arcs */
+	/* construct an itinerary and so forth */
+	node_free(n);
+}
+
+struct arc *
+node_arc_add(struct node *n, struct symbol *name, int weight)
+{
+	struct arc *a;
+
+	MALLOC(a, arc, "graph arc");
+
+	a->name = name;
+	a->weight = weight;
+
+	a->next = n->head;
+	n->head = a;
+	
+	return(a);
+}
+
+struct itinerary *
+itinerary_new(void)
+{
+	struct itinerary *i;
+
+	MALLOC(i, itinerary, "itinerary");
+	i->head = NULL;
+	return(i);
+}
+
+void
+itinerary_free(struct itinerary *i)
+{
+	struct visit *v, *v_last = NULL;
+
+	v = i->head;
+	while (v != NULL) {
+		v_last = v;
+		v = v->next;
+		FREE(v_last, "visit");
+	}
+}
+
+struct visit *
+itinerary_add(struct itinerary *i, struct node *n)
+{
+	struct visit *v;
+
+	MALLOC(v, visit, "visit");
+
+	v->dest = n;
+
+	v->next = i->head;
+	i->head = v;
+
+	return(v);
+}
+
+int
+itinerary_find(struct itinerary *i, struct node *n)
+{
+	struct visit *v;
+
+	for (v = i->head; v != NULL; v = v->next) {
+		if (v->dest == n)
+			return(1);
+	}
+	
+	return(0);
+}
+
+
+void
+node_dump(struct node *n)
+{
+	struct arc *a;
+
+	if (n == NULL) {
+		fprintf(stderr, " *NULLNODE { }\n");
+		return;
+	}
+	symbol_print(n->name);
+	fprintf(stderr, " { ");
+
+	for (a = n->head; a != NULL; a = a->next)
+		arc_dump(a);
+
+	fprintf(stderr, "}\n");
+}
+
+void
+arc_dump(struct arc *a)
+{
+	if (a == NULL) {
+		fprintf(stderr, "*NULLARC*");
+		return;
+	}
+
+	symbol_print(a->name);
+	fprintf(stderr, ":%d ", a->weight);
+}
+
+void
+graph_dump(struct node *start)
+{
+	struct itinerary *i;
+		
+	i = itinerary_new();
+	graph_dump_r(start, i, 0);
+	fprintf(stderr, "\n");
+}
+
+#define INDENT(x) { int j; for (j = 0; j < x; j++) fprintf(stderr, "  "); }
+
+void
+graph_dump_r(struct node *n, struct itinerary *i, int indent)
+{
+	struct arc *a;
+
+	if (n == NULL)
+		return;
+
+	INDENT(indent);
+	
+	if (itinerary_find(i, n)) {
+		symbol_print(n->name);
+	} else {
+		itinerary_add(i, n);
+		symbol_print(n->name);
+		fprintf(stderr, " {\n");
+		for (a = n->head; a != NULL; a = a->next) {
+			graph_dump_r(a->name->dest, i, indent + 1);
+			fprintf(stderr, ":%d\n", a->weight);
+		}
+		INDENT(indent);
+		fprintf(stderr, "}");
+	}
+}
+/*
+ * graph.h
+ * Graph structures and prototypes for kiceberg.
+ * $Id$
+ */
+
+#ifndef __GRAPH_H
+#define __GRAPH_H
+
+#include "symbol.h"
+
+struct node {
+	struct arc		*head;
+	struct symbol		*name;
+};
+
+struct arc {
+	struct arc		*next;
+	struct symbol		*name;	/* symbol of node that this arc points to */
+	int			 weight;
+};
+
+struct itinerary {
+	struct visit		*head;
+};
+
+struct visit {
+	struct visit		*next;
+	struct node		*dest;
+};
+
+struct node		*node_new(struct symbol *);
+void			 node_free(struct node *);
+void			 graph_free(struct node *);
+struct arc		*node_arc_add(struct node *, struct symbol *, int);
+
+struct itinerary	*itinerary_new(void);
+void			 itinerary_free(struct itinerary *);
+struct visit		*itinerary_add(struct itinerary *, struct node *);
+int			 itinerary_find(struct itinerary *, struct node *);
+
+void			 node_dump(struct node *);
+void			 arc_dump(struct arc *);
+void			 graph_dump(struct node *);
+void			 graph_dump_r(struct node *, struct itinerary *, int);
+
+#endif /* !__GRAPH_H */
+/*
+ * Copyright (c)2004 Cat's Eye Technologies.  All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ *   Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * 
+ *   Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * 
+ *   Neither the name of Cat's Eye Technologies nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission. 
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+
+/*
+ * main.c
+ * kiceberg - Reference interpreter for
+ * "The Kangaroo Iceberg Programming Language"
+ * $Id$
+ */
+
+#include <stdio.h>
+#include <sysexits.h>
+#include <unistd.h>
+
+#include "scan.h"
+#include "parse.h"
+#include "symbol.h"
+
+#include "graph.h"
+#include "rule.h"
+
+/* GLOBALS */
+
+struct symbol_table	*gstab;	/* general symbol table */
+struct legislature	*glaw;	/* all rules */
+	
+/* PROTOTYPES */
+
+void			 usage(void);
+
+/* FUNCTIONS */
+
+int
+main(int argc, char **argv)
+{
+	struct scan_st *sc;
+	int ch;
+	int do_dump = 0;
+	struct node *global;
+
+	/* Initialize / allocate globals. */
+	
+	gstab = symbol_table_new();
+	global = node_new(symbol_define(gstab, "__GLOBAL__", SYM_TYPE_NODE));
+	glaw = legislature_new();
+
+	/* Parse arguments. */
+
+	while ((ch = getopt(argc, argv, "d")) != -1) {
+		switch(ch) {
+		case 'd':
+			do_dump = 1;
+			break;
+		case '?':
+		default:
+			usage();
+		}
+	}
+	argc -= optind;
+	argv += optind;
+	
+	/* Parse the input file. */
+
+	while (argc > 0) {
+		sc = scan_open(argv[0]);
+		kangaroo_iceberg(sc, global);
+		scan_close(sc);
+		argc--;
+		argv++;
+	}
+
+	if (do_dump) {
+		fprintf(stderr, "*** Symbol Table ***\n");
+		symbol_table_dump(0, gstab);
+		fprintf(stderr, "\n");
+		fprintf(stderr, "*** Global Graph Node ***\n");
+		graph_dump(global);
+		fprintf(stderr, "*** All Rulesets ***\n");
+		legislature_dump(glaw);
+		fprintf(stderr, "\n");
+	}
+
+	/* symbol_table_free(gstab); */
+	exit(EX_OK);
+}
+
+void
+usage(void)
+{
+	fprintf(stderr, "usage: kiceberg [-d] srcfile ...\n");
+	exit(EX_USAGE);
+}
+/*
+ * mem.h
+ * Memory management macros for kiceberg.
+ * $Id$
+ */
+
+#include <err.h>
+
+#ifdef TRACK_ALLOCATION
+#define TRACK_MALLOC(pointer, structdesc)				\
+		fprintf(stderr, "***** MALLOC'ed " structdesc		\
+		    " %08lx\n", pointer);
+#define TRACK_FREE(pointer, structdesc)					\
+		fprintf(stderr, "***** FREE'ed " structdesc		\
+		    " %08lx\n", pointer);
+#else
+#define	TRACK_MALLOC(pointer, structdesc)
+#define	TRACK_FREE(pointer, structdesc)
+#endif
+
+#define MALLOC(pointer, structure, structdesc)				\
+	{								\
+		if ((pointer = (struct structure *)			\
+		    malloc(sizeof(struct structure))) == NULL)		\
+			errx(1, "Can't allocate " structdesc);		\
+		TRACK_MALLOC(pointer, structdesc);			\
+	}
+
+#define FREE(pointer, structdesc)					\
+	{								\
+		free(pointer);						\
+		TRACK_FREE(pointer, structdesc);			\
+	}
+/*
+ * Copyright (c)2004 Cat's Eye Technologies.  All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ *   Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * 
+ *   Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * 
+ *   Neither the name of Cat's Eye Technologies nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission. 
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+/*
+ * parse.c
+ * Recursive-descent parser for kiceberg.
+ * $Id$
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "scan.h"
+#include "parse.h"
+#include "symbol.h"
+
+#include "graph.h"
+#include "rule.h"
+
+extern struct symbol_table	*gstab;
+extern struct legislature	*glaw;
+
+/*** GRAPH ***/
+
+void
+kangaroo_iceberg(struct scan_st *sc, struct node *global)
+{
+	struct symbol *name;
+
+	while (tokis(sc, TOKEN_IDENTIFIER)) {
+		name = top_level_node(sc);
+		node_arc_add(global, name, 0);
+	}
+}
+
+struct symbol *
+top_level_node(struct scan_st *sc)
+{
+	struct symbol *sym = NULL;
+	struct node *n;
+
+	sym = node_name(sc, gstab, SYM_LOOKUP_DEFINE);
+	n = node_lit(sc, sym);
+
+	return(sym);
+}
+
+struct symbol *
+node_name(struct scan_st *sc, struct symbol_table *stab, int lookup)
+{
+	struct symbol *sym;
+	int type = SYM_TYPE_NODE;
+
+	sym = symbol_lookup(stab, sc->token);
+
+	if (lookup == SYM_LOOKUP_UNIQUE) {
+		if (sym != NULL) {
+			scan_error(sc, "Symbol '%s' already defined", sc->token);
+			scan(sc);
+			return(NULL);
+		} else {
+			sym = symbol_define(stab, sc->token, type);
+			scan(sc);
+			return(sym);
+		}
+	} else if (lookup == SYM_LOOKUP_DEFINE) {
+		if (sym != NULL) {
+			scan(sc);
+			return(sym);
+		} else {
+			sym = symbol_define(stab, sc->token, type);
+			scan(sc);
+			return(sym);
+		}
+	} else if (lookup == SYM_LOOKUP_EXTANT) {
+		if (sym == NULL) {
+			scan_error(sc, "Symbol '%s' not defined", sc->token);
+			scan(sc);
+			return(NULL);
+		} else {
+			scan(sc);
+			return(sym);
+		}
+	}
+
+	return(NULL);
+}
+
+struct node *
+node_lit(struct scan_st *sc, struct symbol *sym)
+{
+	struct node *n = NULL;
+	struct ruleset *rs = NULL;
+
+	scan_expect(sc, "{");
+	n = node_new(sym);
+	while (tokne(sc, "/") && tokne(sc, "}") && !tokis(sc, TOKEN_EOF)) {
+		arc_defn(sc, n);
+	}
+	if (tokeq(sc, "/")) {
+		scan(sc);
+		rs = ruleset(sc, sym);
+		while(tokeq(sc, ";")) {
+			scan(sc);
+			rs = ruleset(sc, sym);
+		}
+	}
+	scan_expect(sc, "}");
+	
+	return(n);
+}	
+
+void
+arc_defn(struct scan_st *sc, struct node *n)
+{
+	struct symbol *name;
+	int weight;
+
+	name = node_ref(sc);
+	scan_expect(sc, ":");
+	weight = weight_defn(sc);
+	node_arc_add(n, name, weight);
+}
+
+struct symbol *
+node_ref(struct scan_st *sc)
+{
+	struct symbol *sym = NULL;
+	struct node *dest = NULL;
+
+	if (tokeq(sc, "{")) {
+		sym = symbol_new_anon(gstab, SYM_TYPE_NODE);
+		dest = node_lit(sc, sym);
+	} else if (tokeq(sc, "^")) {
+		scan(sc);
+		sym = node_name(sc, gstab, SYM_LOOKUP_DEFINE);
+	} else if (tokis(sc, TOKEN_IDENTIFIER)) {
+		sym = node_name(sc, gstab, SYM_LOOKUP_UNIQUE);
+		dest = node_lit(sc, sym);
+	} else {
+		scan_error(sc, "Expected identifier, `^', or `{'");
+	}
+	return(sym);
+}
+
+int
+weight_defn(struct scan_st *sc)
+{
+	int weight;
+
+	weight = atoi(sc->token);
+	scan(sc);
+
+	return(weight);
+}
+
+/*** RULES ***/
+
+struct ruleset *
+ruleset(struct scan_st *sc, struct symbol *sym)
+{
+	struct ruleset *rs;
+
+	rs = ruleset_new(glaw, sym);
+	rule(sc, rs);
+	while(tokeq(sc, ",")) {
+		scan(sc);
+		rule(sc, rs);
+	}
+
+	ruleset_dump(rs);
+
+	return(rs);
+}
+
+void
+rule(struct scan_st *sc, struct ruleset *rs)
+{
+	struct rule *r;
+
+	r = rule_new(rs);
+	while(tokne(sc, "->") && !tokis(sc, TOKEN_EOF)) {
+		arc_app(sc, r, PATTERN_ADD_MATCH);
+	}
+	scan_expect(sc, "->");
+	while(tokne(sc, ",") && tokne(sc, ";") && tokne(sc, "}") &&
+	      !tokis(sc, TOKEN_EOF)) {
+		arc_app(sc, r, PATTERN_ADD_REWRITE);
+	}
+}
+
+void
+arc_app(struct scan_st *sc, struct rule *r, int which_side)
+{
+	struct symbol *name;
+	int weight;
+
+	name = node_app(sc);
+	scan_expect(sc, ":");
+	weight = weight_app(sc);
+	rule_pattern_add(which_side, r, name, weight);
+}
+
+struct symbol *
+node_app(struct scan_st *sc)
+{
+	struct symbol *name = NULL;
+
+	if (tokeq(sc, "$")) {
+		var_name(sc);
+	} else {
+		name = node_ref(sc);
+	}
+	
+	return(name);
+}
+
+int
+weight_app(struct scan_st *sc)
+{
+	int weight = 0;
+
+	if (tokeq(sc, "$")) {
+		var_name(sc);
+	} else {
+		weight = weight_defn(sc);
+	}
+	
+	return(weight);
+}
+
+void
+var_name(struct scan_st *sc)
+{
+	scan_expect(sc, "$");
+	scan(sc);
+}
+/*
+ * parse.h
+ * Parser structures and prototypes for kiceberg.
+ * $Id$
+ */
+
+#ifndef __PARSE_H
+#define __PARSE_H
+
+#include "scan.h"
+#include "symbol.h"
+#include "graph.h"
+#include "rule.h"
+
+void			 kangaroo_iceberg(struct scan_st *, struct node *);
+struct symbol		*top_level_node(struct scan_st *);
+struct symbol		*node_name(struct scan_st *, struct symbol_table *, int);
+struct node		*node_lit(struct scan_st *, struct symbol *);
+void			 arc_defn(struct scan_st *, struct node *);
+struct symbol		*node_ref(struct scan_st *);
+int			 weight_defn(struct scan_st *);
+struct ruleset		*ruleset(struct scan_st *, struct symbol *);
+void			 rule(struct scan_st *, struct ruleset *);
+void			 arc_app(struct scan_st *, struct rule *, int);
+struct symbol		*node_app(struct scan_st *);
+int			 weight_app(struct scan_st *);
+void			 var_name(struct scan_st *);
+
+#endif /* !__PARSE_H */
+/*
+ * Copyright (c)2004 Cat's Eye Technologies.  All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ *   Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * 
+ *   Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * 
+ *   Neither the name of Cat's Eye Technologies nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission. 
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+/*
+ * rule.c
+ * Rule housekeeping and manipulation for kiceberg.
+ * $Id$
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "rule.h"
+#include "symbol.h"
+#include "mem.h"
+
+struct legislature *
+legislature_new(void)
+{
+	struct legislature *l;
+
+	MALLOC(l, legislature, "legislature");
+	l->head = NULL;
+	return(l);
+}
+
+struct ruleset *
+ruleset_new(struct legislature *l, struct symbol *loc)
+{
+	struct ruleset *rs;
+
+	MALLOC(rs, ruleset, "ruleset");
+	rs->head = NULL;
+	rs->loc = loc;
+
+	rs->next = l->head;
+	l->head = rs;
+
+	return(rs);
+}
+
+struct rule *
+rule_new(struct ruleset *rs)
+{
+	struct rule *r;
+
+	MALLOC(r, rule, "rule");
+
+	r->match = NULL;
+	r->rewrite = NULL;
+	r->params = NULL;
+
+	r->next = rs->head;
+	rs->head = r;
+	return(r);
+}
+
+/*
+ * This doesn't handle free variables yet.
+ */
+struct pattern *
+rule_pattern_add(int which_side, struct rule *r, struct symbol *name, int weight)
+{
+	struct pattern *p;
+
+	MALLOC(p, pattern, "pattern");
+
+	p->name = name;
+	p->weight = weight;
+
+	if (which_side == PATTERN_ADD_MATCH) {
+		p->next = r->match;
+		r->match = p;
+	} else if (which_side == PATTERN_ADD_REWRITE) {
+		p->next = r->rewrite;
+		r->rewrite = p;
+	}
+	
+	return(p);
+}
+
+void
+legislature_dump(struct legislature *l)
+{
+	struct ruleset *rs;
+
+	for (rs = l->head; rs != NULL; rs = rs->next) {
+		ruleset_dump(rs);
+	}
+}
+
+void
+ruleset_dump(struct ruleset *rs)
+{
+	struct rule *r;
+
+	if (rs == NULL) {
+		fprintf(stderr, "*NULLRULESET*\n");
+		return;
+	}
+
+	for (r = rs->head; r != NULL; r = r->next) {
+		rule_dump(r);
+		fprintf(stderr, ", ");
+	}
+	fprintf(stderr, ";\n");
+}
+
+void
+rule_dump(struct rule *r)
+{
+	struct pattern *p;
+
+	if (r == NULL) {
+		fprintf(stderr, "*NULLRULE*\n");
+		return;
+	}
+
+	for (p = r->match; p != NULL; p = p->next) {
+		pattern_dump(p);
+		fprintf(stderr, " ");
+	}
+	fprintf(stderr, "-> ");
+	for (p = r->rewrite; p != NULL; p = p->next) {
+		pattern_dump(p);
+		fprintf(stderr, " ");
+	}
+}
+
+void
+pattern_dump(struct pattern *p)
+{
+	if (p == NULL) {
+		fprintf(stderr, "*NULLPATTERN*\n");
+		return;
+	}
+
+	symbol_print(p->name);
+	fprintf(stderr, ":%d", p->weight);
+}
+/*
+ * rule.h
+ * Rule structures and prototypes for kiceberg.
+ * $Id$
+ */
+
+#ifndef __RULE_H
+#define __RULE_H
+
+#include "symbol.h"
+
+struct legislature {
+	struct ruleset		*head;
+};
+
+struct ruleset {
+	struct ruleset		*next;
+	struct rule		*head;
+	struct symbol		*loc;	/* symbol of node we're in */
+};
+
+struct rule {
+	struct rule		*next;
+	struct pattern		*match;
+	struct pattern		*rewrite;
+	struct symbol_table	*params;
+	int			priority;
+};
+
+struct pattern {
+	struct pattern		*next;
+	struct symbol		*name;	/* symbol of node that arc points to */
+	int			 weight;/* weight of arc (match or rewrite) */
+};
+
+#define PATTERN_ADD_MATCH	1
+#define PATTERN_ADD_REWRITE	2
+
+struct legislature	*legislature_new(void);
+struct ruleset		*ruleset_new(struct legislature *, struct symbol *);
+struct rule		*rule_new(struct ruleset *);
+
+struct pattern		*rule_pattern_add(int, struct rule *, struct symbol *, int);
+
+void			 legislature_dump(struct legislature *);
+void			 ruleset_dump(struct ruleset *);
+void			 rule_dump(struct rule *);
+void			 pattern_dump(struct pattern *);
+
+#endif /* !__RULE_H */
+/*
+ * Copyright (c)2004 Cat's Eye Technologies.  All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ *   Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * 
+ *   Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * 
+ *   Neither the name of Cat's Eye Technologies nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission. 
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+/*
+ * scan.c
+ * Lexical scanner for kiceberg.
+ * $Id$
+ */
+
+#include <ctype.h>
+#include <stdarg.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "scan.h"
+#include "mem.h"
+
+struct scan_st *
+scan_open(char *filename)
+{
+	struct scan_st *sc;
+
+	MALLOC(sc, scan_st, "scanner");
+
+	if ((sc->token = (char *)malloc(256 * sizeof(char))) == NULL) {
+		free(sc);
+		return(NULL);
+	}
+	if ((sc->in = fopen(filename, "r")) == NULL) {
+		free(sc->token);
+		free(sc);
+		return(NULL);
+	}
+	sc->lino = 1;
+	sc->columno = 1;
+	sc->toktype = TOKEN_NONE;
+	scan(sc);		/* prime the pump */
+	return(sc);
+}
+
+void
+scan_close(struct scan_st *sc)
+{	
+	fclose(sc->in);
+	free(sc->token);
+	free(sc);
+}
+
+void
+scan_error(struct scan_st *sc, char *fmt, ...)
+{
+	va_list args;
+	char err[256];
+
+	va_start(args, fmt);
+	vsnprintf(err, 255, fmt, args);
+
+	fprintf(stderr, "Error (line %d, column %d, token '%s'): %s.\n",
+	    sc->lino, sc->columno, sc->token, err);
+}
+
+int
+scan_char(struct scan_st *sc, char *x)
+{	
+	*x = (char)getc(sc->in); sc->columno++;
+	if (feof(sc->in)) {
+		sc->token[0] = 0;
+		sc->toktype = TOKEN_EOF;
+		return(0);
+	}
+	return(1);
+}
+
+void
+scan(struct scan_st *sc)
+{
+	char x;
+	int i = 0;
+
+	sc->token[0] = 0;
+	if (feof(sc->in)) {
+		sc->toktype = TOKEN_EOF;
+		return;
+	}
+	if (!scan_char(sc, &x)) return;
+
+	/* Skip whitespace. */
+
+top:
+	while (isspace(x)) {
+		if (x == '\n') {
+			sc->lino++;
+			sc->columno = 0;
+		}
+		if (!scan_char(sc, &x)) return;
+	}
+
+	/* Skip comments. */
+
+	if (x == '#') {
+		while (x != '\n') {
+			if (!scan_char(sc, &x)) return;
+		}
+		goto top;
+	}
+
+	/*
+	 * Scan decimal numbers.  Must start with a
+	 * digit (not a sign or decimal point.)
+	 */
+
+	if (isdigit(x) && !feof(sc->in)) {
+		sc->toktype = TOKEN_NUMBER;
+		while ((isdigit(x) || x == '.') && !feof(sc->in)) {
+			sc->token[i++] = x;
+			if (!scan_char(sc, &x)) return;
+		}
+		ungetc(x, sc->in);
+		sc->columno--;
+		sc->token[i] = 0;
+		return;
+	}
+
+	/* Scan alphanumeric tokens. */
+
+	if (isalpha(x) && !feof(sc->in)) {
+		sc->toktype = TOKEN_IDENTIFIER;
+		while ((isalpha(x) || isdigit(x) || x == '_') && !feof(sc->in)) {
+			sc->token[i++] = x;
+			if (!scan_char(sc, &x)) return;
+		}
+		ungetc(x, sc->in);
+		sc->columno--;
+		sc->token[i] = 0;
+		return;
+	}
+
+	/* It's a symbol. */
+	
+	sc->toktype = TOKEN_SYMBOL;
+
+	/* Is it a multi-character symbol? */
+
+	if (x == '-') {
+		if (!scan_char(sc, &x)) return;
+		if (x == '>') {
+			strcpy(sc->token, "->");
+			return;
+		} else {
+			ungetc(x, sc->in);
+			sc->columno--;
+			x = '-';
+		}
+	}
+	
+	/* Otherwise, it's a single-character symbol. */
+	
+	sc->token[0] = x;
+	sc->token[1] = 0;
+}
+
+void
+scan_expect(struct scan_st *sc, char *x)
+{
+	if (!strcmp(sc->token, x)) {
+		scan(sc);
+	} else {
+		scan_error(sc, "Expected '%s'", x);
+	}
+}
+/*
+ * scan.h
+ * Lexical scanner structures and prototypes for kiceberg.
+ * $Id$
+ */
+
+#ifndef __SCAN_H
+#define __SCAN_H
+
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+
+struct scan_st {
+	FILE	*in;
+	char	*token;
+	int	 toktype;
+	int	 lino;
+	int	 columno;
+};
+
+#define	TOKEN_EOF		-1
+#define	TOKEN_NONE		 0
+#define	TOKEN_SYMBOL		 1
+#define	TOKEN_IDENTIFIER	 2
+#define	TOKEN_NUMBER		 3
+
+#define tokeq(sc, x)	(!strcmp(sc->token, x))
+#define tokne(sc, x)	(strcmp(sc->token, x))
+#define tokis(sc, x)	(sc->toktype == x)
+
+extern struct scan_st *scan_open(char *);
+extern void scan_close(struct scan_st *);
+extern void scan_error(struct scan_st *, char *, ...);
+extern void scan(struct scan_st *);
+extern void scan_expect(struct scan_st *, char *);
+
+#endif /* !__SCAN_H */
+/*
+ * Copyright (c)2004 Cat's Eye Technologies.  All rights reserved.
+ * 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 
+ *   Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * 
+ *   Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
+ *   distribution.
+ * 
+ *   Neither the name of Cat's Eye Technologies nor the names of its
+ *   contributors may be used to endorse or promote products derived
+ *   from this software without specific prior written permission. 
+ * 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
+ * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
+ * OF THE POSSIBILITY OF SUCH DAMAGE. 
+ */
+/*
+ * symbol.c
+ * Symbol and symbol table housekeeping and manipulation for kiceberg.
+ * $Id$
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <ctype.h>
+
+#include "symbol.h"
+#include "graph.h"
+#include "mem.h"
+
+long int anon_ctr = 0;
+
+struct symbol_table *
+symbol_table_new(void)
+{
+	struct symbol_table *stab;
+
+	MALLOC(stab, symbol_table, "symbol table");
+	stab->head = NULL;
+	return(stab);
+}
+
+struct symbol *
+symbol_new_anon(struct symbol_table *stab, int type)
+{
+	char new_token[128];
+
+	snprintf(new_token, 128, "__ANONYMOUS__%08ld__", ++anon_ctr);
+	return(symbol_define(stab, new_token, type));
+}
+
+/* assumed: preceding call to symbol_lookup failed. */
+struct symbol *
+symbol_define(struct symbol_table *stab, char *token, int type)
+{
+	struct symbol *new_sym;
+
+	MALLOC(new_sym, symbol, "symbol");
+	if ((new_sym->token = strdup(token)) == NULL)
+		errx(1, "Could not allocate symbol lexeme");
+	new_sym->type = type;
+	new_sym->dest = NULL;
+	new_sym->next = stab->head;
+	stab->head = new_sym;
+	return(new_sym);
+}
+
+struct symbol *
+symbol_lookup(struct symbol_table *stab, char *s)
+{
+	struct symbol *sym;
+
+	for (sym = stab->head; sym != NULL; sym = sym->next)
+		if (!strcmp(s, sym->token))
+			return(sym);
+	return(NULL);
+}
+
+void
+symbol_table_dump(int indent, struct symbol_table *stab)
+{
+	struct symbol *sym;
+
+	for (sym = stab->head; sym != NULL; sym = sym->next)
+		symbol_dump(indent, sym);
+}
+
+void
+symbol_print(struct symbol *sym)
+{
+	if (sym != NULL)
+		fprintf(stderr, "%s", sym->token);
+	else
+		fprintf(stderr, "*SYMNULL*");
+}
+
+void
+symbol_dump(int indent, struct symbol *sym)
+{
+	char *ty;
+	int i;
+
+	for (i = 0; i < indent; i++)
+		fprintf(stderr, "\t");
+
+	if (sym == NULL) {
+		fprintf(stderr, "*NULLSYM*\n");
+		return;
+	}
+
+	switch (sym->type) {
+	case SYM_TYPE_NODE:
+		ty = "node";
+		break;
+	default:
+		ty = "?";
+		break;
+	}
+
+	fprintf(stderr, "%-30s %-10s", sym->token, ty);
+
+	if (sym->type == SYM_TYPE_NODE) {
+		node_dump(sym->dest);
+	} else {
+		fprintf(stderr, "\n");
+	}
+}
+/*
+ * symbol.h
+ * Symbol structures and prototypes for kiceberg.
+ * $Id$
+ */
+
+#ifndef __SYMBOL_H
+#define __SYMBOL_H
+
+/*
+ * This is just so we don't have to include graph.h
+ * because we don't want a circular dependency.
+ */
+
+struct node;
+
+/*
+ * Along with the global symbol table, individual symbol
+ * tables exist for each rule (for local bindings.)
+ */
+struct symbol_table {
+	struct symbol	*head;
+};
+
+struct symbol {
+	char		*token;		/* lexeme making up the symbol */
+	int		 type;		/* SYM_TYPE_*, below */
+	struct symbol	*next;		/* next symbol in symbol table */
+	/*
+	 * for SYM_TYPE_NODE symbols, this points
+	 * to the node that is named by this symbol.
+	 */
+	struct node	*dest;
+};
+
+#define SYM_TYPE_NODE		1	/* symbol refers to a node */
+
+#define SYM_LOOKUP_UNIQUE	0	/* symbol must not already exist */
+#define SYM_LOOKUP_DEFINE	1	/* symbol may or may not already exist */
+#define SYM_LOOKUP_EXTANT	2	/* symbol must already exist */
+
+struct symbol_table	*symbol_table_new(void);
+void			 symbol_table_free(struct symbol_table *);
+struct symbol		*symbol_new_anon(struct symbol_table *, int);
+struct symbol		*symbol_define(struct symbol_table *, char *, int);
+struct symbol		*symbol_lookup(struct symbol_table *, char *);
+void			 symbol_free(struct symbol *);
+
+void			 symbol_table_dump(int, struct symbol_table *);
+void			 symbol_print(struct symbol *);
+void			 symbol_dump(int, struct symbol *);
+
+#endif /* !__SYMBOL_H */
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.