|
UNIT – I |
||||||||||||||||||||||
|
TOPIC:
Introduction to Compiling and Lexical Analysis |
||||||||||||||||||||||
|
Unit-I/Lecture-01 |
||||||||||||||||||||||
|
Introduction of Compiler: Compiler is a program which translates a program written in one
language (the source language) to an equivalent program in other language
(the target language), if there is no error. Usually the source language is a
high level language like Java, C, and FORTRAN etc. whereas the target
language is machine code or "code" that a computer's processor
understands. The source language is optimized for humans. It is more
user-friendly, to some extent platform-independent. They are easier to read,
write, and maintain and hence it is easy to avoid errors. Ultimately,
programs written in a high-level language must be translated into machine
language by a compiler. The target machine language is efficient for hardware
but lacks readability. Main Tasks of Compiler: ·
Translates from one representation of the
program to another ·
Typically from high level source code to low
level machine code or object code ·
Source code is normally optimized for human
readability - Expressive: matches our notion of languages
(and application?!) - Redundant to help avoid programming errors ·
Machine code is optimized for hardware - Redundancy is reduced Many modern compilers share a common 'two stage' design. The
"front end" translates the source language or the high level
program into an intermediate representation. The second stage is the
"back end", which works with the internal representation to produce
code in the output language which is a low level code. The higher the
abstraction a compiler can support, the better it is. · Compiler and Other Tools All
development systems are essentially a combination of many tools. For
compiler, the other tools are pre-processor, debugger, assembler, linker,
loader, editor etc. If these tools have support for each other than the
program development becomes a lot easier. Preprocessor A
preprocessor produce input to compilers. They may perform the following
functions. 1. Macro processing: A preprocessor
may allow a user to define macros that are short hands for longer constructs.
2. File inclusion: A preprocessor may
include header files into the program text. 3. Language Extensions: These
preprocessor attempts to add capabilities to the language by certain amounts
to build-in macro Assembler Programmers
found it difficult to write or read programs in machine language. They begin
to use a mnemonic (symbols) for each machine instruction, which they would
subsequently translate into machine language. Such a mnemonic machine
language is now called an assembly language. Programs known as assembler were
written to automate the translation of assembly language in to machine
language. The input to an assembler program is called source program, the
output is a machine language translation (object program). Linkers A linker combines object code (machine code that
has not yet been linked) produced from compiling and assembling many source
programs, as well as standard library functions and resources supplied by the
operating system. This involves resolving references in each object file to
external variables and procedures declared in other files. Loaders Compilers, assemblers and linkers usually
produce code whose memory references are made relative to an undetermined
starting location that can be anywhere in memory (relocatable machine code).
A loader calculates appropriate absolute addresses for these memory locations
and amends the code to use these addresses. Reference: {Compilers: Principles, Techniques and Tools. Page No: 1,16} |
||||||||||||||||||||||
|
Unit-I/Lecture-02 |
||||||||||||||||||||||
|
Major Data Structures in a
Compiler: Token: ·
Represented by an integer
value or an enumeration literal ·
Sometimes, it is necessary
to preserve the string of characters that was scanned ·
For example, name of an
identifiers or value of a literal Syntax Tree: ·
Constructed as a
pointer-based structure ·
Dynamically allocated as
parsing proceeds ·
Nodes have fields
containing information collected by the parser and semantic analyzer Symbol Table: ·
Keeps information
associated with all kinds of identifiers: ·
Constants, variables,
functions, parameters, types, fields, etc. ·
Identifiers are entered by
the scanner, parser, or semantic analyzer ·
Semantic analyzer adds
type information and other attributes ·
Code generation and
optimization phases use the information in the symbol table ·
Insertion, deletion, and
search operations need to efficient because they are frequent ·
Hash table with
constant-time operations is usually the preferred choice ·
More than one symbol table
may be used Literal Table: ·
Stores constant values and
string literals in a program. ·
One literal table applies
globally to the entire program. ·
Used by the code generator
to: ·
Assign addresses for
literals. ·
Enter data definitions in
the target code file. ·
Avoids the replication of
constants and strings. ·
Quick insertion and lookup
are essential. Deletion is not necessary. Temporary Files: ·
Used historically by old
compilers due to memory constraints ·
Hold the data of various
stages Reference: {Compiler Construction: Principles and Practice. Page No: 3} The
Analysis-Synthesis Model of Compilation: [RGPV, Dec
2013] There
are two parts to compilation: analysis and synthesis. The analysis part
breaks up the source program into constituent pieces and creates an
intermediate representation of the source program. The synthesis part constructs
the desired target program from the intermediate representation. Of the two
parts, synthesis requires the most specialized technique. • There
are two parts of compilation: 1. Analysis
Part (Machine
Independent/Language Dependent): This part determines the operations implied
by the source program which are recorded in a tree structure. 2. Synthesis
Part (Machine
Dependent/Language independent): This part takes the tree structure and
translates the operations therein into the target program The Analysis consists of three steps. ·
The LINEAR ANALYSIS in which the stream of characters making up the
source program is read from left-to-right
and converted into a stream of words, where a word is a sequence of
characters with a collective meaning. ·
The HIERARCHICAL ANALYSIS (Syntactic Analysis) in which words are
grouped into nested collections (grammatical phrases) with a collective
meaning represented by a PARSE TREE. ·
The SEMANTICAL ANALYSIS in which certain checks are performed to ensure
that the components of a program fit together meaningfully (type checking,
type conversion) and to report on errors. The Synthesis consists of two steps. ·
Code generator: Code generator
produces the object code by deciding on the memory locations for data,
selecting code to access each datum and selecting the registers in which each
computation is to be done. Many computers have only a few high speed
registers in which computations can be performed quickly. A good code
generator would attempt to utilize registers as efficiently as possible. ·
Code Optimization: This is
optional phase described to improve the intermediate code so that the output
runs faster and takes less space. Its output is another intermediate code
program that does the same job as the original, but in a way that saves time
and / or spaces. Compiler structure (Front-End and Back-End: ·
Front End (Language
specific) and Back End (Machine specific) parts of compilation Reference: {Compilers: Principles, Techniques and Tools. Page No: 2-4}
|
||||||||||||||||||||||
|
Unit-I/Lecture-03 |
||||||||||||||||||||||
|
Bootstrapping: [RGPV Dec
2013, June 2006, June 2007]
Writing a compiler in assembly language directly can be a very tedious
task. It is generally written in some high level language. What if the
compiler is written in its intended source language itself? Bootstrapping: A compiler can be characterized by three languages: the source
language (S), the target language (T), and the implementation language (I).
The three languages S, I, and T can be quite different. Such a compiler is
called cross-compiler Compilers are of two kinds: native and cross. Native compilers are written in the same language as the target
language. For example, SMM is a compiler for the language S that is in a
language that runs on machine M and generates output code that runs on
machine M. Cross compilers are written in different language as the target
language. For example, SNM is a compiler for the language S that is in a
language that runs on machine N and generates output code that runs on
machine M. Bootstrapping: The compiler of LSN is written in language S. This compiler code is
compiled once on SMM to generate the compiler's code in a language that runs
on machine M. So, in effect, we get a compiler that converts code in language
L to code that runs on machine N and the compiler itself is in language M. In
other words, we get LMN. Bootstrapping a Compiler. Using the technique described in the last slide, we try to use a
compiler for a language L written in L. For this we require a compiler of L
that runs on machine M and outputs code for machine M. First we write LLN
i.e. we have a compiler written in L that converts code written in L to code
that can run on machine N. We then compile this compiler program written in L
on the available compiler LMM. So, we get a compiler program that can run on
machine M and convert code written in L to code that can run on machine N
i.e. we get LMN. Now, we again compile the original written compiler LLN on
this new compiler LMN we got in last step. This compilation will convert the
compiler code written in L to code that can run on machine N. So, we finally
have a compiler code that can run on machine N and converts code in language
L to code that will run on machine N. i.e. we get LNN. Bootstrapping is obtaining a compiler for a language L by writing the
compiler code in the same language L. Reference: {Compiler Construction: Principles and Practice. Page No: 3}
|
||||||||||||||||||||||
|
Unit-I/Lecture-04 |
||||||||||||||||||||||
|
Phases of a Compiler: [RGPV Dec 2014, June 2007, June 2006] The different phases of a compiler are as follows 1. Lexical Analysis 2. Syntax Analysis 3. Semantic Analysis 4. Intermediate Code generator 5. Code Optimization 6. Code generation.
Lexical Analysis: LA or Scanners
reads the source program one character at a time, carving the source program
into a sequence of atomic units called tokens. Tasks of lexical analysis
phase are- 5. Scanning 6. Tokens
Generation 7. Lexemes
Identification 8. Patterns
Matching 9. Input Buffering 10.
Buffer pairs 11. Sentinels 12. Specification
of Tokens Syntax Analysis: The second stage of translation is called Syntax analysis or parsing.
In this phase expressions, statements, declarations etc… are identified by
using the results of lexical analysis. Syntax analysis is aided by using
techniques based on formal grammar of the programming language. Semantic Analysis: In semantic
analysis phase semantic rules are checked. E.g. Type checking. Intermediate Code Generations: An
intermediate representation of the final machine language code is produced.
This phase bridges the analysis and synthesis phases of translation. Code Optimization: This is
optional phase described to improve the intermediate code so that the output
runs faster and takes less space. Code Generation: The last phase
of translation is code generation. A number of optimizations to reduce the
length of machine language program are carried out during this phase. The
output of the code generator is the machine language program of the specified
computer. Table Management: This is the
portion to keep the names used by the program and records essential information
about each. The data structure used to record this information called a
‘Symbol Table’. A compiler needs to
collect information about all the data objects that appear in the source
program. The information about data objects is collected by the early phases
of the compiler-lexical and syntactic analyzers. The data structure used to
record this information is called as Symbol Table. Error Handlers: It is invoked
when a flaw error in the source program is detected. One of the most
important functions of a compiler is the detection and reporting of errors in
the source program. The error message should allow the programmer to
determine exactly where the errors have occurred. Errors may occur in all or
the phases of a compiler. Whenever a
phase of the compiler discovers an error, it must report the error to the
error handler, which issues an appropriate diagnostic msg. Both of the
table-management and error-Handling routines interact with all phases of the
compiler. Reference: {Compilers: Principles, Techniques and Tools. Page No: 10-15}
|
||||||||||||||||||||||
|
Unit-1/Lecture-05 |
||||||||||||||||||||||
|
Lexical Analysis: [RGPV Dec 2014, Dec 2013, June 2009] It is the
first phase of a Compiler. Lexical analyzer or Scanner reads the characters
in the source program and groups them into a stream of tokens. The usual
tokens are identifiers, keywords, Constants, Operators and Punctuation
Symbols such as Comma and Parenthesis. Each token is a Sub-String of the
source program that is to be treated as a single unit. Tokens are of two
types:
A token is
treated as a pair consisting of two parts. 1.
Token type 2.
Token Value. The character
sequence forming a token is called the lexeme for the token. Certain tokens
will be increased by a lexical value. The lexical analyzer not only generates
a token, but also it enters the lexeme into the symbol table. Token values
are represented by pairs in square brackets. The second component of the pair
is an index to the symbol table where the information’s are kept. For eg.
Consider the expression a = b + c * 20 After lexical
Analysis it will be. id1 = id2 +
id3 *20 The lexical
phase can detect errors where the characters remaining in the input do not
form any token of the language. Eg: Unrecognized Keyword. Role of Lexical Analyzer [RGPV, Dec
2013] 5.
Scanning 6.
Tokens Generation 7.
Lexemes Identification 8.
Patterns Matching 1.
Input Buffering 2.
Buffer pairs 3.
Sentinels 4.
Specification of Tokens Interface to other phases As the first
phase of compiler, the main task of the lexical analyzer is to read the input
characters of the source program group them into lexemes and produce as
output a sequence of tokens for each lexeme in the source program. When the
lexical analyzer discovers a lexeme constituting an identifier, it needs to
enter that lexeme into the symbol table. The lexical analyzer not only
identifies the lexemes but also pre-processes the source text like removing
comments, white spaces, etc. Lexical analyzers are divided into a
cascade of two processes:
Scanning- It consists of simple processes that do not require the
tokenization of the input such as deletion of comments, compaction of
consecutive white space characters into one.
Lexical Analysis- This is the more complex portion where the scanner
produces sequence of tokens as output. Tokens, Patterns and Lexemes:
Input Buffering: [RGPV, Dec 2013, June
2009] Buffer Pairs:
Because of the amount of time taken to process characters and the large
number of characters that must be processed during the compilation of a large
source program, specialized buffering techniques have been developed to
reduce the amount of overhead required to process a single input character. Two pointers
to the input are maintained:
Pointer Lexeme Begin, marks
the beginning of the current lexeme, whose extent we are attempting to
determine
Pointer Forward scans ahead
until a pattern match is found. Once the next
lexeme is determined, forward is
set to character at its right end. Then, after the lexeme is recorded as an
attribute value of a token returned to the parser, Lexeme Begin is set to the character immediately after the lexeme
just found. Sentinels: If we use
the scheme of Buffer pairs we must check, each time we advance forward, that
we have not moved off one of the buffers; if we do, then we must also reload
the other buffer. Thus, for each character read, we make two tests: one for
the end of the buffer, and one to determine what character is read. We can
combine the buffer-end test with the test for the current character if we
extend each buffer to hold a sentinel character at the end. The sentinel is a
special character that cannot be part of the source program, and a natural
choice is the character EOF. Note that EOF
retains its use as a marker for the end of the entire input. Any EOF that
appears other than at the end of a buffer means that the input is at an end. Specification of Tokens: Regular
expressions are important part in specifying lexeme patterns. While they
cannot express all possible patterns, they are very effective in specifying
those type of patterns that we actually need for tokens. Reference: {Compilers: Principles, Techniques and Tools. Page No: 83-90}
|
||||||||||||||||||||||
|
Unit-1/Lecture-06 |
||||||||||||||||||||||
|
LEX: A Scanner
Generator [RGPV Dec 2014, Dec
2012, June
2007] LEX is a tool
for automatically generating lexical analyzers. A LEX source program is a
specification of a lexical analyzer, consisting of a set of regular
expressions together with an action for each regular expression. The output
of LEX is a lexical analyzer program. Lex specifications: A Lex program (the .l file ) consists of three parts: declarations %% translation rules %% auxiliary procedures 1. The declarations section includes declarations of variables,
manifest constants (A manifest constant is an identifier that is declared to
represent a constant e.g. # define PIE 3.14), and regular definitions.
2. The translation rules of a Lex program are statements of the
form : p1 {action 1} p2 {action 2} … … pn {action n} Where each p is a regular expression and each action is a
program fragment describing what action the lexical analyzer should take when
a pattern p matches a lexeme. In Lex the actions are written in C. 3. The third
section holds whatever auxiliary procedures are needed by the actions.
Alternatively these procedures can be compiled separately and loaded with the
lexical analyzer. LEX Specification File To Identify tokens of Language C: [RGPV, Dec
2012] Reference: {Compiler Construction: Principles and Practice. Page No: 81-82}
|
||||||||||||||||||||||
|
Unit-1/Lecture-07 |
||||||||||||||||||||||
|
FINITE AUTOMATA: [RGPV Dec 2014, Dec 2009] Automation is defined as a system where information is transmitted and
used for performing some functions without direct participation of man. 1. An automation in which the output depends only on the input is
called automation without memory. 2. An automation in which the output depends on the input and state
also is called as automation with memory. 3. An automation in which the output depends only on the state of the
machine is called a Moore machine. 4. An automation in which the output depends on the state and input at
any instant of time is called a mealy machine. DESCRIPTION OF AUTOMATA 1. An automata has a mechanism to read input from input tape, 2. Any language is recognized by some automation, Hence these
automation are basically language ‘acceptors’ or ‘language recognizers’. Types of Finite Automata 1.
Deterministic Automata 2.
Non-Deterministic Automata. 1. DFA (DETERMINISTIC AUTOMATA): A deterministic finite automata has at most one transition from each
state on any input. A DFA is a special case of a NFA in which:- 1, it has no transitions on input € , 2, each input symbol has at most one transition from any state. DFA formally defined by 5 tuple notation M = (Q, Σ, δ, qo,
F), where Q is a finite ‘set of states’, which is non empty. Σ is ‘input alphabets’, indicates input set. qo is an ‘initial state’ and qo is in Q ie, qo, Σ, Q F is a set of ‘Final states’, δ is a ‘transmission function’ or mapping function, using this
function the next state can be determined. The regular expression is converted into minimized DFA by the following
procedure: Regular expression → NFA → DFA → Minimized DFA The Finite Automata is called DFA if there is only one path for a
specific input from current state to next state. For Example: 2.
NFA (NONDETERMINISTIC AUTOMATA): A NFA is a mathematical model that consists of ·
A set of states S. ·
A set of input symbols Σ. ·
A transition for move from one state to another. ·
A state so that is distinguished as the start (or initial)
state. ·
A set of states F distinguished as accepting (or final)
state. ·
A number of transitions to a single symbol. A NFA can be diagrammatically
represented by a labeled directed graph, called a transition graph, In which
the nodes are the states and the labeled edges represent the transition
function. This graph looks like a transition
diagram, but the same character can label two or more transitions out of one
state and edges can be labeled by the special symbol € as well as by input symbols. The transition graph for an NFA
that recognizes the language ( a | b ) * abb is shown Reference:
{Compilers: Principles, Techniques and Tools. Page No: 113-120}
|
||||||||||||||||||||||
|
Unit-1/Lecture-08 |
||||||||||||||||||||||
|
REGULAR EXPRESSIONS: [RGPV, Dec 2013, Dec 2012] Definition. R is a regular expression, if R is one of the following: 1. ε 2. a, for some a ∈ Σ 3. ∅ 4. (R1 ∪ R2), where R1
and R2 are regular expressions 5. R1R2, where R1 and R2 are regular expressions 6. (R1)*, where R1 is a regular expression Note: it is a inductive definition - it is defined based on itself. Note: the + symbol will at times be used for union (0+1)* R+ = RR R+ U∈ = R* L((0+1)*1(0+1)*) = {w|w contains a 1 in the middle} Equivalence of Regular Expressions and Finite Automata Theorem. A language is regular if and only if some regular expression
describes it. We need to prove two directions: 1. If a language is described by a regular expression, then it is
regular. 2. If a language is regular, then there is a regular expression that
describes it. Part 1. This is the easy part - "If a language is described by a
regular expression, then it is regular." Say that a regular expression R describes some language A. We will convert R to an NFA N that recognizes A. Then, A has to be
regular. R has one of six possible
forms: In the last three cases, the
constructions given in the proofs that the class of regular languages is
closed under the regular operations can be used here as well. That is, we
assume R1 and R2 are recognized by NFAs N1 and N2, and use the same
constructions to create N from N1 and N2. Convert the following regular
expression to a NFA: Strategy: Regular expression → NFA → DFA →
Minimized DFA RE = (0+1)*1(0+1)* Note: using the letter
"e" to represent ε Note: For the above resulting NFA
- major elimination of states and transistion can take place. Double e's can be ripped
out. Part
2: We need to show that if a language is regular, then
it is described by a regular expression. "If a language is regular,
then there is a regular expression that describes it." If a language A
is regular, then it is recognized by a DFA M. We will show how to convert an
arbitrary DFA M into an equivalent regular expression. The main idea is that
we will gradually eliminate the states of M. Reference:
{Compilers: Principles, Techniques and Tools. Page No: 121-125}
|