01. Which component of the compiler performs lexical analysis?

:-scanner
02. What does DFA stand for in lexical analysis?:- Deterministic Finite Automato
03. What is the role of a lexical analyzer? :- To recognize tokens
04. Which of the following tools is commonly used for lexical analysis?:- Lex, Flex, and Jflex
05. Regular expressions are converted to:- Dfa
06. Minimizing DFA helps in: Reducing number of state
07. The role of the parser is to: -Check syntax
08. Top-down parsing is also known as:- Operator precedence parsing
09. Which parser uses look ahead symbols? :- LALR
10. In LR parsing, the shift-reduce action is used to:- Replace handle with non-terminal
11. YACC tool is used for: Lexical analysis
12. Which of the following is not a type of parser :-
13. Intermediate code is:- machine-independent
14. Three-address code typically has:- three operands
15. Type checking is done to ensure:- Type compatibility
16. Which structure is used to represent intermediate code? :- DAG
17. Syntax directed definitions are used in:- Parsing
18. What is the purpose of a syntax-directed translation scheme?
19. The run-time stack is used for:-
20. Heap memory is used for:
21. What is the main issue in code generation?
22. Non-local data can be accessed using:
23. Stack allocation is used for:
24. What is a simple code generator responsible for?
25. Code optimization is done to:
26. Peep-hole optimization is applied to:
27. DAG stands for:
28. What is optimized in basic block optimization?
29. Global data flow analysis helps in:
30. A major goal of data flow analysis is:
Short questions:-
01. Define a compiler. How it works ?
A compiler is a software program that translates source code written in a high-level programming language (like C++ or
Java) into a lower-level language, typically machine code, which a computer can directly execute. It essentially converts
human-readable code into a form the machine understands.

Here's a more detailed explanation of how a compiler works:-

1. 1. Lexical Analysis:

The compiler first analyzes the source code, breaking it down into individual units called tokens (keywords, identifiers, op erators,

punctuation).

2. 2. Syntax Analysis (Parsing):

The compiler then checks if the tokens are arranged according to the language's grammar rules, constructing a parse tree to

represent the code's structure.

3. 3. Semantic Analysis:

This phase verifies the meaning of the code, ensuring that variables are used correctly, that data types are compatible, and that the

program's logic is valid.

4. 4. Intermediate Code Generation:

02. What is lexical analysis?

 Ans:- Lexical analysis, also known as scanning, is the initial phase of a compiler
(or other language processing system) that reads a stream of characters (e.g.,
text) and breaks it down into a sequence of meaningful tokens. These tokens are
then passed to the next phase, typically syntax analysis or parsing, for further
processing.
03. What is the difference between DFA and NFA?
Ans:-
Feature DFA NFA

State Transitions Single transition per input symbol Multiple transitions per input symbol

Empty String No empty string transitions Can have empty string transitions

Structure Single machine Multiple machines (concurrently)

Determinism Deterministic (predictable) Nondeterministic (multiple paths)

Computational Power Same as NFA (equivalent in power) Same as DFA (equivalent in power)

04. How is input buffering handled?

Ans:- Input buffering temporarily stores user or device input before it's processed
by the system. This helps to smooth user interaction, prevent data loss, and
improve system efficiency. It's often used in compiler design, operating systems,
and even game development for more responsive control.

05. What is a context-free grammar?

Ans:- A Context-Free Grammar (CFG) is a formal system used to define the
syntax of a language, particularly in computer science. It consists of a set of
production rules that specify how symbols (terminals and non-terminals) can be
combined to form valid sentences or strings. CFGs are essential for parsing and
understanding the structure of programming languages and other formal
systems.
06. Define LL(1) grammar.
Ans:- An LL(1) grammar is a type of context-free grammar that can be parsed by
an LL(1) parser, which is a top-down parser. The name LL(1) signifies that the
parser reads the input from left to right, producing a leftmost derivation, and uses
only one input symbol (lookahead) to make parsing decisions at each step.
07. What is the difference between top-down and bottom-up parsing?
Ans:- op-down and bottom-up parsing are two primary approaches to parsing, a
process used to analyze the structure of a string of text or code based on a
grammar. Top-down parsing starts with the start symbol of the grammar and
attempts to derive the input string, while bottom-up parsing starts with the input
string and tries to reduce it to the start symbol.
 08.What is a shift-reduce parser?
