slr.c

/*

	slr table generator by tano - tanoacm@yahoo.it

	this bit of code is released under GPL license

	date - 5 jul 2004
*/

#include <stdio.h>
#include <stdlib.h>

#define ID	1
#define PLUS	2
#define STAR	3
#define LEFT	4
#define RIGHT	5

#define EXPR_	6
#define EXPR	7
#define TERM	8
#define FACTOR	9

#define TOKENS		5
#define NON_TERMINALS	4
#define SYMBOLS		TOKENS + NON_TERMINALS
#define START_SYMBOL	EXPR_

#define is_token(n)		((n) > 0 && (n) < START_SYMBOL)
#define is_non_terminal(n)	((n) >= START_SYMBOL && (n) < (START_SYMBOL + NON_TERMINALS))

char *symbols[] = { "",
		    "id", "+ ", "x ", "( ", ") ",
		    "E'", "E ", "T ", "F " };

int lhs[] = { EXPR_, EXPR, EXPR, TERM, TERM, FACTOR, FACTOR };
int rhs[] = { EXPR, 0,
	      EXPR, PLUS, TERM, 0,
	      TERM, 0,
	      TERM, STAR, FACTOR, 0,
	      FACTOR, 0,
	      LEFT, EXPR, RIGHT, 0,
	      ID, 0 };

struct rule
{
	int lhs;
	int *rhs;
};

struct rule *grammar;
int nrules;

void init_grammar (void)
{
	int i, *p;

	nrules = sizeof(lhs) / sizeof(lhs[0]);
	grammar = malloc(nrules * sizeof(struct rule));
	for (p = rhs, i = 0 ; i < nrules ; ++i)
	{
		grammar[i].lhs = lhs[i];
		grammar[i].rhs = p;
		while (*p++)
			;
	}
}

char *nullable;

void compute_nullable (void)
{
        int i, done, *p;

        nullable = calloc(NON_TERMINALS, sizeof(char)) - START_SYMBOL * sizeof(char);
        do
        {
                done = 1;
                for (i = 0 ; i < nrules ; ++i)
                {
                        for (p = grammar[i].rhs ; is_non_terminal(*p) && nullable[*p] ; ++p)
                                ;
                        if (!*p && !nullable[grammar[i].lhs])
                        {
                                done = 0;
                                nullable[grammar[i].lhs] = 1;
                        }
                }
        }
        while (!done);
}

int nullable_string (int *str)
{
        for ( ; *str ; ++str)
                if (is_token(*str) || !nullable[*str])
                        return 0;
        return 1;
}

void print_nullable (void)
{
        int i;

        printf("\nNullable:\n");
        for (i = START_SYMBOL ; i < START_SYMBOL + NON_TERMINALS ; ++i)
                printf("%s is %s\n", symbols[i], nullable[i] ? "nullable" : "not nullable");
}

int add (char *src, char *dst, int n)
{
        int i, flag;

        for (flag = i = 0 ; i <= TOKENS ; ++i)
                if (src[i] && !dst[i])
                        dst[i] = flag = 1;
        return flag;
}

#define add_firsts_to_firsts(src, dst)          add((src), (dst), TOKENS + 1)
#define add_firsts_to_follows(src, dst)         add((src) + 1, (dst) + 1, TOKENS)
#define add_follows_to_follows(src, dst)        add((src), (dst), TOKENS + 1)

char **firsts;

void compute_firsts (void)
{
        int i, done, *p;

        firsts = malloc(SYMBOLS * sizeof(char *));
        firsts -= sizeof(char *);
        for (i = 1 ; i <= SYMBOLS ; ++i)
                firsts[i] = calloc(TOKENS + 1, sizeof(char));
        for (i = 1 ; i <= TOKENS ; ++i)
                firsts[i][i] = 1;
        for (i = START_SYMBOL ; i < START_SYMBOL + NON_TERMINALS ; ++i)
                if (nullable[i])
                        firsts[i][0] = 1;
        do
        {
                done = 1;
                for (i = 0 ; i < nrules ; ++i)
                        for (p = grammar[i].rhs ; *p ; ++p)
                        {
                                if (add_firsts_to_firsts(firsts[*p], firsts[grammar[i].lhs]))
                                        done = 0;
                                if (is_token(*p) || !nullable[*p])
                                        break;
                        }
        }
        while (!done);
}

char* string_firsts (int *str)
{
        int i;
        static char buffer[TOKENS + 1];

        for (i = 0 ; i <= TOKENS ; ++i)
                buffer[i] = 0;
        for ( ; *str ; ++str)
        {
                add_firsts_to_firsts(firsts[*str], buffer);
                if (is_token(*str) || !nullable[*str])
                        break;
        }
        return buffer;
}

void print_firsts (void)
{
        int i, j;

        printf("\nFirsts:\n");
        for (i = 1 ; i <= SYMBOLS ; ++i)
        {
                printf("%s =", symbols[i]);
                for (j = 0 ; j <= TOKENS ; ++j)
                        if (firsts[i][j])
                                printf(j == 0 ? " epsilon " : " %s", symbols[j]);
                printf("\n");
        }
}

