[Projects] [monoburg: 1] Import monoburg.

8 Oct 2004

Index: ChangeLog
from  Benoit Perrot <benoit@lrde.epita.fr>

	* monoburg.y: Rename to...
	* parser.y: This, and let automake automaticaly invoke bison to
	create `parser.c'.
	* Makefile.am: Let autoconf add the correct extension to the
	generated binary. Distribute `sample.brg' as a test.
	* config/Makefile.am: New.
	* configure.ac: New.

2004-06-24  David Waite  <mass@akuma.org>

	* monoburg.c: change to C90-style comments from C99/C++-style
	
Wed Apr 14 12:40:54 CEST 2004 Paolo Molaro <lupus@ximian.com>

	* monoburg.c, monoburg.h, monoburg.y: changed the grammar so that
	the same emit code can be easily associated with multiple rules.
	Coalesce identical emit functions to reduce code size (10 KB - 10 % -
	with the current unchanged x86 JIT rules).

2002-10-28  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.c (emit_state): use 16bit values for registers, removed
	reg3 and spilled flag.

2002-10-17  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.y: added missing semicolon

2002-10-11  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.c (emit_tree_match): omit unnecessary compare
	(emit_label_func): make it possible to print operator names in
	error messages.

2002-10-09  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.c (check_result): emit a warning instead of an error

2002-10-03  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.c: added new %termprefix mode

2002-09-30  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.c (main): add option to specify default costs, added
	experimental code to handle several input files.

2002-09-26  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.c (emit_state): include additional fields to handle
	register allocation in dag_mode

2002-09-25  Dietmar Maurer  <dietmar@ximian.com>

	* added -p and -e options. monoburg is now able to work with DAGs.

2002-04-20  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.y (yylex): bug fix in number parsing

2002-04-12  Gonzalo Paniagua Javier <gonzalo@ximian.com>

	* monoburg.c: added option -s to specify the c source file for output.

2002-04-11  Gonzalo Paniagua Javier <gonzalo@ximian.com>

	* monoburg.c: added a default handler for warning messages that just
	output the messages to stderr instead of stdout.

Mon Feb 18 14:28:10 CET 2002 Paolo Molaro <lupus@ximian.com>

	* Makefile.am: fix compatibility problem with automake 1.4.

Fri Feb 15 14:20:30 CET 2002 Paolo Molaro <lupus@ximian.com>

	* Makefile.am: avoid automake for build on host stuff.

Fri Feb 8 12:31:40 CET 2002 Paolo Molaro <lupus@ximian.com>

	* monoburg.c: make generated arrays const, so that they are shared.

Fri Feb 1 15:14:16 CET 2002 Paolo Molaro <lupus@ximian.com>

	* Makefile.am: support cross-compilation.

2001-11-07  Miguel de Icaza  <miguel@ximian.com>

	* monoburg.y: Include string.h, stdlib.h to kill warnings.

	* sample.brg: Include string.h to remove warnings.

2001-09-23  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.c: add a macro MBALLOC_STATE to define the allocation 
	function for MBState. Added an additional user data argument to
	mono_burg_label - the data can be used in the cost functions. The
	type can be defined with MBCOST_DATA macro.
	(emit_cost_func): inline cost functions

2001-09-22  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.y (strndup): removed, use g_strndup instead

	* monoburg.c (create_term): bug fix: g_strdup strings from the parser

2001-09-21  Miguel de Icaza  <miguel@ximian.com>

	* Makefile.am (EXTRA_DIST): Add man page to the distro

2001-09-21  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.y (yylex): bug fix

2001-09-19  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.c (emit_header): bug fix for MBCOND macro

Tue Sep 18 13:15:12 CEST 2001 Paolo Molaro <lupus@ximian.com>

	* monoburg.y: fix ANSI C issue.

2001-09-14  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.c (emit_prototypes): add an additional argument to the
	code emit function - a pointer to the code buffer

Tue Sep 11 13:46:35 CEST 2001 Paolo Molaro <lupus@ximian.com>

	* Makefile.am: get it to work on platforms that insist on having
	a weird extension at the end of an executable name.

Mon Sep 10 17:24:45 CEST 2001 Paolo Molaro <lupus@ximian.com>

	* Makefile.am: make it work for make distcheck.

2001-09-09  Nick Drochak  <ndrochak@gol.com>

	* Makefile.am: change CLEANFILES line to use just '=' instead of '+='
		some versions of automake complain if you try to '+=' before you '='
		
2001-09-08  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.c (emit_header): added some convenient macros

	* monoburg.y (optcfunc): allow arbitrary cost functions

2001-09-06  Dietmar Maurer  <dietmar@ximian.com>

	* monoburg.c (emit_header): use macros to access the tree (like in iburg)

++ monoburg.1	(revision 0)
.\" 
.\" monoburg manual page.
.\" (C) Ximian, Inc. 
.\" Author:
.\"   Dietmar Maurer (dietmar@ximian.com)
.\"
.TH Mono "Mono 1.0"
.SH NAME
monoburg \- code generator generator
.SH SYNOPSIS
.PP
.B monoburg
[\-h]  
[\-e]  
[\-p]
[\-c VALUE]    
[\-d HEADER]
[\-DVALUE]
[FILE...]
.SH DESCRIPTION
The \fImonoburg\fP program is used to generate tree pattern matchers 
from BURG specifications. \fImonoburg\fP accepts the following EBNF grammar.
.PP
.nf
.RS
.ft CW
spec:      ccode `%%' { dcl } [`%%' ccode]

