NETAJI SUBHAS

UNIVERSITY OF
TECHNOLOGY

CACSC14:Principles Of
Compiler Construction

NAME:RAGHWENDRA
Ro no:2022UCA1834
BRANCH:CSAI-1
Page 1

ll
 List of Practicals

[Link] Practicals Page

No.

1 Implement a program for symbol table using hashing 3

2 Implement a two-pass assembler 8085/8086 7

3 Develop Lexical Analyzer for ‘C’ using LEX tool 13

4 Represent ‘C’ language using Context Free language. 16

5 Develop a Parser for ‘C’ using the LEX and YACC tools. 19

6 Design a small high-level language and implement a compiler for the 24

same. If the target machine of the compiler is a hypothetical
machine,
then implement a simulator for it.
7 Develop a simple calculator using LEX and YACC tools. 30

8 Add assignment statement, If then else statement and while loop to 32

the calculator and generate the three address code for the same.

Page 2

 Experiment 1

Aim: Implement a program for symbol table using hashing

Code:
lexer.l :

%{
#include "[Link].h"
#include "symbol_table.h"
#include <string.h>
int yywrap(void);
%}

%%
"@"[a-zA-Z0-9]* { printf("Syntax error: Identi ers cannot start with
'@': %s\n", yytext); return ERROR; }
[a-zA-Z][a-zA-Z0-9]* { [Link] = strdup(yytext); return
IDENTIFIER; }
[0-9]+ { [Link] = atoi(yytext); return NUMBER; }
"=" { return '='; }
[ \t\n] { /* ignore whitespace */ }
. { /* handle other characters */ }
%%

int yywrap(void) {
return 1;
}

parser.y :

%{
#include <stdio.h>
#include "symbol_table.h"
int yylex(void);
void yyerror(const char *s);
void print_symbol_table(void); // Add this line
Page 3

fi
 FILE *yyin;
%}

%union {
char *str;
int num;
}

%token <str> IDENTIFIER

%token <num> NUMBER
%token ERROR

%%
program:
declarations
{
printf("Symbol table after parsing:\n");
print_symbol_table();
}
;

declarations:
declaration
| declarations declaration
;

declaration:
IDENTIFIER '=' NUMBER { insert_symbol($1, $3); }
;

%%
int main(int argc, char *argv[]) {
if (argc > 1) {
FILE * le = fopen(argv[1], "r");
if (! le) {
perror(argv[1]);
return 1;
}
Page 4

fi
fi
 yyin = le;
}
return yyparse();
}

void yyerror(const char *s) {

fprintf(stderr, "Error: %s\n", s);
}

symbol_table.c :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "symbol_table.h"

// Define the hash table array

Symbol *hash_table[TABLE_SIZE];

// Hash function to map a name to an index

int hash(char *name)
{
unsigned int hash_value = 0;
for (int i = 0; name[i] != '\0'; i++)
{
hash_value = hash_value * 31 + name[i]; // Simple hash function
}
return hash_value % TABLE_SIZE;
}

// Insert a symbol into the hash table

Symbol *insert_symbol(char *name, int value)
{
int index = hash(name);
Symbol *sym = (Symbol *)malloc(sizeof(Symbol));
if (!sym)
{
fprintf(stderr, "Memory allocation failed\n");
return NULL;
}
sym->name = strdup(name); // Copy of string
sym->value = value;
sym->next = hash_table[index]; // Insert at the beginning of the list for this hash
bucket
hash_table[index] = sym;
return sym;
}

// Lookup a symbol in the hash table

Symbol *lookup_symbol(char *name)
{
int index = hash(name);
for (Symbol *sym = hash_table[index]; sym != NULL; sym = sym->next)
{
if (strcmp(sym->name, name) == 0)
{
return sym; // Found the symbol
}
}
return NULL; // Symbol not found
}

Page 5

fi
 // Print the entire symbol table
void print_symbol_table(void)
{
for (int i = 0; i < TABLE_SIZE; i++)
{
Symbol *sym = hash_table[i];
if (sym != NULL)
{
printf("Bucket %d:\n", i);
while (sym != NULL)
{
printf(" Symbol: %s, Value: %d\n", sym->name, sym->value);
sym = sym->next;
}
}
}
}

symbol_table.h :

#ifndef SYMBOL_TABLE_H
#define SYMBOL_TABLE_H

#define TABLE_SIZE 100 // Define a suitable size for the hash

table

typedef struct Symbol

{
char *name;
int value;
struct Symbol *next;
} Symbol;

Symbol *insert_symbol(char *name, int value);

Symbol *lookup_symbol(char *name);
void print_symbol_table(void);
int hash(char *name);

#endif

Output:

Page 6

 Experiment 2

Aim: Implement a two-pass assembler

Code:
two_pass.c :
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define MAX_SYMBOLS 1000

#define MAX_OPERANDS 2

// Forward declarations of all functions

void add_symbol(char *label, int address);
int find_symbol(char *label);
int get_opcode(char *instruction);
int get_register_code(char *reg);
void print_symbol_table();
void print_binary(int value);
void add_operand(int value);
void print_instruction();
void reset_instruction();
int is_single_operand_instruction(char *instruction);
void parse_line(char *line);
void first_pass(FILE *file);
void second_pass(FILE *file);

typedef struct
{
char label[20];
int address;
} Symbol;

typedef struct
{
int opcode;
int operands[MAX_OPERANDS];
int operand_count;
} Instruction;

Symbol symbol_table[MAX_SYMBOLS];
int symbol_count = 0;
int location_counter = 0;
int pass = 1;
Instruction current_instruction;

void add_symbol(char *label, int address)

{
if (find_symbol(label) == -1)
{
strcpy(symbol_table[symbol_count].label, label);
symbol_table[symbol_count].address = address;
symbol_count++;
}
}

int find_symbol(char *label)

{
for (int i = 0; i < symbol_count; i++)
{
if (strcmp(symbol_table[i].label, label) == 0)
{
return symbol_table[i].address;

Page 7

 }
}
return -1;
}

int get_opcode(char *instruction)

{
if (strcmp(instruction, "MOV") == 0)
return 0x3E;
if (strcmp(instruction, "ADD") == 0)
return 0x80;
if (strcmp(instruction, "SUB") == 0)
return 0x90;
if (strcmp(instruction, "JMP") == 0)
return 0xC3;
if (strcmp(instruction, "CMP") == 0)
return 0x3D;
if (strcmp(instruction, "MUL") == 0)
return 0xF6;
if (strcmp(instruction, "JNE") == 0)
return 0x75;
if (strcmp(instruction, "HLT") == 0)
return 0x76;
if (strcmp(instruction, "JZ") == 0)
return 0x74;
if (strcmp(instruction, "DCR") == 0)
return 0x3B;
return -1;
}

int get_register_code(char *reg)

{
if (strcmp(reg, "A") == 0)
return 0x00;
if (strcmp(reg, "B") == 0)
return 0x01;
if (strcmp(reg, "C") == 0)
return 0x02;
return -1;
}

void print_symbol_table()
{
printf("\nSymbol Table:\n");
printf("Label\tAddress\n");
printf("-----\t-------\n");
for (int i = 0; i < symbol_count; i++)
{
printf("%s\t0x%04X\n", symbol_table[i].label, symbol_table[i].address);
}
printf("\n");
}

void print_binary(int value)

{
for (int i = 7; i >= 0; i--)
{
printf("%d", (value >> i) & 1);
}
}

int is_single_operand_instruction(char *instruction)

{
return (strcmp(instruction, "MUL") == 0 ||
strcmp(instruction, "DCR") == 0 ||
strcmp(instruction, "JMP") == 0 ||
strcmp(instruction, "JZ") == 0);
}

void add_operand(int value)

{
if (current_instruction.operand_count < MAX_OPERANDS)

Page 8

 {
current_instruction.operands[current_instruction.operand_count++] = value;
}
}

void print_instruction()
{
if (current_instruction.opcode == 0)
return;

printf("0x%04X: ", location_counter - current_instruction.operand_count - 1);

printf("%02X ", current_instruction.opcode);

for (int i = 0; i < current_instruction.operand_count; i++)

{
printf("%02X ", current_instruction.operands[i]);
}
printf("\n");
}

void reset_instruction()
{
current_instruction.opcode = 0;
current_instruction.operand_count = 0;
}

void parse_line(char *line)

{
char *token = strtok(line, " ,\n\t");
if (token == NULL)
return;

// Remove any leading whitespace

while (*token && isspace(*token))
token++;
if (!*token)
return;

// Handle labels
if (strchr(token, ':') != NULL)
{
token[strlen(token) - 1] = '\0'; // Remove the colon
add_symbol(token, location_counter);
token = strtok(NULL, " ,\n\t");
if (!token)
return;
}

// Get instruction
char instruction[10];
strncpy(instruction, token, sizeof(instruction) - 1);
instruction[sizeof(instruction) - 1] = '\0';
for (int i = 0; instruction[i]; i++)
{
instruction[i] = toupper(instruction[i]);
}

int opcode = get_opcode(instruction);

if (opcode == -1)
{
if (pass == 2)
{
fprintf(stderr, "Error: Unknown instruction %s\n", instruction);
exit(1);
}
return;
}

current_instruction.opcode = opcode;
location_counter++;

// Handle HLT instruction separately

Page 9

 if (strcmp(instruction, "HLT") == 0)
{
return;
}

// Parse operands
int operand_limit = is_single_operand_instruction(instruction) ? 1 : 2;
int operand_count = 0;

while ((token = strtok(NULL, " ,\n\t")) != NULL && operand_count < operand_limit)
{
while (*token && isspace(*token))
token++;
if (!*token)
continue;

if (isdigit(token[0]) || (token[0] == '-' && isdigit(token[1])))

{
add_operand(atoi(token));
}
else
{
int reg_code = get_register_code(token);
if (reg_code != -1)
{
add_operand(reg_code);
}
else
{
int symbol_addr = find_symbol(token);
if (symbol_addr == -1)
{
if (pass == 2)
{
fprintf(stderr, "Error: Undefined symbol %s\n", token);
exit(1);
}
add_operand(0);
}
else
{
add_operand(symbol_addr);
}
}
}
operand_count++;
}

location_counter += current_instruction.operand_count;
}

void first_pass(FILE *file)

{
char line[256];
location_counter = 0;
pass = 1;

while (fgets(line, sizeof(line), file))

{
reset_instruction();
parse_line(line);
}
}

void second_pass(FILE *file)

{
char line[256];
location_counter = 0;
pass = 2;

printf("\nMachine Code:\n");
printf("Address Code\n");

Page 10

 printf("------- ----\n");

while (fgets(line, sizeof(line), file))

{
reset_instruction();
parse_line(line);
print_instruction();
}
printf("\n");
}

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

{
if (argc < 2)
{
fprintf(stderr, "Usage: %s <assembly_file>\n", argv[0]);
return 1;
}

FILE *file = fopen(argv[1], "r");

if (!file)
{
perror("Could not open file");
return 1;
}

printf("Two-Pass Assembler\n");
printf("=================\n");

first_pass(file);
print_symbol_table();

rewind(file);
second_pass(file);

fclose(file);
return 0;
}

[Link] :

START: MOV A, 05
MOV B, 01
MOV C, A

FACTORIAL: CMP C, 01
JZ END
MUL C
DCR C
JMP FACTORIAL

END: MOV B, A
HLT

Page 11

 Output:

Page 12

 Experiment 3

Aim: Develop Lexical Analyzer for ‘C’ using LEX tool

Code:

lexer.l :

%{
#include <stdio.h>
#include <stdlib.h>
void print_string(const char *str) {
printf("STRING: %s\n", str);
}
%}

%option noyywrap

KEYWORD (int|return|if|else|while|for|void|char| oat|double|long|short|unsigned|signed|

const|static|struct|typedef|union|enum|extern|register|volatile|sizeof|goto)
IDENTIFIER [a-zA-Z_][a-zA-Z0-9_]*
NUMBER [0-9]+
STRING \".*\"
CHARACTER \'([^\\\n]|(\\.))\'
COMMENT \/\/[^\n]*|\/\*([^*]|\*+[^*/])*\*+\/
OPERATOR \+|\-|\*|\/|=|==|!=|<=|>=|<|>|\|\||&&|!|\%
PREPROCESSOR \#[^\n]*
WHITESPACE [ \t\n]+

%%

{IDENTIFIER}\( { printf("FUNCTION: %s\n", yytext); }

{KEYWORD} { printf("KEYWORD: %s\n", yytext); }
{IDENTIFIER} { printf("IDENTIFIER: %s\n", yytext); }
{NUMBER} { printf("NUMBER: %s\n", yytext); }
{STRING} { print_string(yytext); }
{CHARACTER} { printf("CHARACTER: %s\n", yytext); }
{COMMENT} { /* Ignored */ }
{OPERATOR} { printf("OPERATOR: %s\n", yytext); }
{PREPROCESSOR} { printf("PREPROCESSOR DIRECTIVE: %s\n", yytext); }
"{" { printf("BLOCK_START: %s\n", yytext); }
"}" { printf("BLOCK_END: %s\n", yytext); }
";" { printf("SEMICOLON: %s\n", yytext); }

Page 13

fl
 "," { printf("separater: %s\n", yytext); }

{WHITESPACE} { /* Ignored */ }
. {}
%%

int main(int argc, char **argv) {

if (argc > 1) {
FILE * le = fopen(argv[1], "r");
if (! le) {
fprintf(stderr, "Could not open le: %s\n", argv[1]);
exit(1);
}
yyin = le;
}
yylex();
return 0;
}

[Link] :

#include <stdio.h>
#de ne PI 3.14

// This is a single-line comment

/*
This is a
multi-line comment
*/

int main() {
char letter = 'A'; // Character literal
printf("Hello, World!"); // String literal
printf("Value of PI: %f", PI);

// Conditional statement
if (letter == 'A') {
printf("The letter is A.\n");
}

return 0;
}
Page 14
fi

fi
fi
fi
fi
 Output:

Page 15

 Experiment 4

Aim: Represent ‘C’ language using Context Free language.

Code:

%{
#include <stdio.h>
#include <stdlib.h>
int yylex(void);
void yyerror(const char *s);
%}

%token IDENTIFIER INTEGER_CONSTANT FLOAT_CONSTANT CHAR_CONSTANT

%token INT FLOAT CHAR IF ELSE RETURN WHILE
%token PLUS MINUS TIMES DIVIDE ASSIGN
%token SEMICOLON COMMA LPAREN RPAREN LBRACE RBRACE
%%

program:
external_declaration_list
;

external_declaration_list:
external_declaration
| external_declaration_list external_declaration
;

external_declaration:
function_de nition
| declaration
;

function_de nition:
type_speci er declarator compound_statement
;

declaration:
type_speci er init_declarator_list SEMICOLON
;

type_speci er:
INT
| FLOAT
| CHAR
;

init_declarator_list:
init_declarator
| init_declarator_list COMMA init_declarator
;

init_declarator:
Page 16

fi
fi
fi
fi
fi
 declarator
| declarator ASSIGN initializer
;

declarator:
IDENTIFIER
| IDENTIFIER LPAREN parameter_list RPAREN
;

parameter_list:
parameter_declaration
| parameter_list COMMA parameter_declaration
;

parameter_declaration:
type_speci er declarator
;

initializer:
assignment_expression
;

compound_statement:
LBRACE statement_list RBRACE
;

statement_list:
statement
| statement_list statement
;

statement:
expression_statement
| compound_statement
| selection_statement
| iteration_statement
| return_statement
;

expression_statement:
expression SEMICOLON
| SEMICOLON
;

selection_statement:
IF LPAREN expression RPAREN statement
| IF LPAREN expression RPAREN statement ELSE statement
;

iteration_statement:
WHILE LPAREN expression RPAREN statement
;

return_statement:
RETURN expression SEMICOLON
;
Page 17

fi
 expression:
assignment_expression
| expression COMMA assignment_expression
;

assignment_expression:
IDENTIFIER ASSIGN assignment_expression
| additive_expression
;

additive_expression:
multiplicative_expression
| additive_expression PLUS multiplicative_expression
| additive_expression MINUS multiplicative_expression
;

multiplicative_expression:
primary_expression
| multiplicative_expression TIMES primary_expression
| multiplicative_expression DIVIDE primary_expression
;

primary_expression:
IDENTIFIER
| INTEGER_CONSTANT
| FLOAT_CONSTANT
| CHAR_CONSTANT
| LPAREN expression RPAREN
;

%%

void yyerror(const char *s) {

fprintf(stderr, "Error: %s\n", s);
}

int main(void) {
yyparse();
return 0;
}

Page 18

 Experiment 5

Aim: Develop a Parser for ‘C’ using the LEX and YACC tools.

Code:

lex.l :

%{
#include "[Link].h"
#include <stdlib.h>
%}

%%
"int" { return INT; }
" oat" { return FLOAT; }
"char" { return CHAR; }
"if" { return IF; }
"else" { return ELSE; }
"while" { return WHILE; }
"return" { return RETURN; }
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return TIMES; }
"/" { return DIVIDE; }
">" { return GREATER; }
"<" { return LESS; }
"=" { return ASSIGN; }
";" { return SEMICOLON; }
"," { return COMMA; }
"(" { return LPAREN; }
")" { return RPAREN; }
"{" { return LBRACE; }
"}" { return RBRACE; }
[0-9]+ { return INTEGER_CONSTANT; }
[0-9]+\.[0-9]+ { return FLOAT_CONSTANT; }
[a-zA-Z_][a-zA-Z0-9_]* { return IDENTIFIER; }
[ \t\n]+ ; /* ignore whitespace */
. { printf("Unknown character: %c\n", yytext[0]); }

%%

int yywrap(void) {
return 1;
}

Page 19
fl

 parser.y :

%{
#include <stdio.h>
#include <stdlib.h>
void yyerror(const char *s);
int yylex(void);
%}

%token IDENTIFIER INTEGER_CONSTANT FLOAT_CONSTANT

%token INT FLOAT CHAR IF ELSE WHILE RETURN
%token PLUS MINUS TIMES DIVIDE GREATER LESS ASSIGN
%token SEMICOLON COMMA LPAREN RPAREN LBRACE RBRACE
%right ASSIGN
%left PLUS MINUS
%left TIMES DIVIDE
%nonassoc GREATER LESS
%nonassoc LOWER_THAN_ELSE
%nonassoc ELSE
%%

program
: external_declaration
| program external_declaration
;

external_declaration
: function_de nition
| declaration
;

function_de nition
: type_speci er IDENTIFIER LPAREN parameter_list_opt RPAREN compound_statement
;

parameter_list_opt
: parameter_list
| /* empty */
;

parameter_list
: parameter_declaration
| parameter_list COMMA parameter_declaration
;

parameter_declaration
: type_speci er IDENTIFIER
;

declaration
: type_speci er init_declarator_list SEMICOLON
;

init_declarator_list
: init_declarator
Page 20

fi
fi
fi
fi
fi
 | init_declarator_list COMMA init_declarator
;

init_declarator
: IDENTIFIER
| IDENTIFIER ASSIGN expression
;

type_speci er
: INT
| FLOAT
| CHAR
;

compound_statement
: LBRACE statement_list RBRACE
| LBRACE RBRACE
;

statement_list
: statement
| statement_list statement
;

statement
: expression_statement
| compound_statement
| selection_statement
| iteration_statement
| return_statement
| declaration
;

expression_statement
: expression SEMICOLON
| SEMICOLON
;

selection_statement
: IF LPAREN expression RPAREN statement %prec LOWER_THAN_ELSE
| IF LPAREN expression RPAREN statement ELSE statement
;

iteration_statement
: WHILE LPAREN expression RPAREN statement
;

return_statement
: RETURN expression SEMICOLON
| RETURN SEMICOLON
;

expression
: assignment_expression
| expression COMMA assignment_expression
;
Page 21

fi
 assignment_expression
: conditional_expression
| IDENTIFIER ASSIGN assignment_expression
;

conditional_expression
: logical_or_expression
;

logical_or_expression
: logical_and_expression
;

logical_and_expression
: equality_expression
;

equality_expression
: relational_expression
;

relational_expression
: additive_expression
| relational_expression GREATER additive_expression
| relational_expression LESS additive_expression
;

additive_expression
: multiplicative_expression
| additive_expression PLUS multiplicative_expression
| additive_expression MINUS multiplicative_expression
;

multiplicative_expression
: primary_expression
| multiplicative_expression TIMES primary_expression
| multiplicative_expression DIVIDE primary_expression
;

primary_expression
: IDENTIFIER
| INTEGER_CONSTANT
| FLOAT_CONSTANT
| LPAREN expression RPAREN
| IDENTIFIER LPAREN RPAREN
| IDENTIFIER LPAREN argument_list RPAREN
;

argument_list
: assignment_expression
| argument_list COMMA assignment_expression
;

%%

Page 22

 void yyerror(const char *s) {
fprintf(stderr, "Error: %s\n", s);
}

int main(void) {
if (yyparse() == 0) {
printf("Parsing successful\n");
}
return 0;
}

[Link] :

int main() {
int x = 10;
oat y = 5.5;
if (x > y) {
x = x - 1;
}
return x;
}

Output :

Page 23
fl

 Experiment 6

Aim:Design a small high-level language and implement a compiler for the

same. If the target machine of the compiler is a hypothetical machine,
then implement a simulator for it.

Code:

miniLang.l:
%{
#include "[Link].h"
#include <stdlib.h>
#include <stdio.h>
%}

%option noyywrap

DIGIT [0-9]+
ID [a-zA-Z][a-zA-Z0-9]*

%%

"int" { return INT; }

" oat" { return FLOAT; }
"if" { return IF; }
"else" { return ELSE; }
"while" { return WHILE; }
"=" { return ASSIGN; }
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return MULTIPLY; }
"/" { return DIVIDE; }
"{" { return LBRACE; }
"}" { return RBRACE; }
"(" { return LPAREN; }
")" { return RPAREN; }
{DIGIT} { [Link] = atoi(yytext); return NUMBER; }
{ID} { [Link] = strdup(yytext); return IDENTIFIER; }
";" { return SEMICOLON; }
[ \t\n]+ { /* Ignore whitespace */ }
. { printf("Unknown character: %s\n", yytext); }

%%

Page 24
fl

 miniLang.y:
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#de ne MAX_VARS 100

// Symbol table
typedef struct {
char *name;
int value;
} Variable;

Variable vars[MAX_VARS];
int var_count = 0;

void add_var(char *name, int value) {

vars[var_count].name = strdup(name);
vars[var_count].value = value;
var_count++;
}

int get_var(char *name) {

for (int i = 0; i < var_count; i++) {
if (strcmp(vars[i].name, name) == 0) {
return vars[i].value;
}
}
return -1; // Variable not found
}

void yyerror(const char *s);

int yylex(void);

int label_count = 0;

%}

