System programming and compiler design laboratory
Subject Code: 06CSL68 I.A. Marks : 25
Hours/Week : 03 Exam Hours : 03
Total Hours : 42 Exam Marks : 50
PART - A
LEX and YACC Programs:
Execute the following programs using LEX:
1) a. Program to count the number of characters, words, spaces and lines in
a given input file.
b. Program to count the numbers of comment lines in a given C program.
Also eliminate them and copy the resulting program into separate file.
2) a. Program to recognize a valid arithmetic expression and to recognize the
identifiers and operators present. Print them separately.
b. Program to recognize whether a given sentence is simple or
compound.
3) Program to recognize and count the number of identifiers in a given
input file.
Execute the following programs using YACC:
4) a. Program to recognize a valid arithmetic expression that uses
operators +, -, *
and /.
b. Program to recognize a valid variable, which starts with a letter,
followed by any number of letters or digits.
5) a. Program to evaluate an arithmetic expression involving operators +,
-, * and /.
b. Program to recognize strings ‘aaab’, ‘abbb’, ‘ab’ and ‘a’ using the
grammar
(an
bn
, n>= 0).
6) Program to recognize the grammar (a
n
b, n>= 10).
PART B
Unix Programming:
1. a) Non-recursive shell script that accepts any number of arguments
and prints
them in the Reverse order, ( For example, if the script is named rargs,
then executing rargs A B C should produce C B A on the standard
output).
b) C program that creates a child process to read commands from the
standard input and execute them (a minimal implementation of a
shell – like program). You can assume that no arguments will be
passed to the commands to be executed.
2. a) Shell script that accepts two file names as arguments, checks if the
permissions for these files are identical and if the permissions are
identical, outputs the common permissions, otherwise outputs each file
name followed by its permissions.
b) C program to create a file with 16 bytes of arbitrary data from the
beginning
and another 16 bytes of arbitrary data from an offset of 48. Display
the file contents to demonstrate how the hole in file is handled.
3. a) Shell function that takes a valid directory names as an argument and
recursively
descends all the subdirectories, finds the maximum length of any file in
that hierarchy and writes this maximum value to the standard output.
b) C program that accepts valid file names as command line arguments
and for
each of the arguments, prints the type of the file ( Regular file,
Directory file, Character special file, Block special file, Symbolic
link etc.)
4. a) Shell script that accepts file names specified as arguments and
creates a shell
script that contains this file as well as the code to recreate these files.
Thus if the script generated by your script is executed, it would
recreate the original files(This is same as the “bundle” script described
by Brain W. Kernighan and Rob Pike in “ The Unix Programming
Environment”, Prentice – Hall India).
b) C program to do the following: Using fork( ) create a child process.
The child process prints its own process-id and id of its parent and then exits.
The parent process waits for its child to finish (by executing the wait(
)) and prints its own process-id and the id of its child process and
then exits.
Compiler Design:
5. Write a C program to implement the syntax-directed definition of “if E
then S1” and “if E then S1 else S2”. (Refer Fig. 8.23 in the text book
prescribed for 06CS62 Compiler Design, Alfred V Aho, Ravi Sethi,
Jeffrey D Ullman: Compilers- Principles, Techniques and Tools,
Addison-Wesley, 2007.)
6. Write a yacc program that accepts a regular expression as input and
produce its parse tree as output.
Instructions:
In the examination, a combination of one LEX and one YACC problem
has to be asked from Part A for a total of 25 marks and one programming
exercise from Part B has to be asked for a total of 25 marks.
Part A(LEX and YACC)
1a.Count characters, lines and words
%{
int s=0,w=0,l=1,c=0;
%}
%%
[\n]* { l+=yyleng;}
[ \t]* { s+=yyleng;}
[^ \n\t]*[\t] { w++;c+=yyleng-1;s++;}
[^ \n\t]*[ ] { w++;c+=yyleng-1;s++;}
[^ \n\t]*[\n] { w++;c+=yyleng-1;l++;}
[^ \n\t]* { w++;c+=yyleng;}
%%
main(int argc,char **argv)
{
if(argc!=2)
{
printf("\nIncorrect usage!!\n");
return 1;
}
yyin=fopen(*(argv+1),"r");
if(!yyin)
{
printf("\nCannot open the file!\n");
return 1;
}
yylex();
printf("\nChar=%d\nSpaces=%d\nWords=%d\nLines=%d\n",c,s,w,l);
}
1b.Comment Lines
int com=0;
%}
%%
\/\*[^*]*\*(\*|([^*/][^*]*\*))*\/ com++;
\/\/[^\n]*[\n] com++;
% fprintf(yyout,"%%");
.|[\n] fprintf(yyout,yytext);
%%
main(int argc,char **argv)
{
if(argc!=3)
{
printf("\nArguments passed in wrong manner\n");
return 1;
}
yyin=fopen(*(argv+1),"r");
yyout=fopen(*(argv+2),"w");
if(!(yyin&&yyout))
{
printf("\nSpecified file cannot be opened!");
return 1;
}
yylex();
printf("\nTotla number of comment lines=%d\n",com);
}
2a.Valid arithmetic expression
%{
#include<string.h>
int valid,i,j,k,temp,temp1,top=1,num[40];
char arr[40][10],st[80],op[40];
%}
%%
[a-zA-Z][a-zA-Z0-9]* {
strcpy(arr[j++],yytext);
if(st[top-1]=='i')
valid=1;
else if(st[top-1]=='o')
st[top-1]='i';
else
st[top++]='i';
}
[0-9]+ {
num[k++]=atoi(yytext);
if(st[top-1]=='i')
valid=1;
else if(st[top-1]=='o')
st[top-1]='i';
else
st[top++]='i';
}
[\-+/*%^&|] {
op[temp++]=yytext[0];
if(st[top-1]=='i')
st[top-1]='o';
else
valid=1;
}
"(" {
if(st[top-1]=='('||st[top-1]=='$'||st[top-1]=='o')
st[top++]='(';
else
valid=1;
}
")" {
if(st[top-1]=='(')
top--;
else if(st[top-1]=='i'&&st[top-2]=='(')
{
top-=2;
if(st[top-1]=='o')
st[top-1]='i';
else if(st[top-1]=='i')
valid=1;
else
st[top++]='i';
}
else
valid=1;
}
. valid=1;
\n return ;
%%
check()
{
if(!(temp|k|j))
return 0;
if(valid)
return 0;
if(top==2&&st[top-1]=='i')
top--;
if(top==1&&st[top-1]=='$')
top--;
if(top==0)
return 1;
return 0;
}
main()
{
st[top-1]='$';
printf("\nEnter the expression\n");
yylex();
if(check())
{
printf("\nValid expression!\n");
if(j>0)
printf("\nIdentifiers present are ");
for(i=0;i<j;i++)
printf("\n%s",arr[i]);
if(k>0)
printf("\nNumbers used are ");
for(i=0;i<k;i++)
printf("\n%d",num[i]);
if(temp>0)
printf("\nOperators present are ");
for(i=0;i<temp;i++)
printf("\n%c",op[i]);
}
else
printf("\nInvalid expression!\n");
}
2b.Simple or complex statement
%{
int valid;
%}
%%
[a-zA-Z][ ](and|but|if|then|else|nevertheless)[ ][a-zA-Z] { valid=1; }
.|[\n] ;
%%
main()
{
printf("\nEnter the text ");
yylex();
if(valid)
{
printf("\nStatement is compound!\n");
}
else
{
printf("\nStatement is simple!\n");
}
}
3.Identifiers(method1)
%{
char ch;
int id;
%}
%%
^[ \t]*(int|float|double|char) {
ch=input();
while(1)
{
if(ch==',')
id++;
else if(ch==';')
{
id++;
break;
}
ch=input();
}
}
.|[\n] ;
%%
int main(int argc,char **argv)
{
if(argc!=2)
{
printf("\nImproper usage!\n");
return 1;
}
yyin=fopen(*(argv+1),"r");
if(!yyin)
{
printf("\nSpecified file cannot be opened!\n");
return 1;
}
yylex();
printf("\nTotal identifiers is %d\n",id);
}
3.Identifiers(method2)
#include<ctype.h>
char ch,arr[20];
int id,i,j;
int test(char *);
%}
%%
^[ \t]*("int "|"float "|"double "|"char ")[ \t]* {
ch=input();
while(1)
{
if(ch=='\n'||ch==0)
break;
if(ch==','||ch==';')
{
arr[i]=0;
i=0;
j=test(arr);
if(j!=-1)
{
id+=j;
printf("\n%s is a %s",arr,j?"identifier":"nonidentifier");
}
if(ch==';')
break;
ch=input();
continue;
}
arr[i++]=ch;
ch=input();
}
}
.|[\n] ;
%%
yywrap()
{
return 1;
}
int rno(char *a,int state)
{
if(*a=='='&&state==0&&!(*a=0))
return 1;
if(isdigit(*a)&&state==1)
state=1;
if(*a==']'&&state==1)
state=0;
if(*a==0&&state==0)
return 1;
if(*a=='['&&state==0)
state=1;
a++;
return rno(a,state);
}
int test(char *a)
{
char *b=a;
int i;
while(*b==' ')
b++;
if(!isalpha(*b))
return 0;
while(*b!=0)
{
if(*b=='='&&!(*b=0))
return 1;
if(*b=='[')
{
i=rno(b++,1);
b--;
if(i==1)
*b=0;
return i;
}
if(!isalnum(*b))
return 0;
b++;
}
return 1;
}
int main(int argc,char **argv)
{
if(argc!=2)
{
printf("\nImproper usage!\n");
return 1;
}
yyin=fopen(*(argv+1),"r");
if(!yyin)
{
printf("\nSpecified file cannot be opened!\n");
return 1;
}
yylex();
printf("\nTotal identifiers is %d\n",id);
}
4a.Valid arithmetic expression(method 1)
LEX part
%{
#include "y.tab.h"
%}
%%
[a-zA-Z_][a-zA-Z_0-9]* return id;
[0-9]+(\.[0-9]*)? return num;
[+/*] return op;
. return yytext[0];
\n return 0;
%%
YACC part
%{
#include<stdio.h>
int valid=1;
%}
%token num id op
%%
start : id '=' s ';'
s : id x
| num x
| '-' num x
| '(' s ')' x
;
x : op s
| '-' s
|
;
%%
int yyerror()
{
valid=0;
printf("\nInvalid expression!\n");
return 0;
}
int main()
{
printf("\nEnter the expression:\n");
yyparse();
if(valid)
{
printf("\nValid expression!\n");
}
}
4a.Valid arithmetic expression(method 2)
LEX part
%{
#include "y.tab.h"
%}
%%
[a-zA-Z_][a-zA-Z_0-9]* return id;
[0-9]+(\.[0-9]*)? return num;
[+/*] return op;
. return yytext[0];
\n return 0;
%%
YACC part
%{
#include<stdio.h>
int valid=1;
%}
%token num id op
%left '-' op
%%
start : id y '=' s ';'
y : op
| '-'
|
;
s : x op x
| x '-' x
| '(' s ')'
| x
;
x : id
| '-' num
| num
;
%%
int yyerror()
{
valid=0;
printf("\nInvalid expression!\n");
return 0;
}
int main()
{
printf("\nEnter the expression:\n");
yyparse();
if(valid)
{
printf("\nValid expression!\n");
}
}
4b.Valid variable
LEX part
%{
#include "y.tab.h"
%}
%%
[a-zA-Z] return letter;
[0-9] return digit;
. return yytext[0];
\n return 0;
%%
YACC part
%{
#include<stdio.h>
int valid=1;
%}
%token digit letter
%%
start : letter s
s : letter s
| digit s
|
;
%%
int yyerror()
{
printf("\nIts not a identifier!\n");
valid=0;
return 0;
}
int main()
{
printf("\nEnter a name to tested for identifier ");
yyparse();
if(valid)
{
printf("\nIt is a identifier!\n");
}
}
5a.Evaluate valid arithmetic expression
LEX part
%{
#include "y.tab.h"
int extern yylval;
%}
%%
[0-9]+ { yylval=atoi(yytext); return num; }
. return yytext[0];
\n return 0;
%%
YACC part
%
#include<stdio.h>
int valid=0,temp;
%}
%token num
%left '+''-'
%left '*''/'
%nonassoc UMINUS
%%
expr1 : expr { temp=$1; }
expr: expr '+' expr { $$=$1+$3; }
| expr '-' expr { $$=$1-$3; }
| expr '*' expr { $$=$1*$3; }
| expr '/' expr { if($3==0) { valid=1; $$=0; } else { $$=$1/$3; } }
| '(' expr ')' { $$=$2; }
| '-' expr { $$=-1*$2; }
| num { $$=yylval; }
;
%%
int yyerror()
{
printf("\nInvalid expression!\n");
valid=2;
return 0;
}
int main()
{
printf("\nEnter the expression to be evaluated\n");
yyparse();
if(valid==1)
{
printf("\nDivision by 0!\n");
}
if(valid==0)
{
printf("\nValid expression!\n");
printf("The value evaluated is %d\n",temp);
}
}
5b.Language a^nb^n(n>=0)
LEX part
%{
#include "y.tab.h"
%}
%%
a return A;
b return B;
.|[\n] return 0;
%%
YACC part
%{
#include<stdio.h>
int valid=1;
%}
%token A B
%%
start : A start B
|
;
%%
int yyerror()
{
valid=0;
printf("\nPattern not matched!\n");
return 0;
}
int main()
{
printf("\nEnter the pattern ");
yyparse();
if(valid)
{
printf("\nValid pattern!\n");
}
}
6.Language of type a^nb(n>=10)
LEX part
%{
#include "y.tab.h"
%}
%%
a return A;
b return B;
.|[\n] return 0;
%%
YACC part
%{
#include<stdio.h>
int valid=1;
%}
%token A B
%%
start : A A A A A A A A A A s B
s : A s
|
;
%%
int yyerror()
{
valid=0;
printf("\nPattern not matched!\n");
return 0;
}
int main()
{
printf("\nEnter the pattern ");
yyparse();
if(valid)
{
printf("\nValid pattern!\n");
}
}
Part B(Unix Programming)
1a.Non recursively print the arguments in reverse order
while [ $temp –ge 1 ]
do
eval echo \$$temp
temp = `expr $temp – 1`
done
1b.Child process to read commands
#include<sys/types.h>
main()
{
int pid;
char cmd[15];
pid=fork();
if(pid<0)
{
printf(“Fork Error!…\n” );
exit(0);
}
else if(pid==0)
{
printf(“\nEnter the Command:” );
scanf(“%s”, cmd);
system(cmd);
exit(0);
}
}
2a.File permissions
temp2=`ls –l $2 | cut –c 1-10`
if [ $temp1 = $temp2 ] then
echo “The files have common Permissions”
echo $temp1
else
echo “The permission for $1 is:”
echo $temp1
echo “The permission for $2 is:”
echo $temp2
fi
2b.Hole in the file
#include<sys/stat.h>
#include<unistd.h>
char buf1[] = “abcdefghijklmnop” ;
char buf2[] = “ABCDEFGHIJKLMNOP” ;
int main( )
{
int fd;
fd=create(“file.dat”,0);
write(fd,buf1,16);
lseek(fd, 48,SEEK_SET);
write(fd, buf2,16);
system(“od -c file.dat” );
exit(0);
}
3a.Maximum length
#ls –lR $1 | grep –v ^d | sort –nrk5 | head -n 1 > file1
string = `cut –d “ ” –f9 file1`
length=`cut –d “ ” –f5 file1`
echo “The Maximum length file,$string is: $string:”
3b.Type of file
#include<stdlib.h>
#include<sys/types.h>
#include<sys/stat.h>
main(int argc, char *argv[])
{
struct stat st;
int i;
for(i=1;i<argc;i++)
{
if(lstat(argv[i],&st))
{
printf("%s does not exist!",argv[i]);
continue;
}
printf("%s is a ",argv[i]);
switch(st.st_mode&S_IFMT)
{
case S_IFDIR: printf("directory file\n");
break;
case S_IFCHR: printf("character device file\n");
break;
case S_IFBLK: printf("block device file\n");
break;
case S_IFREG: printf("regular file\n");
break;
case S_IFLNK: printf("symbollic link file\n");
break;
case S_IFIFO: printf("FIFO file\n");
}
}
}
4a.Bundle script
for i
do
echo “echo $i 1>&2”
echo “cat > $i <<`end of $i`”
cat $i
echo “end of $i”
done
4b.Pids of child and parent
#include<sys/types.h>
int main()
{
int status, ppid, mpid, pid;
pid=fork();
if(pid<0)
{
printf(“Error in forking a child!…” );
}
if(pid = = 0)
{
ppid=getppid();
printf(“\n Iam Child Executing … and My Parent ID is: %d”,ppid);
mpid=getpid();
printf(“\n My own ID: %d”, mpid);
kill();
exit(0);
}
pid=waitpid(pid,&status, 0)
mpid=getpid();
printf(“\n Iam parent with ID:%d\n My child with ID: %d\n”, mpid, pid);
}
Part B(Compiler Design)
5.SDD(method 1)
#include<stdlib.h>
#include<string.h>
intr parsecondition(char[],int,char*,int);
void gen(char[],char[],char[],int);
int main()
{
int counter=0,stlen=0,elseflag=0;
char stmt[60];
char strB[54];
char strS1[50];
char strS2[45];
printf("format of 'if' statement\n example..\n");
printf("if(a<b) then(s=a);\n");
printf("if(a<b)then(s=a)else(s=b);\n\n");
printf("enter the statement\n");
scanf("%[^\n]",stmt);
stlen=strlen(stmt);
counter=counter+2;
counter=parsecondition(stmt,counter,strB,stlen);
if(stmt[counter]==')')
counter++;
counter=counter+3;
counter=parsecondition(stmt,counter,strS1,stlen);
if(stmt[counter+1]==';')
{
printf("\n parsing the input statement");
gen(strB,strS1,strS2,elseflag);
return 0;
}
if(stmt[counter]==')')
counter++;
counter=counter+3;
counter=parsecondition(stmt,counter,strS2,stlen);
counter=counter+2;
if(counter==stlen)
{
elseflag=1;
printf("\n parsing the input statement");
gen(strB,strS1,strS2,elseflag);
return 0;
}
return 0;
}
int parsecondition(char input[],int cntr,char* dest,int totallen)
{
int index=0,pos=0;
while(input[cntr]!='(' && cntr<=totallen)
cntr++;
if(cntr>=totallen)
return 0;
index=cntr;
while(input[cntr]!=')')
cntr++;
if(cntr>=totallen)
return 0;
while(index<=cntr)
dest[pos++]=input[index++];
dest[pos]='\0';
return cntr;
}
void gen(char B[],char S1[],char S2[],int elsepart)
{
int Bt=101,Bf=102,Sn=103;
printf("\n\t if %s goto%d",B,Bt);
printf("\n\tgoto %d",Bf);
printf("\n %d",Bt);
printf("%s",S1);
if(!elsepart)
printf("\n%d",Bf);
else
{
printf("\n\t goto %d",Sn);
printf("\n %d:%s",Bf,S2);
printf("\n%d",Sn);
}
}
5.SDD(method 2)
#include<stdlib.h>
exitstatus()
{
printf("\nInvalid statement!");
exit(0);
}
main()
{
char arr[50],arr1[25],arr2[25],marr[25];
int cntr,i;
printf("\nEnter the expression ");
scanf("%s",arr);
if(arr[0]=='i'&&arr[1]=='f'&&arr[2]=='(')
{
cntr=3;
i=0;
while(arr[cntr]!=')')
marr[i++]=arr[cntr++];
cntr++;
marr[i]=0;
}
else
exitstatus();
if(arr[cntr]=='t'&&arr[cntr+1]=='h'&&arr[cntr+2]=='e'&&arr[cntr+3]=='n'&&arr[cntr+4]=='(')
{
cntr+=5;
i=0;
while(arr[cntr]!=')')
arr1[i++]=arr[cntr++];
cntr++;
arr1[i]=0;
if(arr[cntr]==';'&&arr[cntr+1]==0)
printf("59:if(%s) goto 60 \ngoto 61\n60:(%s)",marr,arr1);
else if(arr[cntr]=='e'&&arr[cntr+1]=='l'&&arr[cntr+2]=='s'&&arr[cntr+3]=='e'&&arr[cntr+4]=='(')
{
cntr+=5;
i=0;
while(arr[cntr]!=')')
arr2[i++]=arr[cntr++];
cntr++;
arr2[i]=0;
if(arr[cntr]==';'&&arr[cntr+1]==0)
printf("59:if(%s) goto 60 \ngoto 62\n60:(%s) goto 62\n61:(%s)\n62:",marr,arr1,arr2);
else
exitstatus();
}
else
exitstatus();
}
else
exitstatus();
}
6.Parse tree
#include<ctype.h>
char str[20];
int i=0;
%}
%token id
%left '+''/''*''-'
%%
E:S {infix_postfix(str);}
S:S'+'T|S'-'T
|T
T:T'*'F|T'/'F
|F
F:id|'('S')'
;
%%
#include<stdio.h>
main()
{
printf("\n Enter an identifier:");
yyparse();
}
yyerror()
{
printf("invalid");
}
yylex()
{
char ch=' ';
while(ch!='\n')
{
ch=getchar();
str[i++]=ch;
if(isalpha(ch)) return id;
if(ch=='+'||ch=='*'||ch=='-'||ch=='/') return ch;
}
str[--i]='\0';
return(0);
exit(0);
}
void push(char stack[],int *top,char ch)
{
stack[++(*top)]=ch;
}
char pop(char stack[],int *top)
{
return(stack[(*top)--]);
}
int prec(char ch)
{
switch(ch)
{
case '/':
case '*':return 2;
case '+':
case '-':return 1;
case '(':return 0;
default:return -1;
}
}
void infix_postfix(char infix[])
{
int top=-1,iptr=-1,pptr=-1;
char postfix[20],stack[20],stksymb,cursymb;
push(stack,&top,'\0');
while((cursymb=infix[++iptr])!='\0')
{
switch(cursymb)
{
case '(':push(stack,&top,cursymb);
break;
case ')':stksymb=pop(stack,&top);
while(stksymb!='(')
{
postfix[++pptr]=stksymb;
stksymb=pop(stack,&top);
}
break;
case '*':
case '/':
case '+':
case '-':while(prec(stack[top])>=prec(cursymb))
postfix[++pptr]=pop(stack,&top);
push(stack,&top,cursymb);
break;
default:if(isalnum(cursymb)==0)
{
printf("Error in input!");
exit(0);
}
postfix[++pptr]=cursymb;
}
}
while(top!=-1)
postfix[++pptr]=pop(stack,&top);
printf("%s\n",postfix);
}
Note: This is DFA for program 1b
\/\*[^*]\*(\*||([^*\][^*]*\*))*\/