Maharaja Surajmal Institute of Technology

Affiliated to GGSIPU | NAAC Accredited 'A' Grade | NBA (CSE, IT,

ECE,EEE) | Approved by AICTE | ISO 9001:2015 Certified

Bachelor of Technology (2022-2026)

Department of Information Technology

Compiler Design Lab File

CIC-351

Submitted to: Submitted by:

Ms. Saba Khanum NAME: Sakshi

COURSE: B.Tech - IT(E)
SEM: 5th Semester
ENR. NO.: 35196303122

GAUTAM DAHIYA
35296303122
Department of Information Technology

VISION
To build a culture of innovation and research in students and make them
capable of solving upcoming challenges of human life using computing.

MISSION
M1: To develop 'educational pathways' so that students can take their career
towards success.
M2: To imbibe curiosity and support innovativeness by providing guidance to
use the technology effectively.
M3: To inculcate management skills, integrity and honesty through curricular,
co-curricular and extra-curricular activities.

GAUTAM DAHIYA
35296303122
PROGRAM EDUCATIONAL OBJECTIVES
PEO1. Graduates of IT program are prepared to be employed in IT industries
and be engaged in learning, understanding, and applying new ideas.
PEO2. The graduates are prepared to perform effectively as individuals and
team members in the workplace, growing into highly technical or project
management and leadership roles.
PEO3. Graduates are prepared to apply basic principles of practices of
computing grounded in mathematics and science for successfully completing
software related projects to satisfy customer business objectives and
productively engage in research.
PEO4. Graduates are prepared to pursue higher studies so that they can
contribute to the teaching profession/research and development of information
technology and other allied fields.

PROGRAM OUTCOMES
Engineering Graduates will be able to:
Engineering knowledge: Apply the knowledge of mathematics, science,
engineering fundamentals, and an engineering specialization to the solution of
complex engineering problems.
Problem analysis: Identify, formulate, review research literature, and analyze
complex engineering problems reaching substantiated conclusions using first
principles of mathematics, natural sciences, and engineering sciences.
Design/development of solutions: Design solutions for complex engineering
problems and design system components or processes that meet the specified
needs with appropriate consideration for the public health and safety, and the
cultural, societal, and environmental considerations.
Conduct investigations of complex problems: Use research-based knowledge
and research methods including design of experiments, analysis and
interpretation of data, and synthesis of the information to provide valid
conclusions.
Modern tool usage: Create, select, and apply appropriate techniques,
resources, and modern engineering and IT tools including prediction and
modeling to complex engineering activities with an understanding of the
limitations.

GAUTAM DAHIYA
35296303122
The engineer and society: Apply reasoning informed by the contextual
knowledge to assess societal, health, safety, legal and cultural issues and the
consequent responsibilities relevant to the professional engineering practice.
Environment and sustainability: Understand the impact of the professional
engineering solutions in societal and environmental contexts, and demonstrate
the knowledge of, and need for sustainable development.
Ethics: Apply ethical principles and commit to professional ethics and
responsibilities and norms of the engineering practice.
Individual and team work: Function effectively as an individual, and as a
member or leader indiverse teams, and in multidisciplinary settings.
Communication: Communicate effectively on complex engineering activities
with the engineering community and with society at large, such as, being able
to comprehend and write effective reports and design documentation, make
effective presentations, and give and receive clear instructions.
Project management and finance: Demonstrate knowledge and
understanding of the engineering and management principles and apply these to
one’s own work, as a member and leader in a team, to manage projects and in
multidisciplinary environments.
Life-long learning: Recognize the need for, and have the preparation and
ability to engage in independent and life-long learning in the broadest context
of technological change.

PROGRAM SPECIFIC OUTCOME

PSO-1: Ability to understand the principles and working of hardware and
software aspects in information technology.
PSO-2: Ability to explore and develop innovative ideas to solve real world
problems using IT skills.

GAUTAM DAHIYA
35296303122
 INDEX

S.No. Topic Date Sign

GAUTAM DAHIYA
35296303122
 EXPERIMENT – 1

AIM: Practice of LEX/YACC of compiler writing.

THEORY:
What is a Compiler?
The compiler is software that converts a program written in a high-level language
(Source Language) to a low-level language (Object/Target/Machine Language).
The program written in a high-level language is known as a source program, and the
program converted into a low-level language is known as an object (or target)
program. Without compilation, no program written in a high-level language can be
executed. For every programming language, we have a different compiler; however,
the basic tasks performed by every compiler are the same. The process of translating
the source code into machine code involves several stages, including lexical analysis,
syntax analysis, semantic analysis, code generation, and optimization.
A compiler is an intelligent program as compared to an assembler. Compiler verifies
all types of limits, ranges, errors, etc. Compiler program takes more time to run, and it
occupies huge amount of memory space. The speed of the compiler is slower than
other system software. It takes time because it enters through the program and then
does translation of the full program. When the compiler runs on the same machine
and produces machine code for the same machine on which it is running. Then it is
called self-compiler or resident compiler. The compiler may run on one machine and
produces the machine codes for another computer then in that case it is called cross
compiler.

GAUTAM DAHIYA
35296303122
Why do we need a Compiler?

We need a compiler in the context of compiler design for several essential reasons:

1. High-Level Language Translation: Compilers enable programmers to write

code in high-level languages (like C, Java) that are easier to understand and
more human-readable. The compiler translates this code into machine code
that the computer's hardware can execute.
2. Performance Optimization: Compilers can optimize the code during
translation, improving the program's performance. This includes optimizing
memory usage, execution speed, and reducing redundant operations.
3. Portability: By generating platform-independent intermediate code, compilers
allow programs to be run on different hardware architectures with minimal
changes, enhancing the portability of software.
4. Error Detection: During the compilation process, the compiler checks for
syntax, semantic, and logical errors, helping developers identify and fix issues
early in the development process.
5. Abstraction Management: Compilers manage the complexities of hardware
and system-level details, allowing developers to focus on problem-solving at a
higher level of abstraction without worrying about low-level machine
instructions.
6. Efficiency in Software Development: Compilers automate the translation
process, saving time and reducing the likelihood of errors compared to manual
code translation.

In summary, compilers are crucial in transforming high-level code into executable

machine code, optimizing performance, ensuring portability, detecting errors,
managing abstractions, and enhancing overall software development efficiency.

