Transcript Data Structure for Language Processing

Lecture by: Prof. Pooja Vaishnav



Language Processor implementations are
highly influenced by the kind of storage
structure used for program variables and
data.
Managing Language requires allocating and
managing the memory used by the program
in static or dynamic environments.
Implementation of suitable data structure
becomes critical in designing and executing
the system programs.


The Program behavior depends on the search
and allocation structures, the language
support and their features such as external
reference, recursion etc.
Vital operations: Search and Allocation

Choice of Data Structure:
 The design of runtime and storage management
system is greatly influenced by the nature of
source language.
 The structure and composition of source language
commands the requirements of the language
processor, takes up the job of code generation
and allocates memory for the program objects
that have their own logical address space

Choice of Data Structure:
 Nature of Data Structure
▪ Linear or non linear
▪ Linear data structure involves linear data elements
arrangements
▪ Search efficiency is considered by requirement of
contiguous memory allocations for the elements
▪ Sometimes designer may compelled to overestimate the
memory requirements of the linear data structure in order
to ensure that later on memory requirements would not
expand.
▪ This often leads to wastage of memory.
▪ Easy Access
▪ Implemented as Arrays or Linked Lists

Choice of Data Structure:
 Nonlinear data structure are the alternatives
 Uses pointer implementations to access elements
 Need not occupy contiguous memory locations
 More flexible in allocation and availability of space
 Lower search efficiency
 Interleaved memory locations

Choice of Data Structure:
 Purpose of Data Structure
▪ Whether Search data structure or Allocation Data
Structure
▪ Search Data Structure:
▪ Provides efficient search
▪ Maintain attribute information
▪ Include table and sequential organization, binary search
organization, hash tables, linked lists, tree structure

Choice of Data Structure:
 Purpose of Data Structure
▪ Whether Search data structure or Allocation Data
Structure
▪ Allocation Data Structure:
▪ Include stack and heap organizations
▪ Not required the search operation and address of
the memory
Language Processors uses both, search and allocation
data structure.

Choice of Data Structure:
 Lifetime of Data Structure
▪ Whether it is used during language process or the
target program execution
▪ For ex., a data structure used during a language
process would have the scope till that process only.




Also called as search structure
Designed and used for its search efficiency
during language processing
Set of entries, with each encompassing the
information concerning one entity
Maintains attribute information about
different entities defined and used in the
source program





Entry will be done only once but can be
searched many times
Primarily created to store table of
information
Mainly created and used during analysis
phase of program
Target program rarely use this data structure
Used for Symbol Table implementation

Characterized by ‘key’, special symbol field
containing name of entity to assist search
operation



Entry: set of fields referred to as record
Entry contains two parts:
Value in fixed part determines the
information to be stored in the variable part
 Fixed (tag): Symbol, class type, length, dimension
information, number of parameters, their
addresses, type of returned value, length of
returned value, statement number
 Variable : name, class, statement number




Fixed length entry enable use of
homogeneous linear data structures
eg. Arrays, they may contain records having
identical format
Suffers from inefficient use of memory usage
Variable length entry leads to compact
organization with no memory wastage
Fixed length Entry
Variable length
entry
More access
efficiency
Less access
efficiency
Less memory
efficiency
More memory
efficiency

Combining the functionality of two:
 Hybrid Entry Format:
Fixed Part
Pointer
Length
Variable Part

Kind of data structure, which is used in language
processing as both, search and allocation data structures
Fixed (Tag ) Part
Variant Part
Procedure
Variable
Address of Parameter List,
Count of Parameters
Type, Length, Dimension Information
Label
Statement Number
Function
Length of returned value, type of
returned value, number of parentheses
and their addresses



Insert
Search
Delete
Predict entry ‘e’ in the search data structure at
which symbol symb is stored
2. Let symbe be the symbol found at eth entry .
Compare symbe with symb.
a. If a match between the two is found, exit with
success.
b. Else go to the next step.
3. Repeat steps 1 and 2 till all entries are evaluated or
concluded that the symbol does not exist in the
search data structure
1.


Table Organization
Sequential Search Organization


Table Organization
Sequential Search Organization
 Occupied entries
 Free Entries
 Physical Deletion
 Logical Active/ Deleted Records
Binary Search Organization
 Search based on relational operators
 Entry number must not change after adding
record
 Hash Table Organization
 Hash function is used for the mapping of a key
value and the slot where that value belongs to the
hash table
 Hash function takes any key value from the
collection and computes on the integer value from
it in the range of slot names, between 0 and m-1.
