Search this site
Embedded Files
Skip to main content
Skip to navigation
Página principal
Guia2Compiladores
Proyectos Compiladores
Mini SQL
Proyacto Logo
Leng. Manipulacion Polinomios
Mini-JavaScript
Formas
LitleQuilt
Mini-PostScript
GeneradorEnsamblador
Interprete Maquina Post
Compiladores
Guia3Compiladores
tercetos
GeneracionCodigo
Prog para calc conj Primero
Programacion Orientada a Objetos
Polimorfismo
Temario Estudio
Proyectos
Álbum de fotos digital
MiniPaint
FlappyBird
EditorBitmaps
Generador Evaluador Examenes
JuezEnLinea
MiniNapster
Página principal
Guia2Compiladores
Proyectos Compiladores
Mini SQL
Proyacto Logo
Leng. Manipulacion Polinomios
Mini-JavaScript
Formas
LitleQuilt
Mini-PostScript
GeneradorEnsamblador
Interprete Maquina Post
Compiladores
Guia3Compiladores
tercetos
GeneracionCodigo
Prog para calc conj Primero
Programacion Orientada a Objetos
Polimorfismo
Temario Estudio
Proyectos
Álbum de fotos digital
MiniPaint
FlappyBird
EditorBitmaps
Generador Evaluador Examenes
JuezEnLinea
MiniNapster
More
Página principal
Guia2Compiladores
Proyectos Compiladores
Mini SQL
Proyacto Logo
Leng. Manipulacion Polinomios
Mini-JavaScript
Formas
LitleQuilt
Mini-PostScript
GeneradorEnsamblador
Interprete Maquina Post
Compiladores
Guia3Compiladores
tercetos
GeneracionCodigo
Prog para calc conj Primero
Programacion Orientada a Objetos
Polimorfismo
Temario Estudio
Proyectos
Álbum de fotos digital
MiniPaint
FlappyBird
EditorBitmaps
Generador Evaluador Examenes
JuezEnLinea
MiniNapster
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'
| 'b' 'd' a
;
A : 'd'
;
%%
------------------------------------------------------------------------
%%
S : 'a' 'b' S
| 'a'
;
%%
------------------------------------------------------------------------
%%
S: L '=' R
| R
;
L : '*' R
| 'i'
;
R : L
;
%%
------------------------------------------------------------------------
%%
prog: expr
;
expr: 'i'
| '(' expr ')'
| expr '+' expr
| expr '*' expr
;
%%
------------------------------------------------------------------------
%start a
%%
E : T EP
;
EP : '+' T EP
|
;
T : F TP
;
TP : '*' F TP
|
;
F : '(' E ')'
| 'i'
;
%%
------------------------------------------------------------------------
Google Sites
Report abuse
Page details
Page updated
Google Sites
Report abuse