What are Compiler construction tools?

The compiler writer can use some specialized tools that help in implementing various
phases of a compiler. These tools assist in the creation of an entire compiler or its
parts. Some commonly used compiler construction tools include:

1. Parser Generator – It produces syntax analyzers (parsers) from the input that
is based on a grammatical description of programming language or on
context–free grammar. It is useful as the syntax analysis phase is highly
complex and consumes more manual and compilation time. Example: PIC,
EQM

GAUTAM DAHIYA
35296303122
 2. Scanner Generator – It generates lexical analyzers from the input that
consists of regular expression description based on tokens of a language. It
generates a finite automaton to recognize the regular expression. Example:
Lex

3. Syntax directed translation engines – It generates intermediate code with

three address formats from the input that consists of a parse tree. These
engines have routines to traverse the parse tree and then produce the
intermediate code. In this, each node of the parse tree is associated with one or
more translations.
4. Automatic code generators – It generates the machine language for a target
machine. Each operation of the intermediate language is translated using a
collection of rules and then is taken as an input by the code generator. A
template matching process is used. An intermediate language statement is
replaced by its equivalent machine language statement using templates.
5. Data-flow analysis engines – It is used in code optimization. Data flow
analysis is a key part of code optimization that gathers the information, that is
the values that flow from one part of a program to another.
6. Compiler construction toolkits – It provides an integrated set of routines that
aids in building compiler components or in the construction of various phases
of compiler.

What are the Phases of a Compiler?

GAUTAM DAHIYA
35296303122
We basically have two phases of compilers, namely the Analysis phase and Synthesis
phase. The analysis phase creates an intermediate representation from the given
source code. The synthesis phase creates an equivalent target program from the
intermediate representation. The process of converting the source code into machine
code involves several phases or stages, which are collectively known as the phases of
a compiler. The typical phases of a compiler are:

1. Lexical Analysis: The first phase of a compiler is lexical analysis, also known
as scanning. This phase reads the source code and breaks it into a stream of
tokens, which are the basic units of the programming language. The tokens are
then passed on to the next phase for further processing.
2. Syntax Analysis: The second phase of a compiler is syntax analysis, also
known as parsing. This phase takes the stream of tokens generated by the
lexical analysis phase and checks whether they conform to the grammar of the
programming language. The output of this phase is usually an Abstract Syntax
Tree (AST).
3. Semantic Analysis: The third phase of a compiler is semantic analysis. This
phase checks whether the code is semantically correct, i.e., whether it
conforms to the language’s type system and other semantic rules. In this stage,
the compiler checks the meaning of the source code to ensure that it makes
sense. The compiler performs type checking, which ensures that variables are
used correctly and that operations are performed on compatible data types.
The compiler also checks for other semantic errors, such as undeclared
variables and incorrect function calls.
4. Intermediate Code Generation: The fourth phase of a compiler is
intermediate code generation. This phase generates an intermediate
representation of the source code that can be easily translated into machine
code.
5. Optimization: The fifth phase of a compiler is optimization. This phase
applies various optimization techniques to the intermediate code to improve
the performance of the generated machine code.
6. Code Generation: The final phase of a compiler is code generation. This
phase takes the optimized intermediate code and generates the actual machine
code that can be executed by the target hardware.

GAUTAM DAHIYA
35296303122
What is a Symbol Table in Compiler?
The symbol table is defined as the set of Name and Value pairs.
Symbol Table is an important data structure created and maintained by the compiler
in order to keep track of semantics of variables i.e. it stores information about the
scope and binding information about names, information about instances of various
entities such as variable and function names, classes, objects, etc.
 It is built-in lexical and syntax analysis phases.
 The information is collected by the analysis phases of the compiler and is used by
the synthesis phases of the compiler to generate code.
 It is used by the compiler to achieve compile-time efficiency.
 It is used by various phases of the compiler as follows: -
a. Lexical Analysis: Creates new table entries in the table, for example
entries about tokens.
b. Syntax Analysis: Adds information regarding attribute type, scope,
dimension, line of reference, use, etc. in the table.

GAUTAM DAHIYA
35296303122
 c. Semantic Analysis: Uses available information in the table to check
for semantics i.e. to verify that expressions and assignments are
semantically correct (type checking) and update it accordingly.
d. Intermediate Code generation: Refers symbol table for knowing how
much and what type of run-time is allocated and table helps in adding
temporary variable information.
e. Code Optimization: Uses information present in the symbol table for
machine-dependent optimization.
f. Target Code generation: Generates code by using address
information of identifier present in the table.

What are the Applications of Compilers?

 Helps to make the code independent of the platform.
 Makes the code free of syntax and semantic errors.
 Generate executable files of code.
 Translates the code from one language to another.

Name some Compilers used according to the Computer Languages.

 C– Turbo C, Tiny C Compiler, GCC, Clang, Portable C Compiler
 C+ + - GCC, Clang, Dev C++, Intel C++, Code Block
 JAVA– IntelliJ IDEA, Eclipse IDE, NetBeans, BlueJ, JDeveloper
 Kotlin– IntelliJ IDEA, Eclipse IDE J
 Python– CPython, JPython, Wing, Spyder
 JavaScript– WebStorm, Atom IDE, Visual Studio Code, Komodo

VIVA QUESTIONS

1. What are tokens in lexical analysis?

Tokens are the smallest units of meaning in a program, such as keywords, identifiers,
operators, and literals, identified during lexical analysis.

2. What is the difference between keywords and identifiers?

Keywords are reserved words with a predefined meaning. Identifiers are user-defined
names for variables, functions, etc., and cannot be keywords.

3. How does a compiler handle literals during lexical analysis?

Literals are recognized as specific token types (e.g., numeric or string literals) and
passed to syntax analysis with their values.

GAUTAM DAHIYA
35296303122
4. What role do regular expressions play in lexical analysis?
Regular expressions define patterns for tokens, helping the lexical analyzer identify
and categorize them in the source code.

5. What is the significance of a parse tree?

A parse tree represents the syntactic structure of the program and is essential for
validating grammar and guiding further compilation phases.

6. How are different variable scopes managed in the symbol table?

Scopes are managed using a hierarchical symbol table, where each scope has its own
table, referencing outer scopes when needed.

7. What is the role of lookahead in parsing?

Lookahead allows the parser to peek at upcoming tokens to decide which grammar
rule to apply, preventing ambiguity.

