Ways to specify semantics
By a language reference manual
Most common method Clear and more precise May have omissions and ambiguities
By a defining translator
Program has to be executed to discover its meaning Drawbacks are
program behavior can not be known in advance. Bugs and machine dependencies in the translator become part of the language semantics. Translator may not be portable to all machines and may not be generally available
By a formal definition
Uses mathematical model which are precise but are also complex and abstract, requires study to understand
Attributes, binding and semantic functions
A fundamental abstraction mechanism in a programming language is the use of names, or identifiers, to denote language entities or constructs. To describe the semantics of a programming language it needs the concepts of name, location and value. Values are any storable quantities such as integers, reals, or array elements. Locations are addresses in the memory.
The meaning of a name is determined by the properties or attributes associated with the name. Examples: const int n = 5; Associates name n to the data type attribute integer constant and the value attribute 5 double f (int n) { .. .. } Associates the attribute function to the name f and the following additional attributes: 1. The number, names and data types of its parameters 2. The data type of its returned value 3. The body of code to be executed when f is called
Along with declarations, assignment statements can associate attributes to name. Examples: X=2; Associates the attribute value 2 to the variable x. int * y; y= new int; Allocates memory for an integer variable , that is associates a location attribute to it and assigns this location to *y, that is associates a new value attribute to y
Binding time of the attribute: the time during the translation/ execution process when it is computed and bound to a name Static binding occurs prior to execution Ex: const int n=2; int x; Dynamic binding occurs during execution Ex: x = 2; y = new int; Static attribute the attribute that is bound statically Dynamic attribute the attribute that is bound dynamically Functional languages have more dynamic bindings than imperative languages Binding time also depends on the translators Interpreter perform most bindings dynamically Compiler perform many bindings statically
Binding times can be further refined into subcategories.
Language definition time
Data type boolean is specified as having the two values true and false
Language implementation time
The value of a constant and the range of data type
Translation time
Attributes bound during parsing and semantic analysis
Link time
During the linking of the program with library Externally defined function
Load time
Location of a global variable
Execution time
On entry or exit from a procedure or on entry or exit from the entire program
Bindings must be maintained by a translator. The appropriate meanings are given to names during translation and execution.
A translator does this by creating a data structure to maintain the information.
This structure is called symbol table.
Mathematically a symbol table is a function from names to attributes. SymbolTable: Names -> Attributes Graphically we can represent this as Symbol Table Names Attributes
A compiler can compute only static attributes. Compiler generates the target code which maintains the value and location attributes during execution.
Names Symbol Table Static attributes
Environment binding of names to locations
Names Environment locations
Memory binding of locations to values
Locations memory Values
In interpreter symbol table and environment are combined. Memory is also included in this function.
Names environment Attributes (including locations and value)
Declarations, Blocks and Scope
Declarations are principle methods for establishing bindings Bindings can be determined by a declaration either implicitly or explicitly int x;
Establishes the data type x explicitly using the keyword int, but the exact location of x during execution is only bound implicitly and it may be static or dynamic depending on the location of this declaration in the program. Similarly the value of x is either zero or undefined depending on the location of the declaration.
int x = 0;
Explicitly binds 0 as the initial value of x
Bindings can be implicit in a declaration or entire declaration may be implicit. Languages with implicit declarations usually have naming conventions to establish other attributes.
In FORTRAN , All variables which are not explicitly declared are assumed to be integer if their names begin with I, J,K, L, M OR N and real otherwise.
In BASIC, variables ending in % are integers, variables ending with $ are strings and all others are real. In C and C++, declarations that bind all potential attributes are called definitions Declarations that only partially specify attributes are called declarations
Double f( int x); Struct x; declarations
Declarations are commonly associated with particular language constructs and are syntactically and semantically attached to these constructs.
Example for such construct is Block.
Block consists of a sequence of declarations followed by a sequence of statements and surrounded by syntactic markers such as braces or begin and end pairs.
In C, blocks are compound statements appear as the body of functions in function definition and also anywhere an ordinary program statement could appear. In addition to declarations associated with blocks, C also has an external or global declarations outside any compound statement. Declarations that are associated with a specific block are called local, while declarations in surrounding blocks are called non local declarations
Other language constructs beside blocks are important sources of declarations All structured data types are defined using local declarations associated with the type In C, a struct definition is composed of local variable declarations within it.
struct A { int x; double y; struct { int *x; char y; } z; };
/* nested member declarations */
Similarly in object oriented languages, the class is an important source of declarations
Declarations bind various attributes to names, depending on the kind of declarations. Each of these bindings itself has an attribute that is determined by the position of the declaration in the program and the language rules for the binding. The scope of binding is the region of the program over which the binding is maintained. Scope of declaration- if all the bindings established by the declaration have identical scopes. Lexical scope rule- in a block structured language like C, where blocks can be nested, the scope of a binding is limited to the block in which its associated declarations appear.
It follows the structure of the blocks as they appear in the written code.
int x; void p(void) { char y; /* ... */ } /* p */ void q(void) { double z; /* ... */ } /* q */ main() { int w[10]; /* ... */ }
x z q
main
A simple C program wit brackets indicating scope
Declarations in nested blocs take precedence over previous declarations.
1. 2. 3. 4. 5. 6. 7. 8. 9. 10. int x; void p(void) { char x; x= a; /* assigns to char x */ } main() { x= 2; /* assigns to global */ . }
The declaration of x in p (line 3) takes precedence over the global declaration of x (line 1) in the body of p. The global integer x can not be accessed from within p. the global declaration of x is said to be have scope hole inside p. Visibility includes only those regions of a program where the bindings of a declaration apply while scope includes scope hole also. In C++, scope resolution operator in used to access the hidden declarations. In Ada, dot operator is used similar to record structure access. This is called visibility by selection
Symbol Table
Symbol table is like a variable dictionary Supports insertion, lookup and deletion of names with attributes Represents the bindings in declarations The data structures used to maintain the symbols are hash tables, trees and lists
Schematic Representation
Declarations are processed in a stack like fashion. On entry into a block: all declarations of that block are processed and corresponding bindings are added to the symbol table. On exit from the block: the bindings provided by the block are removed, restoring any previous bindings that may have existed. Symbol table can be viewed schematically as a collection of names
Each name has a stack of declarations associated with it. The declarations on top of the stack is the one whose scope is currently active.
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18)
int x; char y; void p(void) { double x; ... { int y[10]; } } /* p */ void q(void) { int y; ... } /* q */ int main() { char x; ... }
name
bindings
doub le local to p
int global
char global
void function
Symbol table structure at line 5
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18)
int x; char y; void p(void) { double x; ... { int y[10]; } } /* p */ void q(void) { int y; ... } /* q */ int main() { char x; ... }
name
bindings
doub le local to p int array local to nested block in p void function
int global
char global
Symbol table structure at line 7
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18)
int x; char y; void p(void) { double x; ... { int y[10]; } } /* p */ void q(void) { int y; ... } /* q */ int main() { char x; ... }
name
bindings
int global
char global
void function
Symbol table structure at line 10
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18)
int x; char y; void p(void) { double x; ... { int y[10]; } } /* p */ void q(void) { int y; ... } /* q */ int main() { char x; ... }
name
bindings
int global
int local to q
char global
void function void function
Symbol table structure at line 13
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18)
int x; char y; void p(void) { double x; ... { int y[10]; } } /* p */ void q(void) { int y; ... } /* q */ int main() { char x; ... }
name
bindings
int global
char global
void function void function
Symbol table structure at line 14
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18)
int x; char y; void p(void) { double x; ... { int y[10]; } } /* p */ void q(void) { int y; ... } /* q */ int main() { char x; ... }
name
bindings char local to main
int global
char global void function void function int function
main
Symbol table structure at line 17
Static scoping: in this representation symbol table processes the declarations statically, prior to execution Dynamic scoping: declarations are processed as they are encountered along an execution path through the program
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18) 19)
#include <stdio.h> int x = 1; char y = 'a'; void p(void) { double x = 2.5; printf("%c\n",y); { int y[10]; } } void q(void) { int y = 42; printf("%d\n",x); p(); } int main() { char x = 'b'; q(); return 0; }
name
bindings char= b local to main
Int=1 global
char =a global void function void function int function
main
Symbol table structure at line 17 using dynamic scope
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18) 19)
#include <stdio.h> int x = 1; char y = 'a'; void p(void) { double x = 2.5; printf("%c\n",y); { int y[10]; } } void q(void) { int y = 42; printf("%d\n",x); p(); } int main() { char x = 'b'; q(); return 0; }
name
bindings char= b local to main
Int=1 global
int = 42 local to q void function void function int function
char =a global
main
Symbol table structure at line 12 using dynamic scope
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18) 19)
#include <stdio.h> int x = 1; char y = 'a'; void p(void) { double x = 2.5; printf("%c\n",y); { int y[10]; } } void q(void) { int y = 42; printf("%d\n",x); p(); } int main() { char x = 'b'; q(); return 0; }
name
double = 2.5 Local to p
bindings
char= b local to main
Int=1 global
int =42 Local to q void function void function int function
char =a global
main
Symbol table structure at line 6 using dynamic scope
Dynamic scoping affects the semantic of the program
When a nonlocal name is used in an expression or statement, the declaration that applies to that name can not be determined by simply reading the program. Since non-local variable references can not be predicted prior to execution, neither can the data types of these variables.
1) 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18)
struct { int a; char b; double c; } x = {1,'a',2.5}; void p(void) { struct { double a; int b; char c; } y = {1.2,2,'b'}; printf("%d, %c, %g\n",x.a,x.b,x.c); printf("%f, %d, %c\n",y.a,y.b,y.c); } int main() { p(); return 0; }
Allocation, Lifetimes and the Environment
Environment : maintains the bindings of names to locations. Environment may be constructed
statically (at load time) eg: FORTRAN dynamically (at execution time) eg: LISP A mixture of two eg: C, C++, Ada, Java
Not all names in a program are bound to locations. In a compiled language, names of constants and data types may represent purely compile time quantities that have no existence at load or execution time. const int MAX = 10;
Declarations are used to construct the environment. In a compiler, the declarations are used to indicate what allocation code the compiler is to generate as the declaration is processed. In an interpreter, attribute binding by a declaration includes the binding of locations.
Allocations in Block structure language
Global variables are allocated statically. Local variables are allocated dynamically. The environment binds the locations to local variables in a stack based fashion.
1) A: { int x; 2) char y; 3) /* ... */ 4) B: { double x; 5) int a; 6) /* ... */ 7) } /* end B */ 8) C: { char y; 9) int b; 10) /* ... */ 11) D: { int x; 12) double y; 13) /* ... */ 14) } /* end D */ 15) /* ... */ 16) } /* end C */ 17) /* ... */ 18) } /* end A */
After the entry into A
X Location bindings of A
Y
. .
Unallocated space
After entry into block B X Location bindings of A
Y
x a
Location bindings of B
..
1) A: { int x; 2) char y; 3) /* ... */ 4) B: { double x; 5) int a; 6) /* ... */ 7) } /* end B */ 8) C: { char y; 9) int b; 10) /* ... */ 11) D: { int x; 12) double y; 13) /* ... */ 14) } /* end D */ 15) /* ... */ 16) } /* end C */ 17) /* ... */ 18) } /* end A */
When block C entered
X Location bindings of A
Y
y b
Location bindings of C
.
On entry into Block D X Location bindings of A
Y
y b x
Location bindings of C Location bindings of D
y
. ..
Behavior of environment in procedures and function blocks
The local variables of a procedure will be allocated when the corresponding procedure is called. Each time a procedure is called, new local variable will be allocated. Each call to a function is called activation The corresponding region of allocated memory is referred as an activation record
In a block structured language with lexical scope, the same name may be associated with several different locations. To distinguish among name, an allocated location, and declaration that causes them to be bound, the allocated location is called as object. An object is an area of storage that is allocated in the environment as a result of the processing of a declarations.
Lifetime or extent
The life time or extent of an object is the duration of its allocation in the environment It can be extended beyond the region of a program where they may be accessed.
Arbitrary allocation and deallocation
This is done using new and delete ( or malloc and free) The environment which provides this is heap Allocation on the heap is referred to as dynamic allocation Allocations of local variables according to stack based scheme is called as stack based or automatic allocation
In a block structured language with heap allocation, there are 3 kinds of allocation in the environment
Static (for global variables) Automatic (for local variables) Dynamic (for heap allocation) These categories also referred to as the storage classes of the variable.
The structure of a typical environment with stack and a heap
Static (global) area stack
unallocated
heap