Definition: A code representation that uses a maximum of three operands to represent an instruction.
Form: The statement a := t5 is encoded as (assign, a, t5).
Ternary Operations:
For x[i] := y, needs two entries in triple structure.
For x := y[i], it requires two operations.
Indirect Triples
Concept: Instead of listing triples directly, point to them using an array of pointers.
Example: Indirect triples can be represented by storing pointers to triples in designated order.
Semantic Analysis
Purpose: Checks the semantics of the parse tree derived from the syntactic representation.
Tasks Involved:
Checking semantics.
Error reporting.
Disambiguation of overloaded operators.
Type coercion and static checking.
Control flow and uniqueness checking.
Maintain symbol tables for variable/function definitions.
Aspects of Translation
Type Checking: Ensures variables are used in a manner consistent with their types, performed during compile-time and/or run-time.
Strongly Typed: Restricts automatic type conversions that lose information.
Weakly Typed: Allows more type conversions.
Uniqueness Checking: Verifies variable names are unique within their scope.
Name Checks: Ensures variable names do not conflict with reserved keywords.
Limitations of Parsers
Parsers focus on syntax and may miss deeper semantic errors:
Example: Using an undeclared variable results in a type error.
Identifiers may have different meanings in different scopes.
Abstract Syntax Tree (AST): A condensed form of the parse tree useful for representing constructs.
Abstract syntax does not necessarily preserve the syntactic structure of the source code.
Constructing Abstract Syntax Trees
Nodes Representation:
Operators: One field for the operator, with remaining fields as pointers to operands.
Identifier: Holds a label and points to the symbol table.
Numbers: Contains value and label.
Example Construction for expression w = a - 4 + c involves function calls (mkleaf, mknode) to create the tree structure:
P1 = mkleaf(id, entry.a)
P2 = mkleaf(num, 4)
P3 = mknode(-, P1, P2)
P4 = mkleaf(id, entry.c)
P5 = mknode(+, P3, P4)
Syntax Directed Definitions and Translation Schemes
Attribute Grammar: Attributes help define additional semantic checks. Can be classified under:
Syntax Directed Definitions (SDDs): Abstract high-level specifications without implementation details.
Syntax-Directed Translation Schemes (SDTs): Define the order of semantic evaluations more explicitly.
Actions and Evaluation Order: Actions are placed strategically to control semantic evaluations, critical for both synthesized and inherited attributes.
Type Checking in Languages
Basic Types: Atomic types such as boolean, char, integer, real.
Derived Types: Arrays, records, pointers, and function types.
Type Expressions: Recursively defined to denote types in expressions:
Derived from basic types or constructed by operators.
Specifications of a Type Checker
Grammar Specification: Rules defined in the grammar for variable declarations, expressions, and their types.
Recursive Checking: Ensures that types on both sides of assignment statements match and types for function applications are correctly inferred.
Example for Type Checking Functions:
E -> E1(E2) { E.type := if E2.type == s and E1.type == s^t then t else type_error }
Important Questions and Assignments
What is Three Address Code? Generate for certain expressions.
Write a note on Attributed Grammar and Annotated Parse Tree.
Explain Syntax Directed Translation for arithmetic expressions.
Define Synthesized and Inherited attributes with examples.
Construct triples, quadruples, and indirect triple notation for expressions like a * -(b + c).