dcl:       `%start' nonterm
           `%term' { identifier [`=' integer] }
           `%termprefix' { identifier }
           nonterm `:' tree [cost] [ `{' ccode `}' ] [costfunc]

tree:      term `(' tree `,' tree `)'
           term `(' tree `)'
           term
           nonterm

cost:      `"' string '"'
           integer

costfunc: `cost' `{' ccode `}'
.RE
.fi
.PP
Where \fIccode\fP is arbitrary C code. \fIcost\fP and \fIcostfunc\fP are
used mutually exclusive, you can't use both in one rule. \fIcost\fP must be a C
expression, whereas \fIccode\fP inside \fIcostfunc\fP is the body of a C 
function. Here are some example rules:
.PP
.nf
.RS
.ft CW
# define some terminal
%term Fetch Four Mul Plus

# this rule uses fixed costs
addr: Plus (con, Mul (Four, reg)) 2 
{
        printf ("Emit your code here.");
} 

# this one computes costs inside a function
reg:  Fetch (addr)  
{
        printf ("Tree address is %p", tree);

} cost {
	int c;

	c = 1; /* calculate the costs here */

	return c;
}
.RE
.fi
.PP
A simple pre-processor is included, consisting of: %ifdef, %else and
%endif.  %ifdef operates on definitions from the command line.
.SH OPTIONS
The following options are supported:
.TP
.I "-h"
Displays usage instructions.
.TP
.I "-d HEADER"
Writes a separate header file which contains all monoburg definitions.
.TP
.I "-p"
Assume termainals are already defined. Its possible to omit the %term
definitions in this mode if you use the %termprefix command. All symbols
starting with a prefix specified in %termprefix are considered to be terminals.
.TP
.I "-e"
Extended mode. Enables monoburg to work with DAGs.
.TP
.I "-c VALUE"
Set the default costs to VALUE
.TP
.I "-Dvar"
Defines the variable "var" as true.  This is used with %ifdef, %else
and %endif in the source files to perform conditional compilation.
.PP
.SH AUTHOR
monoburg was written by Dietmar Maurer. It is based on the papers from 
Christopher W.\ Fraser, Robert R.\ Henry and Todd A.\ Proebsting:
"BURG - Fast Optimal Instruction Selection and Tree Parsing" and
"Engineering a Simple, Efficient Code Generator Generator".
.SH SEE ALSO
.BR monodis(1)
.BR pedump(1)
++ Makefile.am	(revision 0)
## Makefile.am -- Process this file with automake to produce Makefile.in
##

SUBDIRS = config

## Include path
INCLUDES = $(GLIB_CFLAGS) -I$(srcdir)

## MonoBURG binary
bin_PROGRAMS = monoburg

monoburg_SOURCES =			\
	parser.y			\
	monoburg.c monoburg.h
monoburg_LDADD =			\
	$(GLIB_LIBS)

## MonoBURG manual
man_MANS = monoburg.1

EXTRA_DIST = $(man_MANS)

## Check/Sample
check_PROGRAMS = sample

TESTS = sample

sample.c: monoburg$(EXEEXT) $(srcdir)/sample.brg
	./monoburg$(EXEEXT) $(srcdir)/sample.brg > sample.c

sample_SOURCES = sample.brg
sample_LDADD = sample.o $(GLIB_LIBS)

CLEANFILES = sample.c
++ monoburg.c	(revision 0)
/*
 * monoburg.c: an iburg like code generator generator
 *
 * Author:
 *   Dietmar Maurer (dietmar@ximian.com)
 *
 * (C) 2001 Ximian, Inc.
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "monoburg.h"

extern void yyparse (void);

static GHashTable *term_hash;
static GList *term_list;
static GHashTable *nonterm_hash;
static GList *nonterm_list;
static GList *rule_list;
static GList *prefix_list;

FILE *inputfd;
FILE *outputfd;
GHashTable *definedvars;
static FILE *deffd;
static FILE *cfd;

static int dag_mode = 0;
static int predefined_terms = 0;
static int default_cost = 0;

static void output (char *fmt, ...) 
{
	va_list ap;

	va_start(ap, fmt);
	vfprintf (outputfd, fmt, ap);
	va_end (ap);
}

Rule*
make_rule (char *id, Tree *tree)
{
	Rule *rule = g_new0 (Rule, 1);
	rule->lhs = nonterm (id);
	rule->tree = tree;

	return rule;
}

void
rule_add (Rule *rule, char *code, char *cost, char *cfunc)
{
	if (!cfunc && !cost)
		cost = g_strdup_printf ("%d", default_cost);

	rule_list = g_list_append (rule_list, rule);
	rule->cost = g_strdup (cost);
	rule->cfunc = g_strdup (cfunc);
	rule->code = g_strdup (code);

	if (cfunc) {
		if (cost)
			yyerror ("duplicated costs (constant costs and cost function)");
		else {
			if (dag_mode)
				rule->cost = g_strdup_printf ("mono_burg_cost_%d (p, data)",
							      g_list_length (rule_list));
			else
				rule->cost = g_strdup_printf ("mono_burg_cost_%d (tree, data)",
							      g_list_length (rule_list));
		}
	}

	rule->lhs->rules = g_list_append (rule->lhs->rules, rule);

	if (rule->tree->op)
		rule->tree->op->rules = g_list_append (rule->tree->op->rules, rule);
	else 
		rule->tree->nonterm->chain = g_list_append (rule->tree->nonterm->chain, rule);
}

void     
create_rule (char *id, Tree *tree, char *code, char *cost, char *cfunc)
{
	Rule *rule = make_rule (id, tree);

	rule_add (rule, code, cost, cfunc);
}

Tree *
create_tree (char *id, Tree *left, Tree *right)
{
	int arity = (left != NULL) + (right != NULL);
	Term *term = NULL; 
	Tree *tree = g_new0 (Tree, 1);

	if (term_hash)
		term = g_hash_table_lookup (term_hash, id);

	/* try if id has termprefix */
	if (!term) {
		GList *pl;
		for (pl = prefix_list; pl; pl = pl->next) {
			char *pfx = (char *)pl->data;
			if (!strncmp (pfx, id, strlen (pfx))) {
				term = create_term (id, -1);
				break;
			}
		}

	}

	if (term) {
		if (term->arity == -1)
			term->arity = arity;

		if (term->arity != arity)
			yyerror ("changed arity of terminal %s from %d to %d",
				 id, term->arity, arity);

		tree->op = term;
		tree->left = left;
		tree->right = right;
	} else {
		tree->nonterm = nonterm (id);
	}

	return tree;
}

static void
check_term_num (char *key, Term *value, int num)
{
	if (num != -1 && value->number == num)
		yyerror ("duplicate terminal id \"%s\"", key);
}
 
void  
create_term_prefix (char *id)
{
	if (!predefined_terms)
		yyerror ("%termprefix is only available with -p option");

	prefix_list = g_list_prepend (prefix_list, g_strdup (id));
}

Term *
create_term (char *id, int num)
{
	Term *term;

	if (!predefined_terms && nonterm_list)
		yyerror ("terminal definition after nonterminal definition");

	if (num < -1)
		yyerror ("invalid terminal number %d", num);

	if (!term_hash) 
		term_hash = g_hash_table_new (g_str_hash , g_str_equal);

	g_hash_table_foreach (term_hash, (GHFunc) check_term_num, (gpointer) num);

	term = g_new0 (Term, 1);

	term->name = g_strdup (id);
	term->number = num;
	term->arity = -1;

	term_list = g_list_append (term_list, term);

	g_hash_table_insert (term_hash, term->name, term);

	return term;
}

NonTerm *
nonterm (char *id)
{
	NonTerm *nterm;

	if (!nonterm_hash) 
		nonterm_hash = g_hash_table_new (g_str_hash , g_str_equal);

	if ((nterm = g_hash_table_lookup (nonterm_hash, id)))
		return nterm;

	nterm = g_new0 (NonTerm, 1);

	nterm->name = g_strdup (id);
	nonterm_list = g_list_append (nonterm_list, nterm);
	nterm->number = g_list_length (nonterm_list);
	
	g_hash_table_insert (nonterm_hash, nterm->name, nterm);

	return nterm;
}

void
start_nonterm (char *id)
{
	static gboolean start_def;
	
	if (start_def)
		yyerror ("start symbol redeclared");
	
	start_def = TRUE;
	nonterm (id); 
}

static void
emit_tree_string (Tree *tree)
{
	if (tree->op) {
		output ("%s", tree->op->name);
		if (tree->op->arity) {
			output ("(");
			emit_tree_string (tree->left);
			if (tree->right) {
				output (", ");
				emit_tree_string (tree->right);
			}
			output (")");
		}
	} else 
		output ("%s", tree->nonterm->name);
}

static void
emit_rule_string (Rule *rule, char *fill)
{
	output ("%s/* ", fill);
	
	output ("%s: ", rule->lhs->name);

	emit_tree_string (rule->tree);

	output (" */\n");
}

static int
next_term_num ()
{
	GList *l = term_list;
	int i = 1;

	while (l) {
		Term *t = (Term *)l->data;
		if (t->number == i) {
			l = term_list;
			i++;
		} else
			l = l->next;
	}
	return i;
}

static int
term_compare_func (Term *t1, Term *t2)
{
	return t1->number - t2->number;
}

static void
emit_header ()
{
	GList *l;

	output ("#include <glib.h>\n");
	output ("\n");

	output ("#ifndef MBTREE_TYPE\n#error MBTREE_TYPE undefined\n#endif\n");
	output ("#ifndef MBTREE_OP\n#define MBTREE_OP(t) ((t)->op)\n#endif\n");
	output ("#ifndef MBTREE_LEFT\n#define MBTREE_LEFT(t) ((t)->left)\n#endif\n");
	output ("#ifndef MBTREE_RIGHT\n#define MBTREE_RIGHT(t) ((t)->right)\n#endif\n");
	output ("#ifndef MBTREE_STATE\n#define MBTREE_STATE(t) ((t)->state)\n#endif\n");
	output ("#ifndef MBCGEN_TYPE\n#define MBCGEN_TYPE int\n#endif\n");
	output ("#ifndef MBALLOC_STATE\n#define MBALLOC_STATE g_new (MBState, 1)\n#endif\n");
	output ("#ifndef MBCOST_DATA\n#define MBCOST_DATA gpointer\n#endif\n");
	output ("\n");
	output ("#define MBMAXCOST 32768\n");

	output ("\n");
	output ("#define MBCOND(x) if (!(x)) return MBMAXCOST;\n");

	output ("\n");

	for (l = term_list; l; l = l->next) {
		Term *t = (Term *)l->data;
		if (t->number == -1)
			t->number = next_term_num ();
	}
	term_list = g_list_sort (term_list, (GCompareFunc)term_compare_func);

	for (l = term_list; l; l = l->next) {
		Term *t = (Term *)l->data;
		if (t->number == -1)
			t->number = next_term_num ();

		if (predefined_terms)
			output ("#define MB_TERM_%s\t %s\n", t->name, t->name);
		else
			output ("#define MB_TERM_%s\t %d\n", t->name, t->number);

	}
	output ("\n");

}

static void
emit_nonterm ()
{
	GList *l;

	for (l = nonterm_list; l; l = l->next) {
		NonTerm *n = (NonTerm *)l->data;
		output ("#define MB_NTERM_%s\t%d\n", n->name, n->number);
	}
	output ("#define MB_MAX_NTERMS\t%d\n", g_list_length (nonterm_list));
	output ("\n");
}

static void
emit_state ()
{
	GList *l;
	int i, j;

	output ("typedef struct _MBState MBState;\n");
	output ("struct _MBState {\n");
	output ("\tint\t\t op;\n");

	if (dag_mode) {
		output ("\tMBTREE_TYPE\t *tree;\n");
		output ("\tgint32 reg1, reg2;\n");
	}
	
	output ("\tMBState\t\t*left, *right;\n");
	output ("\tguint16\t\tcost[%d];\n", g_list_length (nonterm_list) + 1);

	for (l = nonterm_list; l; l = l->next) {
		NonTerm *n = (NonTerm *)l->data;
		g_assert (g_list_length (n->rules) < 256);
		i = g_list_length (n->rules);
		j = 1;
		while (i >>= 1)
			j++;
		output ("\tunsigned int\t rule_%s:%d;\n",  n->name, j); 
	}
	output ("};\n\n");
}

static void
emit_decoders ()
{
	GList *l;
	GList *rl;

	for (l = nonterm_list; l; l = l->next) {
		NonTerm *n = (NonTerm *)l->data;
		output ("const int mono_burg_decode_%s[] = {\n", n->name);
		output ("\t0,\n");
		for (rl = n->rules; rl; rl = rl->next) {
			Rule *rule = (Rule *)rl->data;
			output ("\t%d,\n", g_list_index (rule_list, rule) + 1);
		}
		
		output ("};\n\n");
	}
}

static void
emit_tree_match (char *st, Tree *t)
{
	char *tn;
	int not_first = strcmp (st, "p->");

	/* we can omit this check at the top level */
	if (not_first) {
		if (predefined_terms)
			output ("\t\t\t%sop == %s /* %s */", st, t->op->name, t->op->name);
		else
			output ("\t\t\t%sop == %d /* %s */", st, t->op->number, t->op->name);
	}

	if (t->left && t->left->op) {
		tn = g_strconcat (st, "left->", NULL);
		if (not_first)
			output (" &&\n");
		not_first = 1;
		emit_tree_match (tn, t->left);
		g_free (tn);
	}

	if (t->right && t->right->op) {
		tn = g_strconcat (st, "right->", NULL);
		if (not_first)
			output (" &&\n");
		emit_tree_match (tn, t->right);
		g_free (tn);
	}
}

static void
emit_rule_match (Rule *rule)
{
	Tree *t = rule->tree; 

	if ((t->left && t->left->op) || 
	    (t->right && t->right->op)) {	
		output ("\t\tif (\n");
		emit_tree_match ("p->", t);
		output ("\n\t\t)\n");
	}
}

static void
emit_costs (char *st, Tree *t)
{
	char *tn;

	if (t->op) {

		if (t->left) {
			tn = g_strconcat (st, "left->", NULL);
			emit_costs (tn, t->left);
			g_free (tn);
		}

		if (t->right) {
			tn = g_strconcat (st, "right->", NULL);
			emit_costs (tn, t->right);
		}
	} else
		output ("%scost[MB_NTERM_%s] + ", st, t->nonterm->name);
}

static void
emit_cond_assign (Rule *rule, char *cost, char *fill)
{
	char *rc;

	if (cost)
		rc = g_strconcat ("c + ", cost, NULL);
	else
		rc = g_strdup ("c");


	output ("%sif (%s < p->cost[MB_NTERM_%s]) {\n", fill, rc, rule->lhs->name);

	output ("%s\tp->cost[MB_NTERM_%s] = %s;\n", fill, rule->lhs->name, rc);

	output ("%s\tp->rule_%s = %d;\n", fill, rule->lhs->name, 
		g_list_index (rule->lhs->rules, rule) + 1);

	if (rule->lhs->chain)
		output ("%s\tclosure_%s (p, %s);\n", fill, rule->lhs->name, rc); 

	output ("%s}\n", fill);

	g_free (rc);
	
}

static void
emit_label_func ()
{
	GList *l;
	int i;

	if (dag_mode) {
		output ("static void\n");
		output ("mono_burg_label_priv (MBTREE_TYPE *tree, MBCOST_DATA *data, MBState *p) {\n");
	} else {
		output ("static MBState *\n");
		output ("mono_burg_label_priv (MBTREE_TYPE *tree, MBCOST_DATA *data) {\n");
	}

	output ("\tint arity;\n");
	output ("\tint c;\n");
	if (!dag_mode) 
		output ("\tMBState *p;\n");
	output ("\tMBState *left = NULL, *right = NULL;\n\n");

	output ("\tswitch (mono_burg_arity [MBTREE_OP(tree)]) {\n");
	output ("\tcase 0:\n");
	output ("\t\tbreak;\n");
	output ("\tcase 1:\n");
	if (dag_mode) {
		output ("\t\tleft = MBALLOC_STATE;\n");
		output ("\t\tmono_burg_label_priv (MBTREE_LEFT(tree), data, left);\n");		
	} else {
		output ("\t\tleft = mono_burg_label_priv (MBTREE_LEFT(tree), data);\n");
		output ("\t\tright = NULL;\n");
	}
	output ("\t\tbreak;\n");
	output ("\tcase 2:\n");
	if (dag_mode) {
		output ("\t\tleft = MBALLOC_STATE;\n");
		output ("\t\tmono_burg_label_priv (MBTREE_LEFT(tree), data, left);\n");		
		output ("\t\tright = MBALLOC_STATE;\n");
		output ("\t\tmono_burg_label_priv (MBTREE_RIGHT(tree), data, right);\n");		
	} else {
		output ("\t\tleft = mono_burg_label_priv (MBTREE_LEFT(tree), data);\n");
		output ("\t\tright = mono_burg_label_priv (MBTREE_RIGHT(tree), data);\n");
	}
	output ("\t}\n\n");

	output ("\tarity = (left != NULL) + (right != NULL);\n");
	output ("\tg_assert (arity == mono_burg_arity [MBTREE_OP(tree)]);\n\n");

	if (!dag_mode)
		output ("\tp = MBALLOC_STATE;\n");

	output ("\tmemset (p, 0, sizeof (MBState));\n");
	output ("\tp->op = MBTREE_OP(tree);\n");
	output ("\tp->left = left;\n");
	output ("\tp->right = right;\n");

	if (dag_mode)
		output ("\tp->tree = tree;\n");	
	
	for (l = nonterm_list, i = 0; l; l = l->next) {
		output ("\tp->cost [%d] = 32767;\n", ++i);
	}
	output ("\n");

	output ("\tswitch (MBTREE_OP(tree)) {\n");
	for (l = term_list; l; l = l->next) {
		Term *t = (Term *)l->data;
		GList *rl;
		
		if (predefined_terms)
			output ("\tcase %s: /* %s */\n", t->name, t->name);
		else
			output ("\tcase %d: /* %s */\n", t->number, t->name);

		for (rl = t->rules; rl; rl = rl->next) {
			Rule *rule = (Rule *)rl->data; 
			Tree *t = rule->tree;

			emit_rule_string (rule, "\t\t");

			emit_rule_match (rule);
			
			output ("\t\t{\n");

			output ("\t\t\tc = ");
			
			emit_costs ("", t);
	
			output ("%s;\n", rule->cost);

			emit_cond_assign (rule, NULL, "\t\t\t");

			output ("\t\t}\n");
		}

		output ("\t\tbreak;\n");
	}
	
	output ("\tdefault:\n");
	output ("#ifdef MBGET_OP_NAME\n");
	output ("\t\tg_error (\"unknown operator: %%s\", MBGET_OP_NAME(MBTREE_OP(tree)));\n");
	output ("#else\n");
	output ("\t\tg_error (\"unknown operator: 0x%%04x\", MBTREE_OP(tree));\n");
	output ("#endif\n");
	output ("\t}\n\n");

	if (!dag_mode) {
		output ("\tMBTREE_STATE(tree) = p;\n");
		output ("\treturn p;\n");
	}

	output ("}\n\n");

	output ("MBState *\n");
	output ("mono_burg_label (MBTREE_TYPE *tree, MBCOST_DATA *data)\n{\n");
	if (dag_mode) {
		output ("\tMBState *p = MBALLOC_STATE;\n");
		output ("\tmono_burg_label_priv (tree, data, p);\n");		
	} else {
		output ("\tMBState *p = mono_burg_label_priv (tree, data);\n");
	}
	output ("\treturn p->rule_%s ? p : NULL;\n", ((NonTerm *)nonterm_list->data)->name);
	output ("}\n\n");
}

static char *
compute_kids (char *ts, Tree *tree, int *n)
{
	char *res;

	if (tree->nonterm) {
		return g_strdup_printf ("\t\tkids[%d] = %s;\n", (*n)++, ts);
	} else if (tree->op && tree->op->arity) {
		char *res2 = NULL;

		if (dag_mode) {
			res = compute_kids (g_strdup_printf ("%s->left", ts), 
					    tree->left, n);
			if (tree->op->arity == 2)
				res2 = compute_kids (g_strdup_printf ("%s->right", ts), 
						     tree->right, n);
		} else {
			res = compute_kids (g_strdup_printf ("MBTREE_LEFT(%s)", ts), 
					    tree->left, n);
			if (tree->op->arity == 2)
				res2 = compute_kids (g_strdup_printf ("MBTREE_RIGHT(%s)", ts), 
						     tree->right, n);
		}

		return g_strconcat (res, res2, NULL);
	}
	return "";
}

static void
emit_kids ()
{
	GList *l, *nl;
	int i, j, c, n, *si;
	char **sa;

	output ("int\n");
	output ("mono_burg_rule (MBState *state, int goal)\n{\n");

	output ("\tg_return_val_if_fail (state != NULL, 0);\n"); 
	output ("\tg_return_val_if_fail (goal > 0, 0);\n\n");

	output ("\tswitch (goal) {\n");

	for (nl = nonterm_list; nl; nl = nl->next) {
		NonTerm *n = (NonTerm *)nl->data;
		output ("\tcase MB_NTERM_%s:\n", n->name);
		output ("\t\treturn mono_burg_decode_%s [state->rule_%s];\n",
			n->name, n->name);
	}

	output ("\tdefault: g_assert_not_reached ();\n");
	output ("\t}\n");
	output ("\treturn 0;\n");
	output ("}\n\n");


	if (dag_mode) {
		output ("MBState **\n");
		output ("mono_burg_kids (MBState *state, int rulenr, MBState *kids [])\n{\n");
		output ("\tg_return_val_if_fail (state != NULL, NULL);\n");
		output ("\tg_return_val_if_fail (kids != NULL, NULL);\n\n");

	} else {
		output ("MBTREE_TYPE **\n");
		output ("mono_burg_kids (MBTREE_TYPE *tree, int rulenr, MBTREE_TYPE *kids [])\n{\n");
		output ("\tg_return_val_if_fail (tree != NULL, NULL);\n");
		output ("\tg_return_val_if_fail (kids != NULL, NULL);\n\n");
	}

	output ("\tswitch (rulenr) {\n");

	n = g_list_length (rule_list);
	sa = g_new0 (char *, n);
	si = g_new0 (int, n);

	/* compress the case statement */
	for (l = rule_list, i = 0, c = 0; l; l = l->next) {
		Rule *rule = (Rule *)l->data;
		int kn = 0;
		char *k;

		if (dag_mode)
			k = compute_kids ("state", rule->tree, &kn);
		else
			k = compute_kids ("tree", rule->tree, &kn);

		for (j = 0; j < c; j++)
			if (!strcmp (sa [j], k))
				break;

		si [i++] = j;
		if (j == c)
			sa [c++] = k;
	}

	for (i = 0; i < c; i++) {
		for (l = rule_list, j = 0; l; l = l->next, j++)
			if (i == si [j])
				output ("\tcase %d:\n", j + 1);
		output ("%s", sa [i]);
		output ("\t\tbreak;\n");
	}

	output ("\tdefault:\n\t\tg_assert_not_reached ();\n");
	output ("\t}\n");
	output ("\treturn kids;\n");
	output ("}\n\n");

}

static void
emit_emitter_func ()
{
	GList *l;
	int i, rulen;
	GHashTable *cache = g_hash_table_new (g_str_hash, g_str_equal);

	for (l =  rule_list, i = 0; l; l = l->next) {
		Rule *rule = (Rule *)l->data;
		
		if (rule->code) {
			if ((rulen = GPOINTER_TO_INT (g_hash_table_lookup (cache, rule->code)))) {
				emit_rule_string (rule, "");
				output ("#define mono_burg_emit_%d mono_burg_emit_%d\n\n", i, rulen);
				i++;
				continue;
			}
			output ("static void ");

			emit_rule_string (rule, "");

			if (dag_mode)
				output ("mono_burg_emit_%d (MBState *state, MBTREE_TYPE *tree, MBCGEN_TYPE *s)\n", i);
			else
				output ("mono_burg_emit_%d (MBTREE_TYPE *tree, MBCGEN_TYPE *s)\n", i);
			output ("{\n");
			output ("%s\n", rule->code);
			output ("}\n\n");
			g_hash_table_insert (cache, rule->code, GINT_TO_POINTER (i));
		}
		i++;
	}

	g_hash_table_destroy (cache);

	output ("MBEmitFunc const mono_burg_func [] = {\n");
	output ("\tNULL,\n");
	for (l =  rule_list, i = 0; l; l = l->next) {
		Rule *rule = (Rule *)l->data;
		if (rule->code)
			output ("\tmono_burg_emit_%d,\n", i);
		else
			output ("\tNULL,\n");
		i++;
	}
	output ("};\n\n");
}

static void
emit_cost_func ()
{
	GList *l;
	int i;

	for (l =  rule_list, i = 0; l; l = l->next) {
		Rule *rule = (Rule *)l->data;
		
		if (rule->cfunc) {
			output ("inline static guint16\n");

			emit_rule_string (rule, "");
			
			if (dag_mode)
				output ("mono_burg_cost_%d (MBState *state, MBCOST_DATA *data)\n", i + 1);
			else
				output ("mono_burg_cost_%d (MBTREE_TYPE *tree, MBCOST_DATA *data)\n", i + 1);
			output ("{\n");
			output ("%s\n", rule->cfunc);
			output ("}\n\n");
		}
		i++;
	}
}

static void
emit_closure ()
{
	GList *l, *rl;

	for (l = nonterm_list; l; l = l->next) {
		NonTerm *n = (NonTerm *)l->data;
		
		if (n->chain)
			output ("static void closure_%s (MBState *p, int c);\n", n->name);
	}

	output ("\n");

	for (l = nonterm_list; l; l = l->next) {
		NonTerm *n = (NonTerm *)l->data;
		
		if (n->chain) {
			output ("static void\n");
			output ("closure_%s (MBState *p, int c)\n{\n", n->name);
			for (rl = n->chain; rl; rl = rl->next) {
				Rule *rule = (Rule *)rl->data;
				
				emit_rule_string (rule, "\t");
				emit_cond_assign (rule, rule->cost, "\t");
			}
			output ("}\n\n");
		}
	}
}

static char *
compute_nonterms (Tree *tree)
{
	if (!tree)
		return "";

	if (tree->nonterm) {
		return g_strdup_printf ("MB_NTERM_%s, ", tree->nonterm->name);
	} else {
		return g_strconcat (compute_nonterms (tree->left),
				    compute_nonterms (tree->right), NULL);
	} 
}

static void
emit_vardefs ()
{
	GList *l;
	int i, j, c, n, *si;
	char **sa;

	if (predefined_terms) {
		output ("guint8 mono_burg_arity [MBMAX_OPCODES];\n"); 

		output ("void\nmono_burg_init (void)\n{\n");

		for (l = term_list, i = 0; l; l = l->next) {
			Term *t = (Term *)l->data;

			output ("\tmono_burg_arity [%s] = %d; /* %s */\n", t->name, t->arity, t->name);

		}

		output ("}\n\n");

	} else {
		output ("const guint8 mono_burg_arity [] = {\n"); 
		for (l = term_list, i = 0; l; l = l->next) {
			Term *t = (Term *)l->data;

			while (i < t->number) {
				output ("\t0,\n");
				i++;
			}
		
			output ("\t%d, /* %s */\n", t->arity, t->name);

			i++;
		}
		output ("};\n\n");

		output ("const char *const mono_burg_term_string [] = {\n");
		output ("\tNULL,\n");
		for (l = term_list, i = 0; l; l = l->next) {
			Term *t = (Term *)l->data;
			output ("\t\"%s\",\n", t->name);
		}
		output ("};\n\n");
	}

	output ("const char * const mono_burg_rule_string [] = {\n");
	output ("\tNULL,\n");
	for (l = rule_list, i = 0; l; l = l->next) {
		Rule *rule = (Rule *)l->data;
		output ("\t\"%s: ", rule->lhs->name);
		emit_tree_string (rule->tree);
		output ("\",\n");
	}
	output ("};\n\n");

	n = g_list_length (rule_list);
	sa = g_new0 (char *, n);
	si = g_new0 (int, n);

	/* compress the _nts array */
	for (l = rule_list, i = 0, c = 0; l; l = l->next) {
		Rule *rule = (Rule *)l->data;
		char *s = compute_nonterms (rule->tree);

		for (j = 0; j < c; j++)
			if (!strcmp (sa [j], s))
				break;

		si [i++] = j;
		if (j == c) {
			output ("static const guint16 mono_burg_nts_%d [] = { %s0 };\n", c, s);
			sa [c++] = s;
		}
	}	
	output ("\n");

	output ("const guint16 *const mono_burg_nts [] = {\n");
	output ("\t0,\n");
	for (l = rule_list, i = 0; l; l = l->next) {
		Rule *rule = (Rule *)l->data;
		output ("\tmono_burg_nts_%d, ", si [i++]);
		emit_rule_string (rule, "");
	}
	output ("};\n\n");
}

static void
emit_prototypes ()
{
	if (dag_mode)
		output ("typedef void (*MBEmitFunc) (MBState *state, MBTREE_TYPE *tree, MBCGEN_TYPE *s);\n\n");
	else
		output ("typedef void (*MBEmitFunc) (MBTREE_TYPE *tree, MBCGEN_TYPE *s);\n\n");
	
	output ("extern const char * const mono_burg_term_string [];\n");
	output ("extern const char * const mono_burg_rule_string [];\n");
	output ("extern const guint16 *const mono_burg_nts [];\n");
	output ("extern MBEmitFunc const mono_burg_func [];\n");

	output ("MBState *mono_burg_label (MBTREE_TYPE *tree, MBCOST_DATA *data);\n");
	output ("int mono_burg_rule (MBState *state, int goal);\n");

	if (dag_mode)
		output ("MBState **mono_burg_kids (MBState *state, int rulenr, MBState *kids []);\n");
	else
		output ("MBTREE_TYPE **mono_burg_kids (MBTREE_TYPE *tree, int rulenr, MBTREE_TYPE *kids []);\n");

	output ("extern void mono_burg_init (void);\n");
	output ("\n");
}

static void check_reach (NonTerm *n);

static void
mark_reached (Tree *tree)
{
	if (tree->nonterm && !tree->nonterm->reached)
		check_reach (tree->nonterm);
	if (tree->left)
		mark_reached (tree->left);
	if (tree->right)
		mark_reached (tree->right);
}

static void
check_reach (NonTerm *n)
{
	GList *l;

	n->reached = 1;
	for (l = n->rules; l; l = l->next) {
		Rule *rule = (Rule *)l->data;
		mark_reached (rule->tree);
	}
}

static void
check_result ()
{
	GList *l;

	for (l = term_list; l; l = l->next) {
		Term *term = (Term *)l->data;
		if (term->arity == -1)
			g_warning ("unused terminal \"%s\"",term->name);
	} 

	check_reach (((NonTerm *)nonterm_list->data));

	for (l = nonterm_list; l; l = l->next) {
		NonTerm *n = (NonTerm *)l->data;
		if (!n->reached)
			g_warning ("unreachable nonterm \"%s\"", n->name);
	}
}

static void
usage ()
{
	fprintf (stderr,
		 "Usage is: monoburg -d file.h -s file.c [inputfile] \n");
	exit (1);
}

static void
warning_handler (const gchar *log_domain,
		 GLogLevelFlags log_level,
		 const gchar *message,
		 gpointer user_data)
{
	(void) fprintf ((FILE *) user_data, "** WARNING **: %s\n", message);
}

int
main (int argc, char *argv [])
{
	char *cfile = NULL;
	char *deffile = NULL;
	GList *infiles = NULL;
	int i;

        definedvars = g_hash_table_new (g_str_hash, g_str_equal);
	g_log_set_handler (NULL, G_LOG_LEVEL_WARNING, warning_handler, stderr);

	for (i = 1; i < argc; i++){
		if (argv [i][0] == '-'){
			if (argv [i][1] == 'h') {
				usage ();
			} else if (argv [i][1] == 'e') {
				dag_mode = 1;
			} else if (argv [i][1] == 'p') {
				predefined_terms = 1;
			} else if (argv [i][1] == 'd') {
				deffile = argv [++i];
			} else if (argv [i][1] == 's') {
				cfile = argv [++i];
			} else if (argv [i][1] == 'c') {
				default_cost = atoi (argv [++i]);
			} else if (argv [i][1] == 'D') {
                                g_hash_table_insert (definedvars, &argv [i][2],
                                                     GUINT_TO_POINTER (1));
			} else {
				usage ();
			}
		} else {
			infiles = g_list_append (infiles, argv [i]);
		}
	}

	if (deffile) {
		if (!(deffd = fopen (deffile, "w"))) {
			perror ("cant open header output file");
			exit (-1);
		}
		outputfd = deffd;
		output ("#ifndef _MONO_BURG_DEFS_\n");
		output ("#define _MONO_BURG_DEFS_\n\n");
	} else 
		outputfd = stdout;


	if (infiles) {
		GList *l = infiles;
		while (l) {
			char *infile = (char *)l->data;
			if (!(inputfd = fopen (infile, "r"))) {
				perror ("cant open input file");
				exit (-1);
			}

			yyparse ();

			reset_parser ();

			l->data = inputfd;
			l = l->next;
		}
	} else {
		inputfd = stdin;
		yyparse ();
	}

	check_result ();

	if (!nonterm_list)
		g_error ("no start symbol found");

	emit_header ();
	emit_nonterm ();
	emit_state ();
	emit_prototypes ();

	if (deffd) {
		output ("#endif /* _MONO_BURG_DEFS_ */\n");
		fclose (deffd);

		if (cfile == NULL)
			outputfd = stdout;
		else {
			if (!(cfd = fopen (cfile, "w"))) {
				perror ("cant open c output file");
				(void) remove (deffile);
				exit (-1);
			}

			outputfd = cfd;
		}

		output ("#include \"%s\"\n\n", deffile);
	}
	
	emit_vardefs ();
	emit_cost_func ();
	emit_emitter_func ();
	emit_decoders ();

	emit_closure ();
	emit_label_func ();

	emit_kids ();

	if (infiles) {
		GList *l = infiles;
		while (l) {
			inputfd = l->data;
			yyparsetail ();
			fclose (inputfd);
			l = l->next;
		}
	} else {
		yyparsetail ();
	}

	if (cfile)
		fclose (cfd);

	return 0;
}
++ sample.brg	(revision 0)
/* 
 * This header (everything before the first "%%") is copied 
 * directly to the output.
 */

#include <glib.h>
#include <stdio.h>
#include <string.h>

#define MBTREE_TYPE  MBTree

typedef struct _MBTree MBTree;
struct _MBTree {
	guint16 op;
	MBTree *left, *right;
	gpointer state;
};

%% these are the monoburg definition
#
# This is the start of the definitions
# comments start with a '#' as first line character
#

#
# we must fisrt define the terminals
# with or without numbers
# 
%term Assign Constant Fetch=3 Four=8 Mul=5 Plus=6 AltFetch=7

#
# optional start nonterminal
#
%start reg

con:  Constant                0 

con:  Four                    0 

addr: con                     0 

addr: Plus(con,reg)           
{
	int ern = mono_burg_rule (tree->state, MB_NTERM_addr);
	printf ("%s\n", mono_burg_rule_string [ern]);
} cost 
{  
  return 1;
}

addr: Plus(con,Mul(Four,reg)) 2 
{
	int ern = mono_burg_rule (tree->state, MB_NTERM_addr);
	printf ("%s\n", mono_burg_rule_string [ern]);
} 

reg:  AltFetch(addr),
reg:  Fetch(addr)             1 
{
	int ern = mono_burg_rule (tree->state, MB_NTERM_reg);
	printf ("%s\n", mono_burg_rule_string [ern]);
}

reg:  Assign(addr,reg)        1 
{
	int ern = mono_burg_rule (tree->state, MB_NTERM_reg);
	printf ("%s\n", mono_burg_rule_string [ern]);
}

%% the rest is also copied directly to the output
/* everything below the second "%%" is also copied directly
 * to the output file.
 */

static MBTree *
create_tree (int op, MBTree *left, MBTree *right)
{
	MBTree *t = g_new0 (MBTree, 1);
	
	t->op = op;
	t->left = left;
	t->right = right;

	return t;
}

static void
reduce (MBTree *tree, int goal) 
{
	MBTree *kids[10];
	int ern = mono_burg_rule (tree->state, goal);
	guint16 *nts = mono_burg_nts [ern];
	int i, n;

	mono_burg_kids (tree, ern, kids);

	// printf ("TEST %d %d %s %d\n", goal, ern, mono_burg_rule_string [ern], nts [0]);
	
	for (i = 0; nts [i]; i++) 
		reduce (kids [i], nts [i]);

	n = (tree->left != NULL) + (tree->right != NULL);

	if (n) { /* not a terminal */
	  // printf ("XXTE %s %d\n", mono_burg_rule_string [ern], n);
		if (mono_burg_func [ern])
			mono_burg_func [ern] (tree, NULL);
		else
			g_warning ("no code for rule %s\n", 
				   mono_burg_rule_string [ern]);
	} else {
		if (mono_burg_func [ern])
			g_warning ("unused code in rule %s\n", 
				   mono_burg_rule_string [ern]);
	}
}

int
main ()
{
	MBTree *t, *l, *r;
	MBState *s;

	l = create_tree (MB_TERM_Constant, NULL, NULL);

	r = create_tree (MB_TERM_Fetch, l, NULL);
	l = create_tree (MB_TERM_Constant, NULL, NULL);

	r = create_tree (MB_TERM_Assign, l, r);
	l = create_tree (MB_TERM_Four, NULL, NULL);

	r = create_tree (MB_TERM_Mul, l, r);
	l = create_tree (MB_TERM_Constant, NULL, NULL);

	l = create_tree (MB_TERM_Plus, l, r);

	t = create_tree (MB_TERM_Fetch, l, NULL);

	s = mono_burg_label (t, NULL);

	g_assert (s);

	reduce (t, MB_NTERM_reg);

	return 0;
}
++ README	(revision 0)
This is an implementation of an IBurg like code generator generator. It is
based on the papers from Christopher W. Fraser, Robert R. Henry and Todd
A. Proebsting:

Reference 1: BURG - Fast Optimal Instruction Selection and Tree Parsing
Reference 2: Engineering a Simple, Efficient Code Generator Generator

Examples: sample.brg

++ bootstrap	(revision 0)
#!/bin/sh

autoreconf -f -v -i -m
Index: configure.ac

--- configure.ac	(revision 0)
+++ configure.ac	(revision 0)
@@ -0,0 +1,46 @@
+## ----------------------------------------------------------------------------
+## Configure MonoBURG, an IBurg-like code generator generator
+##
+
+## ------------------------------------- 
+## Project
+AC_INIT([MonoBURG], [1.0.1])
+
+## -------------------------------------
+## Setup autotools
+
+# Need autoconf 2.57 at least.
+AC_PREREQ([2.57])
+
+# Auxiliary files.
+AC_CONFIG_AUX_DIR([config])
+AC_CONFIG_FILES([config/Makefile])
+
+# Initiate automake.
+AM_INIT_AUTOMAKE([foreign 1.7.5 dist-bzip2])
+
+## -------------------------------------
+## Development tools
+
+# Look for a C compiler
+AC_PROG_CC
+
+# Look for a yacc-like program
+AC_PROG_YACC
+
+## -------------------------------------
+## Environment
+
+# Check for GLIB-2.0 presence
+AM_PATH_GLIB_2_0
+
+## -------------------------------------
+## Epilogue
+
+# Ask for Makefile creation
+AC_CONFIG_FILES([
+  Makefile
+])
+
+# Instantiate the output files
+AC_OUTPUT
Index: parser.y
--- parser.y	(revision 0)
+++ parser.y	(revision 0)
@@ -0,0 +1,363 @@
+%{
+/*
+ * monoburg.y: yacc input grammer
+ *
+ * Author:
+ *   Dietmar Maurer (dietmar@ximian.com)
+ *
+ * (C) 2001 Ximian, Inc.
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <ctype.h>
+#include <assert.h>
+#include <stdarg.h>
+
+#include "monoburg.h"
+  
+static int yylineno = 0;
+static int yylinepos = 0;
+
+%}
+
+%union {
+  char *text;
+  int   ivalue;
+  Tree  *tree;
+  Rule  *rule;
+  GList *rule_list;
+}
+
+%token <text> IDENT
+%token <text> CODE
+%token <text> STRING
+%token  START
+%token  COST
+%token  TERM
+%token  TERMPREFIX
+%token <ivalue> INTEGER
+
+%type   <tree>          tree
+%type   <text>          optcost
+%type   <text>          optcfunc
+%type   <text>          optcode
+%type   <rule>          rule
+%type   <rule_list>     rule_list
+
+%%
+
+decls   : /* empty */ 
+	| START IDENT { start_nonterm ($2); } decls
+	| TERM  tlist decls
+	| TERMPREFIX plist decls
+	| rule_list optcost optcode optcfunc {
+			GList *tmp;
+			for (tmp = $1; tmp; tmp = tmp->next) {
+				rule_add (tmp->data, $3, $2, $4);
+			}
+			g_list_free ($1);
+		} decls
+	;
+
+rule	: IDENT ':' tree { $$ = make_rule ($1, $3); }
+	;
+
+rule_list : rule { $$ = g_list_append (NULL, $1); }
+	| rule ',' rule_list { $$ = g_list_prepend ($3, $1); }
+	;
+
+optcode : /* empty */ { $$ = NULL; }
+	| CODE 
+	;
+
+plist	: /* empty */
+	| plist IDENT { create_term_prefix ($2);}
+	;
+
+tlist	: /* empty */
+	| tlist IDENT { create_term ($2, -1);}
+	| tlist IDENT '=' INTEGER { create_term ($2, $4); }
+	;
+
+tree	: IDENT { $$ = create_tree ($1, NULL, NULL); }
+	| IDENT '(' tree ')' { $$ = create_tree ($1, $3, NULL); }
+	| IDENT '(' tree ',' tree ')' { $$ = create_tree ($1, $3, $5); }
+	;
+
+optcost : /* empty */ {$$ = NULL; }
+	| STRING
+	| INTEGER { $$ = g_strdup_printf ("%d", $1); }
+	;
+
+optcfunc : /*empty */ { $$ = NULL; }
+	 | COST CODE { $$ = $2; }
+	 ;
+%%
+
+static char input[2048];
+static char *next = input;
+
+void 
+yyerror (char *fmt, ...)
+{
+  va_list ap;
+
+  va_start(ap, fmt);
+
+  fprintf (stderr, "line %d(%d): ", yylineno, yylinepos);
+  vfprintf (stderr, fmt, ap);
+  fprintf(stderr, "\n");
+
+  va_end (ap);
+
+  exit (-1);
+}
+
+static int state = 0;
+
+void
+reset_parser ()
+{
+  state = 0;
+}
+
+struct pplist {
+  struct pplist *next;
+  gboolean ignore;
+};
+
+static struct pplist *pp = NULL;
+
+static char*
+getvar (const char *input)
+{
+    char *var = g_strchug (g_strdup (input));
+    char *ptr;
+
+    for (ptr = var; *ptr && *ptr != '\n'; ++ptr) {
+        if (g_ascii_isspace (*ptr)) {
+            break;
+        }
+    }
+    *ptr = '\0';
+
+    return var;
+}
+
+static void
+push_if (char *input, gboolean flip)
+{
+  struct pplist *new_pp = g_new (struct pplist, 1);
+  char *var = getvar (input);
+
+  new_pp->ignore = (g_hash_table_lookup (definedvars, var) == NULL) ^ flip;
+  new_pp->next = pp;
+
+  new_pp->ignore |= (pp ? pp->ignore : 0);
+  pp = new_pp;
+  g_free (var);
+}
+
+static void
+flip_if ()
+{
+  if (!pp)
+      yyerror ("%%else without %%if");
+
+  pp->ignore = !pp->ignore | (pp->next ? pp->next->ignore : 0);
+}
+
+static void
+pop_if ()
+{
+  struct pplist *prev_pp = pp;
+
+  if (!pp)
+      yyerror ("%%endif without %%if");
+
+  pp = pp->next;
+  g_free (prev_pp);
+}
+
+static char
+nextchar ()
+{
+  int next_state ;
+  gboolean ll;
+
+    if (!*next) {
+      next = input;
+      *next = 0;
+      do {
+	if (!fgets (input, sizeof (input), inputfd))
+	  return 0;
+
+	ll = (input [0] == '%' && input [1] == '%');
+	next_state = state;
+
+        if (state == 1) {
+          if (!ll && input [0] == '%') {
+            if (!strncmp (&input [1], "ifdef", 5)) {
+              push_if (&input [6], FALSE);
+              ll = TRUE;
+              continue;
+            }
+            else if (!strncmp (&input [1], "ifndef", 6)) {
+              push_if (&input [7], TRUE);
+              ll = TRUE;
+              continue;
+            }
+            else if (!strncmp (&input [1], "else", 4)) {
+              flip_if ();
+              ll = TRUE;
+              continue;
+            }
+            else if (!strncmp (&input [1], "endif", 5)) {
+              pop_if ();
+              ll = TRUE;
+              continue;
+            }
+          }
+          if (pp && pp->ignore) {
+            ll = TRUE;
+            continue;
+          }
+        }
+
+	switch (state) {
+	case 0:
+	  if (ll) {
+	    next_state = 1;
+	  } else 
+	    fputs (input, outputfd);
+	  break;
+	case 1:
+	  if (ll) {
+	    next_state = 2;
+	    *next = 0;
+	  }
+	  break;
+	default:
+	  return 0;
+	}
+	ll = state != 1 || input[0] == '#';
+	state = next_state;
+	yylineno++;
+      } while (next_state == 2 || ll);
+    } 
+
+    return *next++;
+}
+
+void
+yyparsetail (void)
+{
+  fputs (input, outputfd);
+  while (fgets (input, sizeof (input), inputfd))
+    fputs (input, outputfd);
+}
+
+int 
+yylex (void) 
+{
+  char c;
+
+  do {
+
+    if (!(c = nextchar ()))
+      return 0;
+
+    yylinepos = next - input + 1;
+
+    if (isspace (c))
+      continue;
+
+    if (c == '%') {
+      if (!strncmp (next, "start", 5) && isspace (next[5])) {
+	next += 5;
+	return START;
+      }
+
+      if (!strncmp (next, "termprefix", 10) && isspace (next[10])) {
+	next += 10;
+	return TERMPREFIX;
+      }
+
+      if (!strncmp (next, "term", 4) && isspace (next[4])) {
+	next += 4;
+	return TERM;
+      }
+      return c;
+    }
+
+    if (isdigit (c)) {
+	    int num = 0;
+
+	    do {
+		    num = 10*num + (c - '0');
+	    } while (isdigit (c = (*next++)));
+
+	    yylval.ivalue = num;
+	    return INTEGER;
+    }
+
+    if (isalpha (c)) {
+      char *n = next;
+      int l;
+
+      if (!strncmp (next - 1, "cost", 4) && isspace (next[3])) {
+	next += 4;
+	return COST;
+      }
+
+      while (isalpha (*n) || isdigit (*n) || *n == '_') 
+	      n++;
+
+      l = n - next + 1;
+      yylval.text = g_strndup (next - 1, l);
+      next = n;
+      return IDENT;
+    }
+    
+    if (c == '"') {
+      int i = 0;
+      static char buf [100000];
+ 
+      while ((c = *next++) != '"' && c)
+	buf [i++] = c;
+      
+      buf [i] = '\0';
+      yylval.text = g_strdup (buf);
+
+      return STRING;
+    }
+
+    if (c == '{') {
+      int i = 0, d = 1;
+      static char buf [100000];
+ 
+      while (d && (c = nextchar ())) {
+	buf [i++] = c;
+	assert (i < sizeof (buf));
+
+	switch (c) {
+	case '{': d++; break;
+	case '}': d--; break;
+	default:
+		break;
+	}
+      }
+      buf [--i] = '\0';
+      yylval.text = g_strdup (buf);
+
+      return CODE;
+    }
+    
+    return c;
+  
+  } while (1);
+}
+
Index: config/Makefile.am
--- config/Makefile.am	(revision 0)
+++ config/Makefile.am	(revision 0)
@@ -0,0 +1,7 @@
+## Makefile.am -- Process this file with automake to produce Makefile.in
+##
+
+MAINTAINERCLEANFILES =				\
+	depcomp					\
+	install-sh				\
+	missing
Index: monoburg.h
--- monoburg.h	(revision 0)
+++ monoburg.h	(revision 0)
@@ -0,0 +1,72 @@
+#ifndef __MONO_MONOBURG_H__
+#define __MONO_MONOBURG_H__
+
+#include <glib.h>
+
+void yyerror (char *fmt, ...);
+int  yylex   (void);
+
+extern FILE *inputfd;
+extern FILE *outputfd;
+extern GHashTable *definedvars;
+
+typedef struct _Rule Rule;
+
+typedef struct _Term Term;
+struct _Term{
+	char *name;
+	int number;
+	int arity;
+	GList *rules; /* rules that start with this terminal */
+};
+
+typedef struct _NonTerm NonTerm;
+
+struct _NonTerm {
+	char *name;
+	int number;
+	GList *rules; /* rules with this nonterm on the left side */
+	GList *chain;
+	gboolean reached;
+};
+
+typedef struct _Tree Tree;
+
+struct _Tree {
+	Term *op;
+	Tree *left;
+	Tree *right;
+	NonTerm *nonterm; /* used by chain rules */
+};
+
+struct _Rule {
+	NonTerm *lhs;
+	Tree *tree;
+	char *code;
+	char *cost;
+	char *cfunc;
+};
+
+
+Tree    *create_tree    (char *id, Tree *left, Tree *right);
+
+Term    *create_term    (char *id, int num);
+
+void     create_term_prefix (char *id);
+
+NonTerm *nonterm        (char *id);
+
+void     start_nonterm  (char *id);
+
+Rule    *make_rule      (char *id, Tree *tree);
+
+void     rule_add       (Rule *rule, char *code, char *cost, char *cfunc);
+
+void     create_rule    (char *id, Tree *tree, char *code, char *cost, 
+			 char *cfunc);
+
+void     yyparsetail    (void);
+
+void     reset_parser (void);
+
+#endif

    

[Projects] [monoburg: 1] Import monoburg.

Clement Vasseur