Unit - 4

Run time environments

Q1) What is the symbol table?

A1) Symbol table

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

Q2) Write the operation of the symbol table?

A2) The basic operations listed on the table of symbols include:

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

Q3) Explain dynamic storage allocation technique?

A3) 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.

Q4) What is non block structured language?

A4) 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.

Q5) Define block structured language?

A5) 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.

Q6) language facilities for dynamic storage allocation?

A6) 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.

Q7) What is the run time environment?

A7) Run time environments

A program's source code is nothing more than a collection of text (code, statements, and so on), and it must be brought to life by actions done on the target machine. To execute instructions, a program requires memory resources. A program has names for procedures, identifiers, and other items that must be mapped to actual memory locations during runtime.

A program in execution is referred to as runtime. The runtime environment is a state of the target machine that includes software libraries, environment variables, and other components that provide services to the system's processes.

The runtime support system is a package that supports communication between the process and the runtime environment. It is usually built alongside the executable program itself. While the program is running, it manages memory allocation and deallocation.

Q8) What is the structure of the symbol table?

A8) Structure of the symbol table

When judging various data structures, the following should be taken into consideration:

●      Memory space,

●      Time taken to add and search for a name,

●      How difficult it is to introduce scoping.

Linear lists

Searching is performed in linear fashion from beginning to end. The search halts as soon as the name you are looking for is found.

Linear lists are easy to implement and require little memory space. Scoping is easily introduced using the LIFO principle. However, search times are unacceptable. Reports have shown that a compiler, which implements symbol tables using linear lists, can spend 25% of compilation time on searching.

Trees

The symbol table can be in the form of a tree; then each subprogram has a symbol table attached to its node in the abstract syntax tree. The main program has a similar table for globally declared objects. The advantage of this structure is that it is easy to represent scoping and is quicker than linear lists.

Hashing

When high demands are made on the search time, hashing is used. Entry to the hash table is calculated using a suitable key transformation. If the symbol is not in the entry, you have to follow the link field. By making the hash table large enough you can control the search time.

Q9) What are scopes?

A9) Scopes

Every name in the source program has a valid region called the scope of that name.

The following are the rules for a block-structured language:

●      If a name is declared within block B, it is only valid within that block.

●      Unless the name's identifier is re-declared in B1, the name that is valid for block B2 is likewise valid for B1.

●      These scope rules necessitate a more complex symbol table arrangement than a set of name-attribute connections.

●      Each table has a list of names and their associated properties, and each table is grouped into a stack.

●      A new table is added to the stack every time a new block is entered. The name that is designated as local to this block is stored in the new table.

●      The table is searched for a name once the declaration is constructed.

●      If the name is not found in the table, it is replaced with a new name.

●      After the name's reference has been translated, each table in the stack is searched one by one.

For Example

Int x; 

Void f(int m) { 

Float x, y; 

{ 

Int i, j; 

Int u, v; 

} 

} 

Int g (int n) 

{ 

Bool t; 

} 

Fig 4: Symbol table organization that complies with static scope information rules

Q10) Write the limitations of static allocations?

A10) ​​Limitation of Static Allocation

●      The size of a data object and constraints on its position in memory must be known at compile time.

●      Recursive procedures are restricted, because all activations of a procedure use the same bindings for local names.

●      Dynamic allocation is not allowed. So data structures cannot be created dynamically.