8. How does a compiler handle ambiguous grammar?

The compiler resolves ambiguity by rewriting the grammar, applying precedence
rules, or using backtracking in the parser.

9. What is type checking in semantic analysis?

Type checking verifies that operations are performed on compatible data types,
ensuring correct and safe use of variables and functions.

10. What is constant folding in code optimization?

Constant folding evaluates constant expressions at compile time, reducing runtime
calculations and improving efficiency.

GAUTAM DAHIYA
35296303122
 EXPERIMENT – 2

AIM: Write a program to check whether a string belongs to the

grammar or not.

CODE:
#include <string>

using namespace std;

// Function to check if the string belongs to the given grammar

bool checkGrammar(const string &str) {
int n = str.length();

// If the string is empty, it belongs to the grammar

if (n == 0)
return true;

int aCount = 0;
int bCount = 0;

// Counting number of 'a's and 'b's

for (char c : str) {
if (c == 'a')
aCount++;
else if (c == 'b')
bCount++;
else
return false; // If there is any character other than 'a' or 'b'
}

// To belong to the grammar, the number of 'a's must equal the number of 'b's
// and all 'a's must appear before 'b's.
if (aCount == bCount) {
int i = 0;

// Check that all 'a's are before all 'b's

while (i < n && str[i] == 'a')
i++;

while (i < n && str[i] == 'b')

GAUTAM DAHIYA
35296303122
 i++;

return (i == n);
}

return false;
}

int main() {
string str;
cout << "Enter a string: ";
cin >> str;

if (checkGrammar(str)) {
cout << "The string belongs to the grammar.\n";
} else {
cout << "The string does not belong to the grammar.\n";
}

return 0;
}

OUTPUT:

GAUTAM DAHIYA
35296303122
VIVA QUESTIONS

1. What does it mean for a string to belong to a grammar?

A string belongs to a grammar if it can be generated by following the production rules
defined in that grammar. In other words, the string can be derived starting from the
start symbol of the grammar by applying the rules until the string is produced.

2. What is the difference between a context-free grammar (CFG) and a regular

grammar?
A CFG allows rules where the left-hand side contains a single non-terminal symbol,
and the right-hand side can be a combination of terminal and non-terminal symbols. A
regular grammar is more restricted, where the right-hand side of the rules is usually
limited to a terminal followed by at most one non-terminal (right-linear grammar) or a
non-terminal followed by a terminal (left-linear grammar).

3. Can you describe the basic structure of grammar?

A grammar is typically defined as a 4-tuple G=(V,T,P,S)G = (V, T, P, S)G=(V,T,P,S),
where:
VVV is the set of non-terminal symbols.
TTT is the set of terminal symbols.
PPP is the set of production rules.
SSS is the start symbol.

4. What is a production rule in a grammar?

A production rule defines how non-terminal symbols can be replaced with terminal or
non-terminal symbols. For example, in the rule A→aA, non-terminal A can be
replaced by terminal a followed by non-terminal A.

5. What is a derivation in the context of grammar?

Answer: A derivation is a sequence of applications of production rules starting from
the start symbol and eventually leading to a terminal string. The sequence shows the
step-by-step process of generating the string.

6. How would you approach writing a program to check if a string belongs to a

given grammar?
The program would start by reading the grammar (production rules), then use
techniques such as recursive parsing or parsing tables to check if the input string can
be derived from the start symbol using the production rules. This may involve
constructing a parse tree or using recursive descent parsing.

7. What is recursive descent parsing, and how is it used to check if a string

belongs to a grammar?

GAUTAM DAHIYA
35296303122
Recursive descent parsing is a top-down parsing technique where each non-terminal
in the grammar is associated with a function in the program. These functions
recursively parse the input string by matching the terminals and non-terminals as
specified by the grammar rules.

8. What are the challenges in checking whether a string belongs to a context-free

grammar?

Challenges include handling recursion in the grammar, detecting ambiguity, and

efficiently managing backtracking. Certain strings may require multiple attempts to
find a valid derivation path, making parsing more complex.

9. What are some tools or techniques used to simplify string membership

checking for grammars?
Tools like Finite Automata, Pushdown Automata, and algorithms such as CYK
(Cocke-Younger-Kasami) or Earley’s algorithm can be used to simplify string
membership checking for different types of grammars, particularly context-free
grammars.

10. What is the role of a parsing table in string membership checking?

A parsing table is used in predictive parsers (like LL(1)) to decide which production
rule to apply based on the current input and the top of the parsing stack. It helps to
eliminate backtracking and ensures efficient string membership checking.

GAUTAM DAHIYA
35296303122
 EXPERIMENT – 3

AIM: Write a program to check whether a string includes

keyword or not.

CODE:
#include <iostream>
#include <string>

using namespace std;

// Function to check if the string contains the keyword

bool containsKeyword(const string &str, const string &keyword) {
// Find the keyword in the string
if (str.find(keyword) != string::npos) {
return true;
}
return false;
}

int main() {
string str, keyword;

// Input string
cout << "Enter the string: ";
getline(cin, str);

// Input keyword to search for

cout << "Enter the keyword to search: ";
getline(cin, keyword);

// Check if the string contains the keyword

if (containsKeyword(str, keyword)) {
cout << "The string contains the keyword \"" << keyword << "\".\n";
} else {
cout << "The string does not contain the keyword \"" << keyword << "\".\n";
}

return 0;
}
GAUTAM DAHIYA
35296303122
GAUTAM DAHIYA
35296303122
OUTPUT:

GAUTAM DAHIYA
35296303122
VIVA QUESTIONS

1. What is a keyword in the context of compiler design?

In compiler design, a keyword is a reserved word in a programming language that has
a special meaning and is recognized by the lexical analyzer. Keywords cannot be used
as identifiers like variable names or function names because they are predefined by
the language syntax.

2. What is the role of the lexical analyzer in detecting keywords?

The lexical analyzer, also known as the scanner, is the first phase of a compiler. It
scans the source code character by character, groups them into meaningful sequences
called tokens, and identifies keywords, operators, identifiers, and literals. The lexical
analyzer distinguishes keywords from other tokens using a predefined list of
keywords.

3. How does the lexical analyzer differentiate between a keyword and an

