Syntax directed translation and semantic analysis notes — Unit 3

Parsing just checks if the code is grammatically correct. Semantic analysis and code generation require meaning. SDT provides meaning by attaching rules or actions to the productions of a Context-Free Grammar.

⇒1.1 Attributes and Rules

Each grammar symbol has a set of Attributes (like type, value, or memory location). When a production is applied during parsing, the Semantic Rules attached to that production are executed to compute the values of these attributes.

Example: Production `E -> E1 + T`. Semantic Rule: `E.val = E1.val + T.val`.

⇒2.1 Synthesized Attributes

An attribute of a node in a parse tree is synthesized if its value is computed from the attributes of its children.

Information flows up the tree (from leaves to root). Evaluated perfectly by Bottom-Up parsers during the 'Reduce' step.

⇒2.2 Inherited Attributes

An attribute of a node is inherited if its value is computed from the attributes of its parent and/or its siblings.

Information flows down and across the tree. Often used to pass type information down to variables in a declaration (e.g., `int a, b, c;`).

⇒3.1 S-Attributed Definitions

An SDT is S-Attributed if it uses ONLY Synthesized Attributes. Because all information flows bottom-up, these can be easily evaluated during a bottom-up parsing run (like in YACC).

⇒3.2 L-Attributed Definitions

An SDT is L-Attributed if inherited attributes only depend on parents and Left siblings (never Right siblings). This ensures attributes can be evaluated in a single depth-first, Left-to-right traversal of the parse tree. All S-Attributed definitions are also L-Attributed.

Before evaluating attributes, the compiler must know the order in which to compute them. A dependency graph visualizes this flow of information.

⇒4.1 Topological Sort

If Attribute B needs the value of Attribute A, there is a directed edge from A to B. The compiler performs a topological sort on this graph to determine a valid evaluation order.

If the dependency graph contains a cycle, the SDT is circular and cannot be evaluated.

One of the primary uses of SDT is Semantic Analysis, specifically Type Checking. The compiler must verify that operators are receiving the correct data types.

⇒5.1 Type Systems

• Static Checking: Types are checked at compile time (C, Java). Requires a compiler.
• Dynamic Checking: Types are checked at run time (Python, JS). Requires an interpreter or JIT.
• Strong Typing: Strict enforcement, no implicit conversion that loses data.

⇒5.2 Type Conversions

The compiler may implicitly convert types (Coercion), e.g., promoting an `int` to a `float` before an addition operation.

The Symbol Table stores all information about identifiers (variables, functions, classes).

⇒6.1 What is stored?

• Variable name and Scope.
• Data Type (int, float, array, struct).
• Size in memory.
• Memory Location (Offset relative to the base pointer).
• For functions: Number of arguments, their types, and return type.

The symbol table must support extremely fast Insert and Lookup operations, as the compiler queries it constantly.

⇒7.1 Data Structures

• Linear List: `O(N)` lookup. Too slow for real compilers.
• Binary Search Tree: `O(log N)` lookup. Better, but can become unbalanced.
• Hash Table: `O(1)` lookup. The industry standard. Uses separate chaining to handle hash collisions.

Most languages use block-structured lexical scoping. A variable `x` declared in an inner `{ }` block shadows a variable `x` in the outer block.

⇒8.1 Stack of Symbol Tables

Instead of one giant table, compilers use a Stack of Hash Tables.

• When entering a new block `{`, push a new, empty Hash Table onto the stack.
• Insert new declarations into the top Hash Table.
• When looking up a variable, search from the top of the stack downwards. The first match found is the correct one (handling shadowing automatically).
• When exiting the block `}`, pop the top Hash Table, instantly destroying those local variables from scope.