ans:- A shift-reduce parser is a type of bottom-up parsing method that uses a
stack to analyze an input string. It works by shifting input symbols onto the stack
and reducing them based on grammar rules until a valid parse is achieved,
meaning the entire input string has been parsed according to the grammar.
08. What is a three-address code?
Ans:- Three-address code (TAC) is a type of intermediate code used in
compilers. It represents instructions that use at most three operands: two for the
inputs and one for the output/result. These instructions are generally simple and
easy to translate into machine code, making them a convenient intermediate
representation for optimization purposes.
09. What is the purpose of syntax-directed definitions?
Ans:- Syntax-directed definitions (SDD) serve as a mechanism for associating
semantic information with the syntax of a language by attaching attributes to
grammar symbols and defining semantic rules for computing their values. These
attributes can then be used to perform actions like type checking, expression
evaluation, or code generation, making SDDs a valuable tool in compiler design.
10. What is type checking?
Ans:- Type checking is a process in programming languages where the compiler
or interpreter verifies that operations in a program are performed on compatible
data types. It ensures that variables, expressions, and functions adhere to the
type rules of the language, preventing potential errors. This process can be
performed either at compile time (static type checking) or during program
execution (dynamic type checking).
11. Differentiate between syntax tree and DAG.
Ans:- A syntax tree represents the hierarchical structure of a language or
expression, while a Directed Acyclic Graph (DAG) represents dependencies and
can be used to optimize code. Syntax trees are primarily used for parsing and
semantic analysis, while DAGs are often used in compiler optimization and for
representing data dependencies.
12. What is storage organization in a compiler?
Ans:- n a compiler, storage organization refers to the way the compiler allocates
and manages memory for different data structures and objects during program
execution. This involves deciding where and how to store data, such as variables,
constants, and data structures, in memory to ensure efficient program operation.
13. Define stack allocation.
Ans:- Stack allocation refers to allocating memory for variables and data
structures within a function's or procedure's execution context, typically on the
"stack". This memory is automatically allocated when the function is called and
deallocated when it returns, following a Last-In, First-Out (LIFO) principle.
14. How does a compiler manage heap memory?
Ans:- A compiler generally doesn't manage heap memory directly; it relies on the
operating system and the runtime environment (like a JVM) for heap
management. The compiler's primary role is to generate machine code that, at
runtime, requests memory from the operating system or the runtime
environment's memory manager.
 15. What is the use of an activation record?
Ans:- An activation record, also known as a stack frame, is a data structure used
in programming to store information associated with a single procedure call. It
holds details like parameters, local variables, and the return address, facilitating
the management of function calls and returns. Essentially, it's a temporary
memory region allocated when a procedure is called and deallocated when it
returns.
16. Define code optimization.
Ans:- Code optimization in computer science refers to the process of modifying a
software system to improve its efficiency and performance, such as reducing
execution time or memory usage. It involves making the code run faster, use
fewer resources, and be more efficient without altering the program's
functionality.
17. What is peep-hole optimization?
Ans:- Peephole optimization is a compiler technique that enhances code
performance by examining a small window (the "peephole") of machine code and
replacing sequences of instructions with shorter or more efficient
equivalents. This technique focuses on local improvements, addressing
inefficiencies within a limited code segment.
18. Explain the structure of a compiler in detail.
Ans:- A compiler translates high-level programming language into machine code. This
process is typically divided into several phases, each with a specific role in transforming
the source code into an executable form. The main phases are lexical analysis, syntax
analysis, semantic analysis, intermediate code generation, code optimization, and code
generation.

1. Lexical Analysis (Scanning):

 Task: Reads the source code character by character and groups them into meaningful units called
tokens (keywords, identifiers, operators, punctuation).
 Example: "if", "x", "+", "=", "10" would be recognized as separate tokens.
2. Syntax Analysis (Parsing):
 Task:
Checks if the tokens are arranged according to the language's grammar rules. It builds a parse
tree to represent the structure of the program.
 Example:
Checks if an "if" statement is correctly formed, with the condition, then, and else clauses.
19. Describe the process of lexical analysis with an example.
Ans:- Lexical analysis, also called scanning, is the first phase of a compiler that reads
the input source code, character by character, and groups them into meaningful units
called tokens. These tokens are then passed to the next phase, the syntax analyzer.
Here's a breakdown of the process with an example:

1. Input:
 The lexical analyzer receives the source code as input.
  For example, let's consider the C code: int a = 10;
2. Scanning:
 The lexical analyzer reads the source code character by character.
 It identifies sequences of characters that form tokens.
