● Approved by AICTE, Ministry of HRD, Govt.

of India ●ISO 9001:2015, ISO 14001:2015, ISO 50001:2018

Affiliated: ●VMSB Uttarakhand Technical University ● Sri Dev Suman Uttarakhand University ● Uttarakhand Board of Technical Education

A
Lab Record

Compiler Design
Lab (BCSP-602)

Session: - 2023-24
Department of Computer Science and Engineering

Submitted to Submitted by
Mrs Ritu Pal Satyam Jain
(210120101102) Assistant professor
 INDEX

Teacher’s Remark
S. no. Experiment Name Date
Signature

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.
 EXPERIMENT- 1
OBJECTIVE:

Design a lexical analyzer for given language and 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. Simulate the
same in C language.
PROGRAM:

#include <stdio.h>
#include <stdlib.h>
#include
<string.h>
#include <ctype.h>

#define MAX_IDENTIFIER_LENGTH 50

// Token types
typedef enum {
TOKEN_IDENTIFIER,
TOKEN_INTEGER,
TOKEN_PLUS,
TOKEN_MINUS,
TOKEN_MULTIPLY,
TOKEN_DIVIDE,
TOKEN_ASSIGN,
TOKEN_SEMICOLON,
TOKEN_OPEN_PAREN,
TOKEN_CLOSE_PAREN,
TOKEN_END_OF_INPUT
} TokenType;

// Token structure
typedef struct {
TokenType type;
char value[MAX_IDENTIFIER_LENGTH + 1]; // +1 for null terminator
} Token;

// Function prototypes
void get_next_token(Token *token, FILE *fp);
void skip_whitespace_and_comments(FILE *fp);

int main() {
FILE *fp;
Token token;

// Open file for reading

fp = fopen("input.txt", "r");
 if (fp == NULL) {
perror("Error opening file");
return EXIT_FAILURE;
}

// Get and print tokens until end of

input do {
get_next_token(&token, fp);
switch (token.type) {
case TOKEN_IDENTIFIER:
printf("Identifier: %s\n", token.value);
break;
case TOKEN_INTEGER:
printf("Integer: %s\n",
token.value); break;
case TOKEN_PLUS:
printf("Plus\n");
break;
case TOKEN_MINUS:
printf("Minus\n");
break;
case TOKEN_MULTIPLY:
printf("Multiply\n");
break;
case TOKEN_DIVIDE:
printf("Divide\n");
break;
case TOKEN_ASSIGN:
printf("Assign\n");
break;
case TOKEN_SEMICOLON:
printf("Semicolon\n");
break;
case TOKEN_OPEN_PAREN:
printf("Open Parenthesis\n");
break;
case TOKEN_CLOSE_PAREN:
printf("Close Parenthesis\n");
break;
case TOKEN_END_OF_INPUT:
printf("End of Input\n");
break;
}
} while (token.type != TOKEN_END_OF_INPUT);

// Close file
fclose(fp);

return EXIT_SUCCESS;
}
void get_next_token(Token *token, FILE *fp) {
char c;
int i = 0;

// Skip whitespace and comments

skip_whitespace_and_comments(fp);

// Read characters until a token is

found while ((c = fgetc(fp)) != EOF) {
if (isalpha(c)) {
// Identifier
token->type = TOKEN_IDENTIFIER;
token->value[i++] = c;
while ((c = fgetc(fp)) != EOF && (isalnum(c) || c == '_'))
{ if (i < MAX_IDENTIFIER_LENGTH) {
token->value[i++] = c;
}
}
ungetc(c, fp);
token->value[i] = '\0';
return;
} else if (isdigit(c)) {
// Integer
token->type = TOKEN_INTEGER;
token->value[i++] = c;
while ((c = fgetc(fp)) != EOF && isdigit(c))
{ if (i < MAX_IDENTIFIER_LENGTH) {
token->value[i++] = c;
}
}
ungetc(c, fp);
token->value[i] = '\0';
return;
} else {
// Check for single character
tokens switch (c) {
case '+':
token->type = TOKEN_PLUS;
token->value[0] = c;
token->value[1] = '\0';
return;
case '-':
token->type = TOKEN_MINUS;
token->value[0] = c;
token->value[1] = '\0';
return;
case '*':
token->type =
TOKEN_MULTIPLY; token-
>value[0] = c;
token->value[1] = '\0';
return;
 case '/':
token->type = TOKEN_DIVIDE;
token->value[0] = c;
token->value[1] = '\0';
return;
case '=':
token->type =
TOKEN_ASSIGN; token-
>value[0] = c;
token->value[1] = '\0';
return;
case ';':
token->type =
TOKEN_SEMICOLON; token-
>value[0] = c;
token->value[1] = '\0';
return;
case '(':
token->type =
TOKEN_OPEN_PAREN; token-
>value[0] = c;
token->value[1] = '\0';
return;
case ')':
token->type = TOKEN_CLOSE_PAREN;
token->value[0] = c;
token->value[1] = '\0';
return;
default:
// Ignore unknown
characters break;
}
}
}

// End of input
token->type = TOKEN_END_OF_INPUT;
}

