Prof.C.

Naga Raju
B.Tech(CSE),M.Tech(CSE),PhD(CSE),MIEEE,MCSI,MISTE
Department of CSE
YSR Engineering College of YVU
Proddatur

6/11/2020 1
 Contents
1) Motivation with c programs
2) Introduction to compilers
3) Types of compilers
4) Phases of compilers
5) Previous GATE ,DL and Bank officers questions

6/11/2020 Prof. C.NagaRaju 9949218570 2

 Principles of compiler design is an important
subject for GATE as well as for any other
competitive examinations.
 Principle is a formula or rule or logic.
 In computer every instruction must be in principle
or in logic otherwise it is not possible to solve.
 compilers are designed based on the principles or
rules of variables ,statements ,arrays etc.
 If you want to construct a new compiler, you must
be familiar with these principles.
 If you are good at these principles, it is easy to write
any programs in any programming languages.
6/11/2020 Prof. C.NagaRaju 9949218570 3
1)Variable rules
#include "stdio.h"
int main()
{
int _ = 10;
int __ = 20;
int ___;
___ = _ + __;
printf ("%d", ___);
return 0;
}

6/11/2020 Prof. C.NagaRaju 9949218570 4

 3)What is output 4)What is output
2)What is output
#include<stdio.h> #include<stdio.h
#include<stdio.h>
int main(void) >
int main(void)
{ int main(void)
{
int a; {
int a;
a = (1, 2, 3); int a=1, 2, 3;
a = 1, 2, 3;
printf("%d", a); printf("%d", a);
printf("%d", a);
return 0; return 0;
return 0;
} }
}

6/11/2020 Prof. C.NagaRaju 9949218570 5

Macros Macros
5)What is the output of the program 6) What is the output of the program

#include<stdio.h> #include<stdio.h>
#define x (4+1) #define x 4+1
int main() { int main() {
int i=5; int i=5;
i = x*x*x; i = x*x*x;
printf("%d",i); printf("%d",i);
return 0; return 0;
} }
(a) 125 (b) 13 (c) 17 (d) None of (a) 125 (b) 13 (c) 17 (d) None of above
above

6/11/2020 Prof. C.NagaRaju 9949218570 6

logical operator 8) Arthmetic operation
7) That is the output #include <stdio.h>
int main()
#include<stdio.h>
{
int main() int x = 10;
{ int y = 20;
int x, y, z;
x=y=z=1; x += y += 10;
z = ++x || ++y && ++z;
printf (" %d %d", x, y);
printf("x=%d, y=%d, z=%d\n", x, y, return 0;
z); }
return 0;
}
A. x=2, y=1, z=1 B. x=2, y=2, z=1
C. x=2, y=2, z=2 D.x=1, y=2, z=1

6/11/2020 Prof. C.NagaRaju 9949218570 7

Relational operator I/O statements
9) What is output 10) What is output
#include <stdio.h> #include "stdio.h"
int main() { int main() {
int a = 10, b = 20, c = 30; int a = 10;
if (c > b >a) int b = 15;
printf("TRUE");
printf("%d ",(a+1),(b=a+2));
else
printf(" %d ",b);
printf("FALSE");
return 0; return 0;
} }

6/11/2020 Prof. C.NagaRaju 9949218570 8

❖ Compiler is a program that translates source code into
object code and vice versa.
❖ Source code is a program written in high level languages
❖ object code is a program written in low level languages or
Target program or Machine Language.

6/11/2020 Prof. C.NagaRaju 9949218570 9

Types of compilers
 Cross Compiler: compiler that runs on a machine ‘A’ and
produces a code for another machine ‘B’.
 Hybrid compiler : The compiler which translates a human
readable source code into an intermediate byte code for later
interpretation. It has both features of a compiler and an
interpreter. These types of compilers are commonly known as
Just In-time Compilers (JIT).
 Source compiler: The compiler which converts the high level
language code in to assembly language only.
 Source-to-source Compiler :The compiler that translates source
code written in one high level language into another high level
language
6/11/2020 Prof. C.NagaRaju 9949218570 10
 Native code compiler: The compiler converts a source code for
