Prog para calc conj Primero

Programa que se puede usar para verificar si los conjuntos primero

fueron bien calculados

460 lineas mas abajo hay ejemplos de entrada para este programa

#include <ctype.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef int Sym;

typedef struct symbol Symbol;

typedef struct Rule Rule;

typedef struct TSet TSet;

typedef struct Info Info;

//#define S ((Symbol*) NULL)

#define S ((Sym) -1)

#define Red(n) (- (n+2)) /* involutive, Red(Red(x)) == x */

#define GetBit(s,n) (s[n/32] & (1<<(n%32)))

#define SetBit(s,n) (s[n/32] |= 1<<(n%32))

enum {

IdntSz = 64,

MaxRhs = 32,

MaxTk = 500,

MaxNt = 500,

MaxRl = 800,

MaxTm = 1000,

TSetSz = (MaxTk+31)/32,

Sym0 = MaxTk

};

enum symbol_type {

TERMINAL,

NONTERMINAL,

MULTITERMINAL

};

struct symbol {

const char *name; /* Name of the symbol */

int index; /* Index number for this symbol */

enum symbol_type type;

};

struct Rule {

//Symbol *lhs;

//Symbol *rhs[MaxRhs];

Sym lhs;

Sym rhs[MaxRhs];

char *act;

int actln;

int prec;

};

struct TSet {

unsigned t[TSetSz];

};

struct Info {

int nul;

TSet fst;

int prec;

enum {

ANone,

ALeft,

ARight,

ANonassoc

} assoc;

char name[IdntSz];

char type[IdntSz];

};

int nrl, nsy, nst, ntk;

Rule rs[MaxRl]; /* grammar rules (ordered, rcmp) */

Info is[MaxTk+MaxNt]; /* symbol information */

//Symbol *sstart;

Sym sstart;

int lineno = 1;

char *srca;

FILE *fin;

FILE *fout;

FILE *fgrm;

FILE *fhdr;

enum {

TIdnt,

TTokchr, /* 'c' */

TPP, /* %% */

TLL, /* %{ */

TLangle, /* < */

TRangle, /* > */

TSemi, /* ; */

TBar, /* | */

TColon, /* : */

TLBrack, /* { */

TUnion, TType, TToken, TRight, TLeft,

TNonassoc, TPrec, TStart, TEof

};

struct {

char *name;

int tok;

} words[] = {

{ "%%", TPP }, { "%union", TUnion }, { "%type", TType },

{ "%token", TToken },{ "%right", TRight }, { "%left", TLeft },

{ "%nonassoc", TNonassoc },{ "%prec", TPrec },{ "%start", TStart },

{ 0, 0 }

};

char idnt[IdntSz];

void die(char *s){

fprintf(stderr, "%s (on line %d)\n", s, lineno);

exit(1);

}

void tszero(TSet *ts){

memset(ts, 0, sizeof *ts);

}

int tsunion_1(TSet *tsa, TSet *tsb){

int n;

unsigned *a, *b, c, t;

c = 0;

a = tsa->t;

b = tsb->t;

n = (31+ntk)/32;

while (n-- > 0) {

c = *a | *b;

b++;

a++;

printf("while <%d>", n);

}

return !!c;

}

int tsunion(TSet *tsa, TSet *tsb){

int n;

unsigned *a, *b, c, t;

c = 0;

a = tsa->t;

b = tsb->t;

n = (31+ntk)/32;

//printf("antes while <%d>", n);

while (n-- > 0) {

t = *a;

*a = *a | *b;

b++;

c = c | t ^ *a;

a++;

//printf("while <%d>", n);

}

//printf("despues while <%d>", n);

return !!c;

}

int tsunion_(TSet *tsa, TSet *tsb){

int n;

unsigned *a, *b, c, t;

c = 0;

a = tsa->t;

b = tsb->t;

n = (31+ntk)/32;

while (n-- > 0) {

t = *a;

*a |= *b++;

c |= t ^ *a++;

}

return !!c;

}

void first(TSet *ts, Sym *stnc, TSet *last){

Sym f;

int s;

f = stnc[0];

for (s=0; s< ntk; s++) {

if (GetBit(ts->t, s))

printf("first (%d) < %s > \n", s, is[s].name);

}

if (f == S) {

if (last)

tsunion(ts, last);

return;

}

if (f < ntk) { //es un token

SetBit(ts->t, f);

return;

}

if (is[f].nul)

first(ts, stnc+1, last);

tsunion(ts, &is[f].fst);

}

void ginit(){

int chg;

Rule *r;

Info *i;

Sym *s;

TSet ts;

do {

chg = 0;

for (r=rs; r-rs<nrl; r++) {

i = &is[r->lhs];

for (s=r->rhs; *s!=S; s++)

if (!is[*s].nul)

goto nonul;

chg |= i->nul == 0;

i->nul = 1;

nonul:

tszero(&ts);

first(&ts, r->rhs, 0);

chg |= tsunion(&i->fst, &ts);

}

} while (chg);

}

