Semantic Analysis in Programming

Study Notes

Semantic Analysis

Determines the meaning of statements by applying semantic rules to their structure.
Adds type, length, and dimensionality information to the symbol table for declaration statements.
For imperative statements, derives the sequence of actions for implementation and represents this in intermediate code.
Example: In the expression a = b + i, if b is real and i is int, i is converted to real during evaluation.

Intermediate Representation (IR)

Contains intermediate code and a symbol table.
Symbol table examples include entries for symbols like I, a, b, i*, temp with respective types (int, real).
Intermediate code includes converting identifiers to types and performing arithmetic operations.

Operations on Search Structures

Insert Operation: Adds new symbol entries during processing.
Search Operation: Supports locating symbol entries.
Delete Operation: Removes redundant symbol entries identified during processing.

Sequential Search Organization

Every active entry has an equal probability of being accessed during searches.
Unsuccessful searches allow for entry addition using an 'add' operation.

Binary Search Organization

Requires entries to follow an ordering relation for efficient searches.
Probability of successful search is log2(f) and unsuccessful search is log2(f) where f is the number of occupied entries.
Entry number cannot change after an 'add' operation, which limits addition/deletion.

Hash Table Organization

Maps keys to values using a hash function, effectively storing associative arrays and symbol tables.
Consists of a hash table (fixed array of pointers) and storage table entries organized into linked lists (buckets).
The hash function computes an integer value to map each key to a corresponding slot.

Linked List and Tree Structure Organizations

Linear List: Simple implementation using one or multiple arrays. Requires scanning for new entries, leading to O(n) performance for insertion, but uses minimal space.
Self-Organizing List: Uses pointers for linking records, helping frequently accessed names to be at the top, improving access times.
Search Trees: Organizes symbol tables in binary tree structures with left and right pointers, enabling efficient searching based on record names.

Description

Explore the process of determining the meaning of statements by applying semantic rules to the structure. Learn how type, length, and dimensionality information is added to the symbol table for declaration statements, and how imperative statements are processed to create a sequence of actions in intermediate code.