same type of platform only. The output generated by this type of
compiler is only run on the same type of computer system and OS
that the compiler itself runs on.
 One pass compiler: It is a type of compiler that compiles the whole
process in only one-pass.
 Two Pass or Multi Pass compiler: It is a type of compiler that
processes the source code or abstract syntax tree of a program
multiple times.
 Threaded code compiler: The compiler which simply replace a
string by an appropriate binary code.
 Incremental compiler: The compiler which compiles only the
changed lines from the source code and update the object code.
6/11/2020 Prof. C.NagaRaju 9949218570 11
Phases of compiler:
Compiler is divided into two parts1) analysis part or front–end
2) synthesis part or back-end
Analysis part or front end:
1. It converts source code to intermediate code.
2.Primarily it depends on source language and independent on
target language
3. It includes
a) lexical analysis
b)syntax analysis
c) semantic analysis
Synthesis part or back end:
1. It converts intermediate code to target program
2. Primarily it depends on target language and independent on
source language
3. It includes
a)intermediate code generator
b)code optimizer
c) code generator

6/11/2020 Prof. C.NagaRaju 9949218570 12

6/11/2020 Prof. C.NagaRaju 9949218570 13
LEXICAL ANALYZER OR SCANNER OR LINEAR ANALYSIS

 Lexical analysis is the first phase of a compiler

 It Reads one character at a time from the source program from
left to right and generate lexemes
 A lexeme is the process of word formation based on pattern
known as tokens
 These tokens are divided into keywords, identifiers, operators,
delimiters and punctuation symbols
 each token is represented with pair of values <identifier, number>
 It Recognize the various Tokens with the help of regular
expressions and pattern rules. and It classifies the various Tokens

6/11/2020 Prof. C.NagaRaju 9949218570 14

 //Consider the program
int main() {
// 2 variables
int a, b;
a = 10;
return 0;
}

'int' 'main' '(' ')' '{' 'int' 'a' ',' 'b' ';' 'a' '=' '10' ';' 'return' '0' ';' '}‘
 It Remove comments and white spaces
 It Interacts with the symbol table
 sends lexical errors to error handling table

6/11/2020 Prof. C.NagaRaju 9949218570 15

6/11/2020 Prof. C.NagaRaju 9949218570 16
SYNTAX ANALYZER OR PARSER
 It is second phase of the compiler
 It takes individual tokens from lexical analyzer.
 It understand the over all structure of the tokens and
groups the tokens into sentences.
 It checks whether the given input is in the correct syntax
of the programming language or not.
 It is also known as the Parse Tree or Syntax Tree.
 Ex: 1) Expressions 2) statements 3)Declaration 4) Nested
Statements…
✓ x = (2+3) ∗ 9); Mismatched Parentheses
✓ if x>y x = 2; Missing Parentheses
✓ while (x==3) do f1(); Invalid Keyword Do
6/11/2020 Prof. C.NagaRaju 9949218570 17
6/11/2020 Prof. C.NagaRaju 9949218570 18
Semantic analyzer
 It uses syntax tree and symbol table to check whether the
given program is semantically consistent with language
definition or not.
 It gathers type information and stores it in either syntax
tree or symbol table.
 Functions of Semantic Analysis:
 1)Type Checking 2)Label Checking 3)Flow Control Check
Semantic errors
 Type mismatch
 Undeclared variables
 Reserved identifier misuse
6/11/2020 Prof. C.NagaRaju 9949218570 19
6/11/2020 Prof. C.NagaRaju 9949218570 20
Intermediate code Generator

 It generates intermediate code, that can be readily executed by

machine
 We have many popular intermediate codes. Such as 1)
Quadruples, 2)Triples, 3)Indirect Triples, 4)Abstract Syntax tree
4) Three address code
 Three address code : The instruction consist of three operands
 Intermediate code is converted to machine language using the
last two phases which are platform dependent.
 Till intermediate code, it is same for every compiler but after
that, it depends on the platform.
 To build a new compiler we don’t need to build it from scratch.
 We can take the intermediate code from the already existing
compiler and build the last two parts.
6/11/2020 Prof. C.NagaRaju 9949218570 21
6/11/2020 Prof. C.NagaRaju 9949218570 22
Code Optimizer
 It rearranges the tree generated by parser such that to