identifier?
The lexical analyzer checks each word against a table or list of keywords. If the token
matches an entry in the keyword list, it is classified as a keyword. If it doesn’t match
any keyword, the token is categorized as an identifier or another type of token.

4. What is a symbol table and how does it relate to keyword detection?

A symbol table is a data structure used by a compiler to store information about
identifiers, including variables, functions, and objects. Keywords are not stored in the
symbol table; instead, they are identified directly by the lexical analyzer, and their
predefined meanings are handled separately.

5. What data structures can be used by the lexical analyzer to store keywords for
checking?
Common data structures used to store keywords include hash tables, arrays, and
tries. Hash tables are often preferred for faster lookup times when checking whether a
string is a keyword.

6. What is a DFA (Deterministic Finite Automaton), and how is it used for

keyword recognition in compilers?
A DFA is a finite state machine used to recognize patterns, such as keywords, in
strings. In the context of a compiler, a DFA can be used to match a sequence of
characters (like a keyword) by moving through states and determining whether the
input string belongs to a valid keyword or identifier class.

7. Can keywords be context-sensitive in a language, and how does the compiler

handle that?
GAUTAM DAHIYA
35296303122
 In some languages, keywords can be context-sensitive, meaning their role depends
on where they appear in the code (e.g., in certain situations, they may act as
keywords, while in others, they can be used as identifiers). The compiler manages this
by considering the grammar and context of the language syntax during semantic
analysis.

8. How would you implement a keyword recognition algorithm in the lexical

analyzer?
A keyword recognition algorithm typically involves the following steps:
a. Read the input character by character to form tokens.
b. Once a token is identified, compare it against the list of known keywords.
c. If the token matches a keyword, classify it as such. If not, classify it as an
identifier or another valid token.

9. What is the significance of token classification in compilers?

Token classification is crucial because it allows the compiler to interpret the source
code correctly. The lexical analyzer must correctly classify tokens such as keywords,
identifiers, operators, and literals to ensure proper syntax analysis and ultimately, the
correct generation of machine code or intermediate representation.

10. What challenges might arise in detecting keywords during lexical analysis?
Some challenges include:
 Ambiguity: If a keyword and an identifier have similar names, the lexer must
ensure proper classification.
 Case Sensitivity: Depending on the language, keywords may be case-sensitive
or case-insensitive.
 Handling Reserved Words: In some languages, previously non-keyword
identifiers can become keywords in newer versions, requiring compilers to
handle both cases.

GAUTAM DAHIYA
35296303122
 EXPERIMENT – 4

AIM: Write a program to remove all left recursion from a

grammar.

CODE:
#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Function to remove left recursion from a given grammar

void removeLeftRecursion(const string& nonTerminal, const vector<string>&
productions) {
vector<string> alpha; // To store A -> Aα productions
vector<string> beta; // To store A -> β productions

for (const string& production : productions) {

if (production[0] == nonTerminal[0]) {
alpha.push_back(production.substr(1)); // Remove the non-terminal from the
start
} else {
beta.push_back(production); // Production is in form of β
}
}

if (alpha.empty()) {
cout << "No left recursion detected for " << nonTerminal << ".\n";
return;
}

// Print the non-left-recursive productions

string newNonTerminal = nonTerminal + "'"; // New non-terminal A'

cout << nonTerminal << " -> ";

for (size_t i = 0; i < beta.size(); ++i) {
cout << beta[i] << newNonTerminal;
if (i < beta.size() - 1)
cout << " | ";
}

GAUTAM DAHIYA
35296303122
 cout << "\n";

cout << newNonTerminal << " -> ";

for (size_t i = 0; i < alpha.size(); ++i) {
cout << alpha[i] << newNonTerminal;
if (i < alpha.size() - 1)
cout << " | ";
}
cout << " | ε\n";
}

int main() {
string nonTerminal;
int numProductions;
vector<string> productions;

cout << "Enter the non-terminal (e.g., A): ";

cin >> nonTerminal;

cout << "Enter the number of productions: ";

cin >> numProductions;

cout << "Enter the productions (e.g., Aa | b):\n";

cin.ignore(); // To ignore the newline character after entering the number
for (int i = 0; i < numProductions; ++i) {
string production;
cout << nonTerminal << " -> ";
getline(cin, production);
productions.push_back(production);
}

// Remove left recursion

removeLeftRecursion(nonTerminal, productions);

return 0;
}

GAUTAM DAHIYA
35296303122
OUTPUT:

GAUTAM DAHIYA
35296303122
 VIVA QUESTIONS

1. What is left recursion in a grammar?

Left recursion occurs in a grammar when a non-terminal in a production rule refers to
itself as the first symbol on the right-hand side. For example, in the rule A→AαA,
where A is a non-terminal and α is a sequence of symbols, the non-terminal A directly
or indirectly calls itself, causing left recursion.

2. Why is left recursion problematic for parsers?

Left recursion is problematic for top-down parsers, such as recursive descent
parsers, because it can lead to infinite recursion. The parser gets stuck in an infinite
loop trying to expand the left-recursive rule repeatedly without making progress on
parsing the input string.

3. What is the difference between direct and indirect left recursion?

 Direct left recursion occurs when a non-terminal directly refers to itself in its
production, e.g., A→Aα.
 Indirect left recursion occurs when a non-terminal refers to itself indirectly
through other non-terminals. For example, A→Bα and B→Aβ form indirect
left recursion.

4. How can left recursion be eliminated from grammar?

Left recursion can be eliminated by transforming the grammar rules. For a production
of the form A→Aα∣β, where β does not begin with A, it can be transformed as
follows:
i. A→βA′
ii. A′→αA′∣ϵ This process creates a new non-terminal A′, and the left
recursion is removed.

5. What is the difference between left recursion and right recursion?

 Left recursion refers to a non-terminal on the left side of the production
calling itself first on the right side, e.g., A→Aα.
 Right recursion occurs when a non-terminal appears at the end of the right-
hand side, e.g., A→αA. Right recursion does not cause problems for top-down
parsers.

6. Can you provide a simple example of removing left recursion from a

grammar?
Consider the grammar:
A→Aα∣β
After removing left recursion, it becomes:
A→βA′

GAUTAM DAHIYA
35296303122
A′→αA′∣ϵ
Here,A′ is a new non-terminal introduced to handle the recursion.