%union {
int ival;
char *sval;
}

// Specify token types and values

%token <ival> NUMBER
%token <sval> IDENTIFIER
%token INT FLOAT IF ELSE WHILE
%token ASSIGN PLUS MINUS MULTIPLY DIVIDE LBRACE RBRACE LPAREN RPAREN SEMICOLON

// Specify the types of non-terminals

%type <ival> expr term factor
%type <sval> declaration assignment

%%

Page 25
fi

 // Grammar rules

program: /* empty */
| program stmt
;

stmt: declaration
| assignment
| if_stmt
;

declaration: INT IDENTIFIER ASSIGN expr SEMICOLON {

add_var($2, $4);
printf("PUSH %d\n", $4);
printf("STORE %s\n", $2);
}
;

assignment: IDENTIFIER ASSIGN expr SEMICOLON {

int var_val = get_var($1);
if (var_val != -1) {
printf("PUSH %d\n", $3);
printf("STORE %s\n", $1);
} else {
printf("Error: Unde ned variable %s\n", $1);
}
}
;

if_stmt: IF LPAREN expr RPAREN LBRACE stmt RBRACE {

int label = label_count++;
printf("IF_FALSE GOTO L%d\n", label);
printf("L%d:\n", label);
}
;

expr: expr PLUS term { $$ = $1 + $3; printf("ADD\n"); }

