PANIMALAR ENGINEERING COLLEGE

DEPARTMENT OF CSE
Reg No: 211422104XXX

EXP NO :01

DATE:

IMPLEMENTATION OF SYMBOL TABLE

AIM:

To implement a symbol table for efficient storage and retrieval of

identifiers, their attributes, and scope information in a compiler or
interpreter.

ALGORITHM:

Step 1: Initialize an empty data structure (hash table, tree, or list) for the
symbol table.
Step 2: Insert identifiers with attributes (name, type, scope) when
encountered in the source code.
Step 3: Search for an identifier when referenced to retrieve its attributes.
Step 4: Update attributes if the identifier's properties change.
Step 5: Delete identifiers when they go out of scope.
Step 6: Handle collisions if using a hash table (e.g., chaining or open
addressing).
Step 7: Display the symbol table for debugging or semantic analysis.
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

PROGRAM:

#include<stdio.h>

#include<conio.h>

#include<string.h>

struct sym

int pos;

char n[20],typ[20];

int allst;

int addr;

}s[20];

int main()

int i=0,p=0,n,j,k;

char input[20],typ[20];

char dt[5][20]={"int","char","float","long","double"};

FILE *fp;

clrscr();

fp=fopen("H:\\input.txt","r");

fscanf(fp,"%s",input);

while(strcmp(input,"EOF")!=0)

for(j=0;j<5;j++)
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

if(strcmp(input,dt[j])==0)

strcpy(typ,input);

fscanf(fp,"%s",input);

while(strcmp(input,";")!=0)

if(strcmp(input,",")!=0)

p++;

s[p].pos=++i;

strcpy(s[p].n,input);

strcpy(s[p].typ,typ);

fscanf(fp,"%s",input);

if(strcmp(input,";")!=0)

fscanf(fp,"%s",input);

fscanf(fp,"%s",input);

n=i+1;
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

s[0].allst=0;

s[0].addr=1000;

for(k=1;k<n;k++)

s[k].addr=s[k-1].addr+s[k-1].allst;

if(strcmp(s[k].typ,"int")==0)

s[k].allst=2;

else if((strcmp(s[k].typ,"float")==0)||(strcmp(s[k].typ,"double")==0))

s[k].allst=4;

else if(strcmp(s[k].typ,"char")==0)

s[k].allst=1;

else if(strcmp(s[k].typ,"long")==0)

s[k].allst=8;

printf("\n\t\t\tSymbol Table");

printf("\nPosition\tName\tType\tAllocatedStorage\tAddress");

for(k=1;k<n;k++)

printf("\n%d\t\t%s\t%s\t\t%d\t\t
%d",s[k].pos,s[k].n,s[k].typ,s[k].allst,s[k].addr);

getch();

return 0;

}
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

OUTPUT:

INPUT.txt:

void main ()

int a , d ;

float b ;

c = a + b;

EOF

RESULT:
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

EXP NO: 02

DATE:

DEVELOPING A LEXICAL ANALYZER

AIM:

To develop a lexical analyzer that reads source code, breaks it into

tokens, and identifies lexical errors, serving as the first phase of a
compiler or interpreter.

ALGORITHM:

Step 1: Read the source code character by character.

Step 2: Ignore whitespace, comments, and unnecessary delimiters.
Step 3: Identify lexemes and classify them into tokens (keywords,
identifiers, operators, literals, etc.).
Step 4: Store tokens in a symbol table if necessary.
Step 5: Handle errors like invalid identifiers or unrecognized symbols.
Step 6: Return tokens to the parser for further processing.
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

PROGRAM:

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<conio.h>

#include<ctype.h>

int isKey(char buffer[])

char key[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"};

int i,flag=0;

for(i=0;i<32;i++)

if(strcmp(key[i],buffer)==0)

flag=1;

break;

return flag;

}
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

void main()

char ch,buffer[15],op[]="+-**/%=";

char key[32][10];

FILE *fp;

int i,j=0,k,m=0,f;

clrscr();

strcpy(key[0],"\0");

fp=fopen("H:\\input.txt","r");

if(fp==NULL)

printf("Error while opening\n");

exit(1);

while((ch=fgetc(fp))!=EOF)

for(i=0;i<6;i++)

if(ch== op[i])