3. Token Recognition:
 The lexical analyzer uses a set of rules (usually defined using regular expressions) to recognize
different types of tokens.
 For example:
o int: A keyword (or reserved word)

o a: An identifier
o =: An assignment operator
o 10: An integer constant
o ;:A semicolon (a punctuation mark)
20. Convert a regular expression into a DFA and minimize it.
Ans:- To convert a regular expression to a minimized DFA, the process involves three
main steps: first, converting the regular expression to an NFA, then converting the NFA
to a DFA, and finally, minimizing the DFA.

1. Regular Expression to NFA:

 Thompson's Construction:
This algorithm builds an NFA incrementally from the regular expression by applying rules for
operators like concatenation, union, and Kleene star.
 Graphical Representation:
NFA is typically represented graphically with states and transitions, where a transition can occur
on an input symbol or an epsilon (empty string).
2. NFA to DFA:
 Subset Construction:
This algorithm takes the NFA and constructs an equivalent DFA. It works by exploring all
possible subsets of NFA states.
 Epsilon Closure:
For each state, calculate the epsilon closure, which is the set of states reachable from the
current state by following epsilon transitions.
 DFA Transitions:
For each symbol, determine the next state by following the transitions from the current subset of
NFA states.
21. Explain the construction of an SLR parsing table.
Ans:- An SLR parsing table is constructed by first finding the LR(0) items and their
associated GOTO functions, then determining the parsing actions (shift, reduce,
accept) based on the items and their FOLLOW sets. Finally, the GOTO transitions are
filled in the table.
 Here's a step-by-step breakdown:
1. 1. Augmented Grammar:
Create the augmented grammar, which adds a new start symbol (S') to the original grammar with
a single production S' -> S. This is essential for the parsing process.
2. 2. LR(0) Item Sets:
Calculate the closure and GOTO functions of the LR(0) items for the augmented grammar. This
involves:
 Closure: For a given set of LR(0) items, consider all items that can be derived from the items in the
set by shifting the dot to the right and then finding their closures.
 GOTO: For a set of items and a terminal or non-terminal symbol, the GOTO function determines the
set of items reachable by shifting the dot on the item to the right of the symbol.
22. Describe recursive descent parsing with a sample grammar.
Ans:- A recursive descent parser is a top-down parser that processes input
based on a set of recursive functions, where each function corresponds
to a grammar rule. It parses the input from left to right, constructing a
parse tree by matching the grammar's production rules.
23. Write a grammar for arithmetic expressions and construct its LL(1) table.
Ans:- Here's an LL(1) grammar for arithmetic expressions and its corresponding
parsing table.

Grammar:
Code
E -> T E'
E' -> +TE' | ε
T -> F T'
T' -> *FT' | ε
F -> (E) | num

Where:
 E represents an expression.
 E' represents the additive part of an expression.
 T represents a term.
 T' represents the multiplicative part of a term.
 F represents a factor.
 num represents a numerical value.
 +, *, (, ), num are terminals.
LL(1) Parsing Table:
The table shows which production rule to use based on the current non-terminal and
the next input symbol.
24. Discuss different forms of intermediate code with examples.
Ans:- Intermediate code represents the output of the compilation process before
generating target machine code. It serves as a bridge between the source code and the
 machine code, allowing for optimization and portability. Different forms of intermediate
code include postfix notation, syntax trees, three-address code, quadruples, and
triples.

1. Postfix Notation:
 Description:
A linear representation where operators follow their operands. Parentheses are not needed, as
the operator's position and arity determine the expression's structure.
 Example:
The expression a + b * c in infix notation can be represented as abc*+ in postfix notation.
2. Syntax Tree:
 Description:
An abstract representation of the parse tree, where each node represents an operation or value
and links represent the relationships between nodes.
25. Explain syntax-directed translation with evaluation order.
Ans:- Syntax-directed translation (SDT) uses a context-free grammar to parse code
and associates semantic actions with grammar rules to perform actions during
parsing. Evaluation order in SDT refers to the sequence in which semantic actions are
executed while processing the parse tree. Essentially, it dictates the order in which
attribute values are computed and used during translation.

Elaboration:
1. 1. Syntax-Directed Translation:
SDT is a technique where parsing and translation are combined. Each grammar rule is linked to
a semantic action, which specifies how the translation should occur. These actions can evaluate
expressions, check types, generate code, or handle errors.
2. 2. Attributes:
SDT introduces attributes to grammar symbols. These attributes store semantic information, like
the value of an expression or the type of a variable. Attributes can be inherited (passed from
parent nodes to child nodes) or synthesized (computed by the child nodes and passed back to
the parent).
26. Translate an expression into three-address code and explain type checking
Ans:- Three-address code (TAC) translates a source language expression into a
sequence of instructions where each instruction has at most three operands (x, y, z)
and one operator. Type checking, a part of semantic analysis, ensures that all
operations are performed on compatible data types, preventing errors.

Translating an Expression to Three-Address Code:

Consider the expression: a = b * (c + d) - e

1. Break down the expression into smaller steps:

o t1 = c + d
 o t2 = b * t1

o t3 = t2 - e

o a = t3
2. Convert each step into a three-address statement:
o t1 = c + d

o t2 = b * t1

o t3 = t2 - e

o a = t3
Explanation:
 Each line represents a three-address statement.
 Temporary variables (t1, t2, t3) are used to store intermediate results.
27. Explain the run-time environment and memory management.
Ans:- The runtime environment and memory management are essential for a program's
execution. The runtime environment is the state of the machine during program
execution, including environment variables, software libraries, and other elements that
manage the running processes. Memory management is the process of allocating and
deallocating memory to different parts of the program as needed.

Runtime Environment:
 Purpose:
The runtime environment provides the necessary infrastructure for a program to run, including
hardware resources, software libraries, and system services.
 Components:
It encompasses environment variables, software libraries, and other elements that manage the
system's running processes.
28. Describe access to non-local data on the stack.
Ans:- Accessing non-local data on the stack, often referred to as "non-local" or
"external" data, involves techniques to locate variables and data within the scope of a
function's caller or an enclosing procedure. There are primarily two strategies: access
links and displays.

Access Links:
 What they are:
Access links are pointers embedded within each activation record on the stack. They point to the
activation record of the procedure that encloses the current function.
 How they work:
To access a non-local variable, the current function follows the access link to find the activation
record of the enclosing procedure. From there, the variable's location within that record can be
accessed.
29. Design a simple code generator and discuss the steps involved
 Ans:- he Code Generation Algorithm
1. Set location L = getreg(y, z) to store the result of y op z.
2. If y Ï L then generate. MOV y',L. ...
3. Generate. OP z',L. ...
4. If y and/or z has no next use and is stored in register, update register descriptors to remove y and/or z.

30. Describe different code optimization techniques.

Ans:- Code optimization involves improving the efficiency of code by reducing the number of
instructions executed, memory usage, and execution time. This can be achieved through various
techniques, including loop optimization, dead code elimination, constant propagation, and code
motion, which can be applied at both the compiler and runtime levels.

Code Optimization Techniques:

1. Loop Optimization:
 Loop Unrolling: Replicates the loop body multiple times to reduce loop overhead.
 Loop Invariant Code Motion: Moves code that doesn't change within the loop outside of it to
reduce redundancy.
 Loop Fusion: Combines adjacent loops into a single loop to improve efficiency.
 Loop Fission: Splits a loop into multiple loops to improve optimization opportunities.
31. Explain DAG construction and its use in optimization.

Ans:- A Directed Acyclic Graph (DAG) is a graph where nodes are connected by
directed edges, and there are no cycles. In the context of compiler design and
optimization, a DAG is constructed to represent the control flow and data dependencies
within a program's basic blocks. This representation is then used to perform various
optimization techniques, such as common subexpression elimination and constant
folding, to improve the efficiency of the generated code.
Here's a more detailed explanation:

1. What is a DAG?
 A DAG is a graph where each edge has a direction (from one node to another), and following the
edges will never form a closed loop.
 It's used to represent relationships between nodes, where the relationships are usually
represented as dependencies or control flow.
2. Construction of a DAG in Compiler Design:
 Basic Blocks:
DAGs are typically constructed for each basic block, which is a sequence of instructions that
executes sequentially without any jumps in the middle.
32. What is global data flow analysis? Discuss with examples
Ans:- Global data flow analysis analyzes how data flows throughout an entire program,
including across functions and through object properties. It's a powerful technique used
in compiler optimization and code security analysis. Unlike local analysis, which
 focuses on a specific area of code, global analysis considers the entire program's
scope.

Key Concepts:
 Control Flow Graph (CFG):
Programs are represented as graphs where nodes are statements and edges represent control
flow (e.g., sequence, conditionals, loops).
 Reaching Definitions:
Determining which definitions (assignments) of a variable reach a particular point in the
program.