| expr MINUS term { $$ = $1 - $3; printf("SUB\n"); }
| term { $$ = $1; }
;

term: term MULTIPLY factor { $$ = $1 * $3; printf("MUL\n"); }

| term DIVIDE factor { $$ = $1 / $3; printf("DIV\n"); }
| factor { $$ = $1; }
;

factor: NUMBER { $$ = $1; printf("PUSH %d\n", $1); }

| IDENTIFIER {
int var_val = get_var($1);
if (var_val != -1) {
$$ = var_val;
printf("PUSH %d\n", var_val);
} else {
printf("Error: Unde ned variable %s\n", $1);
$$ = 0;
Page 26

fi
fi
 }
}
| LPAREN expr RPAREN { $$ = $2; }
;

%%

void yyerror(const char *s) {

fprintf(stderr, "Error: %s\n", s);
}

int main() {
return yyparse();
}

vm.c:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#de ne STACK_SIZE 100

#de ne VAR_TABLE_SIZE 100

typedef struct
{
char name[50];
int value;
} Variable;

Variable var_table[VAR_TABLE_SIZE];
int var_count = 0;

int stack[STACK_SIZE];
int sp = -1;

// Push a value onto the stack

void push(int val)
{
if (sp < STACK_SIZE - 1)
{
stack[++sp] = val;
}
else
{
printf("Stack over ow\n");
}
}