printf("%c is operator\n",ch);

if(isalnum(ch))

buffer[j++]=ch;
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

else if((ch==' '||ch=='\n')&&(j!=0))

buffer[j]='\0';

j=0;

f=1;

strcpy(key[m++],buffer);

for(k=0;k<m-1;k++)

if(strcmp(buffer,key[k])==0)

f=0;

if(f==1)

if(isKey(buffer)==1)

printf("%s is keyword \n",buffer);

else

printf("%s is identifier\n",buffer);

fclose(fp);

}
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

OUTPUT:

RESULT:
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

EXP NO: 03(a)

DATE:

IDENTIFY THE CAPITAL LETTERS USING LEXICAL ANALYZER

GENERATING TOOLS

AIM:

To use lexical analyzer generating tools (such as Lex) to identify and

extract capital letters from an input stream.

ALGORITHM:

Step 1: Define lexical rules to recognize capital letters (A-Z).

Step 2: Use a lexical analyzer generator (e.g., Lex) to create the lexer.
Step 3: Provide an input string to the lexer.
Step 4: Scan each character and match it against the defined rules.
Step 5: Extract and output the identified capital letters.
Step 6: Handle errors or invalid inputs if necessary.
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

PROGRAM:

%{

%}

%%

[A-Z] {printf(“%s”,yytext);}

.;

%%

main()

{printf(“Enter Some string”);

yylex();

int yywrap()

{return 1;

OUTPUT:

Enter Some string

Panimalar Engineering College

PEC

RESULT:
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

EXP NO: 03(b)

DATE:

PROGRAM TO COUNT THE NUMBER OF VOWELS AND

CONSONENTS IN THE GIVEN STRING

AIM:

To develop a lexical analyzer using lexical analyzer generating tools

(such as Lex) to count the number of vowels and consonants in a given
string.

ALGORITHM:

Step 1: Define patterns for vowels ([AEIOUaeiou]) and consonants ([a-

zA-Z] excluding vowels) in Lex.
Step 2: Initialize counters for vowels and consonants.
Step 3: Read input string character by character.
Step 4:If a character matches the vowel pattern, increment vowel_count.

If a character matches the consonant pattern, increment

consonant_count.
Step 5: Ignore non-alphabetic characters.
Step 6: Print the total count of vowels and consonants after processing
the input.
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

PROGRAM:

%{

#include<stdio.h>

int v=0;

int c=0;

%}

%%

\n return 0;

[aeiouAEIOU] { ++v; }

[^aeiouAEIOU] { ++c; }

%%

int yywrap()

return 1;

main ()

printf("Enter the string : ");

yylex();

printf("No. of Vowels = %d \n No. of Consonants=%d", v,c);

}
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

OUTPUT:

Enter the string : Computer

No. of Vowels =3

No. of consonants=5

RESULT:
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

EXP NO: 03(c)

DATE:

PROGRAM TO COUNT THE NUMBER OF VOWELS,WORD

SPACE,END OF LINE IN A GIVEN INPUT FILE

AIM:

To develop a program that reads an input file and counts the number of
vowels, word spaces, and end-of-line characters.

ALGORITHM:

Step 1: Start.
Step 2: Open the input file in read mode.
Step 3: Initialize vowel_count, space_count, and newline_count to zero.
Step 4: Read the file character by character until the end of the file is
reached.
Step 5: Check each character:

 If it is a vowel (A, E, I, O, U, a, e, i, o, u), increment vowel_count.

 If it is a space (' '), increment space_count.

 If it is a newline ('\n'), increment newline_count.

Step 6: Close the file after reading all characters.
Step 7: Print the total count of vowels, spaces, and end-of-line
characters.
Step 8: End.
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

PROGRAM:

%{

#include<stdio.h>

int lines=0, words=0,s_letters=0,c_letters=0, num=0, spl_char=0,total=0;

%}

%%

\n { lines++; words++;}

[\t ' '] words++;

[A-Z] c_letters++;

[a-z] s_letters++;

[0-9] num++;

. spl_char++;

%%

main(void)

yyin= fopen("myfile.txt","r");

yylex();

total=s_letters+c_letters+num+spl_char;

printf(" This File contains ...");

printf("\n\t%d lines", lines);

printf("\n\t%d words",words);

printf("\n\t%d small letters", s_letters);

printf("\n\t%d capital letters",c_letters);

printf("\n\t%d digits", num);

 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

printf("\n\t%d special characters",spl_char);

printf("\n\tIn total %d characters.\n",total);

int yywrap()

return(1);

OUTPUT:

'myfile.txt' :

This file contains..

2 lines

9 words

30 small letters

3 capital letters

1 digits

9 special characters

In total 43 characters.
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

RESULT:
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

EXP NO: 03(d)

DATE:

IDENTIFY THE USING LEXICAL ANALYZER GENERATING

TOOLS

AIM:

To develop a lexical analyzer using lexical analyzer generating tools

(such as Lex) to identify vowels, word spaces, and end-of-line
characters in a given input file.

ALGORITHM:

Step 1: Start.
Step 2: Define token patterns for vowels ([AEIOUaeiou]), spaces (" "),
and newlines ("\n") in Lex.
Step 3: Initialize vowel_count, space_count, and newline_count to zero.
Step 4: Read input from a file character by character.
Step 5: Match each character against the defined patterns:

 If it is a vowel, increment vowel_count.

 If it is a space, increment space_count.

 If it is a newline, increment newline_count.

Step 6: Continue scanning until the end of the file is reached.
Step 7: Print the total count of vowels, spaces, and newline characters.
Step 8: End.
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

PROGRAM:

%{

#include<stdio.h>

#include<string.h>

struct st

char LEXeme[25];

char name[25];

}ST[100];

int cnt=0;

%}