void skip_whitespace_and_comments(FILE *fp)

{ char c;

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

{ if (isspace(c)) {
continue; // Skip whitespace
} else if (c == '/') {
// Check if it's a
comment if ((c =
fgetc(fp)) == '/') {
// Line comment, skip until end of line
while ((c = fgetc(fp)) != EOF && c != '\n') {}
} else if (c == '*') {
// Block comment, skip until end of comment
char prev = '\0';
while ((c = fgetc(fp)) != EOF) {
 if (prev == '*' && c == '/')
{ break;
}
prev = c;
}
} else {
// Not a comment, return '/' back to
input ungetc(c, fp);
return;
}
} else {
// Not whitespace or comment, return character back to
input ungetc(c, fp);
return;
}
}
}
Output
 EXPERIMENT-2
OBJECTIVE:
Write a C program to identify whether a given line is a comment or not.

PROGRAM:

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool is_comment(const char *line) {

if (strlen(line) >= 2 && line[0] == '/' && line[1] == '/') {
return true;
}
return false;
}

int main() {
char line[100];
printf("Enter a line: ");
fgets(line, sizeof(line),
stdin); if (is_comment(line))
{
printf("The line is a comment.\n");
} else {
printf("The line is not a comment.\n");
}
return 0;
}
Output
 EXPERIMENT-3

OBJECTIVE:

Write a C program to recognize strings under 'a*', 'a*b+', 'abb'.

PROGRAM:

#include <stdio.h>
#include <stdbool.h>
#include <string.h>

bool matches_a_star(const char *str) {

for (int i = 0; str[i] != '\0'; i++) {
if (str[i] != 'a') {
return false;
}
}
return true;
}

bool matches_a_b_plus(const char *str) {

if (str[0] != 'a') {
return false;
}
for (int i = 1; str[i] != '\0'; i++) {
if (str[i] != 'b') {
return false;
}
}
return true;
}

bool matches_abb(const char *str) {

return strcmp(str, "abb") == 0;
}

int main() {
char str[100];

printf("Enter a string: ");

fgets(str, sizeof(str),
stdin); str[strcspn(str, "\
n")] = '\0';
 if (matches_a_star(str)) {
printf("The string matches 'a*'.\n");
}
if (matches_a_b_plus(str)) {
printf("The string matches 'a*b+'.\n");
}
if (matches_abb(str)) {
printf("The string matches 'abb'.\n");
}
if (!matches_a_star(str) && !matches_a_b_plus(str) && !matches_abb(str)) {
printf("The string does not match any of the patterns.\n");
}
return 0;
}
 Output

If the user enters "aaa", the output will be

If the user enters "abbb", the output will be:

If the user enters "abb", the output will be:

If the user enters "abc", the output will be:

 EXPERIMENT-4

OBJECTIVE:
Write a C program to test whether a given identifier is valid or not

PROGRAM:

#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>

bool isValidIdentifier(const char *identifier) {

if (strlen(identifier) == 0 || isdigit(identifier[0])) {
return false;
}

for (int i = 0; identifier[i] != '\0'; i++) {

if (!isalnum(identifier[i]) && identifier[i] != '_') {
return false;
}
}

return true;
}