// Pop a value from the stack

int pop()
{
if (sp >= 0)
{
return stack[sp--];
}
else
{
printf("Stack under ow\n");
return 0;
}
}

Page 27
fi
fi

fl
fl
 // Store a value in the variable table
void store(char *name, int value)
{
for (int i = 0; i < var_count; i++)
{
if (strcmp(var_table[i].name, name) == 0)
{
var_table[i].value = value;
return;
}
}
strcpy(var_table[var_count].name, name);
var_table[var_count].value = value;
var_count++;
}

// Load a value from the variable table

int load(char *name)
{
for (int i = 0; i < var_count; i++)
{
if (strcmp(var_table[i].name, name) == 0)
{
return var_table[i].value;
}
}
printf("Unde ned variable: %s\n", name);
return 0;
}

// Execute a single instruction

void execute_instruction(char *instruction)
{
if (strcmp(instruction, "ADD") == 0)
{
int b = pop();
int a = pop();
push(a + b);
}
else if (strcmp(instruction, "SUB") == 0)
{
int b = pop();
int a = pop();
push(a - b);
}
else if (strcmp(instruction, "MUL") == 0)
{
int b = pop();
int a = pop();
push(a * b);
}
else if (strcmp(instruction, "DIV") == 0)
{
int b = pop();
int a = pop();
push(a / b);
}
}