ID [a-zA-Z][a-zA-Z0-9]*

DIGIT [0-9]

%%

{DIGIT}+ {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"const
integer literal");cnt++;}

{DIGIT}+"."{DIGIT}+
{strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"const float
literal");cnt++;}

"#include"|"#define"
{strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"pp directive");cnt++;}

{ID}".h"
{strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"includefile");cnt++;}

main |void |switch |case |continue|break|do|while|for|if|else|int|float|char

{strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"keyword");cnt++;}
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

"\""{ID}"\"" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"string
literal");cnt++;}

{ID} {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"identifier");cnt+
+;}

"+"|"-"|"#"|"/"|"%"
{strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"Arithmetic OP");cnt+
+;}

"&"|"|"|"^"+"~"
{strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"Bitwise OP");cnt++;}

"<<"|">>" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"Bitwise
SHift OP");cnt++;}

"&&"|"||"|"!" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"Logical
OP");cnt++;}

"<"|">"|"<="|">="
{strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"Realational OP");cnt+
+;}

"=="|"!=" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"Equality
OP");cnt++;}

"[" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"OSB");cnt++;}

"]" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"CSB");cnt++;}

"{" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"OCB");cnt++;}

"}" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"CCB");cnt++;}

"(" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"ORB");cnt++;}

")" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"CRB");cnt++;}

":" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"Semicolon");cnt+
+;}

"++" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"IncOP");cnt++;}
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

"--" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"DecOp");cnt++;}

"?" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"Ternary OP");cnt+

+;}

