Data structures for Language processing
What are language processors?
Basically language processors are the programs that process the program that is written in programming language i.e normal programs which we generally write such as assemble level, c programming etc.
The next stage is of language translator whose basic function is to translate the program from source language to machine language or some other basic language. The machine code can be for an actual computer or for a virtual (hypothetical) computer. If it is for a virtual computer, then a simulator for the virtual computer is needed in order to execute the translated program.
Source program components are first translated into machine language to produce components called object modules or object files.
Program components in languages such as C are normally compiled into object files, which are combined into an executable file by a linkage editor or linking loader. The linkage editor adjusts addresses as needed when it combines the object modules, and it also puts in the addresses where a module references a location in another module (such as for a function call).
Basically language processors are the programs that process the program that is written in programming language i.e normal programs which we generally write such as assemble level, c programming etc.
The next stage is of language translator whose basic function is to translate the program from source language to machine language or some other basic language. The machine code can be for an actual computer or for a virtual (hypothetical) computer. If it is for a virtual computer, then a simulator for the virtual computer is needed in order to execute the translated program.
Source program components are first translated into machine language to produce components called object modules or object files.
Program components in languages such as C are normally compiled into object files, which are combined into an executable file by a linkage editor or linking loader. The linkage editor adjusts addresses as needed when it combines the object modules, and it also puts in the addresses where a module references a location in another module (such as for a function call).
Agenda
- Classification
- Search Data Structure
- Fixed Size Record
- Variable Size Record
- Hybrid Record
- Other Organization
- Tree Representation
- Hashed Representation
- Allocation Data Structure
- Stack & Extended Stack
- Heap
1. Based on nature ---- Linear and Non-linear
eg :- Linear = array , stack etc.
Non-Linear = Tree , Graph etc.
2. Based on Purpose --- Search and allocation
eg :- Search = Binary search tree
allocation = stacks,heaps
3.Based on Lifetime ---- whether used during Language Processing or during target program executions
eg :- Lang. Processing = Object based data model
Target program = Hash tables
Search Data Structures
A Search data structure (or search structure ) is a set of entries accommodating the information concerning one entity. Each entity is assumed to contain a key field which forms the basis for search .
- Fixed Size Record
- Variable Size Record
- Hybrid Record
Each entry has same type and size
Eg Array
Variable Size Record
Type and size of each record could be different
Hybrid Record
Entry has both fixed length part and variable length part
Entry Format
Generic Search Procedure for locating the entry of symbol
Hash Tables
Interview Guide and how to face interview
Hashing Function
- Hashing function is used to make search system faster.
- It transforms the source symbol or group of symbols to numerical numbers to make faster comparisons and searching
- Hashing do not change the original meaning of symbols it just transforms them to other form.
- Size is pre decided for transforming message to particular format
- If message is of less size than that size , it performs “folding” operation
- In folding message is padded with 0’s to complete the size of it.
Properties of good hashing function
Collision in hashing
Many function result into same number generation which leads to collision of numbers and searching will crash
Thus to avoid collision we have various collision handling techniques
1. Rehasing technique
2. Overflow chaining technique
Allocation Data Structure
Important Allocation Data Structures
- Stack & Extended Stack
- Heap
Extended Stack model
- An extended stack is needed for handling a variable length record . A record consists of a set of consecutive stack entries
- In addition to base and top a new pointer Previous is used.
Heaps
Use of Heap in Memory management
- Due to repetition of allocation and deallocation of memory area holes are created in memory area.
- Memory management takes care of this holes and reallocate this area by managing it properly
- It increases performance and speed of allocation and deallocation of memory spaces
More related posts:
1) Deadlock
2)Two pass assemblers
0 comments:
Post a Comment