Structure of Compiler
Course: Compiler Construction
Topic: Overview, Lexical Analysis, Syntax Analysis, Semantic Analysis,
Intermediate Code Generation, Code Optimization, Code Generation,
Symbol-Table Management, Compiler Construction Tools
Contents
• The Structure of a Compiler
• Lexical Analysis
• Syntax Analysis
• Semantic Analysis
• Intermediate Code Generation
• Code Optimization
• Code Generation
• Symbol-Table Management
• Compiler Construction Tools
Structure of a Compiler
• If we open the Compiler Box a little, There are two parts to this
mapping.
• Analysis determines the operations implied by the source program
which are recorded in a tree structure.
• Synthesis takes the tree structure and translates the operations there in
into the target program.
Analysis
• Operations performed
• Breaks up the source program into pieces
• Imposes a grammatical structure on these pieces
• Then an intermediate representation in created using this structure
• Display error messages (if any)
• It also collects information about the source program & stores in a data
structure called Symbol Table
• Front Ent of a Compiler
Synthesis
• Operations performed
• It takes the intermediate representation and information from the
symbol table as input
• Constructs the desired target program
• Back End of a Compiler.
Compilation Phases
• A typical decomposition of a
compiler can be done into
several phases.
Lexical Analysis
• 1st phase of compiler, also known as Scanner.
• It verifies that input character sequence is lexically valid.
• Group characters into meaningful sequence of lexemes.
• For each lexeme, the lexical analyzer produces as ouput a token of the form
• (Token-name, attribute-value)
• Discards white space and comments.
Lexical Analysis..
• Tokens (token-name, attribute-value)
• These tokens are passes on to the subsequent phase i.e syntax analysis.
• Token comprises of following components
• Token-name is an abstract symbol that is used during syntax analysis.
• Attribute-value points to an entry in the symbol table for this token, Information from
the symbol-table entry needed for semantic analysis and code generation.
Lexical Analysis..
• Example
Position = Initial + rate * 60
Lexemes mapped into Tokens
Position (id,1)
= (=)
initial (id,2)
+ (+)
rate (id,3)
* (*)
60 (60)
After Lexical analysis (id,1)(=)(id,2)(+)(id,3)(*)(60)
Translation of (Ex) Assignment Statement
Syntax Analysis
• 2nd phase of compiler, also known as Parsing or Parser and Parsing
Tree.
• The parser uses the first components of the tokens to create a syntax tree that
depicts the grammatical structure of the token stream.
• In Syntax Tree each interior node represents an operation and the children of
the node represent the arguments of the operation
Semantic Analysis
• The semantic analyzer uses the syntax tree and the information in the
symbol table to check the source program for semantic consistency
with the language definition.
• It gathers type information and saves it in either the syntax tree or the symbol
table.
• An important part of semantic analysis is type checking.
• For example, compiler report an error if a floating- point number is used to
index an array.
Semantic Analysis..
• The language specification may permit some type conversions called
coercions.
• For example, a binary arithmetic operator may be applied to either a pair of
integers or to a pair of floating-point numbers.
• If the operator is applied to a floating-point number and an integer, the
compiler may convert or coerce the integer into a floating-point number.
Intermediate Code Generation
• In the process of translating a source program into target code, a
compiler may construct one or more intermediate representations.
• Ex. Syntax Trees
• An explicit low-level or machine-like intermediate representation is
generated in this phase.
• For ex a three-address intermediate code which consists of a sequence
of assembly-like instructions.
• It contains three operands per instruction.
Intermediate Code Generation..
• The ouput of the intermediate code generator in our example consists of the
three-address code sequence.
t1 = inttofloat(60)
t2 = id3 * t1
t3 = id2 + t2
id1 = t3
• Each three-address assignment instruction has at most one operator on the right side.
• The compiler must generate a temporary name to hold the value computed.
• Can have fewer than three operands.
Code Optimization
• The code-optimization phase helps to improve the intermediate code
so that better target code will be achieved.
• Results of code optimization phase in our Ex..
t1 = id3 * 60.0
id1 = id2 + t1
• Optimizer can deduce that conversion of 60 from integer to floating point 60.0
can be done once and for all at compile time.
• Moreover t3 is used only once to transmit its value to id1 so the optimizer can
transform into the shorter sequence.
Code Generation
• The code generator takes as input an intermediate representation of the
source program and maps it into the target language.
• For example, using registers R1 and R2, the intermediate code is translated into the
machine code
LDF R2, ID3
MULF R2, R2, #60.0
LDF R1, ID2
ADDF R1, R1, R2
STF ID1, R1
• The first operand of each instruction specifies a destination.
• The F in each instruction depicts floating-point numbers.
Symbol Table Managment
• The symbol table is a data structure containing a record for each
varibale name, with fields for the attributes of the name.
• This data structure should be designed with following privileges
• To allow the compiler to find the record for each quickly
• To store or retrieve data from that record quickly.
Compiler Construction Tools
• The compiler programmer can use modern software development
environments containing tools such as language editors, debuggers,
version manager, and so on including some specialized tools.
• The most successful tools are those that hide the details of the
generation algorithm and produce components that can be easily
integrated into the remainder of the compiler.
Compiler Construction Tools..
• Some common tools are:
• Scanner generators produce lexical analyzers from a regular-expression
description of the tokens of a language.
• Parser generators automatically produce syntax analyzers from a grammatical
description of a programming language.
• Syntax-directed translation engines produce collections of routines for waiting
a parse tree and generating intermediate code.
Compiler Construction Tools..
• Code-generators produce a code from a collection of rules for translating each
operation of the intermediate langugae into the machine language for a target
machine.
• Data-flow analysis engines facilitate the gathering of information about how
values are transmitted from one part of a program to each other part.
• Compiler-construction toolkits provide an integrated set of routines for
constructing various phases of a compiler.