"=" {strcpy(ST[cnt].LEXeme,yytext);strcpy(ST[cnt].name,"Assignment
OP");cnt++;}

%%

main(int argc,char *argv[])

int i=0;

yyin=fopen(argv[1],"r");

yylex();

printf("\nTOKEN TABLE");

printf("\nLEXEME\t\t\tNAME\n");

printf("____________\t\t____________\n");

for(i=0;i<cnt;i++)

printf("\n%s",ST[i].LEXeme);

printf("\t\t\t%s",ST[i].name);

printf("\n");

int yywrap()

return 1; }
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

INPUT C PROGRAM:

#include<stdio.h>

main()

int a,b,c=0;

c=a+b;

return c;

OUTPUT:

TOKEN TABLE

LEXEME NAME

____________ ____________

#include pp directive

< Realational OP

stdio.h includefile

> Realational OP

main string literal

( ORB

) CRB

{ OCB

int identifier
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

a identifier

b identifier

c identifier

= Assignment OP

0 const integer literal

c identifier

= Assignment OP

a identifier

+ Arithmetic OP

b identifier

return identifier

c identifier

} CCB

RESULT:

EXP NO:04(a)
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

DATE:

TO RECOGNISE A VALID ARITHMETIC EXPRESSION THAT

USES OPERATOR +,-,* AND /.

AIM:

To develop a lexical analyzer using lexical analyzer generating tools

(such as Lex) to recognize a valid arithmetic expression containing
operators +, -, *, and /.

ALGORITHM:

Step 1: Start.
Step 2: Define token patterns for:

 Operands (digits and identifiers like a, b, c, ...).

 Operators (+, -, *, /).

 Parentheses ((, )) for grouping expressions.

Step 3: Read the input expression character by character.
Step 4: Check each token:

 If it is a number or an identifier, recognize it as an operand.

 If it is an arithmetic operator (+, -, *, /), recognize it as a valid operator.

 If it is a parenthesis, recognize it for correct grouping.

 If an invalid character is found, report an error.

Step 5: Continue scanning until the entire expression is processed.
Step 6: If the expression follows valid arithmetic syntax, print "Valid
Expression"; otherwise, print "Invalid Expression."
Step 7: End.

LEX PROGRAM:
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

%{

#include "y.tab.h"

extern yylval;

%}

%%

[0-9]+ {yylval=atoi(yytext);return NUMBER;}

[a-zA-Z]+ {return ID;}

[\t]+ ;

\n {return 0;}

. {return yytext[0];}

%%

YACC PROGRAM:

%{

#include<stdio.h>

%}

%token NUMBER

%token ID

%left '+''-'

%left '*''/'

%%

expr:expr'+'expr|expr'-'expr|expr'*'expr|expr'/'expr|'-' NUMBER|'-'
ID|'('expr')'| NUMBER| ID ;

%%
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

main()

printf("Enter the expressiobn: ");

yyparse();

printf("\nExpression is valid\n");

exit(0);

int yyerror(char *s)

printf("\nExpression is invalid");

exit(0);

OUTPUT:

Enter the expressiobn: a+b

Expression is valid.

RESULT:

EXP NO: 04(b)

 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

DATE:

TO FIND VALID IDENTIFIERS

AIM:

To develop a lexical analyzer using lexical analyzer generating tools

(such as Lex) to identify valid identifiers in a given input.

ALGORITHM:

Step 1: Start.
Step 2: Define token patterns for valid identifiers:

 An identifier must start with a letter (A-Z, a-z) or an underscore (_).

 The following characters can be letters (A-Z, a-z), digits (0-9), or

underscores (_).
Step 3: Read the input character by character.
Step 4: Match each token against the defined pattern for identifiers.
Step 5: If a token matches the identifier pattern, recognize it as a valid
identifier.
Step 6: If a token does not match the pattern, report an error as an
invalid identifier.
Step 7: Continue scanning until the entire input is processed.
Step 8: Display the list of valid identifiers found.
Step 9: End.
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

LEX PROGRAM :

%{

#include"y.tab.h"

%}

%%

[a-zA-Z] {return LETTER;}

[0-9] {return DIGIT;}

[_] {return UND;}

[\n] {return NL;}

. {return yytext[0];}

%%

YACC PROGRAM:

%{

#include<stdio.h>

#include<stdlib.h>

%}

%token DIGIT LETTER UND NL

%%

stmt: variable NL {printf("valid identifiers\n");exit(0);}

variable: LETTER alphanumeric |LETTER

;
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

alphanumeric: LETTER alphanumeric|DIGIT alphanumeric|UND

alphanumeric|LETTER|DIGIT|UND

%%

int yyerror(char *msg)

printf("Invalid variable\n");

exit(0);

main()

printf("enter the variable: \n");

yyparse();

OUTPUT:

enter the variable:

a122334

valid identifiers

RESULT:

EXP NO: 04(c)

 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

DATE:

DESIGN AND IMPLEMENT A CALCULATOR USING YACC

AND LEX

AIM:

To design and implement a calculator using YACC and Lex that can
evaluate arithmetic expressions involving operators +, -, *, and / with
proper precedence and associativity.

ALGORITHM:

Step 1: Start.
Step 2: Define token patterns for numbers, arithmetic operators (+, -,
*, /), and parentheses.
Step 3: Read the input expression character by character.
Step 4: Identify numbers as operands and operators as tokens.
Step 5: Pass recognized tokens to YACC for parsing and evaluation.

Syntax Analysis and Evaluation (YACC):

Step 6: Define grammar rules for arithmetic expressions, ensuring

correct precedence and associativity.
Step 7: Construct a parse tree based on the grammar rules.
Step 8: Use actions to compute results during parsing.
Step 9: If the input expression follows valid syntax, evaluate and
display the result; otherwise, report an error.
Step 10: End.

Calc.y:
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

%{

#include <stdlib.h>

#include <stdio.h>

int yylex(void);

#include "y.tab.h"

%}

%token INTEGER

%%

PROGRAM:

line program | line

expr '\n' { printf("%d\n",$1); } | 'n'

EXPR:

expr '+' mulex { $$ = $1 + $3; }

| expr '-' mulex { $$ = $1 - $3; }

| mulex { $$ = $1; }

mulex:

mulex '*' term { $$ = $1 * $3; }

| mulex '/' term { $$ = $1 / $3; }

| term { $$ = $1; }

term:

'(' expr ')' { $$ = $2; }

| INTEGER { $$ = $1; }

%%
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

void yyerror(char *s)

{ fprintf(stderr,"%s\n",s);

return;

yywrap()

return(1);

int main(void)

{ /*yydebug=1;*/

yyparse();

return 0;

Lexx.l:

%{

#include <stdlib.h>

#include <stdio.h>

#include "y.tab.h"

void yyerror(char*);

extern int yylval;

%}
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

%%

[ \t]+ ;

[0-9]+ {yylval = atoi(yytext);

return INTEGER;}

[-+*/] {return *yytext;}

"(" {return *yytext;}

")" {return *yytext;}

\n {return *yytext;}

. {char msg[25];

sprintf(msg,"%s <%s>","invalid character",yytext);

yyerror(msg);}

OUTPUT:

$ lex lexx.l

$ yacc -d calc.y

$ gcc y.tab.c lex.yy.c

$ ./a.out

5+6

11

8+9-7

10

6++9

syntax error
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

RESULT:

EXP NO: 05
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

DATE:

CONVERT THE BNF RULES INTO YACC FORM AND

GENERATE ABSTRACT SYNTAX TREE

AIM:

To convert Backus-Naur Form (BNF) rules into YACC form

and generate an Abstract Syntax Tree (AST) for arithmetic
expressions.

ALGORITHM:

Step 1: Define the BNF rules for arithmetic expressions.

Step 2: Convert BNF rules into YACC form.
Step 3: Write a Lex file to provide tokens to YACC.
Step 4: Parse the input expression using YACC.
Step 5: Generate the Abstract Syntax Tree (AST).
Step 6: Traverse the AST for evaluation.
Step 7: Display the generated AST and computed result.
Step 8: End

<int.l>:
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

%{

#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;}

\< |

\> |

\>= |

\<= |
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

== {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;
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

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
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

| WHILEST

DESCT: TYPE VARLIST

VARLIST: VAR ',' VARLIST

| VAR

ASSIGNMENT: VAR '=' EXPR{

strcpy(QUAD[Index].op,"=");

strcpy(QUAD[Index].arg1,$3); | term { $$ = $1; }

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
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

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);
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

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);
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

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[])

{
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

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");
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

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;

}
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

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);

Input:

$vi test.c

main()

int a,b,c;

if(a<b)

a=a+b;

while(a<b)
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

a=a+b;

if(a<=b)

c=a-b;

else

c=a+b;

}
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

OUTPUT:

$lex int.l

$yacc –d int.y

$gcc lex.yy.c y.tab.c –ll –ly

$./a.out test.c

*******************************

Pos Operator Arg1 Arg2 Result

**********************************

0 < a b
t0
1 == t0 FALSE
5
2 + a b
t1
3 = t1
a
4 GOTO
5
5 < a b
t2
6 == t2 FALSE
10
7 + a b
t3
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

8 = t3
a
9 GOTO
5
10 <= a b
t4
11 == t4 FALSE
15
12 - a b
t5
13 = t5
c
14 GOTO
17
15 + a b
t6
16 = t6
c

***********************************

RESULT:
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

EXP NO: 06

DATE:

TYPE CHECKING

AIM:

To implement type checking in a compiler using lexical and syntax

analysis to ensure type correctness in expressions and assignments.

ALGORITHM:

Step 1: Start.
Step 2: Define rules for valid data types (e.g., int, float, char).
Step 3: Read and tokenize the input source code using Lex.
Step 4: Parse the input using YACC to identify expressions and
assignments.
Step 5: Check for type compatibility in operations and assignments.
Step 6: If a type mismatch is found, generate an error; otherwise,
continue processing.
Step 7: Display type-checking results.
Step 8: End.
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

PROGRAM :

#include<stdio.h>

#include<conio.h>

#include<ctype.h>

#include<string.h>

#include<stdlib.h>

char *type(char[],int);

void main()

char a[10],b[10],mess[20],mess1[20];

int i,l;

clrscr();

printf(“\n\n int a,b;\n\n int c=a+b\n”);

printf(“\n\n enter a value for a\n”);

scanf(“%s”,a);

l=strlen(a);

printf(“\n a is:”);

strcpy(mess,type(a,l));

printf(“%s”,mess);

printf(“\n\n enter a value for b\n\n”);

scanf(“%s”,b);

l=strlen(b);

printf(“\n b is:”);
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

strcpy(mess1,type(b,l));

printf(“%s”,mess1);

if(strcmp(mess,”int”)==0&&strcmp(mess1,”int”)==0)

printf(“\n\n no type error”);

else

printf(“\n\n type error”);

getch();

char* type(char x[],int m)

int i;

char mes[20];

for(i=0;i<m;i++)

if(isalpha(x[i]))

strcpy(mes,”alphanumeric”);

goto x;

else if(x[i]==’.’)
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

strcpy(mes,”float”);

goto x;

strcpy(mes,”int”);

x:

return mes;

OUTPUT:

RESULT:
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

EX. NO:7

DATE:

IMPLEMENTATION OF STORAGE ALLOCATION

STRATEGIES(HEAP,STATIC)

AIM:

To implement and analyze storage allocation strategies such as static

allocation and heap (dynamic) allocation in a program.

ALGORITHM:

Step 1: Start.
Step 2: Implement static allocation using global or local variables.
Step 3: Implement heap allocation using dynamic memory functions
(malloc, calloc, free in C).
Step 4: Allocate memory based on the selected strategy.
Step 5: Perform read and write operations on the allocated memory.
Step 6: Deallocate dynamically allocated memory to prevent memory
leaks.
Step 7: Compare the efficiency of static and heap allocation.
Step 8: Display the results and memory usage.
Step 9: End.
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

PROGRAM:

HEAP:

#include <stdio.h>

#include<conio.h>

#include <stdlib.h>

double *multiplyByTwo (double *input)

double *twice = malloc(sizeof(double));

*twice =*input * 2.0;

return twice;

void main (int argc, char *argv[])

int *age = malloc(sizeof(int));

double *salary = malloc(sizeof(double));

double *myList=malloc(3*sizeof(double));

double *twiceSalary=multiplyByTwo(salary);

*salary = 12345.67;

*age=30;

myList[0] = 1.2;

myList[1] = 2.3;

myList[2] = 3.4;

printf("double your salary is %.3f\n", *twiceSalary);

 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

free(age);

free(salary);

free(myList);

free(twiceSalary);

getch();

OUTPUT:

Double your Salary is 24691.340

STATIC:

#include<stdio.h>

#include<conio.h>

double fibonacci();

int main()

int n,i;

printf("How many fibonacci numbers?\n");

scanf("%d",&n);

printf("The first %d fibonacci numbers are:\n",n);

for(i=0;i<=n;i++)

printf("%g\t",fibonacci());

getch();

return 0;
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

double fibonacci()

static double f1=1.0,f2=0.0;

double f;

f=f1+f2;

f1=f2;

f2=f;

return f;

OUTPUT:

How many Fibonacci numbers?

The first 5 fibonacci numbers are:

11235

RESULT:
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

Ex. No : 8

DATE:

CONSTRUCTION OF DAG

AIM:

To construct a Directed Acyclic Graph (DAG) from a given arithmetic

expression to optimize computations by eliminating common
subexpressions.

ALGORITHM:

Step 1: Start.
Step 2: Read the input arithmetic expression.
Step 3: Tokenize the expression to identify operands and operators.
Step 4: Build the DAG by creating nodes for unique subexpressions.
Step 5: If a subexpression is repeated, reuse the existing node instead of
creating a new one.
Step 6: Continue constructing the DAG until the entire expression is
processed.
Step 7: Traverse the DAG to generate an optimized computation
sequence.
Step 8: Display the constructed DAG.
Step 9: End
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

PROGRAM:

#include<stdio.h>

main()

struct da

int ptr,left,right;

char label;

}dag[25];