consume fewer resources and to produces more speed.
 The meaning of the code is not altered.
 It increases the execution speed of the program
 It reduces the storage space
 Optimization can be categorized into two types:
1)machine dependent
2) machine independent.

6/11/2020 Prof. C.NagaRaju 9949218570 23

6/11/2020 Prof. C.NagaRaju 9949218570 24
Target Code Generator
 It generates the target code that the machine can
understand
 It allocates the registers,
 It select the type of instructions.
 The output is dependent on the type of assembler.
 This is the final stage of compilation.

6/11/2020 Prof. C.NagaRaju 9949218570 25

6/11/2020 Prof. C.NagaRaju 9949218570 26
Symbol Table Manager
 Symbol table is a data structure contains record for each
identifier
 It stores information about all identifiers such as name, type
,size ,scope and value
 Determine the correct use of tokens
 Type checking and Variable type expressions
 Use to record each identifier and collect the information about it
 It Locates run time storage to identifier
 It stores Records return type of function ,its arguments and its
return value
 Symbol table has a find function
 Returns pointer for the identifier and Null when no record is
 Insert function to insert new records
6/11/2020 Prof. C.NagaRaju 9949218570 27
 Example

int a, b; float c; char z;

Symbol name Type Address

a Int 1000

b Int 1002

c Float 1004

z char 1008

6/11/2020 Prof. C.NagaRaju 9949218570 28

Error Handling Table
 It handles the lexical errors ,syntax errors and semantic errors
 Errors are reported in the form of message
 At any phase errors may be handled
 Type mismatch
 Undeclared variables
 Reserved identifier misuse
 Error handler goals
 Report the presence of errors clearly and accurately
 Recover from each error quickly enough to detect
subsequent errors
 Add minimal overhead to the processing of correct programs

6/11/2020 Prof. C.NagaRaju 9949218570 29

GATE CS 2011 | Question 1
1)In a compiler, keywords of a language are recognized
during
(A) parsing of the program
(B) the code generation
(C) the lexical analysis of the program
(D) dataflow analysis

6/11/2020 Prof. C.NagaRaju 9949218570 30

GATE | GATE CS 2011 | Question 19
2)The lexical analysis for a modern computer languages
such as Java needs the power of which one of the
following machine models is necessary and sufficient
sense.

(A) Finite state automata

(B) Deterministic pushdown automata
(C) Non-Deterministic pushdown automata
(D) Turing Machine

6/11/2020 Prof. C.NagaRaju 9949218570 31

 GATE-CS-2009 | Question 17
3) Match all items in Group 1 with correct options from those
given in Group 2.
Group 1 Group 2
P. Regular expression 1. Syntax analysis
Q. Pushdown automata 2. Code generation
R. Dataflow analysis 3. Lexical analysis
S. Register allocation 4. Code optimization
(A) P-4. Q-1, R-2, S-3
(B) P-3, Q-1, R-4, S-2
(C) P-3, Q-4, R-1, S-2
(D) P-2, Q-1, R-4, S-3

6/11/2020 Prof. C.NagaRaju 9949218570 32

GATE CS 1998 | Question 27
4)Type checking is normally done during

(A) Lexical analysis

(B) Syntax analysis
(C) Syntax directed translation
(D) Code optimization

6/11/2020 Prof. C.NagaRaju 9949218570 33

GATE CS 2008 | Question 85
5) Some code optimizations are carried out on the
intermediate code because
(A) they enhance the portability of the compiler to
other target processors
(B) program analysis is more accurate on intermediate
code than on machine code
(C) the information from dataflow analysis cannot
otherwise be used for optimization
(D) the information from the front end cannot
otherwise be used for optimization
6/11/2020 Prof. C.NagaRaju 9949218570 34
 GATE CS 1997 | Question 8
6) A language L allows declaration of arrays whose sizes are not known
during compilation. It is required to make efficient use of memory.
Which of the following is true?

(A) A compiler using static memory allocation can be written for L

(B) A compiler cannot be written for L, an interpreter must be used
(C) A compiler using dynamic memory allocation can be written for L
(D) None of the above

