YACC

/*Yacc specifications of simple desktop calculator*/
%{
#include ctype.h
%}
%token DIGIT
%%
line : expr '\n' {printf("%d\n",$1);}

expr : expr '+' term {$$=$1+$3;}
|term

term : term '*' factor {$$=$1*$3;}
|factor

factor : '('expr')' {$$=$2;}
|DIGIT
;
%%
yylex() {
int c;
c=getchar();
if(isdigit(c)){
yylval=c-'0';
return DIGIT;
}
return c;
}

OUTPUT:
$ yacc y1.y
$ cc y.tab.c -ly
$ ./a.out
2+3
5
$

LEX TOOL

%{
#include math.h
#include stdio.h
%}
DIGIT [0-9]
ID [a-z][a-z0-9]*
%%
{DIGIT}+ {printf("An Integer : %(%d) \n",yytext,atoi(yytext));}
{DIGIT}+"."{DIGIT}* {printf("A Float : %s(%g) \n",yytext,atof(yytext));}
if|then|begin|end|procedure|function {printf("A keyword : %s\n",yytext);}
{ID} printf("An identifier:%s \n",yytext);
"+"|"-"|"*"|"/" printf("An Operator:%s \n ",yytext);
%%
int main(int argc,char *argv[])
{
++argv;--argc;/*skip over program name*/
if(argc>0)
yyin=fopen(argv[0],"r");
else
yyin=stdin;
yylex();
}

$ lex lex1.l
$ cc lex.yy.c -ll
$ a.out
if
A keyword : if

thr
An identifier:thr

then
A keyword : then

123
An Integer : %(4203076) CNTR+d

TOP DOWN PARSER

#include stdio.h
#include conio.h
#include string.h
#include ctype.h

int main()
{
char G[2][15]={"S->cAd/cd",
"A->ac/ab" };

char str[20],n[2];
int i,j,k,l,m,t;
int p,q;
clrscr();
printf("Grammar \n");
for(p=0;p<2;p++)
{
for(q=0;q<15;q++)
printf("%c",G[p][q]);
printf("\n\n");
}

printf("Enter the string to be parsed : ");
gets(str);
for(i=0,k=3,l=0;str[i]!='\0';k++)
{
if(G[l][k]!=str[i])
{
if(isupper(G[l][k]))
{
t=k;
m=i;
k=2;
l++;
}
if(G[l][k]=='/'||G[l][k]=='\0'&&l!=0)
{
l--;
k=t;
}
else if(k!=2)
{
for(j=k;G[l][j]!='/'&&G[l][j]!='\0';j++)
if(G[l][j]=='\0')
{
if(i==0)
{
printf("Not Accepted");
exit(0);
}
else
k=2;
}
if(l!=0)
i=m;
k=j;
} }
else
i++;

}
if(str[i]=='\0'&&G[l][k]=='/'||G[l][k]=='\0'&&l==0)
printf("Accepted");
else
printf("Not Accepted");
return 0;
}

OUTPUT:
Grammar
S->cAd/cd
A->ac/ab
Enter the string to be parsed : cabd
Accepted


Grammar
S->cAd/cd
A->ac/ab
Enter the string to be parsed : aaa
Not Accepted

RECURSIVE DESCENT PARSER

#include stdio.h
#include conio.h
int main()
{
char g[30]={"S->icts/wcts/dtcs" };
char s[40];
int i,j,k;
clrscr();
printf("Grammar \n\n");
for(i=0;g[i]!='\0';i++)
printf("%c",g[i]);
printf("Enter the string : ");
gets(s);
for(i=0,k=3;(s[i]!='\0')&&(g[k]!='\0');k++)
{
if(g[k]!=s[i])
{
for(j=k;(g[j]!='/')&&(g[j]!='\0');j++);
k=j;
}
else
i++;
}
if(s[i]=='\0'&&(g[k]=='/'||g[k]=='\0'))
{
printf("String is Accepted");
exit(0);
}
printf("String is not accepted");
return 0;
}
OUTPUT:
Grammar:
S->icts/wcts/dtcs
Enter the string : wctg
String is not accepted

Grammar:
S->icts/wcts/dtcs
Enter the string : dtcs
String is Accepted

OPERATOR PRECEDENCE PARSER

