Experiments
/*Experiment 1. Design a Lexical analyzer for the given language. The lexical analyzer should ignore redundant spaces, tabs and new lines. It should also ignore comments. Although the syntax specification states that identifiers can be arbitrarily long, you may restrict the length to some reasonable value.*/
#include(stdio.h>
#include(ctype.h>
#include(string.h>
void keyw(char *p);
int i = 0, id = 0, kw = 0, num = 0, op = 0;
char keys[32][10] = {"auto", "break", "case", "char", "const", "continue", "default", "do", "double", "else", "enum", "extern", "float", "for", "goto", "if", "int", "long", "register", "return", "short", "signed", "sizeof", "static", "struct", "switch", "typedef", "union", "unsigned", "void", "volatile", "while"};
void main() {
char ch, str[25], seps[15] = " \t\n,;(){}[]#\"<>", oper[] = "!%^&*-+=~|.<>/?";
int j;
FILE *f1;
f1 = fopen("E:/SCET/CDCF/LAB/cd1.txt", "r");
if (f1 == NULL) {
printf("Error opening file.\n");
return;
}
while ((ch = fgetc(f1)) != EOF) {
for (j = 0; j <= 14; j++) {
if (ch == oper[j]) {
printf("%c is an operator\n", ch);
op++;
str[i] = '\0';
keyw(str);
}
}
for (j = 0; j <= 14; j++) {
if (i == -1)
break;
if (ch == seps[j]) {
if (ch == '#') {
while ((ch = fgetc(f1)) != '>' && ch != EOF) {
printf("%c", ch);
}
printf("%c is a header file\n", ch);
i = -1;
break;
} else if (ch == '"') {
do {
ch = fgetc(f1);
printf("%c", ch);
} while (ch != '"' && ch != EOF);
printf("\b is a literal\n");
i = -1;
break;
}
str[i] = '\0';
keyw(str);
}
}
if (i != -1) {
str[i] = ch;
i++;
} else {
i = 0;
}
}
fclose(f1); // Close the file
printf("Keywords: %d\nIdentifiers: %d\nOperators: %d\nNumbers: %d\n", kw, id, op, num);
}
void keyw(char *p) {
int k, flag = 0;
for (k = 0; k <= 31; k++) {
if (strcmp(keys[k], p) == 0) {
printf("%s is a keyword\n", p);
kw++;
flag = 1;
break;
}
}
if (flag == 0) {
if (isdigit(p[0])) {
printf("%s is a number\n", p);
num++;
} else {
if (p[0] != '\0') {
printf("%s is an identifier\n", p);
id++;
}
}
}
i = -1;
}
/* 2. Implement the lexical analyzer using JLex, flex or lex or other lexical analyzer generating stools.*/
%{
#include(stdio.h>
%}
delim [\\t]
ws {delim}+
letter [A-Za-z]
digit [0-9]
id {letter}({letter}|{digit})*
num {digit}+(\\.{digit}+)?(E[+|-]?{digit}+)?
%%
{ws} { printf("no action\\n"); }
if|else|then { printf("%s is a keyword\\n", yytext); }
{id} { printf("%s is an identifier\\n", yytext); }
{num} { printf("it is a number\\n"); }
"<" { printf("it is a relational operator less than\\n"); }
"<=" { printf("it is a relational operator less than or equal\\n"); }
">" { printf("it is a relational operator greater than\\n"); }
">=" { printf("it is a relational operator greater than or equal\\n"); }
"==" { printf("it is a relational operator equal\\n"); }
"<>" { printf("it is a relational operator not equal\\n"); }
%%
int main() {
yylex();
return 0;
}
int yywrap() {
return 1;
}
/*3. Design Predictive parser for the given language.*/
#include(stdio.h>
#include(conio.h>
#include(string.h>
char prol[7][10] = {"S", "A", "A", "B", "B", "C", "C"};
char pror[7][10] = {"Aa", "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] = {"$", "$", "$", "a$", "b$", "c$", "d$"};
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;
default: return -1;
}
}
void main() {
int i, j, k;
//clrscr();
// Initialize the table
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 < k; 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("%s\t", table[i][j]);
if (j == 5)
printf("\n--------------------------------------------\n");
}
}
getch();
}
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-->@
---------------------------------------------------
C C-->Cc C--> C-->
---------------------------------------------------
//Experiment:4 Design LALR bottom-up parser for the given language.
1st we need to reate a lexer program with the exetnstion of .l file
lexer.l
Program
%{
#include(stdio.h>
#include "y.tab.h"
%}
%%
[0-9]+ { yylval.dval = atof(yytext); return DIGIT; }
\n { return yytext[0]; }
. { return yytext[0]; }
%%
2nd we need to reate a parser program with the exetnstion of .y file
parser.y
Program
%{
#include(stdio.h>
int yylex(void);
void yyerror(char *s);
%}
%union
{
double dval;
}
%token (dval> DIGIT
%type (dval> expr
%type (dval> term
%type (dval> factor
%%
line: expr '\n' {
printf("%g\n",$1);
}
;
expr: expr '+' term {
$$ = $1 + $3;
}
| term
;
term: term '*' factor {
$$ = $1 * $3;
}
| factor
;
factor: '(' expr ')' {
$$ = $2;
}
| DIGIT
;
%%
int main()
{
yyparse();
}
void yyerror(char *s)
{
printf("%s",s);
}
Sample Output
$lex parser.l
$yacc –d parser.y
$cc lex.yy.c y.tab.c –ll –lm
$./a.out
6+3
It Gives 9
// 5.Convert the BNF rules into Yacc form and write code to generate abstract syntax tree
// lex file
%{
#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];
%%
Parser part parser.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 NUM VAR RELOP
%token MAIN IF ELSE WHILE TYPE
%type 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 \tArg1 \tArg2 \tResult" "\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++;
if(stk.top==100)
{
printf("\n Stack overflow\n");
exit(0);
}
stk.items[stk.top]=data;
}
int pop()
{
int data;
if(stk.top==-1)
{
printf("\n Stack underflow\n");
exit(0);
}
data=stk.items[stk.top--];
return data;
}
void AddQuadruple(char op[5],char arg1[10],char arg2[10],char result[10])
{
strcpy(QUAD[Index].op,op);
strcpy(QUAD[Index].arg1,arg1);
strcpy(QUAD[Index].arg2,arg2);
sprintf(QUAD[Index].result,"t%d",tIndex++);
strcpy(result,QUAD[Index++].result);
}
yyerror()
{
printf("\n Error on line no:%d",LineNo);
}
Creata another c File test.c and place the below content in the file
main()
{
int a,b,c;
if(ab)
{
a=a+b;
}
if(a<=b)
{
c=a-b;
}
else
{
c=a+b;
}
}
Steps to Execute
Step1: lex lexer2.l
Step2: yacc -v -d parser.y
Step3: gcc lex.yy.c y.tab.c -ll -lm -w
Step4: ./a.out test.c
Finally it display the its out put as table
Experiment - 6
Write program to generate machine code from the abstract syntax tree generated by the parser.
#include(stdio.h>
#include(stdlib.h>
#include(string.h>
int label[20];
int no=0;
int main()
{
FILE *fp1,*fp2;
char fname[10],op[10],ch;
char operand1[8],operand2[8],result[8];
int i=0,j=0;
printf("\n Enter filename of the intermediate code");
scanf("%s",fname);
fp1=fopen(fname,"r");
fp2=fopen("target.txt","w");
if(fp1==NULL || fp2==NULL)
{
printf("\n Error opening the file");
exit(0);
}
while(!feof(fp1))
{
fprintf(fp2,"\n");
fscanf(fp1,"%s",op);
i++;
if(check_label(i))
fprintf(fp2,"\nlabel#%d",i);
if(strcmp(op,"print")==0)
{
fscanf(fp1,"%s",result);
fprintf(fp2,"\n\t OUT %s",result);
}
if(strcmp(op,"goto")==0)
{
fscanf(fp1,"%s %s",operand1,operand2);
fprintf(fp2,"\n\t JMP %s,label#%s",operand1,operand2);
label[no++]=atoi(operand2);
}
if(strcmp(op,"[]=")==0)
{
fscanf(fp1,"%s %s %s",operand1,operand2,result);
fprintf(fp2,"\n\t STORE %s[%s],%s",operand1,operand2,result);
}
if(strcmp(op,"uminus")==0)
{
fscanf(fp1,"%s %s",operand1,result);
fprintf(fp2,"\n\t LOAD -%s,R1",operand1);
fprintf(fp2,"\n\t STORE R1,%s",result);
}
switch(op[0])
{
case '*': fscanf(fp1,"%s %s %s",operand1,operand2,result);
fprintf(fp2,"\n \t LOAD",operand1);
fprintf(fp2,"\n \t LOAD %s,R1",operand2);
fprintf(fp2,"\n \t MUL R1,R0");
fprintf(fp2,"\n \t STORE R0,%s",result);
break;
case '+': fscanf(fp1,"%s %s %s",operand1,operand2,result);
fprintf(fp2,"\n \t LOAD %s,R0",operand1);
fprintf(fp2,"\n \t LOAD %s,R1",operand2);
fprintf(fp2,"\n \t ADD R1,R0");
fprintf(fp2,"\n \t STORE R0,%s",result);
break;
case '-': fscanf(fp1,"%s %s %s",operand1,operand2,result);
fprintf(fp2,"\n \t LOAD %s,R0",operand1);
fprintf(fp2,"\n \t LOAD %s,R1",operand2);
fprintf(fp2,"\n \t SUB R1,R0");
fprintf(fp2,"\n \t STORE R0,%s",result);
break;
case '/': fscanf(fp1,"%s %s %s",operand1,operand2,result);
fprintf(fp2,"\n \t LOAD %s,R0",operand1);
fprintf(fp2,"\n \t LOAD %s,R1",operand2);
fprintf(fp2,"\n \t DIV R1,R0");
fprintf(fp2,"\n \t STORE R0,%s",result);
break;
case '%': fscanf(fp1,"%s %s %s",operand1,operand2,result);
fprintf(fp2,"\n \t LOAD %s,R0",operand1);
fprintf(fp2,"\n \t LOAD %s,R1",operand2);
fprintf(fp2,"\n \t DIV R1,R0");
fprintf(fp2,"\n \t STORE R0,%s",result);
break;
case '=': fscanf(fp1,"%s %s",operand1,result);
fprintf(fp2,"\n\t STORE %s %s",operand1,result);
break;
case '>': j++;
fscanf(fp1,"%s %s %s",operand1,operand2,result);
fprintf(fp2,"\n \t LOAD %s,R0",operand1);
fprintf(fp2,"\n\t JGT %s,label#%s",operand2,result);
label[no++]=atoi(result);
break;
case '<': fscanf(fp1,"%s %s %s",operand1,operand2,result);
fprintf(fp2,"\n \t LOAD %s,R0",operand1);
fprintf(fp2,"\n\t JLT %s, label#%d",operand2,result);
label[no++]=atoi(result);
break;
} }
fclose(fp2); fclose(fp1);
fp2=fopen("target.txt","r");
if(fp2==NULL)
{
printf("Error opening the file\n");
exit(0);
}
do
{
ch=fgetc(fp2);
printf("%c",ch);
}while(ch!=EOF);
fclose(fp1);
return 0;
}
int check_label(int k)
{
int i;
for(i=0;i(no ; i++)
{
if(k==label[i])
return 1;
}
return 0;
}
while ((ch = fgetc(f1)) != EOF) {
for (j = 0; j <= 14; j++) {
if (ch == oper[j]) {
printf("%c is an operator\\n", ch);
op++;
str[i] = '\\0';
keyw(str);
}
}
}
while ((ch = fgetc(f1)) != EOF) {
for (j = 0; j <= 14; j++) {
if (ch == oper[j]) {
printf("%c is an operator\\n", ch);
op++;
str[i] = '\\0';
keyw(str);
}
}
}