int ptr,l,j,change,n=0,i=0,state=1,x,y,k;

char store,*input1,input[25],var;

clrscr();

for(i=0;i<25;i++)

dag[i].ptr=NULL;

dag[i].left=NULL;

dag[i].right=NULL;

dag[i].label=NULL;

printf("\n\nENTER THE EXPRESSION\n\n");

scanf("%s",input1);

/*EX:((a*b-c))+((b-c)*d)) like this give with aranthesis.limit is 25 char

ucan change that*/
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

for(i=0;i<25;i++)

input[i]=NULL;

l=strlen(input1);

a:for(i=0;input1[i]!=')';i++);

for(j=i;input1[j]!='(';j--);

for(x=j+1;x<i;x++)

if(isalpha(input1[x]))

input[n++]=input1[x];

else

if(input1[x]!='0')

store=input1[x];

input[n++]=store;

for(x=j;x<=i;x++)

input1[x]='0';

if(input1[0]!='0')goto a;

for(i=0;i<n;i++)

dag[i].label=input[i];

dag[i].ptr=i;

if(!isalpha(input[i])&&!isdigit(input[i]))

dag[i].right=i-1;

ptr=i;
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

var=input[i-1];

if(isalpha(var))

ptr=ptr-2;

else

ptr=i-1;

