Compiler Design
Unit-I
Lecture-1
Introduction to Compiler & Translators:
Translator:
A translator is a program that takes as input a program written in one programming language i.e. Source language & produces as output a program in another language i.e. Object or target language.
Types of Translators:
Translators are generally classified into three types
1) Compiler
2) Interpreter
3) Assembler
Compiler:
Compiler is a program that translates a high level language program into a functionally equivalent low level language program.
So a Compiler is basically a translator whose source language is the high level language and the target language is a low level language, such as an assembly language or machine language.
COMPILERSource program Object program
Written in high Written in low
Level language level language
Error Message
The Compiler reports to its user the presence of errors in the source program.
Interpreter:
Interpreter is a translator which translates high level language program into low level language program line by line & also interpreter executes the program.
Assembler:
Assembler is a translator which translates assembly language program into a functionally equivalent machine language program.
ASSEMBLERAssembly language Machine language
Program program
Difference between Compiler & Interpreter:
Compiler
Interpreter
Compiler translates the high level language program into low level language program whole at a time.
Interpreter translates the high level language program into low level language program line by line.
It can not execute a program
It can execute a program
It works fast as whole program is converted at a time.
It works slowly as line by line conversion occurs.
Chances of error finding are less.
Chances of error finding are more.
Cross Compiler:
A cross compiler is a Compiler that runs on one machine & produces object code for another machine.
The cross compiler is used to implement the Compiler, which is characterized by three languages:
1) The Source language
2) The Object language
3) The language in which it is written.
BootStrap Compiler:
If a Compiler has been implemented in its own language , then this Compiler is called bootstrap Compiler.
Implementing a bootstrap Compiler:
Suppose we have a new language L that we want to make available on machine A and B.
As a first step, we can write a small compiler SCAA, which will translate an S subset of L to the object Code for machine A, written in a language available on A.
We then write a compiler SCSA, which is compiled in language L and generates object code written in an S subset of L for machine A, But this will not be able to execute unless and until it is translated by SCAA. Therefore SCSA is an input into SCAA. As shown below, producing a compiler for L that will run a machine A and self generate code for machine A.
SCSA à SCAA à LCAA9 -
Tuesday, July 29, 2008
Assignment-1
Gurgaon Institute of Technology and Management
Assignment No. 1
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 1 & II
Faculty : ARUN KUMAR PATEL
Q.1.Describe different phases of a Compiler with the help of a neat diagram.
Q.2. Describe different Compiler Construction tools.
Q.3. Write and explain the algorithm to minimize the number of states of DFA.
Q.4. Explain the role of Lexical analyzer in Compiler and Describe about LEX.
Prepared by: Approved by:
Assignment No. 1
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 1 & II
Faculty : ARUN KUMAR PATEL
Q.1.Describe different phases of a Compiler with the help of a neat diagram.
Q.2. Describe different Compiler Construction tools.
Q.3. Write and explain the algorithm to minimize the number of states of DFA.
Q.4. Explain the role of Lexical analyzer in Compiler and Describe about LEX.
Prepared by: Approved by:
Tutorial sheet-1
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 1
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 1
Faculty : ARUN KUMAR PATEL
Q.1.What is meant by Compilers and Translators? Why do we need this? Discuss the structure of compiler.
Q.2. Differentiate between:
(i) Phase and Pass of Compiler
(ii) Compiler and Interpreter
(iii) Code Optimization and Code Generation
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 2
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 2
Faculty : ARUN KUMAR PATEL
Q.1. (a) What are regular expressions? Discuss their role in construction of compiler.
Q.2. (b) What is LEX? Discuss LEX source program structure.
Q.3. Discuss the implementation of a Lexical Analyzer ?
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 3
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 3
Faculty : ARUN KUMAR PATEL
Q.1.What do you understand by Ambiguity in grammar? Discuss the ambiguity of the following grammar
Eà E+E E-E E*E E/E E E (E) -E id
Q.2.What is parse tree? Justify its significance.
Q.3. Consider the grammar
Sà a Ù (T) , T à T,S S
Find the right most derivation for (a,(a,a)).
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 4
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 4
Faculty : ARUN KUMAR PATEL
Q.1.What do you understand by a handle? Explain the stack implementation of shift reduce parser with the help of example.
Q.2. For the following grammar with E as starting symbol, find the FIRST and FOLLOW sets of each of the non terminals
E à TE’
E’à TE’ E
T à +FT’
T’à *FT’ E
Fà (E) id
Also write algorithms to compute First and Follow set.
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 5
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 5
Faculty : ARUN KUMAR PATEL
Q.1. Differentiate between SLR and LALR Parser.
Q.2. Explain the LR parsing scheme. Define an item. Write procedure to compute LR(0) items.
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 6
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 6
Faculty : ARUN KUMAR PATEL
Q.1. Define quadruples, triples and indirect triples. Write for the expression
- (a+b) * (c+d) – (a+b+c)
Q.2. What is meant by syntax directed translation scheme? What is its significance in compiler designing?
Q.3.What is syntax trees? How these can be constructed?
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 7
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 7
Faculty : ARUN KUMAR PATEL
Q.1. What information a good symbol table should contain? Explain how linked lists are used to store a symbol table.
Q.2.What are various sources of error? Explain how error detection and recovery is done in Compiler.
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 8
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 8
Faculty : ARUN KUMAR PATEL
Q.1.What is meant by resister allocation? Why is it considered to be important?
Q.2. Discuss briefly about Code Optimization
Q.3. Discuss the problem faced by compilers during Code generations.
Prepared by: Approved by:
Tutorial Sheet No. 1
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 1
Faculty : ARUN KUMAR PATEL
Q.1.What is meant by Compilers and Translators? Why do we need this? Discuss the structure of compiler.
Q.2. Differentiate between:
(i) Phase and Pass of Compiler
(ii) Compiler and Interpreter
(iii) Code Optimization and Code Generation
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 2
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 2
Faculty : ARUN KUMAR PATEL
Q.1. (a) What are regular expressions? Discuss their role in construction of compiler.
Q.2. (b) What is LEX? Discuss LEX source program structure.
Q.3. Discuss the implementation of a Lexical Analyzer ?
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 3
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 3
Faculty : ARUN KUMAR PATEL
Q.1.What do you understand by Ambiguity in grammar? Discuss the ambiguity of the following grammar
Eà E+E E-E E*E E/E E E (E) -E id
Q.2.What is parse tree? Justify its significance.
Q.3. Consider the grammar
Sà a Ù (T) , T à T,S S
Find the right most derivation for (a,(a,a)).
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 4
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 4
Faculty : ARUN KUMAR PATEL
Q.1.What do you understand by a handle? Explain the stack implementation of shift reduce parser with the help of example.
Q.2. For the following grammar with E as starting symbol, find the FIRST and FOLLOW sets of each of the non terminals
E à TE’
E’à TE’ E
T à +FT’
T’à *FT’ E
Fà (E) id
Also write algorithms to compute First and Follow set.
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 5
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 5
Faculty : ARUN KUMAR PATEL
Q.1. Differentiate between SLR and LALR Parser.
Q.2. Explain the LR parsing scheme. Define an item. Write procedure to compute LR(0) items.
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 6
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 6
Faculty : ARUN KUMAR PATEL
Q.1. Define quadruples, triples and indirect triples. Write for the expression
- (a+b) * (c+d) – (a+b+c)
Q.2. What is meant by syntax directed translation scheme? What is its significance in compiler designing?
Q.3.What is syntax trees? How these can be constructed?
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 7
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 7
Faculty : ARUN KUMAR PATEL
Q.1. What information a good symbol table should contain? Explain how linked lists are used to store a symbol table.
Q.2.What are various sources of error? Explain how error detection and recovery is done in Compiler.
Prepared by: Approved by:
Gurgaon Institute of Technology and Management
Tutorial Sheet No. 8
Department: Computer Science & Engineering
Semester : VII
Subject Name &Code: Compiler Design & CSE-405-E
Issue Date:
Pages :
Unit: 8
Faculty : ARUN KUMAR PATEL
Q.1.What is meant by resister allocation? Why is it considered to be important?
Q.2. Discuss briefly about Code Optimization
Q.3. Discuss the problem faced by compilers during Code generations.
Prepared by: Approved by:
Subscribe to:
Comments (Atom)