int main() {
char identifier[100];

printf("Enter an identifier:
"); scanf("%s", identifier);

if (isValidIdentifier(identifier)) {
printf("'%s' is a valid identifier.\n", identifier);
} else {
printf("'%s' is not a valid identifier.\n", identifier);
}
 Output

return 0;
}
 EXPERIMENT-5

OBJECTIVE:

Write a C program to simulate lexical analyzer for validating operators.

PROGRAM:

#include <stdio.h>
#include <stdbool.h>
#include <ctype.h>

bool isValidOperator(char ch) {

switch(ch) {
case '+':
case '-':
case '*':
case '/':
case '=':
case '>':
case '<':
case '&':
case '|':
case '^':
case '!':
return true;
default:
return false;
}
}

int main() {
char ch;

printf("Enter an operator:
"); scanf(" %c", &ch);

if (isValidOperator(ch)) {
printf("'%c' is a valid operator.\n", ch);
} else {
printf("'%c' is not a valid operator.\n", ch);
}
 Output

return
}
 EXPERIMENT-6

OBJECTIVE:
Implement the lexical analyzer using JLex, flex or other lexical analyzer generating tools.

PROGRAM:
// lexer.l
%{
#include <stdio.h>
#include <string.h>
%}
%option noyywrap
ID [a-zA-Z][a-zA-Z0-9]*
PLUS \+
MULTIPLY \*
LPAREN \(
RPAREN \)
WS [ \t\n]+
%%
{ID} { printf("ID: %s\n", yytext); }
{PLUS} { printf("PLUS\n"); }
{MULTIPLY} { printf("MULTIPLY\n"); }
{LPAREN} { printf("LPAREN\n"); }
{RPAREN} { printf("RPAREN\n"); }
{WS} { /* Ignore whitespace */ }
. { printf("Error: Invalid character\n"); }
%%
int main() {
yylex();
return 0;

6
INPUT & OUTPUT:

6
 EXPERIMENT-7

OBJECTIVE:
Write a C program for implementing the functionalities of predictive parser for the mini language specified
inNote 1.
PROGRAM:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <ctype.h>
// Define token types
#define ID 1
#define PLUS 2
#define MULTIPLY 3
#define LPAREN 4
#define RPAREN 5
#define END 6
// Define grammar production
rules char *productions[] = {
"E->TE'",
"E'->+TE' | ε",
"T->FT'",
"T'->*FT' | ε",
"F->(E) | id"
};
// Function to get the next token from input
string int getNextToken(char **input) {
// Skip whitespaces
while (**input && isspace(**input))
(*input)++;
// Check for end of
input if (**input == '\0')
return END;
// Check for other
tokens switch (**input)
{
case '+':
(*input)++;
return PLUS;
case '*':
(*input)++;
return MULTIPLY;
case '(':
(*input)++;
return LPAREN;
case ')':
(*input)++;
return RPAREN;
default:
if (isalpha(**input)) {
(*input)++;
return ID;
} else {
printf("Invalid token: %c\n", **input);
6
 exit(1);
}
}
}
// Function to match token
void match(int expected_token, char **input) {
int token = getNextToken(input);
if (token != expected_token) {
printf("Error: Expected token %d, got %d\n", expected_token, token);
exit(1);
}
}
// Function to parse E
void E(char **input);
// Function to parse E'
void E_prime(char **input);
// Function to parse T
void T(char **input);
// Function to parse T'
void T_prime(char **input);
// Function to parse F
void F(char **input);
// Function to parse E
void E(char **input)
{
printf("E -> TE'\n");
T(input);
E_prime(input);
}
// Function to parse E'
void E_prime(char **input) {
int token =
getNextToken(input); if (token
== PLUS) {
printf("E' -> +TE'\
n"); match(PLUS,
input); T(input);
E_prime(input);
} else {
printf("E' -> ε\n");
// Do nothing, epsilon production
}
}
// Function to parse T
void T(char **input)
{
printf("T -> FT'\n");
F(input);
T_prime(input);
}
// Function to parse T'
void T_prime(char **input) {
int token =

6
getNextToken(input); if (token
== MULTIPLY) {
printf("T' -> *FT'\n");
match(MULTIPLY, input);

6
 F(input);
T_prime(input);
} else {
printf("T' -> ε\n");
// Do nothing, epsilon production
}
}
// Function to parse F
void F(char **input)
{
int token =
getNextToken(input); if (token
== LPAREN) {
printf("F -> (E)\n");
match(LPAREN, input);
E(input);
match(RPAREN, input);
} else if (token == ID)
{ printf("F -> id\n");
match(ID, input);
} else {
printf("Error: Invalid token\
n"); exit(1);
}
}
int main() {
char input[100];
printf("Enter the input string: ");
fgets(input, sizeof(input),
stdin);
input[strcspn(input, "\n")] = '\0'; // Remove trailing newline
char *input_ptr =
input; E(&input_ptr);
int token = getNextToken(&input_ptr);
if (token == END) {
printf("Input string is accepted!\n");
} else {
printf("Error: Unexpected token %d\n", token);
}
return 0;
}

6
INPUT & OUTPUT:

6
 EXPERIMENT-8
OBJECTIVE:
*Write a C program for constructing of LL (1) parsing.
PROGRAM:

#include <stdio.h>
#include <stdlib.h>
#include
<string.h>
#include <ctype.h>

#define MAX_STACK_SIZE 100

#define MAX_INPUT_SIZE 100

// Function prototypes
void error();
void push(char);
char pop();
void parse();

// Parsing table
char parsing_table[5][6][4] = {
{ "", "", "", "", "", "" },
{ "", "TE'", "", "TE'", "", "" },
{ "", "", "", "", "ε", "ε" },
{ "", "FT'", "", "FT'", "", "" },
{ "", "", "", "", "ε", "ε" }
};

// Stack
char stack[MAX_STACK_SIZE];
int top = -1;

// Input string
char input[MAX_INPUT_SIZE];
int input_index = 0;

// Push to stack
void push(char symbol) {
if (top >= MAX_STACK_SIZE - 1) {
printf("Stack Overflow\n");
exit(1);
}
stack[++top] = symbol;
}

// Pop from stack

char pop() {
if (top < 0) {
printf("Stack Underflow\n");
6
exit(1);

6
 }
return stack[top--];
}

// Error
function void
error() {
printf("Error: Invalid input\
n"); exit(1);
}

// Parse
void parse() {
push('$'); // Bottom of stack
marker push('E'); // Start symbol

while (1) {
char top_symbol = stack[top];
char lookahead = input[input_index];

if (top_symbol == '$' && lookahead == '$') {

printf("Input string is accepted!\n");
break;
} else if (top_symbol == lookahead)
{ pop();
input_index++;
} else if (top_symbol == 'E' && (lookahead == '(' || isalpha(lookahead))) {
pop();
push('E\'');
push('T');
} else if (top_symbol == 'E' && lookahead == '$')
{ error();
} else if (top_symbol == 'T' && (lookahead == '(' || isalpha(lookahead))) {
pop();
push('T\'');
push('F');
} else if (top_symbol == 'T' && lookahead == '+')
{ error();
} else if (top_symbol == 'T' && lookahead == '*')
{ error();
} else if (top_symbol == 'T' && lookahead == ')')
{ error();
} else if (top_symbol == 'T' && lookahead == '$')
{ error();
} else if (top_symbol == 'E\'' && lookahead == '+')
{ pop();
push('+');
push('T');
push('E\'');
} else if (top_symbol == 'E\'' && lookahead == '$')
{ pop();
} else if (top_symbol == 'T\'' && lookahead == '+') {
6
 error();
} else if (top_symbol == 'T\'' && lookahead == '*')
{ pop();
push('*');
push('F');
push('T\'');
} else if (top_symbol == 'T\'' && lookahead == ')')
{ pop();
} else if (top_symbol == 'T\'' && lookahead == '$')
{ pop();
} else if (top_symbol == 'F' && lookahead == '(')
{ pop();
push(')');
push('E');
push('(');
} else if (top_symbol == 'F' && isalpha(lookahead)) {
pop();
push('d');
} else {
error();
}
}
}

int main() {
printf("Enter the input string:
"); scanf("%s", input);

parse();

return 0;
}

6
INPUT & OUTPUT:

6
 EXPERIMENT-8

OBJECTIVE:
Construction of recursive descent parsing for the
followinggrammar
E->TE' E'->+TE/@ "@ represents
nullcharacter" T->FT'
T`->*FT'/@F->(E)/ID

PROGRAM:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <stdbool.h>
#include <string.h>

// Function prototypes
bool E(char*);
bool E_prime(char*);
bool T(char*);
bool T_prime(char*);
bool F(char*);

// Function to check if a character is an identifier

bool isID(char c) {
return isalnum(c) || c == '_';
}

// Function to skip whitespaces

char* skipWhitespace(char* input) {
while (*input && isspace(*input))
{ input++;
}
return input;
}

// Function to parse
E bool E(char*
input) {
input = skipWhitespace(input);

if (T(input) && E_prime(input)) {

return true;
6
}

6
 return false;
}

// Function to parse E'

bool E_prime(char* input) {
input = skipWhitespace(input);

if (*input == '+') {
input++;
if (T(input) && E_prime(input)) {
return true;
} else {
return false;
}
}

return true; // E' can be empty

}

// Function to parse
T bool T(char*
input) {
input = skipWhitespace(input);

if (F(input) && T_prime(input)) {

return true;
}

return false;
}

// Function to parse T'

bool T_prime(char* input) {
input = skipWhitespace(input);

if (*input == '*') {
input++;
if (F(input) && T_prime(input)) {
return true;
} else {
return false;
}
}

return true; // T' can be empty

}

// Function to parse F
6
bool F(char* input) {
input = skipWhitespace(input);

if (*input == '(') {
input++;
if (E(input) && *input == ')') {
input++;
return true;
}
} else if (isID(*input)) {
while (isID(*input)) {
input++;
}
return true;
}

return false;
}

int main() {
char input[100];

printf("Enter the expression:

"); scanf("%[^\n]", input);

if (E(input) && *input == '\0') {

printf("Expression is valid!\
n");
} else {
printf("Expression is invalid!\n");
}

return 0;
}

6
INPUT & OUTPUT:

6
 EXPERIMENT-9

OBJECTIVE:
Write a program to Design LALR Bottom up Parser
PROGRAM:
#include <stdio.h
#include <stdlib.h>
#include <string.h>

#define MAX_STACK_SIZE 100

#define MAX_INPUT_SIZE 100

// Grammar

char *grammar[] = {
"S->E",
"E->E+T",

"E->T",

"T->T*F",

"T->F",
"F->(E)",
"F->id"

};

// Action table

char *action_table[][7] = {

{" ", "s5", " ", "s4", " ", " ", " "},

{" ", " ", "s6", " ", " ", "accept", " "},

{" ", "r2", "r4", " ", "r2", "r2", "r2"},

{" ", "r4", "r6", " ", "r4", "r4", "r4"},

{" ", "s5", " ", "s4", " ", " ", " "},

6
 {" ", "r6", "r6", " ", "r6", "r6", "r6"},

{" ", "r8", "r8", " ", "r8", "r8", "r8"},

{" ", "s5", " ", "s4", " ", " ", " "},

{" ", "r1", "s6", " ", "r1", "r1", "r1"},

{" ", "r3", "r3", " ", "r3", "r3", "r3"},

{" ", "r5", "r5", " ", "r5", "r5", "r5"},

{" ", "r7", "s6", " ", "r7", "r7", "r7"},

{" ", "r8", "r8", " ", "r8", "r8", "r8"}

};

// Goto table

int goto_table[][4] = {

{1, 2, 3, 0},

{0, 0, 0, 0},

{0, 0, 0, 0},

{0, 0, 0, 0},

{1, 2, 3, 0},

{0, 0, 0, 0},

{0, 0, 0, 0},

{1, 2, 3, 0},

{0, 0, 0, 0},

{0, 0, 0, 0},

{0, 0, 0, 0},

{1, 2, 3, 0},
{0, 0, 0, 0}

};

// Stack

int stack[MAX_STACK_SIZE];
int top = -1;

6
// Input string

char input[MAX_INPUT_SIZE];
int input_index = 0;

// Push to stack
void push(int state) {

if (top >= MAX_STACK_SIZE - 1) {

printf("Stack Overflow\n");
exit(1);
}

stack[++top] = state;
}

// Pop from stack

int pop() {

if (top < 0) {
printf("Stack Underflow\n");
exit(1);
}

return stack[top--];

// Parse
void parse() {

push(0); // Initial state

while (1) {
int state = stack[top];
char lookahead = input[input_index];

// Get action from action table

char *action = action_table[state][lookahead - '0'];

if (action[0] == 's') { // Shift

6
 push(atoi(action + 1));
input_index++;
} else if (action[0] == 'r') { //
Reduce int production =
atoi(action + 1);
int len_rhs = strlen(grammar[production]) - 3; // Length of RHS
for (int i = 0; i < len_rhs; i++) {
pop();

int non_terminal = grammar[production][0] -

'A'; push(goto_table[stack[top]][non_terminal]);

} else if (strcmp(action, "accept") == 0) { //

Accept printf("Input string is accepted!\n");
break;

} else { // Error

printf("Error: Invalid action!\

n"); break;
}

int main() {

printf("Enter the input string:

"); scanf("%s", input);

parse();

return 0;

6
INPUT & OUTPUT:

Input:
grammar:

6
 EXPERIMENT-10

OBJECTIVE:
Program to implement semantic rules to calculate the expression that takes an expression with
digits+ and * and computes the value.

PROGRAM:
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

// Function to evaluate the expression

int evaluateExpression(char *expression)
{ int result = 0;
int num = 0;
char op =
'+';

while (*expression) {
if (isdigit(*expression)) {
num = num * 10 + (*expression - '0');
} else if (*expression == '+' || *expression == '*')
{ if (op == '+') {
result += num;
} else if (op == '*')
{ result *= num;
}
num = 0;
op = *expression;
}
expression++;
}

if (op == '+') {
result += num;
} else if (op == '*')
{ result *= num;
}

return result;
}

int main() {
char expression[100];

printf("Enter the expression:

"); scanf("%s", expression);

6
 int result = evaluateExpression(expression);
printf("Result: %d\n", result);

return 0;
}

6
INPUT & OUTPUT:
Inp

Outp