b:

if(!isalpha(var)&&!isdigit(var))

ptr=dag[ptr].left;

var=input[ptr];

goto b;

else

ptr=ptr-1;

dag[i].left=ptr;

printf("\n SYNTAX TREE FOR GIVEN EXPRESSION\n\n");

printf("\n\n PTR\t\t LEFT PTR\t\t RIGHT PTR\t\t LABEL\n\n");

for(i=0;i<n;i++)/* draw the syntax tree for the following

output with pointer value*/

 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

printf("\n%d\t%d\t%d\t%c\
n",dag[i].ptr,dag[i].left,dag[i].right,dag[i].label);

getch();

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if((dag[i].label==dag[j].label&&dag[i].left==dag[j].left)&&dag[i].right=
=dag[j].right)

for(k=0;k<n;k++)

if(dag[k].left==dag[j].ptr)dag[k].left=dag[i].ptr;

if(dag[k].right==dag[j].ptr)dag[k].right=dag[i].ptr;

dag[j].ptr=dag[i].ptr;

}}}

printf("\n DAG FOR GIVEN EXPRESSION\n\n");

printf("\n\n PTR\t LEFT PTR\t RIGHT PTR\t LABEL\n\n");

for(i=0;i<n;i++)/*draw DAG for the following output with

pointer value*/

