|
Unit-III |
||||||||||||||||||||||||
|
TOPIC: Type Checking & Run Time Environment |
||||||||||||||||||||||||
|
Unit-3/Lecture-01 |
||||||||||||||||||||||||
|
Semantic Analysis: Parsing only verifies that the
program consists of tokens arranged in a syntactically valid combination. Now
we’ll move forward to semantic
analysis, where we delve even deeper to
check whether they form a sensible set of instructions in the programming
language. Whereas any old noun phrase followed by some verb phrase makes a
syntactically correct English sentence, a semantically correct one has
subject verb agreement, proper use of gender, and the components go together
to express an idea that makes sense. For a program to be semantically valid,
all variables, functions, classes, etc. must be properly defined, expressions
and variables must be used in ways that respect the type system, access
control must be respected, and so forth. Semantic analysis is the front end’s
penultimate phase and the compiler’s last chance to weed out incorrect
programs. We need to ensure the program is sound enough to carry on to code
generation. A large part of semantic analysis consists of tracking
variable/function/type declarations and type checking. Type Checking: [RGPV, Dec 2012, June 2006] Type
checking is the process of verifying that each
operation executed in a program respects the type system of the language.
This generally means that all operands in any expression are of appropriate
types and number. Much of what we do in the semantic analysis phase is type
checking. Sometimes the rules regarding operations are defined by other parts
of the code (as in function prototypes), and sometimes such rules are a part
of the definition of the language itself (as in "both operands of a
binary arithmetic operation must be of the same type"). If a problem is
found, e.g., one tries to add a char pointer to a double in C, we encounter a
type error. A language is
considered strongly typed if
each and every type error is detected during compilation. Type checking can be
done during compilation time or during execution time. ·
Static type
checking is done at compile time.
The information the type checker needs is obtained via declarations and
stored in a master symbol table. After this information is collected, the
types involved in each operation are checked. It is very difficult for a
language that only does static type checking to meet the full definition of
strongly typed. Even motherly old Pascal, which would appear to be so because
of its use of declarations and strict type rules, cannot find every type
error at compile time. This is because many type errors can sneak through the
type checker. For example, if a and b are of type int and we assign very
large values to them, a * b may not be in the acceptable range of int, or an
attempt to compute the ratio between two integers may raise a division by
zero. These kinds of type errors usually cannot be detected at compile time.
C makes a somewhat paltry attempt at strong type checking—things as the lack
of array bounds checking, no enforcement of variable initialization or
function return create loopholes. The typecast operation is particularly
dangerous. By taking the address of a location, casting to something
inappropriate, dereferencing and assigning, you can wreak havoc on the type
rules. The typecast basically suspends type checking, which, in general, is a
pretty risky thing to do. ·
Dynamic type
checking is implemented by
including type information for each data location at runtime. For example, a
variable of type double would contain both the actual double value and some
kind of tag indicating "double type". The execution of any
operation begins by first checking these type tags. The operation is
performed only if everything checks out. Otherwise, a type error occurs and
usually halts execution. For example, when an add operation is invoked, it
first examines the type tags of the two operands to ensure they are
compatible. Dynamic type checking clearly comes with a runtime performance
penalty, but it usually much more difficult to subvert and can report errors
that are not possible to detect at compile time. Many compilers have built-in
functionality for correcting the simplest of type errors. Implicit type conversion, or coercion, is when a compiler finds
a type error and then changes the type of the variable to an appropriate
type. Type Conversion: [RGPV, Dec 2013] • Example. What’s the type
of “x + y” if: 1. x is of type real; 2. y is of type int; 3. Different machine
instructions are used for operations on reals and integers. • Depending on the
language, specific conversion rules must be adopted by the compiler to
convert the type of one of the operand of +. – The type checker in a
compiler can insert these conversion operators into the intermediate code. – Such an implicit type
conversion is called Coercion. • The syntax directed
definition for coercion from integer to real for a generic arithmetic
operation op is: Reference:
{Compilers: Principles, Techniques and Tools. Page No: 280-286} Reference:
{Principles of Compiler Design. Page No: 189-196}
|
||||||||||||||||||||||||
|
Unit-3/Lecture-02 |
||||||||||||||||||||||||
|
A Simple Type Checking System: P → D;E D → D;D D → id:T { addtype(id.entry,T.type) } T → char { T.type=char } T → int { T.type=int } T → real { T.type=real } T → ↑T1 { T.type=pointer(T1.type) } T → array[intnum] of T1 { T.type=array(1..intnum.val,T1.type) Type Checking of Expressions: E → id {
E.type=lookup(id.entry) } E → charliteral { E.type=char } E → intliteral { E.type=int } E → realliteral { E.type=real } E → E1 + E2 {
if (E1.type=int and E2.type=int) then E.type=int else if (E1.type=int and E2.type=real)
then E.type=real else if (E1.type=real and E2.type=int)
then E.type=real else if (E1.type=real and E2.type=real)
then E.type=real else E.type=type-error } E → E1 [E2] { if (E2.type=int and E1.type=array(s,t))
then E.type=t else E.type=type-error } E → E1 ↑ { if (E1.type=pointer(t))
then E.type=t else E.type=type-error } Type Checking of Statements: S ® id = E {
if (id.type=E.type then S.type=void else S.type=type-error } S ® if E then S1 {
if (E.type=boolean then S.type=S1.type else S.type=type-error } S ® while E do S1 { if (E.type=boolean then S.type=S1.type else S.type=type-error } Type Checking of Functions: Structural
Equivalence of Type Expressions: •
How do we know that two type expressions are
equal? •
As long as type expressions are built from
basic types (no type names), we may use structural equivalence between two
type expressions Structural Equivalence Algorithm (sequiv): if (s and t are same basic types) then return true else
if (s=array(s1,s2) and t=array(t1,t2))
then return (sequiv(s1,t1) and sequiv(s2,t2)) else
if (s = s1 x s2 and t = t1 x t2)
then return (sequiv(s1,t1) and sequiv(s2,t2)) else
if (s=pointer(s1) and t=pointer(t1)) then return
(sequiv(s1,t1)) else
if (s = s1 ® s2 and t = t1 ® t2) then return (sequiv(s1,t1)
and sequiv(s2,t2)) else
return false Reference:
{Compilers: Principles, Techniques and Tools. Page No: 343-346} |
||||||||||||||||||||||||
|
Unit-3/Lecture-03 |
||||||||||||||||||||||||
|
Overloading Functions & Operators: Overloaded
Symbol: one that has different meanings depending on its context Example:
Addition operator + ·
Resolving
(operator identification): overloading is resolved when a unique meaning is determined. ·
Context:
it is not always possible to resolve overloading by looking only the
arguments of a function -
Set of
possible types -
Context
(inherited attribute) necessary Function
“*” (i, j: integer) return complex; Function
“*” (x, y: complex) return complex; Overloaded function has the
following types: -
fcn(tuple(integer,
integer), integer) -
fcn(tuple(integer,
integer), complex) -
fcn(tuple(complex,
complex), complex) int i,
j; k = i *
j; Polymorphic Functions: Defn: a
piece of code (functions, operators) that can be executed with arguments of different
types. Examples:
Built in Operator indexing arrays, pointer manipulation Why use
them: facilitate manipulation of data structures regardless of types. Example: fun
length(lptr) = if null (lptr) then 0 else
length(+l(lptr)) + 1 A Language for Polymorphic
Functions: P
→D ; E D
→D ; D | id : Q Q
→∀α.
Q | T T
→fcn (T, T) | tuple (T, T) | unary (T) | (T) | basic |α E→E
(E) | E, E | id Example
of Polymorphism in Java Language: POLYMORPHISM: Polymorphism
literally means taking more than one form .polymorphism is a characteristic
of being able to assign a different behavior or value in a subclass,to
something that was declared in a parent class. Polymorphism
means—One name many form. Polymorphism is of two types: 1. Compile time: Overloding. 2. Run time: Overriding. Method(function) Overloading: In same
class, if name of the method remains common but the number and type of
parameters are different, then it is called method overloading in Java.
Example: Java Code class
functionOverload { /* * void add(int a, int b) // 1 - A method
with two parameters { * * int sum = a + b;
System.out.println(\"Sum of a+b is \"+sum); * * } */ void add(int a, int b, int c) { int sum
= a + b + c; System.out.println(\"Sum
of a+b+c is \"+sum); } void add(double a, double b) { double
sum = a + b; System.out.println(\"Sum
of a+b is \"+sum); } void add(String s1, String s2) { String s = s1 + s2; System.out.println(s); } } Reference:
{Compilers: Principles, Techniques and Tools. Page No: 361-365} |
||||||||||||||||||||||||
|
Unit-3/Lecture-04 |
||||||||||||||||||||||||
|
RUNTIME ENVIRONMENT: ·
Runtime organization of
different storage locations ·
Representation of scopes
and extents during program execution. ·
Components of executing
program reside in blocks of memory (supplied by OS). ·
Three kinds of entities
that need to be managed at runtime: 1. Generated code for various procedures and programs ·
Forms text or code segment
of your program: size known at compile time. 2. Data objects: ·
Global
variables/constants: size known at compile time ·
Variables declared within
procedures/blocks: size known ·
Variables created
dynamically: size unknown. 3.
Stack to keep track of
procedure activations. Subdivide memory
conceptually into code and data areas: ·
Code: Program ·
Instructions 1.
Stack: Manage activation
of procedures at runtime. 2.
Heap: holds variables
created dynamically Run-Time
Storage Organization: [RGPV, Dec 2013, Dec 2012] A program obtains a single
contiguous block of storage (virtual memory) from the operating system at the
start of program execution. The generated code assumes a subdivision of the
storage into different areas Code -- this area contains the
generated target code for all procedures in the program. The size of this can
be determined statically by the compiler/linker. Static Data-- this area contains
global data objects whose size can be determined statically at compile time.
Static variables are mapped to offsets in the static data area. Stack--runtime stack of
activation records reflecting the stack structure of dynamic procedure calls
and returns. An activation record contains the information needed by a single
procedure call. Local variables are mapped to offsets in the activation
record. Heap--used to store all other
program data (data that is dynamically sized or data with lifetime pattern
that cannot be represented in the run-time stack). Heap data allocations
incur more overhead than static or stack data allocation. Organization
of storage: ·
Fixed-size objects can be
placed in predefined locations. ·
The heap and the stack
need room to grow, however. Every execution of a
procedure is called ACTIVATION. The LIFETIME of an activation of procedure P
is the sequence of steps between the first and last steps of P’s body,
including any procedures called while P is running. Normally, when control
flows from one activation to another, it must (eventually) return to the same
activation. When activations are thusly nested, we can represent control flow
with ACTIVATION TREES. The STACK is used to
store: −
Procedure activations. −
The status of the machine
just before calling a procedure, so that the status can be restored when the
called procedure returns. The HEAP stores data
allocated under program control (e.g. by malloc() in C). Activation
records: [RGPV, June 2008] Any information needed for
a single activation of a procedure is stored in the ACTIVATION RECORD
(sometimes called the STACK FRAME). Today, we’ll assume the stack grows
DOWNWARD, as on, e.g., the Intel architecture. The activation record gets
pushed for each procedure call and popped for each procedure return. Static
allocation: [RGPV, Dec 2009] Statically allocated names
are bound to storage at compile time. Storage bindings of statically
allocated names never change, so even if a name is local to a procedure, its
name is always bound to the same storage. The compiler uses the type of a
name (retrieved from the symbol table) to determine storage size required. The
required number of bytes (possibly aligned) is set aside for the name. The
address of the storage is fixed at compile time. Limitations: −
The size required must be
known at compile time. −
Recursive procedures
cannot be implemented as all locals are statically allocated. −
No data structure can be
created dynamically as all data is static. Reference:
{Compilers: Principles, Techniques and Tools. Page No: 390-395}
|
||||||||||||||||||||||||
|
Unit-3/Lecture-05 |
||||||||||||||||||||||||
|
Dynamic
Storage Allocation: [RGPV, Dec 2013, Jun e 2006] Stack-Dynamic
Allocation ·
Storage is organized as a
stack. ·
Activation records are
pushed and popped. ·
Locals and parameters are
contained in the activation records for the call. ·
This means locals are
bound to fresh storage on every call. ·
If we have a stack growing
downwards, we just need a stack_top pointer. ·
To allocate a new
activation record, we just increase stack_top. ·
To de-allocate an existing
activation record, we just decrease stack_top. Address
generation in stack allocation: The position of the
activation record on the stack cannot be determined statically. Therefore the compiler
must generate addresses RELATIVE to the activation record. If we have a
downward-growing stack and a stack_top pointer, we generate addresses of the
form stack_top + offset. HEAP ALLOCATION:[RGPV, Dec 2013, June 2006] Some languages do not have
tree-structured allocations. In these cases, activations have to be allocated
on the heap. This allows strange situations, like callee activations that
live longer than their callers’ activations. This is not common Heap is used
for allocating space for objects created at run time. For example: nodes of
dynamic data structures such as linked lists and trees Dynamic memory allocation
and de-allocation based on the requirements of the programmalloc() and free() in C programs new()
and delete()
in C++ programs new()
and garbage collection in Java programs PARAMETERS PASSING: [RGPV, June 2009] A language has first-class
functions if functions can be declared within any scope passed as arguments
to other functions returned as results of functions. In a language with
first-class functions and static scope, a function value is generally
represented by a closure. A pair consisting of a pointer to function codes a
pointer to an activation record. Passing functions as arguments is very
useful in structuring of systems using up-calls. Call by value --
caller places r-value for actual parameter in the storage formal parameter. Call by reference --
caller places l-value for actual parameter in the storage for formal
parameter. Call by value result -- caller places r-value for the actual parameter in the storage for
formal parameter and also determines the l-value of the actual parameter. On
return, the current r-value of the formal parameter is copied to the l-value
of the actual parameter. An example: Passing Functions as Parameters main() { int x = 4; int f (int y) { return x*y; } int g (int →int h){ int x = 7; return h(3) + x; } g(f);//returns 12 } Reference:
{Compilers: Principles, Techniques and Tools. Page No: 396-410}
|
||||||||||||||||||||||||
|
Unit-3/Lecture-06 |
||||||||||||||||||||||||
|
SYMBOL TABLES: [RGPV, June 2008] A symbol table is a major data structure used in a
compiler. Associates attributes with identifiers used in a program. For
instance, a type attribute is usually associated with each identifier. A
symbol table is a necessary component Definition (declaration) of identifiers
appears once in a program .Use of identifiers may appear in many places of
the program text Identifiers and attributes are entered by the analysis
phases. When processing a definition (declaration) of an identifier. In
simple languages with only global variables and implicit declarations. The
scanner can enter an identifier into a symbol table if it is not already
there In block-structured languages with scopes and explicit declarations: ·
The parser and/or semantic analyzer enter identifiers and
corresponding attributes ·
Symbol table information is used by the analysis and
synthesis phases ·
To verify that used identifiers have been defined
(declared) ·
To verify that expressions and assignments are
semantically correct – type checking ·
To generate intermediate or target code Symbol
Table Interface The
basic operations defined on a symbol table include: ·
allocate – to allocate a new empty symbol table ·
free – to remove all entries and free the storage of a
symbol table ·
insert – to insert a name in a symbol table and return a
pointer to its entry · lookup – to search for a name and return a pointer to its entry · set_attribute – to associate an attribute with a given entry · get_attribute – to get an attribute associated with a given entry Key
points: · 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 Symbol Table can be used
in: 1. Compiler: a data
structure used by the compiler to keep track of identifiers used in the
source program. This is a compile-time data structure. Not used at run time. 2. Object files: a
symbol table (mapping var name to address) can be build into object programs,
to be used during linking of different object programs to resolve reference. 3. Executables: a
symbol table (again mapping name to address) can be included in executables,
to recover variable names during debugging Variable Declarations •In static-typing
programming languages, variables need to be declared before they are used.
The declaration provides the data type ofthe variable. E.g.int a; float b; string
c; •Most typically,
declaration is valid for the scope in which it occurs: •Function Scoping: each
variable is defined anywhere in the function in which it is defined, after
the point of definition •Block Scoping: variables
are only valid within the block of code in which it is defined, e.g, prog xxx {int a; float b} { int c; { int b; c = a + b; } return float(c) / b } Identifiers: User-supplied names, such as: •variable names •function names •labels (e.g., where goto
is allowed) Symbol table typically implemented as a hash table: •KEY: the symbol •VALUE: information about
the symbol A simple symbol table: •Data Structure: A hash
table where: • Key: a symbol • Value: the token for the
symbol (id, num, etc.) Reference:
{Compilers: Principles, Techniques and Tools. Page No: 429-436}
|