// Print all variables and their values

void print_variables()
{
printf("Final state of variables:\n");
for (int i = 0; i < var_count; i++)
{
printf("%s = %d\n", var_table[i].name, var_table[i].value);
Page 28

fi
 }
}

int main()
{
char line[100];

// Read instructions from standard input

while (fgets(line, sizeof(line), stdin))
{
char command[10], arg[50];
int value;

if (sscanf(line, "PUSH %d", &value) == 1)

{
push(value);
}
else if (sscanf(line, "STORE %s", arg) == 1)
{
int top_value = pop();
store(arg, top_value);
}
else if (sscanf(line, "%s", command) == 1)
{
execute_instruction(command);
}
}

// Print nal variable values after executing all instructions

print_variables();

return 0;
}

[Link]:
int x = 5;
int y = 10;
int z = x + y;

Output :

Page 29

fi
 Experiment 7

Aim: Develop a simple calculator using the LEX and YACC tools.

Code:

calc.l :
%{
#include "[Link].h"
#include <stdio.h>
#include <stdlib.h> // For atoi
extern int yylval;
%}

%%
[0-9]+ { yylval = atoi(yytext); return NUMBER; }
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return TIMES; }
"/"|"÷" { return DIVIDE; }
\n { return EOL; }
[ \t\r] {} // Ignore whitespaces
%%