printf("\n%d\t\t%d\t\t%d\t\t%c\
n",dag[i].ptr,dag[i].left,dag[i].right,dag[i].label);

getch(); }
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

OUTPUT:

Enter the expression : ((a*(b-c)*(b-c)))

DAG:

RESULT:
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

Ex. No : 9

DATE:

IMPLEMENT BACKEND OF THE COMPILER

AIM:

To implement the backend of a compiler, which involves generating

intermediate code, optimizing it, and translating it into target machine
code.

ALGORITHM:

Step 1: Start.
Step 2: Take intermediate representation (IR) as input from the
compiler's front-end.
Step 3: Perform code optimization techniques such as constant folding,
dead code elimination, and loop optimizations.
Step 4: Generate assembly code or machine code from the optimized
intermediate representation.
Step 5: Allocate registers efficiently using register allocation algorithms.
Step 6: Perform instruction selection and scheduling for efficient
execution.
Step 7: Write the final machine code or assembly code as output.
Step 8: End.
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

PROGRAM:

#include<stdio.h>

#include<stdio.h>

#include<conio.h>

#include<string.h>

void main()

char icode[10][30],str[20],opr[10];

int i=0;

clrscr();

printf("\n Enter the set of intermediate code (terminated by exit):\n");

do

scanf("%s",icode[i]);

} while(strcmp(icode[i++],"exit")!=0);

