Test: Syntax Directed Translation - Computer Science Engineering (CSE) MCQ

It is the Second Phase of the Compiler after Lexical Analyzer. It is also called Hierarchical Analysis or Parsing.

Given grammar, is
 is an ambiguous grammar.
Therefore two outputs are possible for single input i.e. 3 * 2 + 4.
Like: output 1 = 10
output 2 = 18
This problem is resolved by YACC Tool. So, according to rule of YACC Tool:
(1)  S-R conflict is resolved by ‘S’
(2) R_i – R_j conflict is resolved by R_i where i < j.
So, scanning input from left to right 

Concept:
The given grammar along with translation rules is,

The given string is=  20#10%5#8%2%2
Rule 1:
In the given SDT, % has more precedence than # and % because it is away from starting symbol.
Rule 2:
Both % and * are left-associative because the left non-terminal is present left most on the right side grammar.
The given string is=  20#10%5#8%2%2
The given string is=  20x10÷5 x 8÷2÷2
The given string is= 20 x2x4÷2
The given string is= 20 x2x2
The given string is= 40 x2
The given string is= 80
Hence the correct answer is 80.

Option 1: The actions will lead to an infinite loop.
This statement is not correct.

Option 2: The actions can be used to correctly type-check any syntactically correct program.
This statement is not correct. Because These SDT actions can not type-check boolean expressions or float expressions.
for example :
float a=3.46;
bool b = 0,c;
c = a+b; 

Option 3: The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.
This statement is not correct. Because the SDT actions can not be used to correctly type check boolean expressions.
for example : 
bool a = 0;
bool b = 1;
bool c = a+b;

Option 4: The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.
This statement is Correct. Because These SDT actions can be used to correctly type check both integer variables and integer expressions as well.

Concept:
Basic idea of syntax directed translation:
Syntax-Directed Constructing a parse tree or syntax tree and computing the values of attributes at the nodes of the tree by visiting them in some order is the definition of translation. In many circumstances, translation can be done without creating an explicit tree during parsing.

Evaluation Orders for syntax directed translation:

• Dependency Graphs.
• Ordering the Evaluation of Attributes.
• S-Attributed Definitions.
• L-Attributed Definitions.
• Semantic Rules

Note:

• Evaluation of the semantic rules may generate code, save information in a symbol table, issue error messages, or perform any other activities.
• Special cases of syntax-directed definitions can be implemented in a single pass by evaluating semantic rules during parsing, without explicitly constructing a parse tree or a graph showing dependencies between attributes.

Hence the correct answer is the Conceptual view of syntax-directed translation.

(A+B)*C - (D*E)-(F+G)
+AB*C - (D*E)-(F+G)
+AB*C - *DE - (F+G)
+AB*C - *DE - +FG
*+ABC - *DE - +FG
-*+ABC*DE - +FG
--*+ABC*DE+FG

Compiler is a translator which converts high level language (source program) into low level language (machine program).

Concepts:
Synthesized attributes:
A Synthesized attribute is an attribute of the non-terminal on the left-hand side of a production. Synthesized attributes represent information that is being passed up the parse tree. The attribute can take value only from its children.
S-attributed SDT
If an SDT uses only synthesized attributes, it is called as S-attributed SDT.

Inherited attributes:
An attribute of a nonterminal on the right-hand side of a production is called an inherited attribute. The attribute can take value either from its parent or from its siblings.

L-attributed SDT
If an SDT uses both synthesized attributes and inherited attributes with a restriction that inherited attribute can inherit values from left siblings only, it is called as L-attributed SDT.

In SDT:
D → T L {X₁.type = X₂.type}
L.type = T.type (Inherited attributed)
∴ X₁ = L and X₂ = T
T can be int or float
In SDT:
L → L₁, id {X₃.type = X₄.type}
L₁.type = L.type (Inherited attributed)
∴ X₃ = L₁ and X₄ = L
Hence option 1 is correct.

Input: a c b a c
(1) Construct the syntax tree for the given input.

Syntax Directed Translation is done by attaching augmented rules to the grammar that facilitate semantic analysis. It involves passing information top bottom and/or bottom up the parse tree in form of attributes attached to the nodes. Syntax directed translation rules use the following

1. lexical values of nodes
2. constants
3. attributes associated to the non-terminals in their definitions.