7. What are the key steps in removing left recursion from a grammar?
The key steps are:
i. Identify all left-recursive production rules.
ii. For each left-recursive rule, rewrite the grammar by introducing a new non-
terminal.
iii. Replace the left-recursive rule with new rules that eliminate the recursion.

8. How does eliminating left recursion affect the grammar?

Eliminating left recursion makes the grammar suitable for top-down parsing
techniques like recursive descent parsing. The grammar remains equivalent in terms
of the language it generates, but it no longer causes infinite recursion during parsing.

9. What data structures are typically used to represent grammar in a program

that eliminates left recursion?
Common data structures include:
 Arrays or lists: To store non-terminals and their productions.
 Hash maps: To map each non-terminal to its set of productions. These
structures help efficiently manage the grammar and perform transformations
like removing left recursion.

10. What is the role of epsilon (ϵ) in the transformation process for removing left
recursion?
Answer: In the transformation process, ϵ (representing an empty string) is used in the
production rule of the new non-terminal A′ to allow termination of the recursive
derivation. This ensures that the derivation can end when needed, as A′ can derive ϵ.

GAUTAM DAHIYA
35296303122
 EXPERIMENT – 5

AIM: Write a program to perform Left Factoring on a

Grammar.

CODE:
#include<iostream>
#include<vector>
#include<string>
using namespace std;

// Function to find the common prefix of two strings

string findCommonPrefix(string str1, string str2) {
string result = "";
int n = min(str1.length(), str2.length());

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

if (str1[i] == str2[i]) {
result += str1[i];
} else {
break;
}
}

return result;
}

// Function to perform Left Factoring on grammar

void leftFactoring(vector<string>& productions, char non_terminal) {
string prefix = findCommonPrefix(productions[0], productions[1]);

// If no common prefix is found, no left factoring is required

if (prefix == "") {
cout << "No Left Factoring required for the grammar.\n";
return;
}

// New productions after left factoring

vector<string> factored;
vector<string> remaining;

GAUTAM DAHIYA
35296303122
 for (int i = 0; i < productions.size(); i++) {
if (productions[i].find(prefix) == 0) {
factored.push_back(productions[i].substr(prefix.length()));
} else {
remaining.push_back(productions[i]);
}
}

// Print the result

cout << non_terminal << " -> " << prefix << non_terminal << "'\n";
cout << non_terminal << "' -> ";
for (int i = 0; i < factored.size(); i++) {
if (factored[i] == "") {
cout << "ε";
} else {
cout << factored[i];
}
if (i != factored.size() - 1) {
cout << " | ";
}
}
cout << "\n";

if (!remaining.empty()) {
cout << non_terminal << " -> ";
for (int i = 0; i < remaining.size(); i++) {
cout << remaining[i];
if (i != remaining.size() - 1) {
cout << " | ";
}
}
cout << "\n";
}
}

int main() {
char non_terminal;
int num_productions;

// Input the grammar

cout << "Enter the non-terminal: ";
cin >> non_terminal;
cout << "Enter the number of productions for " << non_terminal << ": ";
GAUTAM DAHIYA
35296303122
 cin >> num_productions;

vector<string> productions(num_productions);
cout << "Enter the productions:\n";
for (int i = 0; i < num_productions; i++) {
cout << non_terminal << " -> ";
cin >> productions[i];
}

// Perform Left Factoring

leftFactoring(productions, non_terminal);

return 0;
}

OUTPUT:

GAUTAM DAHIYA
35296303122
VIVA QUESTIONS

1. What is left factoring in grammar?

Left factoring is a grammar transformation technique used to eliminate common
prefixes from multiple production rules. It helps in resolving ambiguity and preparing
the grammar for top-down parsing by ensuring that no two alternatives for a non-
terminal begin with the same prefix.

2. Why is left factoring necessary in grammar?

Left factoring is necessary to make the grammar suitable for top-down parsers, such
as recursive descent parsers. Without left factoring, the parser may struggle to choose
the correct production rule when alternatives start with the same prefix, leading to
ambiguity.

3. Can you explain the process of left factoring with an example?

Consider the grammar:
A→αβ1 ∣αβ2
The common prefix α can be factored out, resulting in:
A→αA′
A′→β1 ∣β2
This eliminates the ambiguity in selecting the correct rule for A.

4. What problems does left factoring solve in parsing?

Left factoring resolves ambiguity in grammar and ensures that the parser can make a
deterministic choice about which production to use. This is crucial for top-down
parsers that rely on predicting the correct production based on the next input symbol.

5. What is the difference between left recursion and left factoring?

 Left recursion occurs when a non-terminal refers to itself as the first symbol
in its production, leading to infinite recursion in top-down parsers.
 Left factoring deals with removing common prefixes from production rules,
ensuring the parser can differentiate between multiple rules.
While left recursion deals with infinite loops, left factoring addresses ambiguity.

6. What steps are involved in performing left factoring on a grammar?

Answer: The steps to perform left factoring are:
i. Identify the production rules that have a common prefix.
ii. Factor out the common prefix.
iii. Introduce a new non-terminal for the remaining part of the alternatives.
iv. Replace the original rules with the factored-out version.

7. Does left factoring change the language generated by the grammar?

GAUTAM DAHIYA
35296303122
No, left factoring does not change the language generated by the grammar. It only
restructures the grammar to make it easier for parsers to process, without altering the
set of strings that the grammar generates.

8. How does left factoring improve the efficiency of a parser?

Left factoring helps a top-down parser by ensuring that it can always make a
deterministic choice about which production to use without backtracking. This
reduces the number of lookahead symbols needed and makes the parsing process
more efficient.

9. How would you implement a left factoring algorithm in a program?

To implement left factoring in a program:
a. Parse the grammar and identify production rules with common prefixes.
b. Factor out the common prefix into a new rule.
c. Generate the new grammar with the factored-out rules.
d. Output the transformed grammar.

10. What are some common challenges when applying left factoring to
grammar?
Challenges include:
 Identifying deeply nested common prefixes that may not be immediately
obvious.
 Handling grammar with multiple levels of productions that need factoring.
 Ensuring that the transformed grammar remains correct and generates the
same language as the original.

GAUTAM DAHIYA
35296303122
 EXPERIMENT – 6

AIM: Write a program to show all operations on stack.

CODE:
#include <iostream>
#include <stack> // Include stack library
using namespace std;