Sym findsy(char *name, int add){

int n;

for (n=0; n<nsy; n++) {

if (n == ntk) {

if (name[0]=='\'') {

if (ntk>=MaxTk)

die("too many tokens");

ntk++;

strcpy(is[n].name, name);

return n;

}

n = MaxTk;

}

if (strcmp(is[n].name, name)==0)

return n;

}

if (add) {

if (nsy>=MaxTk+MaxNt)

die("too many non-terminals");

strcpy(is[nsy].name, name);

return nsy++;

} else

return nsy;

}

int istok(int c){

return isalnum(c) || c=='_' || c=='%';

}

int nexttk(){

int n;

char c, *p;

while (isspace(c=fgetc(fin)))

if (c == '\n')

lineno++;

switch (c) {

case '<':

return TLangle;

case '>':

return TRangle;

case ';':

return TSemi;

case '|':

return TBar;

case ':':

return TColon;

case '{':

return TLBrack;

case EOF:

return TEof;

case '\'':

idnt[0] = '\'';

idnt[1] = fgetc(fin);

idnt[2] = '\'';

idnt[3] = 0;

if (fgetc(fin)!='\'')

die("syntax error, invalid char token");

return TTokchr;

}

p = idnt;

while (istok(c)) {

*p++ = c;

if (p-idnt >= IdntSz-1)

die("identifier too long");

c = fgetc(fin);

}

*p = 0;

if (strcmp(idnt, "%")==0)

if (c=='{')

return TLL;

ungetc(c, fin);

for (n=0; words[n].name; n++)

if (strcmp(idnt, words[n].name) == 0)

return words[n].tok;

return TIdnt;

}

void getdecls(){

int tk, prec, p, a, c, c1, n;

Info *si;

char type[IdntSz], *s;

strcpy(is[0].name, "$");

ntk = 1;

strcpy(is[Sym0].name, "@start");

nsy = MaxTk+1;

sstart = S;

prec = 0;

tk = nexttk();

for (;;)

switch (tk) {

case TStart:

tk = nexttk();

if (tk!=TIdnt)

die("syntax error, ident expected after %start");

sstart = findsy(idnt, 1);

if (sstart<ntk)

die("%start cannot specify a token");

tk = nexttk();

break;

case TPP:

return;

case TEof:

die("syntax error, unfinished declarations");

default:

die("syntax error, declaration expected");

}

}

void getgram(){

extern char *retcode;

int tk;

Sym hd, *p, s;

//Symbol *hd, **p, *s;

Rule *r;

for (;;) {

tk = nexttk();

if (tk==TPP || tk==TEof) {/* %% */

if (sstart==S)

die("syntax error, empty grammar");

r = &rs[nrl++];

r->lhs = Sym0;

r->rhs[0] = sstart;

r->rhs[1] = 0;

r->rhs[2] = S;

//r->act = retcode;

//qsort(rs, nrl, sizeof rs[0], rcmp);

return;

}

if (tk!=TIdnt)

die("syntax error, production rule expected");

if (nexttk()!=TColon) /* : */

die("syntax error, colon expected after production's head");

hd = findsy(idnt, 1);

if (sstart==S)

sstart = hd;

do {

if (nrl>=MaxRl-1)

die("too many rules");

r = &rs[nrl++];

r->lhs = hd;

r->act = 0;

p = r->rhs;

while ((tk=nexttk())==TIdnt || tk==TTokchr || tk==TPrec) {

if (tk==TPrec) {

tk = nexttk();

if (tk!=TIdnt

|| (s=findsy(idnt, 0))>=ntk)

die("token expected after %prec");

r->prec = is[s].prec;

continue;

}

s = findsy(idnt, 1);

*p++ = s;

//if (s<ntk && is[s].prec>0)

// r->prec = is[s].prec;

if (p - r->rhs >= MaxRhs-1)

die("production rule too long");

}

*p = S;

if (tk==TLBrack) {

r->actln = lineno;

//r->act = cpycode();

tk = nexttk();

}

} while (tk==TBar);

if (tk!=TSemi)

die("syntax error, ; or | expected");

}

}