int yywrap(void){
return 1;
}

calc.y :
%{
#include <stdio.h>
#include <stdlib.h> // For atoi
void yyerror(const char *s);
int yylex();
%}

%token NUMBER PLUS MINUS TIMES DIVIDE EOL

%left PLUS MINUS
%left TIMES DIVIDE
%start statements

Page 30

 %%

statements : statement statements

| statement
;

statement : expression EOL { printf("= %d\n", $1); }

expression : NUMBER { $$ = $1; printf("number: %d\n", $$); }

| expression TIMES expression { $$ = $1 * $3; printf("operator:*\n"); }
| expression PLUS expression { $$ = $1 + $3; printf("operator:+\n"); }
| expression MINUS expression { $$ = $1 - $3; printf("operator:-\n"); }
| expression DIVIDE expression { $$ = $1 / $3; printf("operator:/\n"); }
;

%%

void yyerror(const char *s) {

fprintf(stderr, "Error: %s\n", s);
}

int main() {
return yyparse();
}

Output :

Page 31

 Experiment 8

Aim: Add assignment statement, If then else statement and while loop to
the calculator and generate the three address code for the same.

Code:

calc.l :
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "[Link].h"

void yyerror(char *s);

int line_no = 1;
%}

%%
[ \t] ;
[\n] { line_no++; }
"if" { return IF; }
"then" { return THEN; }
"else" { return ELSE; }
"while" { return WHILE; }
"do" { return DO; }
";" { return SEMICOLON; }
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return MULTIPLY; }
"/" { return DIVIDE; }
"=" { return ASSIGN; }
"==" { return EQ; }
"!=" { return NEQ; }
"<" { return LT; }
">" { return GT; }
"<=" { return LEQ; }
">=" { return GEQ; }
"(" { return LPAREN; }
")" { return RPAREN; }
"{" { return LBRACE; }
"}" { return RBRACE; }
[0-9]+ { [Link] = atoi(yytext); return NUMBER; }
[a-zA-Z][a-zA-Z0-9_]* { [Link] = strdup(yytext); return IDENTIFIER; }
. { printf("Unexpected character %s\n", yytext); }
%%