class StackOperations {
private:
stack<int> s;

public:
// Push operation: Add an element to the stack
void push(int value) {
s.push(value);
cout << "Pushed " << value << " onto the stack." << endl;
}

// Pop operation: Remove the top element from the stack

void pop() {
if (!s.empty()) {
int topValue = s.top();
s.pop();
cout << "Popped " << topValue << " from the stack." << endl;
} else {
cout << "Stack is empty. Nothing to pop." << endl;
}
}

// Peek operation: Get the top element of the stack

void peek() {
if (!s.empty()) {
cout << "Top element is: " << s.top() << endl;
} else {
cout << "Stack is empty. No top element." << endl;
}
}

// Check if the stack is empty

GAUTAM DAHIYA
35296303122
 void isEmpty() {
if (s.empty()) {
cout << "Stack is empty." << endl;
} else {
cout << "Stack is not empty." << endl;
}
}

// Display all elements in the stack

void display() {
if (s.empty()) {
cout << "Stack is empty. Nothing to display." << endl;
return;
}

// Use a temporary stack to display elements

stack<int> tempStack = s;
cout << "Stack elements: ";
while (!tempStack.empty()) {
cout << tempStack.top() << " ";
tempStack.pop();
}
cout << endl;
}

// Get the size of the stack

void size() {
cout << "Stack size: " << s.size() << endl;
}
};

// Main function to demonstrate stack operations

int main() {
StackOperations stackOps;
int choice, value;

do {
cout << "\nStack Operations Menu:\n";
cout << "1. Push\n";
cout << "2. Pop\n";
cout << "3. Peek (Top Element)\n";
cout << "4. Check if Empty\n";
cout << "5. Display Stack\n";
GAUTAM DAHIYA
35296303122
 cout << "6. Stack Size\n";
cout << "0. Exit\n";
cout << "Enter your choice: ";
cin >> choice;

switch (choice) {
case 1:
cout << "Enter value to push: ";
cin >> value;
stackOps.push(value);
break;
case 2:
stackOps.pop();
break;
case 3:
stackOps.peek();
break;
case 4:
stackOps.isEmpty();
break;
case 5:
stackOps.display();
break;
case 6:
stackOps.size();
break;
case 0:
cout << "Exiting..." << endl;
break;
default:
cout << "Invalid choice. Please try again." << endl;
}
} while (choice != 0);

return 0;
}

GAUTAM DAHIYA
35296303122
OUTPUT:

GAUTAM DAHIYA
35296303122
GAUTAM DAHIYA
35296303122
 VIVA QUESTIONS

1. How is the stack used in a compiler?

The stack is used during expression evaluation (e.g., for managing operands and
operators in postfix notation), syntax parsing, and for storing activation records during
function calls.

2. Which data structure is used in parsing techniques like recursive descent?

Recursive descent parsers use the call stack (implicit or explicit) to manage recursive
function calls for grammar rules.

3. How does a stack help in implementing recursion in compilers?

In recursion, the stack stores function call information such as return addresses,
parameters, and local variables, enabling the program to return correctly after each
recursive call.

4. What role does a stack play in syntax-directed translation?

The stack helps in managing intermediate values and semantic attributes during the
translation of syntactic structures, especially in postfix evaluation and three-address
code generation.

5. How is stack overflow related to compiler design?

Stack overflow can occur during deep recursion or excessive function calls, which
compilers must manage by detecting recursion depth or optimizing tail-recursive
calls.

6. Which stack operation is closely related to backtracking in parsing algorithms?

The pop operation is crucial for backtracking parsers, as it undoes decisions made
during parsing when encountering errors or ambiguous grammar.

7. How do LL and LR parsers use the stack?

LL parsers use the stack to store symbols while expanding grammar rules, and LR
parsers use the stack to hold states and grammar symbols during bottom-up parsing.

8. What stack operation is used to resolve reduce actions in LR parsers?

The pop operation is used to remove symbols from the stack when a reduction occurs,
replacing a set of symbols with a non-terminal according to the grammar rules.

9. Can the stack be used for error recovery in parsers?

Yes, the stack can be used to discard incorrect symbols during error recovery and
resume parsing from a known state.

GAUTAM DAHIYA
35296303122
 EXPERIMENT-7

AIM: Write a program to find out the leading of a non-

terminal in a grammar.

Code-
#include <iostream>
#include <unordered_set>
#include <vector>
#include <algorithm>
using namespace std;
using Production = pair<string, string>;
unordered_set<char> findLeading(const vector<Production> &productions, char
nonTerminal) {
unordered_set<char> leading;
for (const auto &production : productions) {
if (production.first[0] == nonTerminal) {
const char firstSymbol = production.second[0];
if (isupper(firstSymbol)) {
leading.insert(firstSymbol);
} else {
leading.insert(production.second.begin(), production.second.end());
}
}
}
return leading;
}
int main() {
vector<Production> productions = {{"S", "aAb"},
{"A", "c"},
{"A", "d"},
{"B", "e"},
{"B", "f"}
};
cout << "Leading of A: ";
for (char symbol : findLeading(productions, 'A')) {
cout << symbol << " ";
}
cout << endl;
cout << "Leading of B: ";
for (char symbol : findLeading(productions, 'B')) {

GAUTAM DAHIYA
35296303122
cout << symbol << " ";
}
cout << endl;
return 0;
}

OUTPUT:

VIVA QUESTIONS

1. What does "leading" of a non-terminal in a grammar mean?

The "leading" of a non-terminal is the set of terminal symbols that can appear as the
first symbols in strings derived from that non-terminal.

2. Why is finding the leading of a non-terminal useful in compiler design?

Leading symbols help in constructing parsing tables and are essential for syntax
analysis in predictive parsing and error detection.

3. What is the difference between "leading" and "FIRST" sets in context-free

grammar?
The terms are sometimes used interchangeably, but "leading" typically refers to
terminals that appear first in derivations specifically in left-to-right derivation, while
"FIRST" set generally refers to all possible terminals that can begin derivations from
a symbol.

4. How does recursion in a grammar affect the calculation of leading symbols?

GAUTAM DAHIYA
35296303122
Recursion, especially left recursion, can cause infinite loops. Therefore, algorithms
must handle recursion by carefully checking previously computed symbols to avoid
repeating calculations.

5. How can epsilon (ε) affect the computation of leading symbols?