char **follows;

void compute_follows (void)
{
        int i, done, *p;
        char *s;

        follows = malloc(NON_TERMINALS * sizeof(char *));
        follows -= START_SYMBOL * sizeof(char *);
        for (i = START_SYMBOL ; i < START_SYMBOL + NON_TERMINALS ; ++i)
                follows[i] = calloc(TOKENS + 1, sizeof(char));
        follows[START_SYMBOL][0] = 1;
        do
        {
                done = 1;
                for (i = 0 ; i < nrules ; ++i)
                        for (p = grammar[i].rhs ; *p ; ++p)
                                if (is_token(*p))
                                        continue;
                                else if (add_firsts_to_follows(string_firsts(p + 1), follows[*p]))
                                        done = 0;
                                else if (nullable_string(p + 1) && add_follows_to_follows(follows[grammar[i].lhs], follows[*p]))
                                        done = 0;
        }
        while (!done);
}

void print_follows (void)
{
        int i, j;

        printf("\nFollows:\n");

        for (i = START_SYMBOL ; i < START_SYMBOL + NON_TERMINALS ; ++i)
        {
                printf("%s =", symbols[i]);
                for (j = 0 ; j <= TOKENS ; ++j)
                        if (follows[i][j])
                                printf(j == 0 ? " $ " : " %s", symbols[j]);
                printf("\n");
        }
}

struct item
{
	int rule;
	int pos;
	struct item *next;
};

struct link
{
	int symbol;
	struct itemset *state;
	struct link *next;
};

struct itemset
{
	int index;
	struct item *list;
	struct link *link;
	struct itemset *next;
};

struct itemset *lr0_sets;
int counter;

int cmp_item (struct item *item, int rule, int pos)
{
	if (item->rule != rule) return item->rule - rule;
	else if (item->pos != pos) return item->pos - pos;
	else return 0;
}

struct item* insert_item (struct item *items, int rule, int pos)
{
	struct item *new, *curr, *prev;
	int ret;

	for (prev = NULL, curr = items ; curr ; prev = curr, curr = curr->next)
		if ((ret = cmp_item(curr, rule, pos)) > 0)
			break;
		else if (!ret)
			return items;
	new = malloc(sizeof(struct item));
	new->rule = rule;
	new->pos = pos;
	if (prev)
		prev->next = new;
	else
		items = new;
	new->next = curr;
	return items;
}

struct item* closure (struct item *items)
{
	struct item *cl, *p;
	char *boolean;
	int i, done, symbol;

	cl = NULL;
	for (p = items ; p ; p = p->next)
		cl = insert_item(cl, p->rule, p->pos);
	boolean = calloc(NON_TERMINALS, sizeof(char));
	do
	{
		done = 1;
		for (p = cl ; p ; p = p->next)
		{
			symbol = grammar[p->rule].rhs[p->pos];
			if (is_non_terminal(symbol) && !boolean[symbol])
			{
				done = 0;
				for (i = 0 ; i < nrules ; ++i)
					if (grammar[i].lhs == symbol)
						cl = insert_item(cl, i, 0);
				boolean[symbol] = 1;
			}
		}
	}
	while (!done);
	free(boolean);
	return cl;
}

int same_itemlist (struct item *p, struct item *q)
{
	for ( ; p && q ; p = p->next, q = q->next)
		if (p->rule != q->rule || p->pos != q->pos)
			return 0;
	if (!p && !q)
		return 1;
	return 0;
}

void free_itemlist (struct item *list)
{
	struct item *p;

	if (!list)
		return;
	for ( ; list ; list = p)
	{
		p = list->next;
		free(list);
	}
}

struct itemset* goto_op (struct itemset *set, int symbol)
{
	struct item *p, *items, *cl;
	struct itemset *q, *newset;
	int ret;

	items = NULL;
	for (p = set->list ; p ; p = p->next)
		if (grammar[p->rule].rhs[p->pos] == symbol)
			items = insert_item(items, p->rule, p->pos + 1);
	cl = closure(items);
	free_itemlist(items);
	for (q = lr0_sets ; q->next ; q = q->next)
		if (same_itemlist(q->list, cl))
		{
			free_itemlist(cl);
			return q;
		}
	newset = malloc(sizeof(struct itemset));
	newset->index = counter++;
	newset->list = cl;
	newset->link = NULL;
	newset->next = NULL;
	q->next = newset;
	return newset;
}

void init_lr_sets (void)
{
	struct item *new, *cl;

	new = insert_item(NULL, 0, 0);
	cl = closure(new);
	free_itemlist(new);
	lr0_sets = malloc(sizeof(struct itemset));
	lr0_sets->index = counter = 0;
	++counter;
	lr0_sets->list = cl;
	lr0_sets->link = NULL;
	lr0_sets->next = NULL;
}

void append_goto (struct itemset *set, int symbol, struct itemset *state)
{
	struct link *p, *q;

	p = malloc(sizeof(struct link));
	p->symbol = symbol;
	p->state = state;
	p->next = NULL;
	if (!set->link)
	{
		set->link = p;
		return;
	}
	for (q = set->link ; q->next ; q = q->next)
		;
	q->next = p;
	return; 
}