int yywrap(void) {
return 1;
}

Page 32

 calc.y :
%{
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void yyerror(char *s);

int yylex();
int temp_count = 0;
int label_count = 0;

char* new_temp() {
char* temp = (char*)malloc(10);
sprintf(temp, "t%d", temp_count++);
return temp;
}

char* new_label() {
char* label = (char*)malloc(10);
sprintf(label, "L%d", label_count++);
return label;
}
%}

%union {
int num;
char* id;
struct {
char* code;
char* place;
char* true_label;
char* false_label;
} expr;
}

%token <num> NUMBER

%token <id> IDENTIFIER
%token IF THEN ELSE WHILE DO
%token PLUS MINUS MULTIPLY DIVIDE
%token ASSIGN EQ NEQ LT GT LEQ GEQ
%token LPAREN RPAREN LBRACE RBRACE SEMICOLON

%type <expr> expr stmt stmt_list condition block while_stmt if_stmt assignment

%%

program:
stmt_list
;

stmt_list:
stmt { printf("%s", $[Link]); }
| stmt_list stmt { printf("%s", $[Link]); }
;

Page 33

 stmt:
assignment SEMICOLON { $$ = $1; }
| if_stmt { $$ = $1; }
| while_stmt { $$ = $1; }
;

assignment:
IDENTIFIER ASSIGN expr {
$$.code = (char*)malloc(1000);
sprintf($$.code, "%s%s = %s\n", $[Link], $1, $[Link]);
$$.place = $1;
}
;

