Education4U

Compiler Design (CD)

Lec-01 : Introduction

Description

• Compiler Design Tutorial gives basic and advanced concepts of Compiler.

• The compiler works as a translator that converts the high-level language into machine-level language.

• This compiler Tutorial consists of all topics of the Compiler such as introduction, grammar, parsing, error detection & recovery, syntax-directed translation, symbol table, code optimization, code generation, etc.

Prerequisite

• This tutorial does not need prior knowledge of compiler design but needs a basic understanding of at least one programming language such as C, Java, etc.

• It would be one advantage if you have had prior exposure to Assembly Programming.

Topics Covered

• Parsing Techniques • Different types of Parsers • Tools • Syntax Directed Translation

• Intermediate Code Generation & Type Checking • Symbl Table

• Optimization & code Generator

For whom

• For students interested in learning the basic principles of compilers

• The students who would like to know more regarding compilers and those who wish to design or create a compiler themselves may begin from here

Reference books

1.“Compiler Design” by Chattopadhyay

2. “Compiler Design” by O G Kakde

3. “Principles Of Compiler Design” by Alfred V Aho

4. “Express Learning – Principles of Compiler Design” by ITL ESL

Q & A
Exam Questions

Q1 . What is a translator? Write down the steps to execute a program.
Q2 . Discuss all the phases of the compiler with a diagram
Q3 . Explain the parsing techniques with a hierarchical diagram
Q4 . What are the problems associated with Top-down Parsing?
Q5 . Write the algorithm to create a Predictive parsing table with the scanning of the input string.
Q6 . Write the properties of the LR parser with its structure. Also, explain the techniques of LR parser.
Q7 . Differentiate between synthesized translation and inherited translation.
Q8 . What are the basic blocks? Write the algorithm for partitioning into Blocks.
Q9 . What are the control and data flow analysis? Explain with an example.
Q10 . What is code optimization? Explain machine-dependent and independent code optimization.

The intermediate code representation for the expression a or b and not c is the three address sequence. t1:= not c t2:= b and t1 t3:= a or t2

The cost of instruction can be computed as one plus cost associated with source and destination addressing modes given by added cost. MOV P0, R1 1 MOV R1, M2 SUB 5 (R0), *10(R1)3

Directed Acyclic Graph (DAG) is a useful data structure used to implement transformations on basic blocks. DAG is used in • Determining the common sub-expressions. • Determining which names are used inside the block and computed outside the block. • Determining which statements of the block could have their computed value outside the block. • Simplifying the list of quadruples by eliminating the common sub-expressions and performing the assignment of form x: = y unless and until it is a must.

Phrase level error recovery is implemented by filling in the blank entries in the predictive parsing table with pointers to error routines. These routines may change, insert, or delete symbols on the input and issue appropriate error messages. They may also pop from the stack.

An LR (o) item of a grammar G is a production of G with a dot at some position of the right side. Thus, production A - XYZ yields the four items. A - .XYZ A – X.YZ A – XY.Z A – XYZ.

A Grammar G is said to be ambiguous if it generates more than one parse tree for some sentence of language L (G). I.e. both leftmost and rightmost derivations are the same for the given sentence.

An identifier is defined as a letter followed by zero or more letters or digits. The regular expression for an identifier is given a letter (letter | digit)*.

The analysis includes three stages:  Linear Analysis.  Hierarchical Analysis.  Semantic Analysis.

The code motion is an optimization technique that reduces the amount of code in the loop. This conversion is suitable for expressions that produce the same result regardless of the number of loop executions. Such expressions are placed before the loop.

 Call by value  Call by reference  Copy-restore  Call by name

The strategies are:  Static allocation  Stack allocation  Heap allocation

The activation record is a piece of memory used to manage the information required for one execution of the process. The various fields of the activation record are: • Temporary variables • Local variables • Saved machine registers • Control link • Access link • Actual parameters • Return values

In dynamic scope, the use of non-local variables refers to non-local data declared during the most recent call and still active. Therefore, every time a discovery is set for a local name called "procedure". In dynamic scope, a symbol table may be required at runtime.

Linear analysis is to read the character stream composing the source program from left to right and group them into tokens, which are character sequences with a common meaning. Also called lexical analysis or scanning.

The following are the various phases of a compiler:  Lexical Analyzer  Syntax Analyzer  Semantic Analyzer  Intermediate code generator  Code optimizer  Code generator