If a non-terminal can derive ε, we also consider the leading symbols of the subsequent
symbols in derivations, as ε does not contribute to the terminal symbols in output.

6. How do you calculate the leading of a non-terminal if it has multiple

productions?
Calculate the leading symbols for each production separately, then take the union of
all terminals that appear at the start of each production’s derivation.

7. How does indirect recursion impact the computation of leading sets?

Indirect recursion requires tracking the non-terminals already being processed to
avoid circular dependencies and ensure all reachable leading symbols are captured.

8. If a production rule is A → BC, how do you determine the leading of A?

To find the leading of A, first compute the leading of B (the first non-terminal). If B
can derive ε, also include the leading of C.

9. What data structure is commonly used to store and compute leading sets for
non-terminals?
A set or hash set is commonly used to store the leading symbols, as it ensures unique
terminal symbols and allows for efficient union operations.

GAUTAM DAHIYA
35296303122
 EXPERIMENT-8

AIM: Write a program to Implement Shift Reduce Parsing

for a String.

Code-
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const vector<pair<string, string>> productions = {
{"S", "E"},
{"E", "E+T"},
{"E", "T"},
{"T", "T*F"},
{"T", "F"},
{"F", "(E)"},
{"F", "id"}
};
void shift(stack<string> &p, string &i, int &j) {
p.push(string(1, i[j++]));
}
void reduce(stack<string> &p) {
for (const auto &r : productions) {
string t, s;
for (size_t i = 0; i < r.second.size(); ++i) {
t = p.top() + t;
p.pop();}
if (t != r.second) {
p.push(r.first);
for (char c : t) {
p.push(string(1, c));
}
}
}
}
bool srParser(const string &i) {
stack<string> p;
int j = 0;
while (j < i.size() || p.size() > 1) {
if (j < i.size()) {

GAUTAM DAHIYA
35296303122
shift(p, i, j);
} else {
reduce(p);
}
}
return p.top() == "S";
}
int main() {
string i;
cout << "Enter the input string: ";
cin >> i;
if (srParser(i)) {cout << "Accepted" << endl;
} else {
cout << "Not Accepted" << endl;
}
return 0;
}

OUTPUT:

GAUTAM DAHIYA
35296303122
VIVA QUESTIONS

1. What is Shift-Reduce Parsing?

Shift-Reduce Parsing is a bottom-up parsing technique that involves shifting input
symbols onto a stack and reducing them based on grammar rules to recognize the
string.

2. What are the main actions in Shift-Reduce Parsing?

The main actions are:
Shift: Move the next input symbol onto the stack.
Reduce: Replace a sequence of symbols on the stack with a non-terminal according to
a grammar production.
Accept: Successfully recognize the input string.
Error: Detect a syntax error in the input string.

3. What is the difference between Shift-Reduce Parsing and Recursive Descent

Parsing?
Shift-Reduce Parsing is a bottom-up approach, building the parse tree from leaves to
root, while Recursive Descent Parsing is a top-down approach, starting from the root
and expanding nodes down to leaves.

4. What data structures are typically used in Shift-Reduce Parsing?

A stack is used to hold symbols as they are shifted, and the input buffer holds the
remaining input symbols to be parsed.

5. What is a "handle" in Shift-Reduce Parsing?

A handle is a substring that matches the right-hand side of a production and is
replaced by the corresponding non-terminal in a reduce step.

6. How do you identify when to apply a reduction in Shift-Reduce Parsing?

A reduction is applied when the top of the stack matches the right-hand side of a
production rule, indicating that this sequence can be reduced to a non-terminal.

7. What is a Shift-Reduce Conflict?

A Shift-Reduce Conflict occurs when the parser can either shift the next input symbol
or reduce the current stack symbols, and its unclear which action to take. This often
arises in ambiguous grammar.

8. What is the role of the parsing table in Shift-Reduce Parsing?

GAUTAM DAHIYA
35296303122
The parsing table guides the parser by specifying actions (shift, reduce, accept, or
error) based on the current state and input symbol, helping resolve conflicts in certain
parsing strategies.

9. How is an LR parser related to Shift-Reduce Parsing?

An LR parser is a type of Shift-Reduce Parser that uses lookahead to make more
informed shift or reduce decisions, reducing conflicts and making the parser more
powerful for a broader class of grammars.

10. What would cause a parser to enter an infinite loop during Shift-Reduce
Parsing?
An infinite loop can occur if the parser repeatedly shifts and reduces without making
progress, usually due to improper handling of grammar rules, recursion, or incorrect
parser state transitions.

GAUTAM DAHIYA
35296303122
 EXPERIMENT-9

AIM: Write a program to find the first of the non-terminals

in a given grammar.

Code-
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <string>
using namespace std;
// Function to compute FIRST set of a non-terminal
set<char> compute_first(char symbol, map<char, vector<string>> &productions,
map<char, set<char>>
&first_sets) {
// If symbol is a terminal, return it as the FIRST set
if (islower(symbol) || !isalpha(symbol)) {
return {symbol};
}
// If FIRST set is already computed, return it
if (!first_sets[symbol].empty()) {
return first_sets[symbol];
}
set<char> first; // Initialize the FIRST set
// Iterate over productions for the non-terminal symbol
for (string production : productions[symbol]) {
// If production is empty (epsilon), add epsilon to FIRST
if (production.empty()) {
first.insert('$'); // Let's assume $ represents epsilon
continue;
}
for (char ch : production) {
set<char> char_first = compute_first(ch, productions, first_sets);
// Add non-epsilon elements of the FIRST set of the current character
for (char c : char_first) {
if (c != '$') {
first.insert(c);
}
}

GAUTAM DAHIYA
35296303122
// If epsilon is not in the FIRST set of the current character, stop
if (char_first.find('$') == char_first.end()) {
break;
}
}
// If we finished the loop without breaking, add epsilon to FIRST
if (production == "" || first.find('$') != first.end()) {
first.insert('$');
}
}
// Memoize the result in the FIRST set
first_sets[symbol] = first;
return first;
}// Helper function to print a set
void print_set(set<char> s) {
for (char c : s) {
if (c == '$') cout << "epsilon, ";
else cout << c << ", ";
}
cout << endl;
}
int main() {
// Input grammar: map of non-terminal -> list of productions
map<char, vector<string>> productions;
productions['S'] = {"AC"};
productions['A'] = {"aA", ""}; // epsilon is represented as an empty string
productions['C'] = {"cC", "d"};
// Map to store FIRST sets
map<char, set<char>> first_sets;
// Compute and display FIRST sets for each non-terminal
cout << "Grammar:\n";
for (auto prod : productions) {
char non_terminal = prod.first;
cout << "FIRST(" << non_terminal << ") = { ";
set<char> first = compute_first(non_terminal, productions, first_sets);
print_set(first);
cout << "}" << endl;
}
return 0;
}

