Compiler Design Study Guide

This study guide compiles the key theory, solved question types, and
recurring exam-style patterns discussed across recent BRAC
University CSE 420 midterm papers from Spring 2025, Summer 2025,
and Fall 2025. It is organized section-wise to match the course
syllabus and to support both theory preparation and problem-solving
practice. [1][2][3][4][5][6]

1. Introduction to Compiler
A compiler is a software system that translates a source program
written in a high-level language into an equivalent target program,
often machine code or intermediate code. The translated program
should preserve the meaning of the original source while making it
executable on a machine. [6]

Structure and stages of a compiler

The major phases of a compiler are:
Lexical analysis
Syntax analysis
Semantic analysis
Intermediate code generation
Code optimization
Code generation
These phases are often grouped into the front end and the back end.
The front end analyzes the source program, while the back end
synthesizes target code from the analyzed form. [6]

Analysis-synthesis model
The analysis phase breaks the source program into progressively
more meaningful structures, such as tokens, parse trees, and
semantically checked forms. The synthesis phase uses those analyzed
representations to generate output code. This is why compiler design
is often described as an analysis-synthesis process. [6]

Compiler vs interpreter
A compiler translates the whole program before execution, while an
interpreter usually translates and executes one statement at a time.
Compilers generally produce faster executable output, whereas
interpreters provide quicker stepwise execution feedback. [6]

Theory questions
Q: What is the goal of compiler error recovery during syntax
analysis?
A compiler attempts to detect syntax errors, report them clearly, and
recover in a way that allows parsing to continue so that more errors
can be found in a single run. Common recovery methods include
panic mode, phrase-level recovery, error productions, and global
correction. [6]

Q: Why are the front end and back end separated?

The separation improves modularity and allows the same front end
to support different target machines, or the same back end to support
different source languages with suitable front ends. [6]

2. Introduction to Lexical Analysis

The lexical analyzer reads the raw stream of characters from the
source program and groups them into tokens such as identifiers,
keywords, operators, and numbers. It removes irrelevant characters
like spaces and comments, and passes a clean token stream to the
parser. [2]

Tokens, patterns, and attributes

A token is a category such as id, num, or if.
A pattern describes the form of lexemes belonging to a token.
A token attribute stores extra information, such as a pointer to
a symbol table entry or a numeric value. [2]
Regular definitions
Lexical analyzers often use regular definitions and regular
expressions to describe token classes. This works because most
lexical structures of programming languages are regular. [2]

Structure of a generated lexical analyzer

A FLEX specification is converted into a C scanner program that uses
regular-expression rules to match the longest possible input prefix. If
two rules match the same longest input, the one appearing earlier in
the specification is selected. [2]

Solved question pattern: FLEX internal working

mechanism
A typical answer should mention three ideas:
1. A lex/FLEX file is converted into a C scanner program.
2. The generated scanner processes input left to right and identifies
lexemes using regular expressions.
3. It returns tokens to the syntax analyzer, often with attributes
such as symbol table references. [2]

Theory questions
Q: What is the role of a lexical analyzer?
The lexical analyzer converts characters into tokens, removes white
space and comments, identifies lexical errors, and provides token
attributes to later phases. [2]

Q: How does a lexical analyzer distinguish keywords from

identifiers?
It usually matches the lexeme using the identifier pattern first, then
checks whether the recognized lexeme belongs to the reserved
keyword list. [2]
Q: Why are regular expressions suitable for lexical analysis?
Most token classes such as identifiers, numbers, and operators can be
described by regular languages, so regular expressions provide a
compact and efficient recognition method. [2]

3. Introduction to Syntax Analysis

The parser receives tokens from the lexical analyzer and checks
whether they form a valid sentence of the language according to a
context-free grammar. It also helps construct parse trees and other
structural representations. [3][4]

Context-free grammars
A context-free grammar consists of terminals, nonterminals,
productions, and a start symbol. It is used to define the syntactic
structure of programming languages. [3][4]

Parse trees and derivations