Cousins of the compiler are:  Preprocessors  Assemblers  Loaders and Link-Editors

The following is a list of some compiler construction tools:  Parser generators  Scanner generators  Syntax-directed translation engines  Automatic code generators  Data-flow engines

• Token-A sequence of characters with collective meaning. • Pattern-There is a set of strings in the input, for which the same token will be produced as the output. This set of strings is described by a rule called the pattern associated with the token. • Lexeme-A series of characters in the source program that match the token pattern.

• Union – L U M ={s | s is in L or s is in M} • Concatenation – LM ={st | s is in L and t is in M} • Kleene Closure – L* (zero or more concatenations of L) • Positive Closure – L+ ( one or more concatenations of L)

• One or more instances (+) • Zero or one instance (?) • Character classes ([abc] where a, b, c are alphabet symbols denote the regular expressions a | b | c.) • Non-regular sets

Semantic analysis is a way of performing certain checks to ensure that the various components of the program are grouped meaningfully. Mainly perform type checking.

Possible error recovery actions are: • Panic mode recovery • Deleting an extraneous character • Inserting a missing character • Replacing an incorrect character by a correct character • Transposing two adjacent characters

There are two important issues in parsing.  Specification of syntax  Representation of input after parsing. Reasons for separating the analysis phase into lexical and syntax analyzers:  Simpler design.  Compiler efficiency is improved.  Compiler portability is enhanced.

 SLR parser- simple LR parser  LALR parser- look ahead LR parser  Canonical LR parser

The following are the problems associated with top-down parsing:  Backtracking  Left recursion  Left factoring  Ambiguity

Student

In today's fast-paced world, staying informed about the latest updates both domestically and globally is more crucial than ever. With a plethora of news outlets struggling for attention, it's important to find a reliable source that provides not just

Review :

0 | 0 Reviews

Course Feature

Category Computer Science
Language English
Price 89.00
Validity 1 Year
Q & A 25
Exam Questions 10
Full Course PDF View

Wishlist

Add to Cart

Computer Science

Compiler Design (CD)

Lec-01 : Introduction

Student

Course Feature

Share

Data Communication

Distributed Systems

Adhoc & Sensor

Operating Systems(OS)

Useful Links

Download

Computer Science

1.Compiler Phases

2.Parsing & Types

3.Parser : LL, LR

4. Parser :SLR, CLR & LALR

5.Tools : LEX, YACC & PLY

6.SDT : Syntax Directed translation

7.Intermediate code Generation & Type checking

8.Symbol Table

9.Optimisation & Code Generator

Compiler Design (CD)

Lec-01 : Introduction

1.Compiler Phases

2.Parsing & Types

3.Parser : LL, LR

4. Parser :SLR, CLR & LALR

5.Tools : LEX, YACC & PLY

6.SDT : Syntax Directed translation

7.Intermediate code Generation & Type checking

8.Symbol Table

9.Optimisation & Code Generator

Q1 . What is the intermediate code representation for the expression a or b and not c?

Q2 . How do you calculate the cost of instruction?

Q3 . What is a DAG? Mention its applications.

Q4 . What is phrase-level error recovery?

Q5 . Define LR (o) items.

Q6 . Define ambiguous grammar.

Q7 . Write a regular expression for an identifier.

Q8 . List the subparts or phases of the analysis part?

Q9 . What is code motion?

Q10 . What are the various ways to pass a parameter in a function?

Q11 . List the different storage allocation strategies?

Q12 . What are the contents of the activation record?

Q13 . What is dynamic scoping?

Q14 . What is a linear analysis?

Q15 . List the various phases of a compiler?

Q16 . Mention some of the cousins of a compiler.

Q17 . List the various compiler construction tools.

Q18 . Differentiate Tokens, Patterns, and Lexeme.

Q19 . List the operations on languages.

Q20 . Mention the various notational shorthand for representing regular expressions.

Q21 . What does a semantic analysis do?

Q22 . List the various error recovery strategies for lexical analysis.

Q23 . Mention the basic issues in parsing. And why lexical and syntax analyzers are separated?

Q24 . Mention the types of Lr-Parser?

Q25 . What are the problems with top-down parsing?

Student

Course Feature

Share

Related Courses

Data Communication

Distributed Systems

Adhoc & Sensor

Operating Systems(OS)

Useful Links

Download