Implementation of Syntax directed Translators

Syntax-directed translation (SDT) is a technique used in compiler design to associate semantic actions with the parsing process. This allows for building the structure (syntax) of the program while simultaneously performing actions related to its meaning (semantics). Here's a breakdown of implementing SDT:

Core Idea:

We use an augmented context-free grammar where:
- Symbols can have attributes (additional information).
- Productions have semantic actions enclosed in braces {}.
These actions access:
- Lexical values of the symbols (obtained during lexing).
- Constants defined in the grammar.
- Other attributes associated with symbols in the production.

Implementation Approaches:

Attribute Evaluation:
- Parse tree is constructed while parsing the input.
- Attributes are attached to the nodes of the parse tree.
- Two main approaches for attribute evaluation exist:
  - S-attributed (static): Attribute values depend only on the structure of the parse tree (can be computed during parsing).
  - L-attributed (lookahead): Attribute values depend on both the structure and some future information (like upcoming tokens). Requires more complex evaluation strategies.
Parsing Techniques:
- SDT can be implemented with various parsing techniques like:
  - Recursive descent parsing
  - LL(k) parsers
  - LR parsers (better suited for L-attributed SDTs)
Data Structures:
- A common approach uses a stack with two arrays:
  - STATE: Holds pointers to parsing table entries for symbols.
  - VAL: Stores the values associated with the corresponding symbols in the STATE array.

Example:

Consider a grammar for expressions with an attribute val to store the evaluated value:

E -> T { val = T.val }
T -> T * F { val = T.val * F.val }
T -> F { val = F.val }
F -> (E) { val = E.val }
F -> num { val = atoi(num) }  // atoi converts string to integer

During parsing, semantic actions are evaluated as productions are reduced. The val attribute is populated as the parse tree is built.

Benefits of SDT:

Simple and easy to implement.
Clear separation of concerns between syntax and semantics.

Implementation of Syntax directed Translators

Related Posts