A derivation shows how a string is generated from the start symbol.
A parse tree visually represents that derivation using grammar
symbols as nodes. [3][4]

Ambiguity and mitigation

A grammar is ambiguous if at least one string has more than one
parse tree. This is dangerous because a compiler needs one unique
structure for semantic analysis and code generation. A common fix is
to rewrite the grammar to encode precedence and associativity. [1][2]

Solved question pattern: Why ambiguous CFG cannot be

used in compiler syntax analysis
An ambiguous grammar cannot reliably be used for syntax analysis
because the same string can produce different parse trees and
therefore different meanings. For example, id + id * id may represent
either (id + id) * id or id + (id * id). [1][2]
Theory questions
Q: What is the role of a parser?
The parser checks whether the token stream follows the grammar of
the language and identifies the structural relationship among tokens.
[3][4]

Q: What is the difference between leftmost and rightmost

derivation?
In leftmost derivation, the leftmost nonterminal is expanded at each
step. In rightmost derivation, the rightmost nonterminal is expanded
at each step. [3][4]

Q: Why is ambiguity a serious problem?

Ambiguity causes multiple valid parse trees for the same input, which
can lead to inconsistent semantic interpretation and code generation.
[1][2]

4. Introduction to Bottom-up Parsing

Bottom-up parsing starts from the input string and repeatedly
reduces substrings to nonterminals until the start symbol is obtained.
It is closely related to constructing a rightmost derivation in reverse.
[5][6]

Concept of reduction
A reduction replaces a substring matching the right-hand side of a
production with the corresponding left-hand side nonterminal. [5][6]

Shift-reduce parsing
Shift-reduce parsing uses a stack and an input buffer. A shift moves
the next input token onto the stack, and a reduce replaces a
recognized handle with a nonterminal. [5][6]
Handles and handle pruning
A handle is the substring that should be reduced at a particular step
in a rightmost derivation in reverse. Handle pruning repeatedly
performs such reductions until only the start symbol remains. [5][6]

Theory questions
Q: What is a handle?
A handle is the correct substring to reduce in a bottom-up parser so
that the derivation can be reversed properly. [5][6]

Q: Why is bottom-up parsing called rightmost derivation in

reverse?
Because every reduction undoes one step of a rightmost derivation.
[5][6]

Q: What is the difference between shift and reduce?

Shift pushes the next input token onto the stack, whereas reduce
replaces a recognized pattern on the stack with a nonterminal. [5][6]

5. Introduction to Simple LR Parsing

LR parsing is a bottom-up method that reads input from left to right
and constructs a rightmost derivation in reverse. The number inside
parentheses indicates the amount of lookahead used. [7][8]

Lookahead, LR(0), and SLR(1)

Lookahead means the parser may inspect the next one or more input
symbols before deciding what action to take. LR(0) uses no lookahead
at all, while SLR(1) uses one-symbol lookahead indirectly through
FOLLOW sets. [7][8][9]

LR(0) items
An LR(0) item is a production with a dot showing parser progress,
such as A -> X . Y. The dot indicates how much of the right-hand side
has already been seen. [8][9]
Closure of LR(0) item set
If the dot is before a nonterminal, closure adds the productions of
that nonterminal with the dot at the beginning. This ensures the
parser state includes all possible next expansions. [8][10]

LR(0) automaton construction

The LR(0) automaton is built from item sets and transitions on
grammar symbols. Each state is a set of LR(0) items, and each DFA
transition corresponds to moving the dot over a symbol. [8][10]

Important conceptual question: Do we need LR(0)

automaton for SLR(1)?
Yes. SLR(1) is constructed on top of the LR(0) automaton. The states
and transitions come from LR(0); then FOLLOW sets are used to
control where reductions are placed. [8][10]

Theory questions
Q: What does LR mean?
L means scanning the input from left to right, and R means
constructing a rightmost derivation in reverse. [7]

Q: What is the difference between LR(0) and SLR(1)?

LR(0) uses only parser states and no lookahead. SLR(1) uses the same
LR(0) states, but reduce actions are placed only on FOLLOW sets,
which provides one-symbol guidance. [8][9]