void lr0 (void)
{
	struct item *new, *cl, *item;
	struct itemset *p, *state;
	char *boolean;
	int symbol;

	init_lr_sets();
	for (p = lr0_sets ; p ; p = p->next)
	{
		boolean = calloc(SYMBOLS, sizeof(char));
		for (item = p->list ; item ; item = item->next)
		{
			symbol = grammar[item->rule].rhs[item->pos];
			if (symbol && !boolean[symbol])
			{
				boolean[symbol] = 1;
				state = goto_op(p, symbol);
				append_goto(p, symbol, state);
			 }
		}
		free(boolean);
	}
}

void print_grammar (void)
{
	int i, j;

	printf("\nGrammar:\n");
	for (i = 0 ; i < nrules ; ++i)
	{
		printf("\t%s -> ", symbols[grammar[i].lhs]);
		for (j = 0 ; grammar[i].rhs[j] ; ++j)
			printf(" %s", symbols[grammar[i].rhs[j]]);
		printf("\n");
	}
}

void print_itemset (struct itemset *itemset)
{
	struct item *p;
	struct link *q;
	int i;

	printf("\nState %d\n", itemset->index);
	for (p = itemset->list ; p ; p = p->next)
	{
		printf("\t%s ->", symbols[grammar[p->rule].lhs]);
		i = 0;
		do
		{
			if (i == p->pos) printf(" .");
			printf(" %s", symbols[grammar[p->rule].rhs[i]]);
		}
		while (grammar[p->rule].rhs[i++]);
		printf("\n");
	}
	for (q = itemset->link ; q ; q = q->next)
		printf("On %s, switch to state %d\n", symbols[q->symbol], q->state->index);
	printf("\n");
}

void print_lr0_sets (void)
{
	struct itemset *p;
 
	for (p = lr0_sets ; p ; p = p->next)
		print_itemset(p);
}

int goto_index (struct itemset *p, int symbol)
{
	struct link *link;

	for (link = p->link ; link ; link = link->next)
		if (link->symbol == symbol)
			return link->state->index;
	exit(1);
}

#define ERROR	0
#define SHIFT	1
#define REDUCE	2
#define GOTO	3
#define ACCEPT	4

struct entry
{
	char op;
	int val;
};

struct entry **table;

void slr (void)
{
	struct itemset *p;
	struct item *q;
	int i, j, symbol;

	table = malloc(counter * sizeof(struct entry *));
	for (i = 0 ; i < counter ; ++i)
		table[i] = calloc(SYMBOLS + 1, sizeof(struct entry));
	for (i = 0, p = lr0_sets ; p ; ++i, p = p->next)
		for (q = p->list ; q ; q = q->next)
		{
			symbol = grammar[q->rule].rhs[q->pos];
			if (is_token(symbol))
			{
				table[i][symbol].op = SHIFT;
				table[i][symbol].val = goto_index(p, symbol);
				continue;
			}
			else if (!symbol)
			{
				if (grammar[q->rule].lhs != START_SYMBOL)
				{
					for (j = 0 ; j <= TOKENS ; ++j)
						if (follows[grammar[q->rule].lhs][j])
						{
							table[i][j].op = REDUCE;
							table[i][j].val = q->rule;
						}
					continue;
				}
				else
				{
					table[i][0].op = ACCEPT;
					continue;
				}
			}
			else if (is_non_terminal(symbol))
			{
				table[i][symbol].op = GOTO;
				table[i][symbol].val = goto_index(p, symbol);
				continue;
			}
			else
				exit(1);
		}	
}

void print_table (void)
{
	int i, j;

	printf("\nTable:\n");
	printf("            |   $        |");
	for (i = 1 ; i <= SYMBOLS ; ++i)
		if (i == START_SYMBOL)
			continue;
		else
			printf("   %s       |", symbols[i]);
	printf("\n");
	for (i = 0 ; i <= SYMBOLS ; ++i)
		printf("------------+");
	printf("\n");  
	for (i = 0 ; i < counter ; ++i)
	{
		printf("  %3d       |", i);
		for (j = 0 ; j <= SYMBOLS ; ++j)
		{
			if (j == START_SYMBOL)
				continue;
			switch (table[i][j].op)
			{
				case ERROR:	printf("            |");
						break;
				case SHIFT:	printf(" Shift  %3d |", table[i][j].val);
						break;
				case REDUCE:	printf(" Reduce %3d |", table[i][j].val);
						break;
				case GOTO:	printf(" Goto   %3d |", table[i][j].val);
						break;
				case ACCEPT:	printf(" Accept     |");
						break;
			}
		}
		printf("\n");
	}			
}

int main (void)
{
	init_grammar();
	print_grammar();
	compute_nullable();
	print_nullable();
	compute_firsts();
	print_firsts();
	compute_follows();
	print_follows();
	lr0();
	print_lr0_sets();
	slr();
	print_table();
	return 0;
} 

Generated by GNU enscript 1.6.3.