6/11/2020 Prof. C.NagaRaju 9949218570 35

GATE-CS-2014-(Set-3) | Question 65
7) One of the purposes of using intermediate code
in compilers is to
(A) make parsing and semantic analysis
simpler.
(B) improve error recovery and error reporting.
(C) increase the chances of reusing the
machine-independent code optimizer in other
compilers.
(D) improve the register allocation.
6/11/2020 Prof. C.NagaRaju 9949218570 36
GATE-CS-2015 (Set 2) | Question 29
8) Match the following:
List-I List-II
A. Lexical analysis 1. Graph coloring
B. Parsing 2. DFA minimization
C. Register allocation 3. Post-order traversal
D. Expression evaluation 4. Production tree

Codes: A B C D
(a) 2 3 1 4 (b) 2 1 4 3 (c) 2 4 1 3 (d) 2 3 4 1
OPTION C
6/11/2020 Prof. C.NagaRaju 9949218570 37
9) In a two-pass assembler, symbol table is

 A) Generated in first pass

 B) Generated in second pass
 C) Not generated at all
 D) Generated and used only in second pass

6/11/2020 Prof. C.NagaRaju 9949218570 38

10) How many tokens will be generated by the
scanner for the following statement ?
x = x ∗ (a + b) – 5;

 A) 12
 B) 11
 C) 10
 D) 07

6/11/2020 Prof. C.NagaRaju 9949218570 39

 11) Incremental-Compiler is a compiler?
 A) which is written in a language that is
different from the source language
 B) compiles the whole source code to generate
object code afresh
 C) compiles only those portion of source code
that have been modified.
 D) that runs on one machine but produces
object code for another machine

6/11/2020 Prof. C.NagaRaju 9949218570 40

 12) DU-chains(Definition-Use) in compiler design
 A) consist of a definition of a variable and all its
uses, reachable from that definition
 B) are created using a form of static code analysis
 C) are prerequisite for many compiler
optimization including constant propagation and
common sub-expression elimination
 D) All of the above

6/11/2020 Prof. C.NagaRaju 9949218570 41

 13) Which phase of compiler generates stream
of atoms?
 A) Syntax Analysis
 B) Lexical Analysis
 C) Code Generation
 D)Code Optimization
14)Which data structure in a compiler is used
for managing information about variables and
their attributes?
A)Abstract syntax tree
B) Symbol tree
C)Semantic stack
D) Parse table

6/11/2020 Prof. C.NagaRaju 9949218570 43

15) Which one of the following is NOT performed
during compilation?
A)Dynamic memory allocation
B)Type checking
C)Symbol table management
D)Inline expansion

6/11/2020 Prof. C.NagaRaju 9949218570 44

 16) Symbol table can be used for:
A) Checking type compatibility
B) Suppressing duplication of error message
C) Storage allocation
D) All of these

6/11/2020 Prof. C.NagaRaju 9949218570 45

17) In two-pass assembler, symbol table is
A) Generated in first pass
B) Generated in second pass
C) Not generated at all
D) Generated and used only in second pass

6/11/2020 Prof. C.NagaRaju 9949218570 46

18) The access time of the symbol, table will
be logarithmic if it is implemented by
A)Linear list
B) Search tree
C) Hash table
D) Self organization list

6/11/2020 Prof. C.NagaRaju 9949218570 47

19) Which one of the following is FALSE?
A) A basic block is a sequence of instructions where
control enters the sequence a the beginning and exits at
the end.
B)Available expression analysis can be used for common
sub expression elimination.
C)Live variable analysis can be used for dead code
elimination.
D) X=4*5=>x=20 is an example of common sub
expression elimination

6/11/2020 Prof. C.NagaRaju 9949218570 48

20) One of the purposes of using intermediate code
in compilers is to
A) Make parsing and semantic analysis simpler
B) Improve error recovery and error reporting
C) Increase the chances of reusing the machine
independent code optimizer in other compilers
D) Improve the register allocation

6/11/2020 Prof. C.NagaRaju 9949218570 49

 Thank you

6/11/2020 Prof. C.NagaRaju 9949218570 50