#include stdio.h
#include string.h
#include conio.h
char stack[20],stack1[20],next,s[10];
int top=-1;
char prod[9][10]={
">><<<<<>>",
">><<<<<>>",
">>>><<<>>",
">>>><<<>>",
">>>><<<>>",
">>>>>ee>>",
"<<<<<<<=e",
">>>>>ee>>",
"<<<<<< };
char G[7][6]={
"E->E+E",
" /E-E",
" /E*E",
" /E/E",
" /(E)",
" /i "
};


int main()
{
char symbol;
int i=0,flag=0;
int j,k;
clrscr();
printf("Grammar\n");
for(j=0;j<7;j++)
{
for(k=0;k<6;k++)
printf("%c",G[j][k]);
printf("\n");
}
printf("\n\n OPERATOR PRECEDENCE RELATIONS \n");
printf("\n -------------------------------------------------------- \n");
printf("%c\t%c\t%c\t%c\t%c\t%c\t%c\t%c\t%c\t",'+','-','*','/','^','i','(',')','$');
printf("\n------------------------------------------------------------------\n");
for(j=0;j<9;j++)
{
for(k=0;k<10;k++)
printf("%c\t",prod[j][k]);
printf("\n");
}
printf("Enter the string : ");
gets(s);
++top;
stack[top]='$';
next=s[i];
while(1)
{
if(stack[top]=='$'&& next=='$'||next=='\0')
break;
else
{
symbol=prod[f(stack[top])][f(next)];
if(symbol=='<'||symbol=='=')
{
stack[++top]=symbol;
stack[++top]=next;
}
else if(symbol=='>')
{
do
{
top--;
}while(stack[top]!='<');
stack[++top]=next;
if(next!='$')
{
for(j=0;j<=top;j++)
stack1[j]=stack[j];
stack1[j]=symbol;
}
}
else
flag=1;
next=s[++i];
}
}

printf("\n STACK : ");
for(j=0;j<=top;j++)
printf("%c",stack1[j]);
printf("%c",'$');
if(flag==0)
printf("\n\n Accepted");
else
printf("Rejected");
return 0;
}


int f(char ch)
{
switch(ch)
{
case '+':return 0;
case '-':return 1;
case '*':return 2;
case '/':return 3;
case '^':return 4;
case 'i':return 5;
case '(':return 6;
case ')':return 7;
case '$':return 8;
default :
{
printf("\n ERROR ");
exit(0);
}
}
}

OUTPUT:



OPERATOR PRECEDENCE RELATIONS

--------------------------------------------------------
+ - * / ^ i ( ) $
------------------------------------------------------------------
> > < < < < < > >

> > < < < < < > >

> > > > < < < > >

> > > > < < < > >

> > > > < < < > >

> > > > > e e > >

< < < < < < < = e

> > > > > e e > >

< < < < < < < e e

Enter the string : i + i @ i $
ERROR

Enter the string : i +i*i$
STACK : $<+<*> $
Accepted

LR PARSER

#include stdio.h
#include conio.h
#include string.h
#define MAX 36
char action_table[12][6][4]={
"s5","e1","e1","s4","e1","e1",
"e1","s6","e1","e1","e1","A",
"e1","r2","s7","e1","r2","r2",
"e1","r4","r4","e1","r4","r4",
"s5","e1","e1","s4","e1","e1",
"e1","r6","r6","e1","r6","r6",
"s5","e1","e1","s4","e1","e1",
"s5","e1","e1","s4","e1","e1",
"e1","s6","e1","e1","s11","e1",
"e1","r1","s7","e1","r1","r1",
"e1","r3","r3","e1","r3","r3",
"e1","r5","r5","e1","r5","r5"
};
char goto_table[12][3][4]={
"1","2","3",
" "," "," ",
" "," "," ",
" "," "," ",
"8","2","3",
" "," "," ",
" ","9","3",
" "," ","10",
" "," "," ",
" "," "," ",
" "," "," ",
" "," "," "
};

char G[6][10]={
"E-->E+T",
"E-->T",
"T-->T*F",
"T-->F",
"F-->(E)",
"F-->i"
};

int i,top=-1;
char stack[MAX],st[20];
char err_flag;
void push(char ch)
{
if(top>MAX-1)
printf("\n Stack is full \n");
else
{
if(ch=='')
return;
else
stack[++top]=ch;
}
}
char pop()
{
char ch;
if(top<0)
{
printf("\n stack is empty \n");
return '\0';
}
ch=stack[top--];
stack[top+1]='\0';
return ch;
}
int char_val(char ch)
{
int x;
switch(ch)
{
case'i':
case'E': x=0;
break;
case'+':
case'T': x=1;
break;
case'*':
case'F': x=2;
break;
case'(':x=3;
break;
case')':x=4;
break;
case'$' :x=5;
break;
}
return x;
}
void error()
{
err_flag=1;
}
void main()
{
char x,a,tab_e[5],goto_e[4];
int i=0,len,xx,yy,zz,red_val,l;
clrscr();
printf("\n Enter a string ending with a $: ");
fflush(stdin);
scanf("%s",st);
printf("\n Input string is %s ",st);
push('0');
printf("\n\n\n\n\t\t parse table for expression grammar");
printf("-------------------------------------------------\n");
printf("\n\t\tAction_Table\t\t\tGoto_table");
printf("-------------------------------------------------\n");
printf("\n%7s%7s%7s%7s%7s%7s%7s%7s%7s","id","+","*","(",")","$","E","T","F");
printf("\n-----------------------------------------------\n");

for(xx=0;xx<12;xx++)
{
for(yy=0;yy<6;yy++)
printf("%7s",action_table[xx][yy]);
for(yy=0;yy<3;yy++)
printf("%7s",goto_table[xx][yy]);
printf("\n\n");
}
printf("\n MOVES MADE BY LR PARSER \n");
printf("---------------------------\n");
printf("STACK\t\t\tINPUT_STRING \n");
printf("--------------------------\n");
do
{
if(stack[top]=='\n')
{
for(l=0;l printf("%c",stack[l]);
printf("%d\t\t",stack[top]);
}
else
printf("%s\t\t\t",stack);
for(xx=0;st[xx]!='\0';xx++)
if(xx printf(" ");
else
printf("%c",st[xx]);
printf("\n");
if(stack[top]=='1' && stack[top-1]=='1')
x=11;
else
x=stack[top];
a=st[i];
if(stack[top]=='\n')
xx=10;
else if(stack[top]=='1' && stack[top-1]=='1')
{
xx=11;
stack[--top]=11;
}
else
xx=x-'0';
if(top>2)
switch(stack[top-1])
{
case 'i':
case '+':
case '*':
case '(':
case ')':
case '$':
case 'E':
case 'T':
case 'F':
break;
default:
xx+=(stack[top-1]-'0')*10;
break;
}
yy=char_val(a);
strcpy(tab_e,action_table[xx][yy]);
if(tab_e[0]=='s')
{
push(a);
push(tab_e[1]);
if(tab_e[2]!='\0')
push(tab_e[2]);
a=st[++i];
}
else
if(tab_e[0]=='r')
{
red_val=tab_e[1]-'0';
len=strlen(G[red_val-1]);
for(len=len-4;len>0;len--)
{
pop();
pop();
}
xx=stack[top]-'0';
push(G[red_val-1][0]);
yy=char_val(G[red_val-1][0]);
if(xx==7&&yy==2)
push(10);
else
push(goto_table[xx][yy][0]);
}
else if(action_table[xx][yy][0]=='A')
break;
else
error();

}while(!err_flag);
if(err_flag)
printf("Parsing is unsuccessfull");
else
printf("\n parsing is successfull\n");
getch();
}

OUTPUT:
Input string is : i*i+i$

-------------------------------------------------------------------
parse table for expression grammar
-------------------------------------------------------------------
Action_Table Goto_table
-------------------------------------------------------------------
id + * ( ) $ E T F
-------------------------------------------------------------------
s5 e1 e1 s4 e1 e1 1 2 3

e1 s6 e1 e1 e1 A

e1 r2 s7 e1 r2 r2

e1 r4 r4 e1 r4 r4

s5 e1 e1 s4 e1 e1 8 2 3

e1 r6 r6 e1 r6 r6

s5 e1 e1 s4 e1 e1 9 3

s5 e1 e1 s4 e1 e1 10

e1 s6 e1 e1 s11 e1

e1 r1 s7 e1 r1 r1

e1 r3 r3 e1 r3 r3

e1 r5 r5 e1 r5 r5


MOVES MADE BY LR PARSER
---------------------------------------------
STACK INPUT_STRING
----------------------------------------------
0 i*i+i$
0i5 *i+i$
0F3 *i+i$
0T2 *i+i$
0T2*7 i+i$
0T2*7i5 +i$
0T2*7F10 +i$
0T2 +i$
0E1 +i$
0E1+6 i$
0E1+6i5 $
0E1+6F3 $
0E1+6T9 $
0E1 $

parsing is successfull

LEXICAL ANALYSER

#include stdio.h
#include conio.h
#include string.h
#include ctype.h

/*SYMBOL TABLE*/

struct symbol_table
{
char * token_type;
const char * att;
}symbol[30];
/*GLOBAL VARIABLES*/

int index=0,look=0;
char st1[10],st2[10];
/*LOOK UP TABLE*/

int lookup(char st[])
{
int i;
for(i=1;i<=30;i++)
{
if(!strcmp(symbol[i].att,st))
return i;
else if(!i)
return 0;
}
return -1;
}

void insert(char st1[],const char st2[])
{
symbol[index].token_type=(char *)malloc(strlen(st1));
symbol[index].att=(char *)malloc(strlen(st2));
strcpy(symbol[index].token_type,st1);
strcpy(symbol[index].att,st2);
index++;
}


int main()
{
int i,j,k,val,flag,ln=0,x,y=0;
char c,ch,chr[50];
char res[10][10]={"if","else","while","do","for"};
clrscr();
printf("Enter the string : ");
while(1)
{
j=0;
flag=0;
chr[0]='\0';
c=getchar();
if(c=='$')
break;
else if((c==' ')||(c=='\t'));
else if(c=='\n')
ln++;
else if(isdigit(c))
{
while(isdigit(c))
{
chr[j]=c;
j++;
c=getchar();
}
chr[j]='\0';
ungetc(c,stdin);
insert("Num",chr);
printf("\n",chr);
}
else if(isalpha(c))
{
while(isalpha(c))
{
chr[j]=c;
j++;
c=getchar();
}
chr[j]='\0';
for(k=0;k<5;k++)
if(!strcmp(chr,res[k]))
{
insert(chr,res[k]);
flag=1;
printf("\n",res[k]);
break;
}
if(!flag)
{
look=lookup(chr);
if(look!=0)
{
insert("Id",chr);
printf("\n",chr);
}
else
{
printf("\n",chr);
insert("Id",chr);
index++;
}
}
ungetc(c,stdin);
}
else if(c=='>')
{
chr[0]=c;
chr[1]='\0';
c=getchar();
if(c=='=')
{
chr[1]=c;
chr[2]='\0';
printf("\n",chr);
insert("GTE",chr);
}
else
{ ungetc(c,stdin);
printf("\n",chr);
insert("GT",chr);
}
}
else if(c=='<')
{
chr[0]=c;
chr[1]='\0';
c=getchar();
if(c=='>')
{
chr[1]=c;
chr[2]='\0';
printf("\n",chr);
insert("NE",chr);
}
else if(c=='=')
{
chr[1]=c;
chr[2]='\0';
printf("\n",chr);
insert("LTE",chr);
}
else
{
ungetc(c,stdin);
printf("\n",chr);
insert("LT",chr);
}
}
else if(c=='=')
{
chr[0]=c;
chr[1]='\0';
c=getchar();
if(c=='=')
{
chr[1]=c;
chr[2]='\0';
printf("\n",chr);
insert("EQU",chr);
}
else
{
printf("\n",chr);
insert("ASS_OP",chr);
ungetc(c,stdin);
}
}
else
{
switch(c)
{
case '+':
chr[0]=c;
chr[1]='\0';
printf("\n",c);
insert("PLUS",chr);
break;
case '-':

chr[0]=c;
chr[1]='\0';
printf("\n",c);
insert("MINUS",chr);
break;
case '*':

chr[0]=c;
chr[1]='\0';
printf("\n",c);
insert("MULTI",chr);
break;
case '/':

chr[0]=c;
chr[1]='\0';
printf("\n",c);
insert("DIVISION",chr);
break;
case '%':

chr[0]=c;
chr[1]='\0';
printf("\n",c);
insert("MODULOS",chr);
break;
case '(':
chr[0]=c;
chr[1]='\0';
printf("\n",c);
insert("(",chr);
break;
case ')':
chr[0]=c;
chr[1]='\0';
printf("\n",c);
insert(")",chr);
break;
default:
printf("\n",chr);
}
}
}

printf("\n\t\tSYMBOL TABLE");
printf("\n..............................................\n");
printf("%s\t\t%s\t\t%s","TOKEN","TOKEN_TYPE","TOKEN_VALUE");
printf("\n...............................................\n");
for(k=0;k {
y=0;
for(x=0;x if(!strcmp(symbol[k].att,symbol[x].att))
{
y=1;
printf("%s\t\t%s\t\t%d\n",symbol[k].att,symbol[k].token_type,x);
break;
}
if(y==0)
{
printf("%s\t\t%s\t\t%d\n",symbol[k].att,symbol[k].token_type,k);
}
}
getch();
return 0;
}


OUTPUT:

Enter the string : if(a==b) a+b$









SYMBOL TABLE
............................................…………………………………..
TOKEN TOKEN_TYPE TOKEN_VALUE
.............................................…………………………………
if if 0
( ( 1
a Id 2
== EQU 3
b Id 4
) ) 5
a Id 2
+ PLUS 7
b Id 4