Online compiler
unknown
c_cpp
a year ago
21 kB
16
Indexable
Design a DFA to accept all strings containing a substring(01)
AIM: To design a Deterministic Finite Automata
Hardware: Intel® CORE™ i3-3240 CPU@3.40GHZ
HDD:500 GB ,RAM:4GB
Software: OS: LINUX using putty
C Compiler
ALGORITHM:
1.start
2.declare the variable and character array
3.enter the string to be checked
4.find the length of the string
5.for loop starts from and move till 1
6.use decision making statements to check the string containing substring (01)or not
7.print accepted ,if the string containing substring (01)
8.print rejected ,if the string not containing substring(01)
9.stop
PROGRAM:
#include<stdio.h>
#include<string.h>
void main()
{
char s[20],ch;
int i,l,r=0;
printf("Enter the string to be checked\n");
scanf("%s",&s);
l=strlen(s);
for(i=0;i<l;i++)
{
ch=s[i];
if(ch=='0')
{
ch=s[++i];
if(ch=='1')
{
printf("The entered string is in DFA\n");
r=1;
break;
}
i--;
}
if(r==0)
{
printf("The entered string is not in DFA\n");
break;
}
}
}
OUTPUT:
Enter the string to be checked
011001
The entered string is in DFA
Enter the string to be checked
111000
The entered string is not in DFA
Write a LEX Program to scan reserved word & Identifiers of C Language
AIM: Implement the Lexical Analyzer Using Lex Tool.
Hardware: Intel® CORE™ i3-3240 CPU@3.40GHZ
HDD:500 GB ,RAM:4GB
Software: OS: LINUX using putty,
C Compiler and LEX compiler
ALGORITHM:
1. start
2. lex program consists of 3 parts
a.declaration %{%}
b.translation rules %%
c. auxilary procedure
3. the declaration section includes declaration of variables ,main test,constants,and regular definitions
4. translation rule of lex program are statements of the form p1{action},p2{action}………..pn{action}
5. write a program in the FLEX windows editor and save it with .l extension
6. write a c-program and save it with .c extension in the same directory as an input
7. open CMD in tools ,type the following for compile and run
a.type lex<filename.l>and press the enter button
b. type gcc lex .yy.c -0<executable filename>press the enter
c.type<executable filename><filename.c>
8. verify output
PROGRAM:
%{
#include<stdio.h>
%}
digit[0-9]
letter[a-zA-Z]
%%
int|main|include|stdio|void|printf|case|char|return|for|void|do|if|static|while|float {printf("%s-keyword\n",yytext);}
{letter}({letter}|{digit})* { printf("%s-identifier\n",yytext); }
{digit}+ {printf("%s-not an identifier\n",yytext);}
.|\n;
%%
int yywrap( )
{
return 1;
}
void main(int argc,char**argv)
{
if(argc>1)
yyin=fopen(argv[1],"r");
else
yyin=stdin;
yylex();
printf("\n");
}
C-PROGRAM (for output):
#include<stdio.h>
void main()
{
int a,b,c;
printf("enter a,b values:");
scanf("%d%d",&a,&b);
c=a+b;
printf("%d",c)
}
OUTPUT:
[exam1@localhost compiler]$ lex filename.l
[exam1@localhost compiler]$ cc lex.yy.c
[exam1@localhost compiler]$ ./a.out program.c
include-keyword
stdio-keyword
h-identifier
void-keyword
main-keywor
int-keyword
a-identifier
b-identifier
c-identifier
printf-keyword
enter-identifier
a-identifier
b-identifier
values-identifier
scanf-identifier
d-identifier
d-identifier
a-identifier
b-identifier
c-identifier
a-identifier
b-identifier
printf-keyword
d-identifier
c-identifier
Write a LEX Program to scan integers as Float Numbers in C Language
AIM: Implementation of lex program to scan integers as float values.
Hardware: Intel® CORE™ i3-3240 CPU@3.40GHZ HDD:500 GB ,RAM:4GB
Software: OS: LINUX using putty,
C Compiler and LEX compiler
ALGORITHM:
declare the digit and letters that are to be identified
check the token ,if token is matched with the pattern then it will print integer numbers 3.check the token ,if token is matched with the pattern then it will print decimal values 4.call the yylex function in main methode
5.call the yywrap function which is auxilary function 6.write a c-program for scanning integers and float values 7.then compute the compilation and get the result 8.(or)else directly execute the program in putty as
a.vi lname.l b.lex lname.l
b.cc lex.yy.c
c./a.out
PROGRAM:
%{
#include<stdio.h>
%}
digit[0-9]*
%%
{digit} {ECHO; printf("-integer");
}
{digit}*?\.{digit}* {ECHO; printf("-float");
}
%%
int yywrap()
{
return 1;
}
int main(void)
{
yylex();
return 0;
}
OUTPUT:-
1
1-integer
2.33
2.33-float
Implement Predictive Parsing algorithm
AIM: Implement a c program for implementing the functionalities of predictive parser for the mini language specified
Hardware: Intel® CORE™ i3-3240 CPU@3.40GHZ
HDD:500 GB ,RAM:4GB
Software: OS:LINUX using putty,
C Compiler and LEX compiler
ALGORITHM:
1.start
2.declare the required array pro[7][10],pror,prod,first,follow,tables
3.using swicth case under numr(),select and return specific values for given character
4.In the main function,copy the table values into a string and print the table
5.stop
PROGRAM:
#include<stdio.h>
#include<string.h>
char prol[7][10]={"S","A","A","B","B","C","C"};
char pror[7][10]={"A","Bb","Cd","aB","ℇ","Cc","ℇ"};
char prod[7][10]={"S->A","A->Bb","A->Cd","B->ab","B->ℇ","C->Cc","C->ℇ"};
char first[7][10]={"abcd","ab","cd","a","ℇ","c","ℇ"};
char follow[7][10]={"$","$","$","b$","b$","cd","cd"};
char table[5][6][10];
int numr(char c)
{
switch(c)
{
case 'S':return 0;
case 'A':return 1;
case 'B':return 2;
case 'C':return 3;
case 'a':return 0;
case 'b':return 1;
case 'c':return 2;
case 'd':return 3;
case '$':return 4;
}
return(2);
}
void main()
{
int i,j,k;
for(i=0;i<5;i++)
for(j=0;j<6;j++)
strcpy(table[i][j]," ");
printf("\n The following is the predictive parsing table for the following grammar:\n");
for(i=0;i<7;i++)
printf("%s\n",prod[i]);
printf("\n predictive parsing table is\n");
fflush(stdin);
for(i=0;i<7;i++)
{
k=strlen(first[i]);
for(j=0;j<10;j++)
if(first[i][j]!='ℇ')
strcpy(table[numr(prol[i][0])+1][numr(first[i][j])+1],prod[i]);
}
for(i=0;i<7;i++)
{
if(strlen(pror[i])==1)
{
if(pror[i][0]=='ℇ')
{
k=strlen(follow[i]);
for(j=0;j<k;j++)
strcpy(table[numr(prol[i][0])+1][numr(follow[i][j])+1],prod[i]);
}
}
}
strcpy(table[0][0]," ");
strcpy(table[0][1],"a");
strcpy(table[0][2],"b");
strcpy(table[0][3],"c");
strcpy(table[0][4],"d");
strcpy(table[0][5],"$");
strcpy(table[1][0],"S");
strcpy(table[2][0],"A");
strcpy(table[3][0],"B");
strcpy(table[4][0],"C");
printf("\n------------------------------------------------\n");
for(i=0;i<5;i++)
for(j=0;j<6;j++)
{
printf("%-10s",table[i][j]);
if(j==5)
printf("\n ------------------------------------\n");
}
}
OUTPUT:
The following is the predictive parsing table for the following grammar:
S->A
A->Bb
A->Cd
B->ab
B->ℇ
C->Cc
C->ℇ
predictive parsing table is
------------------------------------------------
a b c d $
------------------------------------
S S->A S->A S->A S->A
------------------------------------
A A->Bb A->Bb A->Cd A->Cd
------------------------------------
B B->ab B->ℇ B->ℇ B->ℇ
------------------------------------
C C->ℇ C->ℇ C->ℇ
------------------------------------
Implement RD Parser for the Grammar S->AB
A->a/ε
B->b/ε
AIM: To implement a c program for recursive desent parser
Hardware: Intel® CORE™ i3-3240 CPU@3.40GHZ
HDD:500 GB ,RAM:4GB
Software: OS:LINUX using putty,
C Compiler and LEX compiler
ALGORITHM:
1.start
2.define the grammer for recursive descent parser
3.enter the string that is to be checked
4.if the given string satisfies the conditions then the string is accepted
5.otherwise the string is not accepted
6.stop
PROGRAM:
#include<stdio.h>
#include<string.h>
char input[100];
int i,l;
void main()
{
printf("\n Recursive decent parsing\n");
printf("\n E->TE'\n E'->+TE'/ℇ\n T->FT'\n T'->*FT'/ℇ\n F->(E)/ID\n");
printf("\n Enter the string to be checked:");
scanf("%s",&input);
if(E( ))
{
if(input[i+1]=='\0')
printf("\n String is accepted");
else
printf("\n String is not accepted");
}
else
printf("\n String not accepted");
}
E( )
{
if(T( ))
{
if(EP( ))
return(1);
else
return(0);
}
else
return(0);
}
EP( )
{
if(input[i]=='+')
{
i++;
if(T( ))
{
if(EP( ))
return(1);
else
return(0);
}
else
return(0);
}
else
return(1);
}
T()
{
if(F())
{
if(TP())
return(1);
else
return(0);
}
else
return(0);
}
TP()
{
if(input[i]=='*')
{
i++;
if(F())
{
if(TP())
return(1);
else
return(0);
}
else
return(0);
}
else
return(1);
}
F()
{
if(input[i]=='(')
{
i++;
if(E())
{
if(input[i]==')')
{
i++;
return(1);
}
else
return(0);
}
else
return(0);
}
else if(input[i]>='a'&&input[i]<='z' || input[i]>='A'&&input[i]<='Z')
{
i++;
return(1);
}
else
return(0);
}
OUTPUT:
Recursive decent parsing
E->TE'
E'->+TE'/ℇ
T->FT'
T'->*FT'/ℇ
F->(E)/ID
Enter the string to be checked: (a+b)*(c+d)
String is accepted
Enter the string to be checked: b-c
String is not accepted
Write a C program to generate three address code.
AIM:A Program to generate intermediate code as a three address code
Hardware: Intel® CORE™ i3-3240 CPU@3.40GHZ
HDD:500 GB ,RAM:4GB
Software: OS: LINUX using putty,
C Compiler and LEX compiler
ALGORITHM:
1.start
2.get the expression from the user.the datatype of expression is string
3.each string is compared with an operator .if the operator is seen then the previous string and next string are concatnated and stored in a first temporary value and three address code is printed
4.if another operator is seen then the first temporary value is concatnated to the next string using the operator and the expression is printed
5.final temporary value is replaced in the left operand value
6.stop
PROGRAM:
#include<stdio.h>
#include<string.h>
int i=1,j=0,no=0,tmpch=90;
char str[100],left[15],right[15];
void findopr();
void explore();
void fleft(int);
void fright(int);
struct exp
{
int pos;
char op;
}k[15];
void main()
{
printf("\t\tTHREE ADDRESS CODE\n\n");
printf("Enter the Expression :");
scanf("%s",&str);
printf("The Three Address Code:\t\tExpression\n");
findopr();
explore();
}
void findopr()
{
for(i=0;str[i]!='\0';i++)
if(str[i]==':')
{
k[j].pos=i;
k[j++].op=':';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='/')
{
k[j].pos=i;
k[j++].op='/';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='*')
{
k[j].pos=i;
k[j++].op='*';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='+')
{
k[j].pos=i;
k[j++].op='+';
}
for(i=0;str[i]!='\0';i++)
if(str[i]=='-')
{
k[j].pos=i;
k[j++].op='-';
}
}
void explore()
{
i=1;
while(k[i].op!='\0')
{
fleft(k[i].pos);
fright(k[i].pos);
str[k[i].pos]=tmpch--;
printf("\t%c := %s%c%s\t\t",str[k[i].pos],left,k[i].op,right);
for(j=0;j<strlen(str);j++)
if(str[j]!='$')
printf("%c",str[j]);
printf("\n");
i++;
}
fright(-1);
if(no==0)
{
fleft(strlen(str));
printf("\t%s := %s",right,left);
}
printf("\t%s := %c",right,str[k[--i].pos]);
}
void fleft(int x)
{
int w=0,flag=0;
x--;
while(x!= -1 &&str[x]!= '+' &&str[x]!='*'&&str[x]!='='&&str[x]!='\0'&&str[x]!='-'&&str[x]!='/'&&str[x]!=':')
{
if(str[x]!='$'&& flag==0)
{
left[w++]=str[x];
left[w]='\0';
str[x]='$';
flag=1;
}
x--;
}
}
void fright(int x)
{
int w=0,flag=0;
x++;
while(x!= -1 && str[x]!= '+'&&str[x]!='*'&&str[x]!='\0'&&str[x]!='='&&str[x]!=':'&&str[x]!='-'&&str[x]!='/')
{
if(str[x]!='$'&& flag==0)
{
right[w++]=str[x];
right[w]='\0';
str[x]='$';
flag=1;
}
x++;
}
}
OUTPUT:
THREE ADDRESS CODE
Enter the Expression : a+b*c-d/a+b*c
The Three Address Code: Expression
a+b*c-d/a+b*c$
Z := b*c a+Z-d/a+b*c$
U := d/a a+Z-U +b*c$
Y := b*c a+Z-U+Y$
X := a+Z X-U+Y$
W := X-U W+Y$
S := W+Y S$
Implement SLR(1) parsing algorithm.
AIM: To implement Simple LR(1) parsing algorithm
Hardware: Intel® CORE™ i3-3240 CPU@3.40GHZ
HDD:500 GB ,RAM:4GB
Software: OS:LINUX using putty,
C Compiler and LEX compiler
ALGORITHM:
1.start
2.Include all the header files required for SLR program
3.write the procedure for non-terminal
4.read the token and write appropriate non-terminal for that token
5.follow the same procedure untill get the end of the string
6.after replacing the tokens with appropriate non-terminals
7.stop
PROGRAM:
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>
void main()
{
char table[20][20][20],ter[20],stack[20],ip[20],st1[20],pro[20][20],num;
int i,j,k,t,top=0,st,col,row,pop,np,no,len;
for(i=0;i<20;i++)
{
ter[i]=NULL;
stack[i]=NULL;
ip[i]=NULL;
st1[i]=NULL;
for(j=0;j<20;j++)
{
pro[i][j]=NULL;
for(k=0;k<20;k++)
{
table[i][j][k]=NULL;
}
}
}
printf("enter no. of productions:");
scanf("%d",&np);
printf("enter productions");
for(i=0;i<np;i++)
{
scanf("%s",&pro[i]);
}
printf("enter the no. of states:");
scanf("%d",&st);
printf("enter the states");
scanf("%s",&st1);
printf("enter the no. of terminals");
scanf("%d",&t);
printf("enter terminals:");
scanf("%s",&ter);
for(i=0;i<st;i++)
{
for(j=0;j<t;j++)
{
printf("\n enter thhe value for %c,%c:",st1[i],ter[j]);
scanf("%s",&table[i][j]);
}
}
printf("\n SLR table:");
for(i=0;i<t;i++)
{
printf("\t %c",ter[i]);
}
for(i=0;i<st;i++)
{
printf("\n\n%c",st1[i]);
for(j=0;j<t;j++)
{
printf("\t%s",table[i][j]);
}
}
stack[top]='a';
printf("\n enter the input string:");
scanf("%s",&ip);
i=0;
printf("\n\nstack\t\tinputstring\t\taction");
printf("\n%s\t\t%s\t\t",stack,ip);
while(i<=strlen(ip))
{
for(j=0;j<st;j++)
{
if(stack[top]==st1[j])
col=j;
}
for(j=0;j<t;j++)
{
if(ip[i]==ter[j])
{
row=j;
}
}
if((stack[top]=='b')&&(ip[i]=='$'))
{
printf("\nstring accepted");
break;
}
else if(table[col][row][0]=='s')
{
top++;
stack[top]=ter[row];
top++;
stack[top]=table[col][row][1];
i++;
printf("shift %c %d\n",ter[row],table[col][row][1]);
}
else if(table[col][row][0]=='r')
{
no=(int)table[col][row][1];
no=no-48;
len=strlen(pro[no]);
len=len-3;
pop=2*len;
printf("pop%d",pop);
for(j=0;j<pop;j++)
{
top=top-1;
}
top++;
stack[top]=pro[no][0];
k=top;k=k-1;
printf("push[%c",pro[no][0]);
for(j=0;j<st;j++)
{
if(stack[k]==st1[j])
{
col=j;
}
}
k++;
for(j=0;j<t;j++)
{
if(stack[k]==ter[j])
{
row=j;
}
}
stack[top]=table[col][row][0];
printf("%c]\n",table[col][row][0]);
}
else
{
printf("\n error\n string not accepted");
break;
}
printf("\n");
for(j=0;j<=top;j++)
{
printf("%c",stack[j]);
}
printf("\t\t");
for(j=i;j<strlen(ip);j++)
{
printf("%c",ip[j]);
}
printf("\t\t");
}
}
OUTPUT:
Menu
1. E
2. a + b
3. a.b
4. a
5. (a/b)*
Enter the option 2
Write a YACC program to parse the Strings
AIM: To write a C program to convert the BNF rules into YACC form
Hardware: Intel® CORE™ i3-3240 CPU@3.40GHZ
HDD:500 GB ,RAM:4GB
Software: OS:LINUX using putty,
C Compiler and LEX compiler
ALGORITHM:
1. Start the program.
2. Declare the declarations as a header file. {include}
3. Token digit
4. Define the translations rule like line,expr,term,factor. Line:exp\n{print\n%d\n,$1)} Expr:expr+term($$=$1=$3} Term:term+factor($$=$1*$3} Factor Factor(enter),{$$=$2) %%
5. Define the supporting C routines.
6. Execute and verify it. 7. Stop the program.
PROGRAM:
<int.l>
%{
#include"y.tab.h"
#include<stdio.h>
#include<string.h>
int LineNo=1;
%}
identifier [a-zA-Z][_a-zA-Z0-9]*
number [0-9]+|([0-9]*\.[0-9]+)
%%
main\(\) return MAIN;
if return IF;
else return ELSE;
while return WHILE;
int |
char |
float return TYPE;
{identifier} {strcpy(yylval.var,yytext);
return VAR;}
{number} {strcpy(yylval.var,yytext);
return NUM;}
\< |
\> |
\>= |
\<= |
== {strcpy(yylval.var,yytext);
return RELOP;}
[ \t] ;
\n LineNo++;
. return yytext[0];
%%
<int.y>
%{
#include<string.h>
#include<stdio.h>
struct quad
{
char op[5];
char arg1[10];
char arg2[10];
char result[10];
}QUAD[30];
struct stack
{
int items[100];
int top;
}stk;
int Index=0,tIndex=0,StNo,Ind,tInd;
extern int LineNo;
%}
%union
{
char var[10];
}
%token <var> NUM VAR RELOP
%token MAIN IF ELSE WHILE TYPE
%type <var> EXPR ASSIGNMENT CONDITION IFST ELSEST WHILELOOP
%left '-' '+'
%left '*' '/'
%%
PROGRAM : MAIN BLOCK
;
BLOCK: '{' CODE '}'
;
CODE: BLOCK
| STATEMENT CODE
| STATEMENT
;
STATEMENT: DESCT ';'
| ASSIGNMENT ';'
| CONDST
| WHILEST
;
DESCT: TYPE VARLIST
;
VARLIST: VAR ',' VARLIST
| VAR
;
ASSIGNMENT: VAR '=' EXPR{
strcpy(QUAD[Index].op,"=");
strcpy(QUAD[Index].arg1,$3);
strcpy(QUAD[Index].arg2,"");
strcpy(QUAD[Index].result,$1);
strcpy($$,QUAD[Index++].result);
}
;
EXPR: EXPR '+' EXPR {AddQuadruple("+",$1,$3,$$);}
| EXPR '-' EXPR {AddQuadruple("-",$1,$3,$$);}
| EXPR '*' EXPR {AddQuadruple("*",$1,$3,$$);}
| EXPR '/' EXPR {AddQuadruple("/",$1,$3,$$);}
| '-' EXPR {AddQuadruple("UMIN",$2,"",$$);}
| '(' EXPR ')' {strcpy($$,$2);}
| VAR
| NUM
;
CONDST: IFST{
Ind=pop();
sprintf(QUAD[Ind].result,"%d",Index);
Ind=pop();
sprintf(QUAD[Ind].result,"%d",Index);
}
| IFST ELSEST
;
IFST: IF '(' CONDITION ')' {
strcpy(QUAD[Index].op,"==");
strcpy(QUAD[Index].arg1,$3);
strcpy(QUAD[Index].arg2,"FALSE");
strcpy(QUAD[Index].result,"-1");
push(Index);
Index++;
}
BLOCK {
strcpy(QUAD[Index].op,"GOTO");
strcpy(QUAD[Index].arg1,"");
strcpy(QUAD[Index].arg2,"");
strcpy(QUAD[Index].result,"-1");
push(Index);
Index++;
};
ELSEST: ELSE{
tInd=pop();
Ind=pop();
push(tInd);
sprintf(QUAD[Ind].result,"%d",Index);
}
BLOCK{
Ind=pop();
sprintf(QUAD[Ind].result,"%d",Index);
};
CONDITION: VAR RELOP VAR {AddQuadruple($2,$1,$3,$$);
StNo=Index-1;
}
| VAR
| NUM
;
WHILEST: WHILELOOP{
Ind=pop();
sprintf(QUAD[Ind].result,"%d",StNo);
Ind=pop();
sprintf(QUAD[Ind].result,"%d",Index);
}
;
WHILELOOP: WHILE '(' CONDITION ')' {
strcpy(QUAD[Index].op,"==");
strcpy(QUAD[Index].arg1,$3);
strcpy(QUAD[Index].arg2,"FALSE");
strcpy(QUAD[Index].result,"-1");
push(Index);
Index++;
}
BLOCK {
strcpy(QUAD[Index].op,"GOTO");
strcpy(QUAD[Index].arg1,"");
strcpy(QUAD[Index].arg2,"");
strcpy(QUAD[Index].result,"-1");
push(Index);
Index++;
}
;
%%
extern FILE *yyin;
int main(int argc,char *argv[])
{
FILE *fp;
int i;
if(argc>1)
{
fp=fopen(argv[1],"r");
if(!fp)
{
printf("\n File not found");
exit(0);
}
yyin=fp;
}
yyparse();
printf("\n\n\t\t ----------------------------""\n\t\t Pos Operator Arg1 Arg2 Result" "\n\t\t
--------------------");
for(i=0;i<Index;i++)
{
printf("\n\t\t %d\t %s\t %s\t %s\t
%s",i,QUAD[i].op,QUAD[i].arg1,QUAD[i].arg2,QUAD[i].result);
}
printf("\n\t\t -----------------------");
printf("\n\n");
return 0;
}
void push(int data)
{
stk.top++;
Editor is loading...
Leave a Comment