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.