Q: What is lookahead?
Lookahead is the number of next input symbols the parser considers
before choosing an action such as shift or reduce. [7][8]

6. Construction of SLR Parsing Table

To construct an SLR(1) parser, the standard steps are:
1. Augment the grammar.
2. Compute FIRST and FOLLOW sets.
 3. Build the canonical LR(0) item sets.
4. Construct the LR(0) automaton.
5. Fill the ACTION table.
6. Fill the GOTO table. [1][2][8]

FIRST and FOLLOW computation

FIRST tells what terminals can begin strings derived from a symbol.
FOLLOW tells what terminals may appear immediately after a
nonterminal in some sentential form. [3][4]
A standard FOLLOW rule is:
If S -> α X β, then FOLLOW(X) includes FIRST(β) except ε.
If β => ε, then FOLLOW(X) also includes FOLLOW(S). [3][4]

Solved theory question: Why does this FOLLOW

property hold?
Because anything derivable from β may appear immediately after X
in the sentential form. If β can disappear, then whatever follows S can
also follow X. [3][4]

Solved question pattern: SLR(1) construction

For the grammar from Spring 2025 Set A:
A -> B A C
B -> x
C -> y
A -> w
A -> ε [2]
A correct answer should include:
Augmented grammar
FIRST and FOLLOW sets
LR(0) item sets and automaton
ACTION table
GOTO table [2]
For the grammar from Spring 2025 Set B:
 A -> B A C
B -> x
C -> y
C -> w
A -> ε [1]
The same method applies, but the FIRST/FOLLOW results and
reduction placements change because the grammar differs. [1]

Conflict questions
A shift-reduce conflict happens when a state suggests both shifting a
symbol and reducing a production. A reduce-reduce conflict
happens when two reductions are possible in the same context. [5]
A shift-reduce conflict may disappear in SLR(1) if the reduce action is
restricted to FOLLOW of the left-hand side and the conflicting
terminal is not in that FOLLOW set. [3][4][9]
A shift-shift conflict cannot happen because the LR automaton is
deterministic, so a state cannot have two different shift transitions on
the same terminal. [5]

Theory questions
Q: Why do we augment a grammar?
Augmentation gives the parser a unique start production and a clear
accepting configuration. [8]

Q: What is the ACTION table?

The ACTION table tells the parser whether to shift, reduce, accept, or
signal an error for a given state and terminal. [1][2]

Q: What is the GOTO table?

The GOTO table tells the parser which state to move to after reducing
to a nonterminal. [1][2]
Q: Why are FOLLOW sets used in SLR(1)?
FOLLOW sets restrict reduction entries to only the lookaheads that
can legally follow the reduced nonterminal. [8][9]

7. SLR Parsing Algorithm

An SLR parser uses a stack of states and symbols together with the
ACTION and GOTO tables. On each step, it consults the current state
and the next input token. [1][2][3][4]

Runtime behavior
If ACTION says shift, push the token and next state.
If ACTION says reduce, pop symbols corresponding to the right-
hand side, then push the left-hand side and the state from GOTO.
If ACTION says accept, parsing succeeds.
If no valid action exists, it is a syntax error. [1][2][3][4]

Solved parsing simulations

Spring 2025 Set A
The provided SLR table is used to parse ((id + (id))), and the input is
accepted through a sequence of shift and reduce operations using the
grammar:
E -> E + T
E -> T
T -> T * F
T -> F
F -> (E)
F -> id [2]

Spring 2025 Set B

The same table structure is used to parse ((id * (id))), and the string is
also accepted. [1]
Fall 2025 Set A
The input while id do end is checked against the provided parsing
table, and the task is to simulate the parser step by step to determine
whether the string is syntactically valid. [3]

Fall 2025 Set B

The input if id do end is simulated similarly using the corresponding
parsing table. [4]

Summer 2025 Set A

The input if (a) while (a) a is tested using the given CFG, LR(0)
automaton, FIRST/FOLLOW sets, and SLR table. [6]

