Data Structures For Language Processing (System Programming/Search Organization/Hash Table/Heap)

What are language processors?

data structure

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

     

Classification

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 : executions eg- Search = Binary search tree
allocation = stacks,heaps

3.Based on Lifetime —- whether used during Language Processing or during 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 .

  1. Fixed Size Record
  2. Variable Size Record
  3. Hybrid Record

Fixed Size 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

 

Binary Search Organization

 



Hash Tables

Interview Guide and how to face interview

Industrial Management: Functions, Principles, Objectives

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

Stacks



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

One Response

  1. rossfc99 February 1, 2017

Leave a Reply


Are You in Search
of A Job?

Subscribe to get job Alerts straight to your email inbox absolutely Free!

Thank you for subscribing.

Something went wrong.