Every Unit I topic is explained in RGPV 14-mark answer format with definitions, diagrams, working, examples, advantages, limitations and exam-oriented points.
Definition: A compiler is system software that translates a program written in a high-level source language into an equivalent target program, normally machine code or assembly code, while reporting errors found in the source program.
Introduction
A computer processor understands machine instructions, while programmers prefer high-level languages such as C, C++ and Java. A compiler acts as a bridge between these two forms. It examines the complete source program, checks whether the program follows the rules of the language, creates an internal representation, improves the code and finally produces target code.
Basic Compiler Model
Source Program
|
v
+------------------+
| COMPILER |
+------------------+
|
v
Target Program
Additional Input: Symbol Table
Additional Output: Error Messages
Main Functions of a Compiler
Read and analyze the source program.
Identify tokens such as identifiers, constants and operators.
Check grammatical structure.
Check data types and semantic correctness.
Generate an intermediate representation.
Optimize the intermediate code.
Generate target-machine instructions.
Detect and report errors.
Compiler, Interpreter and Assembler
Translator
Input
Output/Working
Speed
Compiler
High-level program
Translates the complete program and produces target code
Compiled program executes fast
Interpreter
High-level program
Translates and executes one statement at a time
Execution is relatively slower
Assembler
Assembly program
Produces machine code
Fast translation
Advantages
Produces efficient executable code.
Detects many errors before execution.
Allows machine-independent programming.
Performs code optimization.
The target program can be executed repeatedly without recompilation.
Limitations
Compiler construction is complex.
Compilation may require significant memory and time.
Error messages can sometimes be difficult for beginners.
A compiler is generally language and target dependent.
Conclusion: A compiler is an essential language-processing tool that converts human-readable source code into efficient machine-executable code through a sequence of analysis and synthesis operations.
2. Analysis of Source Program 14 Marks
Source program analysis is the process of examining a program at different levels to determine its tokens, grammatical structure and meaning before target code is produced.
Two Major Parts of Compilation
COMPILER
|
+------------+------------+
| |
Analysis Part Synthesis Part
(Front End) (Back End)
| |
Source Program Intermediate Code
| |
Tokens, Tree, Optimization and
Symbol Table Target Code
Analysis Phase
The analysis phase breaks the source program into smaller components and creates an intermediate representation. It includes:
Lexical analysis: groups characters into tokens.
Syntax analysis: checks grammatical structure.
Semantic analysis: checks meaning, types and declarations.
Synthesis Phase
The synthesis phase uses the intermediate representation and symbol-table information to produce the target program. It includes:
Intermediate code generation
Code optimization
Target code generation
Example
For the statement position = initial + rate * 60;:
Lexical analysis identifies identifier, assignment, addition, multiplication and number tokens.
Syntax analysis builds a tree according to operator precedence.
Semantic analysis checks whether identifiers are declared and types are compatible.
Intermediate code may be generated as t1 = rate * 60 and position = initial + t1.
Role of Symbol Table
The symbol table stores information about identifiers, such as name, type, scope, memory location, parameter list and return type.
Role of Error Handler
Error handling is active throughout compilation. It reports lexical, syntax and semantic errors and attempts recovery so that more errors can be detected.
Conclusion: Source-program analysis converts a stream of source characters into a structured and meaningful intermediate form that can be used by the synthesis phase.
3. Phases of a Compiler 14 Marks
A compiler phase is a logically organized operation that transforms one representation of a source program into another representation.
Compiler Phase Diagram
Source Program
|
v
1. Lexical Analysis
|
v
2. Syntax Analysis
|
v
3. Semantic Analysis
|
v
4. Intermediate Code Generation
|
v
5. Code Optimization
|
v
6. Target Code Generation
|
v
Target Program
Symbol Table and Error Handler interact with all phases.
1. Lexical Analysis
It reads source characters and groups them into meaningful units called tokens. Spaces and comments are generally removed.
2. Syntax Analysis
It checks whether the token sequence follows the grammar of the programming language and constructs a parse tree or syntax tree.
3. Semantic Analysis
It checks declarations, type compatibility, scope rules and other meaning-related constraints.
4. Intermediate Code Generation
It generates a machine-independent representation such as three-address code.
5. Code Optimization
It improves the intermediate code to reduce execution time or memory usage without changing program meaning.
6. Target Code Generation
It selects machine instructions, assigns registers and generates assembly or machine code.
Example Through All Phases
Statement: a = b + c * 2;
Tokens:
id(a) = id(b) + id(c) * num(2)
Syntax:
=
/ \
a +
/ \
b *
/ \
c 2
Three-address code:
t1 = c * 2
t2 = b + t1
a = t2
Importance
Modular compiler design
Easy testing and maintenance
Clear separation of responsibilities
Reuse of front end and back end
Conclusion: The compiler phases transform source code step by step from characters to efficient target instructions while maintaining correctness and reporting errors.
4. Phases and Passes 14 Marks
A phase is a logical compiler operation, whereas a pass is one complete reading or processing of the source program or its intermediate representation.
Difference Between Phase and Pass
Basis
Phase
Pass
Meaning
Logical compilation function
Physical traversal of program representation
Examples
Lexical analysis, parsing, optimization
First pass, second pass
Relationship
One or more phases can be grouped
A pass may contain several phases
Purpose
Defines what operation is performed
Defines how many times input is scanned
Single-Pass Compiler
A single-pass compiler processes the program once and generates output during the same pass.
Advantages
Fast compilation
Lower memory requirement
Simple for small languages
Limitations
Limited optimization
Difficult handling of forward references
Less flexibility
Multi-Pass Compiler
A multi-pass compiler processes the source or intermediate representation multiple times.
Advantages
Better optimization
Clear modular organization
Supports complex language features
Limitations
More compilation time
More intermediate storage
Typical Pass Organization
Pass 1:
Lexical + Syntax + Semantic Analysis
|
v
Intermediate Representation
Pass 2:
Optimization + Target Code Generation
|
v
Target Program
Conclusion: Compiler phases describe logical tasks, while passes describe actual scans. The compiler designer groups phases into passes according to memory, speed and optimization requirements.
5. Bootstrapping of Compiler 14 Marks
Bootstrapping is the process of developing a compiler for a programming language using the same language that the compiler is intended to compile.
Basic Idea
If a compiler for language L is written in language L, an earlier translator or a compiler on another machine is required to produce the first executable version.
Bootstrapping Process
Develop a small initial compiler using an existing language or assembly language.
Use that compiler to compile a more complete compiler written in the source language.
Improve the compiler and compile the new version using the previous version.
Repeat until a stable self-hosting compiler is obtained.
Step 1:
Compiler for L written in existing language M
|
M Compiler
|
v
Executable Compiler for L
Step 2:
Improved Compiler for L written in L
|
Executable Compiler for L
|
v
Improved Self-Hosting Compiler
Cross Compiler
A cross compiler runs on one machine but generates target code for another machine.
Benefits
Tests the expressive power of a language.
Improves portability.
Allows compiler development for new machines.
Supports self-hosting compiler development.
Provides a practical method for compiler improvement.
Challenges
Requires an initial translator.
Errors in an earlier compiler may affect later versions.
Cross-platform validation may be difficult.
Conclusion: Bootstrapping enables a language to become self-supporting and is widely used to create portable and self-hosting compiler systems.
6. Lexical Analyzer 14 Marks
A lexical analyzer is the first compiler phase. It reads source characters, groups them into lexemes and produces tokens for the syntax analyzer.
Position in Compiler
Source Program
|
v
Lexical Analyzer ----> Symbol Table
|
Tokens
|
v
Syntax Analyzer
Errors are sent to the error handler.
Important Terms
Token: category of a lexical unit, such as ID or NUM.
Lexeme: actual character sequence matching a token.
Pattern: rule describing the set of lexemes for a token.
Lexeme
Token
Pattern
count
ID
letter followed by letters or digits
25
NUM
one or more digits
+
PLUS
plus symbol
while
WHILE
reserved word
Functions of Lexical Analyzer
Read source input.
Remove white spaces, tabs and comments.
Recognize tokens.
Enter identifiers and constants into symbol table.
Allows specialized buffering and pattern-matching methods.
Lexical Errors
Illegal character
Malformed number
Unterminated string
Identifier exceeding allowed length
Conclusion: The lexical analyzer converts raw source characters into a clean token stream and forms the foundation for syntax analysis.
7. Data Structures Used in Compilation 14 Marks
Compiler data structures store program information, intermediate representations and analysis results required by different phases.
Major Data Structures
1. Symbol Table
Stores identifier information such as name, type, scope, size, memory location and parameter details.
2. Syntax Tree
Represents the hierarchical grammatical structure of expressions and statements.
3. Intermediate Code List
Stores three-address instructions, quadruples or triples.
4. Literal Table
Stores constants and literal values used in the program.
5. Error Table
Records error type, line number and description.
6. Stack
Used in parsing, expression evaluation, scope control and runtime storage.
7. Hash Table
Provides fast symbol-table lookup and insertion.
8. Directed Graph
Used for control-flow graphs, dependency graphs and DAG-based optimization.
Symbol Table Operations
Insert a new symbol
Search an existing symbol
Update attributes
Begin and end scope
Delete temporary scope entries
Implementation Methods
Method
Search Time
Use
Linear list
Slow for large input
Simple compiler
Binary search tree
Depends on tree balance
Ordered symbols
Hash table
Very fast average lookup
Common symbol-table implementation
Conclusion: Efficient data structures are essential because compiler performance depends heavily on fast storage, lookup and transformation of program information.
8. LEX: Lexical Analyzer Generator 14 Marks
LEX is a tool that automatically generates a lexical analyzer from token patterns written as regular expressions and associated actions.
The programmer writes token patterns and actions in a .l file.
LEX translates the specification into a C source file, commonly lex.yy.c.
The C compiler compiles this source file.
The resulting lexical analyzer reads input and executes actions for matched patterns.
LEX Specification (.l)
|
v
LEX
|
v
lex.yy.c
|
C Compiler
|
v
Lexical Analyzer Executable
Important LEX Functions
yylex(): scans input and returns tokens.
yytext: stores the currently matched lexeme.
yyleng: stores the length of the matched lexeme.
yywrap(): indicates end of input.
Advantages
Reduces manual coding.
Regular-expression-based specification is simple.
Easy modification of token rules.
Works well with YACC.
Generates efficient scanner code.
Conclusion: LEX automates lexical-analyzer construction by translating regular-expression rules into an executable scanner.
9. Input Buffering 14 Marks
Input buffering is a technique used by a lexical analyzer to read source characters efficiently in blocks instead of performing one input operation for every character.
Need for Input Buffering
Character-by-character input is slow.
Lexical recognition often requires lookahead.
The analyzer may need to retract one or more characters.
System calls should be minimized.
Two-Buffer Scheme
Two equal-size buffers are used. Each buffer ends with a sentinel character.
lexemeBegin: points to the beginning of the current lexeme.
forward: moves ahead to search for the end of the lexeme.
Working
Fill the first buffer with a block of source characters.
Move the forward pointer while recognizing a token.
When the sentinel is reached, load the other buffer.
Continue scanning without stopping token recognition.
After recognizing a token, set lexemeBegin to the next character.
Sentinel Advantage
A sentinel reduces repeated boundary checking. When the forward pointer reads the sentinel, the analyzer checks whether it is the real end of file or only the end of one buffer.
Advantages
Fewer input operations
Efficient lookahead
Easy retraction
Improved lexical-analyzer speed
Conclusion: The two-buffer scheme with sentinels provides fast and convenient source scanning for lexical analysis.
10. Specification of Tokens 14 Marks
Token specification defines the lexical structure of programming-language elements through patterns, commonly expressed using regular expressions.
Reserved words such as if, while and int match the identifier pattern. They can be handled using a reserved-word table or separate high-priority rules.
Priority Rules
Choose the longest possible matching lexeme.
If two rules match the same longest string, choose the rule written first.
Input: count123 <= 50
Tokens: ID, RELOP, NUM
Conclusion: Regular expressions provide a precise and compact method to specify tokens for automatic or manual lexical analyzers.
11. Recognition of Tokens 14 Marks
Token recognition is the process of matching source-program lexemes with token patterns and returning the corresponding token to the parser.
Transition Diagram
A transition diagram is a directed graph in which states represent recognition progress and edges are labeled by input characters or character classes.
Identifier Recognition
(start) --letter--> (1)
/ \
letter digit
\ /
--(1)--
|
other
|
[accept ID]
Number Recognition
(start) --digit--> (1) --digit--> (1)
|
other
|
[accept NUM]
Finite Automata
NFA: may have multiple transitions for an input and epsilon transitions.
DFA: has exactly one transition for each input symbol from a state.
Recognition Process
Start at the initial state.
Read the next input character.
Follow the matching transition.
Continue until an accepting state is reached.
Return the token and attribute.
If no valid transition exists, report a lexical error.
Handling Lookahead and Retraction
Sometimes one extra character is read to identify a token. The extra character is retracted so that it can become part of the next token.
To distinguish < and <=, the analyzer reads one character after <. If it is =, it returns LE; otherwise it retracts the character and returns LT.
Recognition Algorithm Outline
repeat
skip whitespace
if letter then recognize identifier/keyword
else if digit then recognize number
else if operator prefix then recognize operator
else if delimiter then return delimiter
else report lexical error
until end of file
Conclusion: Token recognition converts regular-expression patterns into practical scanning logic using transition diagrams and finite automata.
12. YACC – Yet Another Compiler Compiler 14 Marks
YACC is an automatic parser generator that creates a syntax analyzer from a context-free grammar and associated semantic actions.
Structure of a YACC Program
%{
C declarations
%}
Token declarations
Grammar declarations
%%
Grammar rules and actions
%%
User-defined functions
Example YACC Grammar
%token NUM
%%
expr : expr '+' term
| term
;
term : term '*' factor
| factor
;
factor : '(' expr ')'
| NUM
;
%%
Working of YACC
The programmer writes grammar rules and semantic actions in a .y file.
YACC checks the grammar and constructs parsing tables.
It generates a C source file such as y.tab.c.
The generated parser calls yylex() to obtain tokens from LEX.
The parser performs shift-reduce parsing.
Semantic actions are executed when productions are reduced.
LEX Specification YACC Specification
| |
LEX YACC
| |
lex.yy.c y.tab.c
\ /
\ /
C Compiler
|
v
Complete Language Processor
Important Components
yyparse(): main parsing function.
yylex(): obtains tokens from lexical analyzer.
yyerror(): handles syntax errors.
yylval: carries semantic values of tokens.
Advantages
Automatically creates parsing tables.
Reduces manual parser coding.
Supports semantic actions.
Integrates with LEX.
Provides conflict reporting.
LEX and YACC Difference
Basis
LEX
YACC
Purpose
Generates lexical analyzer
Generates parser
Input notation
Regular expressions
Context-free grammar
Output function
yylex()
yyparse()
Input unit
Characters
Tokens
Conclusion: YACC simplifies syntax-analyzer construction by generating a table-driven parser directly from grammar specifications.
13. Context-Free Grammar 14 Marks
A context-free grammar is a formal system used to describe the syntactic structure of a programming language.
Formal Definition
A CFG is represented as G = (V, T, P, S), where:
V: finite set of non-terminals
T: finite set of terminals
P: set of productions
S: start symbol
Production Form
A → α
A is one non-terminal.
α is a string of terminals and/or non-terminals.
Example Grammar for Arithmetic Expression
E → E + T | T
T → T * F | F
F → ( E ) | id
Terminology
Terminal: actual language symbol.
Non-terminal: syntactic variable.
Sentential form: any string derived from the start symbol.
Sentence: a sentential form containing only terminals.
Language of grammar: set of all terminal strings generated by the grammar.
Role in Compiler Design
Defines programming-language syntax.
Supports parser construction.
Represents recursive structures.
Helps detect syntax errors.
Forms the basis for parse trees.
Ambiguous Grammar
A grammar is ambiguous if at least one sentence has more than one parse tree or more than one leftmost or rightmost derivation.
Grammar: E → E + E | E * E | id
The string id + id * id can have different parse trees unless precedence is encoded.
Conclusion: CFG is the standard formalism for expressing programming-language syntax and is the theoretical basis of syntax analysis.
14. Derivation in CFG 14 Marks
Derivation is the sequence of production applications used to generate a string from the start symbol of a grammar.
Types of Derivation
Leftmost Derivation
At every step, the leftmost non-terminal is replaced first.
Rightmost Derivation
At every step, the rightmost non-terminal is replaced first.
Example Grammar
E → E + T | T
T → id
Leftmost Derivation of id + id
E
⇒ E + T
⇒ T + T
⇒ id + T
⇒ id + id
Rightmost Derivation of id + id
E
⇒ E + T
⇒ E + id
⇒ T + id
⇒ id + id
Derivation Symbols
⇒ means derives in one step.
⇒* means derives in zero or more steps.
⇒+ means derives in one or more steps.
Importance
Shows how a grammar generates a sentence.
Helps construct parse trees.
Used in top-down and bottom-up parsing theory.
Helps determine ambiguity.
Conclusion: Leftmost and rightmost derivations provide systematic methods for generating and analyzing grammatical sentences.
15. Parse Tree 14 Marks
A parse tree is an ordered rooted tree that shows how a string is derived from the start symbol according to a context-free grammar.
Properties
The root is the start symbol.
Internal nodes are non-terminals.
Leaf nodes are terminals or epsilon.
Children of a node correspond to the right side of an applied production.
Reading leaves from left to right gives the generated string.
Example
Grammar:
E → E + T | T
T → id
Parse tree for id + id:
E
/ | \
E + T
| |
T id
|
id
Parse Tree vs Syntax Tree
Basis
Parse Tree
Syntax Tree
Detail
Shows all grammar symbols
Shows essential program structure
Size
Larger
More compact
Purpose
Syntax verification
Semantic analysis and code generation
Punctuation
May include delimiters
Usually removes unnecessary symbols
Relation with Ambiguity
If one input string has two different parse trees under the same grammar, the grammar is ambiguous.
Applications
Parser output
Syntax checking
Semantic-action execution
Intermediate-code generation
Expression evaluation
Conclusion: A parse tree is a graphical representation of derivation and clearly shows the hierarchical syntactic structure of a sentence.
16. Capabilities and Limitations of CFG 14 Marks
The capabilities of a CFG refer to the programming-language structures that can be described through context-free productions.
Structures Described by CFG
Arithmetic expressions
Operator precedence and associativity
Nested parentheses
Conditional statements
Loop structures
Blocks and statement lists
Function calls and parameter lists
Recursive language constructs
Examples
Balanced Parentheses
S → ( S ) S | ε
Statement List
L → L S | S
Conditional Statement
S → if E then S
| if E then S else S
| other
Why CFG is Powerful
It describes recursive syntax naturally.
It is more powerful than regular expressions.
It supports automatic parser generation.
It separates language syntax from compiler implementation.
It provides formal methods for grammar analysis.
Limitations of CFG
CFG cannot conveniently express several context-sensitive rules, including:
An identifier must be declared before use.
Type compatibility in expressions.
Number and type of function arguments.
Uniqueness of declarations within a scope.
Matching of declaration and use information.
How Limitations Are Handled
These rules are checked by semantic analysis using symbol tables, attributes and type-checking rules.
Regular Expression vs CFG
Feature
Regular Expression
CFG
Compiler use
Lexical structure
Syntactic structure
Recognized by
Finite automaton
Pushdown automaton
Nested structure
Cannot represent arbitrary nesting
Can represent recursive nesting
Conclusion: CFG is highly effective for describing programming-language syntax, but context-sensitive semantic requirements must be handled by later compiler phases.
Unit 1 Quick Revision
A compiler translates source code into target code.
The front end performs lexical, syntax and semantic analysis.
The back end performs optimization and code generation.
A phase is a logical task; a pass is a complete traversal.
Bootstrapping creates a self-hosting compiler.
The lexical analyzer converts characters into tokens.
LEX generates lexical analyzers from regular expressions.
YACC generates parsers from context-free grammars.
Input buffering improves scanner efficiency.
CFG describes syntactic structures.
Derivations and parse trees show how strings are generated.
Important RGPV Exam Questions
Long Answer Questions
Define compiler and explain its functions with a neat diagram.
Explain analysis and synthesis parts of a compiler.
Draw and explain all phases of a compiler with an example.
Differentiate between compiler phases and passes.
Explain bootstrapping and cross compiler.
Explain the lexical analyzer and its interaction with the parser and symbol table.
Discuss important data structures used in compilation.
Explain LEX structure, working and important functions.
Explain the two-buffer input-buffering scheme with sentinels.
Define token, pattern and lexeme. Explain token specification using regular expressions.
Explain recognition of tokens using transition diagrams and finite automata.
Explain YACC structure, working and its integration with LEX.
Define CFG and explain its components with an example.
Explain leftmost and rightmost derivations.
Define parse tree and compare it with syntax tree.
Discuss capabilities and limitations of context-free grammars.
Short Answer Questions
What is a compiler?
Define a compiler pass.
What is bootstrapping?
Define token and lexeme.
What is yytext?
What is the role of yylex()?
Define context-free grammar.
What is an ambiguous grammar?
What is a sentinel?
Differentiate between LEX and YACC.
14-Mark Writing Strategy: Begin with definition, draw a neat diagram, explain working point by point, add an example or comparison table, write advantages or limitations and end with a conclusion.
Download Study Resources
Unit 1 PDF
Printable detailed notes will be uploaded soon.
Coming Soon
Important Questions
Exam-oriented question bank will be available soon.
Coming Soon
PYQ Analysis
Repeated Unit 1 questions will be added soon.
Coming Soon
Frequently Asked Questions
Its main purpose is to translate a high-level source program into an equivalent target program and report errors.
Lexical analysis is the first phase of a compiler.
A token is a category such as ID, while a lexeme is the actual character sequence such as totalCount.
LEX generates a lexical analyzer, commonly in the C source file lex.yy.c.
YACC generates a syntax analyzer or parser from grammar rules.
CFG formally specifies programming-language syntax and supports parser construction.