Summer 2025 Set B

The input while (a) if (a) a is tested the same way. [5]

Theory questions
Q: What happens during a shift action?
The parser pushes the current input symbol and the target state onto
the stack, then moves the input pointer ahead. [1][2]

Q: What happens during a reduce action?

The parser pops the stack according to the production’s right-hand
side, then pushes the left-hand side nonterminal and the
corresponding GOTO state. [1][2]

Q: What does accept mean?

It means the full input has been parsed successfully and corresponds
to the start symbol. [1][2]

8. Symbol Table
A symbol table is a compiler data structure that stores information
about identifiers such as variables and functions. Typical attributes
include name, type, scope, size, memory location, and parameter
information. [1][5][6]
Importance of symbol tables
The symbol table helps lexical analysis, semantic analysis, and code
generation. It supports declaration checking, type checking, scope
management, and address allocation. [5][6]

Scopes and nesting

In block-structured languages, nested scopes are handled using
nested symbol tables. A lookup starts in the current scope and moves
outward to enclosing scopes. [5][6]

Solved theory question: symbol tables and scope

management
A complete answer should explain that symbol tables are used to:
insert declarations,
detect redeclaration within the same scope,
detect undefined identifiers during use,
map names to memory locations or offsets during translation.
[5][6]

Implementations
Common implementations include arrays, linked lists, trees, and hash
tables. Lists are simple but slow for searching, trees preserve
ordering, and hash tables usually give fast average lookup. [1]

Theory questions
Q: What is redeclaration error?
It occurs when the same identifier is declared more than once in the
same scope when the language does not allow it. [5]

Q: What is an undefined variable error?

It occurs when an identifier is used but no declaration can be found in
the current scope or any enclosing scope. [5]
Q: Why is scope information necessary?
Because the same identifier name can refer to different entities in
different program blocks. [5][6]

9. Syntax-Directed Translation and SDD

Rules
Syntax-directed translation attaches semantic rules to grammar
productions so that attributes can be computed while parsing. This is
used to build parse trees, syntax trees, ASTs, or intermediate code. [3]
[4][5][6]

Synthesized and inherited attributes

Synthesized attributes are computed from children and flow
upward.
Inherited attributes are computed from parent or siblings and
flow downward or sideways. [3][4]

S-attributed and L-attributed definitions

An S-attributed definition uses only synthesized attributes and works
naturally with bottom-up parsing. L-attributed definitions allow
restricted inherited attributes. [3][4]

Parse tree, syntax tree, AST

A parse tree shows the full grammar structure. A syntax tree is
more compact. An AST removes unnecessary grammar details and
keeps the essential operators and operands. [11][12][13]

Solved theory point: What does F -> (E) {[Link] =

[Link];} mean?
This means parentheses do not create a new AST node; instead, the
node for F simply reuses the node of the inner expression E. The
grouping effect of parentheses is preserved without adding extra
syntax tree clutter. [5][6]
Solved question pattern: Fill missing semantic rules
For expressions such as x + ((y + z) * w) or x + ((y * z) + w), missing
rules were of the form:
E -> E1 + T { ... }
T -> T1 * F { ... }
F -> id { ... } [3][4]
A typical completion creates nodes such as PlusNode, MultNode, and
IdNode, or generic Node and Leaf structures depending on the style
requested. [3][4]

Solved question pattern: Draw parse tree / AST

according to SDD
For Summer 2025, Question 4 asks for a parse tree of nodes for:
Set A: (id + id * id / id) [6]
Set B: (id / id + id * id) [5]
The important instruction is that the ordering of children must match
the SDD, such as:
E -> E1 + T storing children in order [[Link], '+', [Link]]
T -> T1 * F storing children in order [[Link], '*', [Link]]
T -> T1 / F storing children in order [[Link], '/', [Link]] [5][6]
This means the student must pay attention not just to the grammar,
but also to the exact node ordering created by semantic actions. [5][6]