void init(int ac, char *av[]){

int c, vf, df;

char *pref, buf[100], *opt;

(void) ac;

pref = "y";

vf = df = 0;

for (av++; av[0] && av[0][0]=='-'; av++)

for (opt = &av[0][1]; (c = *opt); opt++)

switch (c) {

case 'v':

vf = 1;

break;

case 'd':

df = 1;

break;

case 'b':

if ((pref = *++av))

break;

default:

usage:

fputs("usage: myacc [-vd] [-b file_prefix] grammar\n", stderr);

exit(1);

}

if (!(srca = *av))

goto usage;

fin = fopen(srca, "r");

if (strlen(pref) + 10 > sizeof buf)

die("-b prefix too long");

sprintf(buf, "%s.tab.c", pref);

fout = fopen(buf, "w");

if (vf) {

sprintf(buf, "%s.output", pref);

fgrm = fopen(buf, "w");

}

if (df) {

sprintf(buf, "%s.tab.h", pref);

fhdr = fopen(buf, "w");

if (fhdr) {

fprintf(fhdr, "#ifndef Y_TAB_H_\n");

fprintf(fhdr, "#define Y_TAB_H_\n");

}

}

if (!fin || !fout || (!fgrm && vf) || (!fhdr && df))

die("cannot open work files");

}

void main (int ac, char *av[]){

Rule *r;

Sym *s1;

int s;

int i=0;

//infile = argv[1];

srca=strdup("gansito");

//printf("arch ent=(%s)\n",infile);

strcpy(is[0].name, "$");

ntk = 1;

strcpy(is[Sym0].name, "@start");

nsy = MaxTk+1;

sstart = S;

init(ac, av);

getdecls();

getgram();

ginit();

printf("nsy = (%d) ntk = (%d) \n", nsy, ntk);

//fprintf(fhdr, "#define %s %d\n", is[n].name, m);

for (s=0; s< ntk; s++) {

printf("token (%d) < %s> \n", s, is[s].name);

}

for (s=MaxTk; s< nsy; s++) {

printf("(%d) < %s> \n", s, is[s].name);

}

for (r=rs; r-rs< nrl; r++) {

printf("\n11main (%s) Regla %03d: %s ->",

is[r->lhs].type, (int)(r-rs), is[r->lhs].name);

for (s1=r->rhs; *s1!=S; s1++)

printf(" %s", is[*s1].name);

}

for (r=rs; r-rs<nrl; r++) {

printf("\n22main (%s) %03d: %s ->\n", is[r->lhs].type, (int)(r-rs), is[r->lhs].name);

for (s=0; s< ntk; s++) {

if (GetBit(is[r->lhs].fst.t, s))

printf("(%d) < %s > \n", s, is[s].name);

}

}

}

----------------------------------------------------------------------

%%

S : A A

;

A : 'a' A

| 'b'

;

%%

---------------------------------------------------------------------

%%

A : '(' A ')'

| 'a'

;

%%

-------------------------------------------------------------------

%%

A : '(' A ')'

| 'a'

| 'b'

;

%%

--------------------------------------------------------------------

%%

S: '[' S ']'

| 'x'

;

%%

--------------------------------------------------------------------

%%

E : '(' E ',' E ')'

| 'a'

;

%%

-------------------------------------------------------------------

%%

S : 'c' S A 'd'

| 'd'

;

A : 'a' B

| 'a'

;

B : 'a'

| 'b'

;

%%

-------------------------------------------------------------------

%%

S: S 'a'

| 'b'

;

%%

--------------------------------------------------------------------

%%

S: B B

;

B : 'b' B

| 'c'

;

%%

---------------------------------------------------------------------

%%

S : A

;

A :

| A 'b' 'b'

;

%%

----------------------------------------------------------------------

%%

S : A 'a'

| 'b' A 'c'

| 'd' 'c'

| 'b' 'd' 'a'

;

A : 'd'

;

%%

----------------------------------------------------------------------

%%

S : 'a'

| '(' S R

;

R : ',' S R

| ')'

;

%%

-----------------------------------------------------------------------

%%

S : '[' L ']'

| 'a'

;

L : L ',' S

| S

;

%%

------------------------------------------------------------------------

%%

S : '[' S L

| 'a'

;

L : ',' S L

| ']'

;

%%

------------------------------------------------------------------------

%%

R : R '|' R

| R R

| R '*'

| '(' R ')'

| 'a'

| 'b'

;

%%

------------------------------------------------------------------------

%%

S : A

;

A :

| 'b' 'b' A

;

%%

-------------------------------------------------------------------------

%%

S : A 'a' A 'b'

| B 'b' B 'a'

;

A :

;

B :

;

%%

-------------------------------------------------------------------------

%%

A : 'x' A

| 'y' A

| 'y'

;

%%

--------------------------------------------------------------------------

%%

S : X

;

X : 'a' X 'c'

| X X

| 'b'

;

%%

-------------------------------------------------------------------------

%%

S : 'a' S 'b' S

| 'a'

;

%%

---------------------------------------------------------------------------

%%

C : A B

;

A : 'a'

;

B : 'a'

;

%%

------------------------------------------------------------------------

%%

S: 'd' 'c' 'a'

| 'd' A 'b'

| A 'a'

;

A: 'c'

;

%%

------------------------------------------------------------------------

%%

S : A 'a'

| 'b' A 'c'

| 'd' 'c'