if_stmt:
IF LPAREN condition RPAREN THEN block ELSE block {
char* label1 = new_label();
char* label2 = new_label();
$$.code = (char*)malloc(1000);
sprintf($$.code, "%s"
"if %s goto %s\n"
"goto %s\n"
"%s:\n"
"%s"
"goto %s\n"
"%s:\n"
"%s"
"%s:\n",
$[Link], $[Link], label1, label2,
label1, $[Link], $3.true_label,
label2, $[Link], $3.false_label);
}
;

while_stmt:
WHILE LPAREN condition RPAREN DO block {
char* start_label = new_label();
char* body_label = new_label();
char* end_label = new_label();
$$.code = (char*)malloc(1000);
sprintf($$.code, "%s:\n"
"%s"
"if %s goto %s\n"
"goto %s\n"
"%s:\n"
"%s"
"goto %s\n"
"%s:\n",
start_label, $[Link], $[Link], body_label, end_label,
body_label, $[Link], start_label, end_label);
}
;

block:
LBRACE stmt_list RBRACE { $$ = $2; }
;
Page 34

 condition:
expr LT expr {
char* temp = new_temp();
$$.code = (char*)malloc(1000);
sprintf($$.code, "%s%s%s = %s < %s\n",
$[Link], $[Link], temp, $[Link], $[Link]);
$$.place = temp;
$$.true_label = new_label();
$$.false_label = new_label();
}
| expr GT expr {
char* temp = new_temp();
$$.code = (char*)malloc(1000);
sprintf($$.code, "%s%s%s = %s > %s\n",
$[Link], $[Link], temp, $[Link], $[Link]);
$$.place = temp;
$$.true_label = new_label();
$$.false_label = new_label();
}
;

expr:
NUMBER {
char* temp = new_temp();
$$.code = (char*)malloc(1000);
sprintf($$.code, "%s = %d\n", temp, $1);
$$.place = temp;
}
| IDENTIFIER {
$$.code = strdup("");
$$.place = $1;
}
| expr PLUS expr {
char* temp = new_temp();
$$.code = (char*)malloc(1000);
sprintf($$.code, "%s%s%s = %s + %s\n",
$[Link], $[Link], temp, $[Link], $[Link]);
$$.place = temp;
}
| expr MINUS expr {
char* temp = new_temp();
$$.code = (char*)malloc(1000);
sprintf($$.code, "%s%s%s = %s - %s\n",
$[Link], $[Link], temp, $[Link], $[Link]);
$$.place = temp;
}
| expr MULTIPLY expr {
char* temp = new_temp();
$$.code = (char*)malloc(1000);
sprintf($$.code, "%s%s%s = %s * %s\n",
$[Link], $[Link], temp, $[Link], $[Link]);
$$.place = temp;
}
| expr DIVIDE expr {
char* temp = new_temp();
Page 35

 $$.code = (char*)malloc(1000);
sprintf($$.code, "%s%s%s = %s / %s\n",
$[Link], $[Link], temp, $[Link], $[Link]);
$$.place = temp;
}
| LPAREN expr RPAREN {
$$ = $2;
}
;

%%

void yyerror(char *s) {

fprintf(stderr, "Error: %s\n", s);
}

int main(void) {
yyparse();
return 0;
}

[Link] :
x = 5;
y = 10;
if (x < y) then {
max = y;
} else {
max = x;
}
while (x < 100) do {
x = x + 1;
}

Output :

Page 36

 Page 37