Theory questions
Q: Why are synthesized attributes easier for LR parsing?
Because bottom-up parsing recognizes children before reducing to the
parent, so child information is already available when a synthesized
attribute is computed. [3][4]
Q: Why is AST preferred over parse tree in later compiler phases?
Because AST removes unnecessary grammar details and represents
only the meaningful program structure, which is easier for semantic
analysis and code generation. [12][13]

Q: What is a dependency graph?

A dependency graph shows how attribute values depend on each
other and helps determine a valid evaluation order. [3][4]

10. Panic Mode Error Recovery

Panic mode error recovery is a simple syntax error recovery strategy
in which the parser discards input symbols until it finds a
synchronizing token, such as ;, ) or } depending on the grammar and
parser design. [3][4]

Why it may report more errors than actually exist

Panic mode may skip too much input and lose context, so a single real
syntax error can trigger several additional misleading errors
afterward. This is known as cascading error reporting. [3][4]

Theory question
Q: What is panic mode error recovery?
It is a recovery method where the parser skips input tokens until it
reaches a safe synchronization point, allowing parsing to continue.
[3][4]

11. LR(1) vs LR(3) Theory

An LR(1) parser uses one lookahead symbol in its decision making,
while an LR(3) parser uses three-symbol lookahead context. The
general layout of ACTION and GOTO remains conceptually similar,
but LR(3) states and reduction contexts are more detailed and usually
much larger. [14][15][16]
Solved theory question: How would the parsing table
structure change for LR(3) instead of LR(1)?
The table structure remains ACTION/GOTO in concept, but item sets
and reduce decisions would depend on three-symbol lookahead
strings instead of one lookahead token. This leads to more context-
specific states and a significantly larger table. [14][15][16]

Theory questions
Q: What does LR(0), LR(1), LR(2), LR(3) mean?
The number indicates how many lookahead symbols are used when
deciding parser actions. LR(0) uses none, LR(1) uses one, LR(2) uses
two, and LR(3) uses three. [7][17]

Q: Is SLR(3) a common classroom construction?

Usually no. Most compiler courses focus on LR(0), SLR(1), LALR(1),
and canonical LR(1). Larger lookahead values are mostly theoretical.
[18][16]

12. Mid and Hard Theory Practice

Mid-level questions
Q: Why does a compiler separate lexical analysis from syntax
analysis?
The separation simplifies design and implementation. The lexical
analyzer works at the character level, while the parser works at the
token and grammar level. [2][3]

Q: Why is a handle important in shift-reduce parsing?

Because reducing the wrong substring would break the derivation. A
handle identifies the correct reducible substring at each bottom-up
step. [5][6]
Q: Why does a symbol table need scope information?
Because the same identifier may refer to different declarations in
different nested blocks. [5][6]

Hard-level questions
Q: Why can shift-shift conflict not happen in LR parsing?
Because the LR automaton is deterministic, so for a given state and
terminal there can be at most one shift transition. [5]

Q: Why may a shift-reduce conflict appear in LR(0) but disappear

in SLR(1)?
Because LR(0) may reduce too broadly, while SLR(1) restricts reduce
actions to FOLLOW sets and may avoid the conflict if the terminal is
not in the relevant FOLLOW. [3][4][9]

Q: Why are inherited attributes harder than synthesized

attributes in LR parsing?
Inherited attributes may require information from parents or siblings
before reduction is complete, which does not naturally align with
bottom-up evaluation. [3][4]

13. Exam Writing Advice

For theory answers, use short definitions first, then add one or two
lines explaining why the concept matters. Many of the theory
questions in these papers reward concise explanation tied to compiler
behavior rather than long descriptions. [3][4][5][6]
For simulation questions, always show stack, input, and action in
tabular form. For parser construction questions, show all requested
parts in order: augmented grammar, FIRST/FOLLOW, LR(0)
automaton, ACTION table, and GOTO table. [1][2][5][6]
For syntax-directed translation questions, pay close attention to the
exact node ordering in the semantic actions. The marks depend not
only on the final operator tree, but also on whether the child list
order matches the SDD. [5][6]