Study Notes : Syntax Directed Translation

Attribute Grammar Framework

• Generalization of CFG where each grammar symbol has an associated set of attributes
• Values of attributes are computed by semantic rules
• Two notations for associating semantic rules with productions

Syntax directed definition

• high level specifications
• hides implementation details
• explicit order of evaluation is not specified

Translation schemes

• indicate order in which semantic rules are to be evaluated
• allow some implementation details to be shown

Evaluation of the semantic rules are as follows

1. May generate intermediate codes
2. May put information into the symbol table
3. May perform type checking
4. May issue error messages
5. May perform some other activities

• An attribute may hold a string, a number, a memory location, a complex record etc.
• Evaluation of a semantic rule defines the value of an attribute, but a semantic rule may also have some side effects such as printing a value.

Attributes

• Attributes fall into two classes: synthesized and inherited
• The value of a synthesized attribute is computed from the values of its children nodes
• The value of an inherited attribute is computed from the sibling and parent nodes.

S-Attributed grammar: A syntax directed definition that uses only synthesized attributes is said to be an S- attributed definition. A parse tree for an S-attributed definition can be annotated by evaluating semantic rules for attributes.

Translations are appended only at the end.

It uses bottom up parsing for evaluation.

L-attributed grammar: When translation takes place during parsing, order of evaluation is linked to the order in which nodes are created. L-attributed definition: where attributes can be evaluated in depth-first order.

This definition can use synthesized attributes and also restricted inherited attributes(the value can be taken from parent and left siblings only).

Translations can append anywhere in the rhs of the production.

It uses a natural order in both top-down and bottom-up parsing is depth first-order.

Evaluation order of SDT’s

• Using definitions: L-attributed definition and S-attributed definition
• Using parsing: Top-down evaluation and Bottom up evaluation

Dependency Graph : Directed graph indicating interdependencies among the synthesized and inherited attributes of various nodes in a parse tree.

Syntax directed translation table: Symbols E, T and F are associated with an attribute value.

You can follow the detailed champion study plan for GATE CS 2022 from the following link:

Detailed GATE CSE 2022 Champion Study Plan

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU’S Exam Prep Test Series check the following link:

Click Here to Avail GATE CSE Test Series!(100+ Mock Tests)

Get unlimited access to 21+ structured Live Courses all 112+ mock tests with Online Classroom Program for GATE CS & PSU Exams:

Click here to avail Online Classroom Program for Computer Science Engineering

Thanks

#DreamStriveSucceed