GAUTAM DAHIYA
35296303122
OUTPUT:

VIVA QUESTIONS

1. What is the FIRST set of a non-terminal in a grammar?

The FIRST set of a non-terminal is the set of terminal symbols that can appear at the
beginning of any string derived from that non-terminal.

2. Why is the FIRST set important in parsing?

The FIRST set is crucial for constructing parsing tables in LL(1) parsers and helps in
deciding which production to use based on the lookahead symbol.

3. How do you calculate the FIRST set if a non-terminal has multiple

productions?
For each production, compute the FIRST of each symbol from left to right, adding
terminals directly to the FIRST set or recursively finding the FIRST of non-terminals.
If a non-terminal can derive ε, continue checking the next symbols in the production.

4. How does ε (epsilon) affect the FIRST set computation?

If a non-terminal in a production can derive ε, then ε is added to its FIRST set, and the
FIRST computation continues to the next symbols in the production until a terminal
or a non-ε-producing symbol is encountered.

5. What is the difference between the FIRST and FOLLOW sets in grammar?
The FIRST set contains terminals that can appear at the start of derivations of a non-
terminal. The FOLLOW set contains terminals that can appear immediately after a
non-terminal in any derivation.

GAUTAM DAHIYA
35296303122
6. How do you handle left recursion when computing FIRST sets?
Left recursion does not directly affect FIRST set computation. However, left
recursion can make it challenging for LL(1) parsing if not eliminated, since the parser
would encounter an infinite loop without left recursion elimination.

7. What data structure is commonly used to store the FIRST sets?

Sets or hash sets are typically used to store FIRST sets since they avoid duplicates and
allow efficient insertion and union operations.

8. If a production is A → BC, how would you find FIRST(A)?

Compute FIRST(B) and add it to FIRST(A). If B can derive ε, also add FIRST(C) to
FIRST(A).

9. How does indirect recursion affect the computation of FIRST sets?

Indirect recursion can complicate the calculation by creating circular dependencies.
Recursive calls must be carefully managed to ensure that each non-terminal’s FIRST
set is calculated without redundancy or infinite loops.

10. Can a terminal appear in the FIRST set of more than one non-terminal?
Yes, a terminal can appear in the FIRST sets of multiple non-terminals, especially if
multiple non-terminals can derive strings that start with the same terminal.

GAUTAM DAHIYA
35296303122
 EXPERIMENT-10

AIM: Write a program to check whether a grammar is

operator precedent.

Code:
#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;
// Function to check operator precedence
bool isOperatorPrecedence(const vector<string>& productions, const map<char,
int>& precedence) {
for (const string& production : productions) {
// Check each production for operator precedence
for (size_t i = 0; i < production.length() - 1; ++i) {
char current = production[i];
char next = production[i + 1];
// If both characters are operators, check their precedence
if (precedence.count(current) && precedence.count(next)) {
if (precedence.at(current) > precedence.at(next)) {
cout << "Error: " << current << " has higher precedence than " << next << endl;
return false;
}
}
}
}
return true;
}int main() {
// Define grammar productions
vector<string> productions = {
"E -> E + E",
"E -> E * E",
"E -> id"
};
// Define operator precedence
map<char, int> precedence = {
{'+', 1}, // Lower precedence
{'*', 2} // Higher precedence
};
GAUTAM DAHIYA
35296303122
// Check if grammar is operator precedence
if (isOperatorPrecedence(productions, precedence)) {
cout << "The grammar is operator precedence." << endl;
} else {
cout << "The grammar is not operator precedence." << endl;
}
return 0;
}

OUTPUT:

VIVA QUESTIONS

1. What is Operator Precedence Grammar?

Operator Precedence Grammar is a type of grammar where precedence relations are
defined between operators to help parse expressions without ambiguity, mainly used
in expressions with operators like +, *, etc.

2. What are the conditions for grammar to be operator precedence?

The grammar must not have epsilon (ε) productions or non-terminals that derive ε,
and it must not have any ambiguous or left-recursive productions. It should allow
defining precedence relations between terminals.

3. What are the three types of precedence relations in operator precedence

parsing?
The three types of precedence relations are:
i. <. (less precedence): Indicates that an operator has lower precedence than the
following symbol.
ii. =. (equal precedence): Indicates that two symbols have the same precedence.
iii. >. (greater precedence): Indicates that an operator has higher precedence
than the following symbol.
GAUTAM DAHIYA
35296303122
4. Why can’t operator precedence grammars have ε-productions?
Epsilon productions create ambiguity in the precedence relationships between
terminals, as they introduce situations where the presence of terminals can be
inconsistent, complicating parsing decisions.

5. How is a precedence table constructed for operator precedence parsing?

A precedence table is constructed by assigning precedence relations between
terminals based on the operators' priority, helping the parser decide when to shift or
reduce based on operator precedence.

6. How do left-recursive productions affect operator precedence grammars?

Left recursion is not allowed in operator precedence grammars because it creates
ambiguity in the precedence of symbols, leading to infinite loops during parsing.

7. What is the purpose of the precedence relations (<., =., >.) in an operator
precedence parser?
These relations help the parser decide whether to shift the next input symbol or reduce
the current stack contents based on the operators' precedence.

8. How can you detect if a grammar is operator precedence by looking at its

productions?
Check if the grammar has no ε-productions, no left recursion, and if all operators have
well-defined precedence relations that do not conflict, allowing clear precedence
between symbols.

9. Why is it challenging to handle nested operators in operator precedence

grammars?
Nested operators can complicate precedence definitions and lead to ambiguous
interpretations, especially if the grammar lacks clear precedence relations between
operators at different levels.

10. What data structure is commonly used to represent operator precedence

relations in a parser?
A precedence table or matrix is used to represent operator precedence relations, where
rows and columns correspond to operators, and each cell indicates the precedence
relation between the row and column operators.

GAUTAM DAHIYA
35296303122