printf("\n target code generation");

printf("\n************************");

i=0;

do {

strcpy(str,icode[i]);

switch(str[3])

case '+':

strc
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

py(opr,"ADD");

break;

case '-':

strcpy(opr,"SUB");

break;

case '*':

strcpy(opr,"MUL");

break;

case '/':

strcpy(opr,"DIV");

break;

printf("\n\tMov %c,R%d",str[2],i);

printf("\n\t%s%c,R%d",opr,str[4],i);

printf("\n\tMov R%d,%c",i,str[0]);

}while(strcmp(icode[++i],"exit")!=0);

getch();

}
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

OUTPUT:

RESULT:
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

Ex.No:10

DATE:

SIMPLE CODE OPTIMIZATION TECHNIQUES

AIM:

To implement simple code optimization techniques in a compiler to

improve execution efficiency by reducing redundant computations.

ALGORITHM:

Step 1: Start.
Step 2: Read the intermediate code generated by the compiler front-end.
Step 3: Apply Constant Folding by replacing constant expressions with
their computed values.
Step 4: Apply Constant Propagation by replacing variables with known
constant values.
Step 5: Apply Dead Code Elimination by removing code that does not
affect the program's output.
Step 6: Apply Common Subexpression Elimination (CSE) by reusing
previously computed expressions instead of recomputing them.
Step 7: Apply Strength Reduction by replacing expensive operations
with equivalent cheaper operations (e.g., replacing multiplication with
shifts).
Step 8: Generate optimized code after applying the above
transformations.
Step 9: Display the optimized code.
Step 10: End.
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

PROGRAM:

#include<stdio.h>

#include<conio.h>

#include<string.h>

struct op

char l;

char r[20];

op[10],pr[10];

void main()

int a,i,k,j,n,z=0,m,q;

char *p,*l;

char temp,t;

char *tem;

clrscr();

printf("Enter the Number of Values:");

scanf("%d",&n);

for(i=0;i<n;i++)

printf("left: ");

op[i].l=getche();

printf("\tright: ");
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

scanf("%s",op[i].r);

printf("Intermediate Code\n") ;

for(i=0;i<n;i++)

printf("%c=",op[i].l);

printf("%s\n",op[i].r);

for(i=0;i<n-1;i++)

temp=op[i].l;

for(j=0;j<n;j++) {

p=strchr(op[j].r,temp);

if(p) {

pr[z].l=op[i].l;

strcpy(pr[z].r,op[i].r);

z++; }}}

pr[z].l=op[n-1].l;

strcpy(pr[z].r,op[n-1].r);

z++;

printf("\nAfter Dead Code Elimination\n");

for(k=0;k<z;k++) {

printf("%c\t=",pr[k].l);
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

printf("%s\n",pr[k].r);

for(m=0;m<z;m++) {

tem=pr[m].r;

for(j=m+1;j<z;j++) {

p=strstr(tem,pr[j].r);

if(p) {

t=pr[j].l;

pr[j].l=pr[m].l;

for(i=0;i<z;i++) {

l=strchr(pr[i].r,t) ;

if(l) {

a=l-pr[i].r;

printf("pos: %d",a);

pr[i].r[a]=pr[m].l; }}}}}

printf("Eliminate Common Expression\n");

for(i=0;i<z;i++)

printf("%c\t=",pr[i].l);

printf("%s\n",pr[i].r);

for(i=0;i<z;i++)

for(j=i+1;j<z;j++)
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

q=strcmp(pr[i].r,pr[j].r);

if((pr[i].l==pr[j].l)&&!q)

pr[i].l='\0';

strcpy(pr[i].r,'\0');

printf("Optimized Code\n");

for(i=0;i<z;i++)

if(pr[i].l!='\0')

printf("%c=",pr[i].l);

printf("%s\n",pr[i].r);

getch();

}
 PANIMALAR ENGINEERING COLLEGE
DEPARTMENT OF CSE
Reg No: 211422104XXX

OUTPUT:

Enter the Number of Values: 4

RESULT: