Unit - 4
Run time environments
The Symbol Table is an essential data structure generated and maintained by the compiler to keep track of variable semantics, i.e. to store information about scope and binding information about names, information about instances of different entities, such as variable and function names, classes, objects, etc.
A table of symbols used for the following purposes:
● It is used to store the names of all individuals in one location in a standardised way.
● To check if a variable has been declared, it is used.
● It is used to evaluate a name's scope.
● It is used to enforce type checking by verifying the assignments and semantically correct expressions in the source code.
A table of symbols may either be linear or a table of hashes. Using the following format, the entry for each name is kept
<symbol name, type, attribute>
For reference, suppose that a variable stores information about the following declaration of a variable:
Static int salary
Then, in the following format, it stores an entry:
<salary, int, static>
The attribute of the clause includes the name-related entries.
Symbol Table entries –
Every entry in the symbol table is associated with attributes that the compiler supports at various stages.
Items contained in Table Symbols:
● Variable names and constants
● Procedure and function names
● Literal constants and strings
● Compiler generated temporaries
● Labels in source languages
Details from the Symbol table used by the compiler:
● Data type and name
● Declaring procedures
● Offset in storage
● If structure or record then, pointer to structure table.
● For parameters, whether parameter passing by value or by reference
● Number and type of arguments passed to function
● Base Address
Operations of Symbol table –
The basic operations listed on the table of symbols include:
Operation | Functions |
Insert | To insert a name into a table of symbols and return a pointer to its input.
|
Lookup | To check for a name and return its input to the pointer
|
Free | Removal of all entries and free symbol table storage.
|
Allocate | To assign a new empty table of symbols. |
Implementation:
If the compiler is used to handle a small amount of data, the symbol table can be implemented in the unordered list.
In one of the following methods, a symbol table can be implemented:
● Linear list
● List
● Hash table
● Binary search tree
Key takeaway:
The symbol table is implemented primarily as a hash table.
A significant data structure used in a compiler is the Symbol table.
A table of symbols may either be linear or a table of hashes
Explicit and implicit memory allocation to variables
● The majority of programming languages allow for dynamic memory allocation.
● Pascal has new(p) and dispose(p) functions for pointer types.
● The standard library of C includes malloc() and free().
● The new and unrestricted operators are available in C++.
● These are all EXPLICIT allocation examples.
● IMPLICIT allocation is used in other languages such as Python and Lisp.
Garbage - locating variables that are no longer referenced by the program.
● The programmer must be careful to free every dynamically allocated variable in languages with explicit deallocation, or GARBAGE will collect.
● Garbage is memory that has been dynamically allocated but is no longer accessible due to the lack of pointers pointing to it.
● GARBAGE COLLECTION is occasionally required in some languages with implicit deallocation.
● Other languages with implicit deallocation keep track of allocated memory references and automatically free it when no one refers to it.
The strategies required to enable dynamic storage allocation are largely determined by how storage is dealt with. If implicit deallocation is used, the run-time support package is in charge of deciding when a storage block is no longer required. When deallocation is done explicitly by the program, the compiler has less work to complete.
The strategies required to achieve dynamic storage allocation approaches are determined by how space is dealt with. Ie, implicitly or explicitly.
Explicit Allocation of Fixed-Sized Blocks
● Blocks with a fixed size are used in the simplest kind of dynamic allocation.
● Allocation and deallocation can be completed fast and with minimal storage requirements.
● Assume that blocks are to be pulled from a single storage place. The region is initialized by using a piece of each block to link to the next block.
● A pointer to the first block is available. Allocation entails removing a block from the list, while deallocation entails returning the block to the list.
Fig 1: Explicit allocation of fixed sized
Explicit Allocation of Variable-Sized Blocks
● Storage can become fragmented as blocks are allocated and deallocated, resulting in the heap consisting of alternative blocks that are free.
● If a program allocates five blocks and then de-allocates the second and fourth, this situation can arise.
● If blocks are fixed size, fragmentation is unimportant; but, if they are variable size, we couldn't allocate a block larger than any of the free blocks, despite the fact that space was available.
● Allocating variable-sized blocks can be done in a variety of ways, including first fit, worst fit, and best fit.
Fig 2: Explicit allocation of variable sized
Implicit Deallocation
● Because the run-time package has to know when a storage block is no longer in use, implicit deallocation necessitates collaboration between the user program and the run-time package.
● This collaboration is made possible by the standardization of storage block formats.
Fig 3: Implicit deallocation
Two approaches can be used for implicit deallocation.
● Reference counts
● Marking techniques
Reference counts:
● The number of blocks that point directly to the current block is kept track of. When this count reaches 0, the block can be deallocated because it can no longer be referenced.
● To put it another way, the block has devolved into trash that can be collected. Keeping track of reference counts can be time consuming.
Marking techniques:
Another option is to temporarily halt the user program's execution and utilize the frozen pointers to ascertain which blocks are in use.
Key takeaway
The strategies required to enable dynamic storage allocation are largely determined by how storage is dealt with. If implicit deallocation is used, the run-time support package is in charge of deciding when a storage block is no longer required. When deallocation is done explicitly by the program, the compiler has less work to complete.
The compiler is responsible for allocating storage and providing access to variables and data.
There are two methods for allocating resources:
Compiler Time Allocation or Static Storage Allocation
● The compiler makes a static storage allocation choice based solely on the program's text, rather than what the program does when it executes.
● Allocation is done during the compilation process.
Runtime Allocation or Dynamic Storage Allocation
● If a storage allocation choice can only be made while the program is running, it is said to be dynamic.
● At runtime, allocation takes place.
● There are two sorts of data variables that can be allocated to storage:
Local data
Non local data
● Non-local data can be managed with scope information, whereas local data can be handled with activation records.
● Static scope can be used to allocate block organized storage.
● Dynamic scope can be used for non-block structured allocation.
Block structured language
● The block structured language is a type of language in which delimiters such as "" and "" or begin and end are used to separate parts of source code.
● This part is run as a single unit, procedure, or function, and it may be controlled by conditional statements (if, while, do-while).
● Block structured languages are typically used to facilitate structured programming.
○ Example: C, C++, JAVA, PASCAL, FORTRAN, LISP and SNOBOL
● LISP, FORTRAN, and SNOBOL are non-block organized languages.
Implementation of Symbol Table:
Each symbol table entry can be represented as a record with several fields.
Block structured languages are organized using the following data structures:
Linear List
Self-Organizing List
Hashing
Tree Structure
Symbol table organization using Linear List:
● The simplest approach to build the symbol table is to use a linear list of records.
● An array is used to hold names and associated information in this procedure.
● In the order in which they arrive, the new names are added to the symbol database.
● At the end of all recorded records, the pointer "available" is kept.
● To get information on a specific name, we start at the beginning of the array and work our way up to the available pointer. We get an error "use of undeclared name" if we arrive to the pointer available without finding a name.
● We must confirm that a new name is not currently in use before introducing it. If it is already existent, another error, "Multiple Defined Name," occurs.
References:
- Thomas W. Parsons, Introduction to Compiler Construction. Computer Science Press,1992.
- Compiler construction (Theory and Practice), A.Barret William and R.M. Bates, Galgotia Publication.
- Compiler design in C, A.C. Holub, PHI.
- Http://estudies4you.blogspot.com/2017/09/organization-for-block-structured.html
- Https://www.wikitechy.com/tutorials/compiler-design/dynamic-storage-allocation
