GATE CS

Syntax-directed translation

Syntax-directed translation attaches attributes and semantic rules (or embedded actions) to grammar productions so that a parser can compute values, build syntax trees, check types and emit code while it recognises the input. GATE questions ask you to evaluate attributes on a given parse tree, classify a definition as S-attributed or L-attributed, and work out what a translation scheme prints in a bottom-up or top-down parse.

7 previous-year questions · 7 solved · 5 practice questions

Attributes, semantic rules and annotated parse trees

A syntax-directed definition (SDD) attaches attributes to grammar symbols and a semantic rule to each production. A rule computes an attribute of a symbol in the production from other attributes in the same production. Convention: the start symbol is the left side of the first production, and $E . val$ means the attribute val of the symbol $E$ . When a symbol occurs twice in one production, subscripts tell the occurrences apart, e.g. $E \to E_{1} + T$ .

Synthesized and inherited attributes

Property	Synthesized attribute	Inherited attribute
Defined by a rule of	the production whose head is the node	the production whose body contains the node (the production at the node's parent)
Value comes from	attributes of the node's children (and of the node itself)	attributes of the node's parent and siblings (and of the node itself)
Flows	up the parse tree	down or sideways in the parse tree
Typical use	expression value, syntax-tree pointer, type of an expression	type passed to a list of identifiers, left operand passed to the right
Terminals	may have synthesized attributes (such as `num.lexval`), supplied by the lexical analyser	none: by convention a terminal has no inherited attributes

FORM OF A SYNTHESIZED RULE

A . s = f (X_{1} . a_{1}, \dots, X_{n} . a_{n}) for the production A \to X_{1} X_{2} \dots X_{n}

The attribute being defined belongs to the head $A$ ; its arguments are attributes of the body symbols (or of $A$ itself).

FORM OF AN INHERITED RULE

X_{i} . a = g (A . b, X_{1} . c_{1}, \dots, X_{n} . c_{n}) for the production A \to X_{1} X_{2} \dots X_{n}

The attribute being defined belongs to a body symbol $X_{i}$ ; the arguments may be attributes of the head and of the body symbols.

An annotated parse tree is a parse tree in which every node shows the values of its attributes. A dependency graph has one vertex per attribute instance in the parse tree and an edge $u \to v$ whenever the rule that computes $v$ reads $u$ . A valid evaluation order is any topological order of this graph, so one exists if and only if the graph has no cycle. If the rules make an attribute instance depend on itself, directly or through other attributes, the attributes of that tree cannot be evaluated. For example, the production $A \to B$ with rules $A . s = B . i$ and $B . i = A . s + 1$ is circular on every tree that uses it.

An SDD in which no rule has side effects is called an attribute grammar: every rule only defines an attribute from other attributes. Rules that call functions such as print or addType have side effects. An SDD may contain them only if every evaluation order the dependency graph allows gives an acceptable result. In a translation scheme the position of each action fixes the moment it runs, so the side effects happen in a definite order.

S-attributed and L-attributed definitions

The two classes

Class	Condition	Evaluation order	Parsing fit
S-attributed	uses synthesized attributes only	bottom-up (post-order of the parse tree)	bottom-up (LR) parsing: evaluate at each reduction, keeping the values on the parser stack
L-attributed	each inherited attribute of $X_{i}$ in $A \to X_{1} \dots X_{n}$ depends only on inherited attributes of $A$ , on attributes of $X_{1}, \dots, X_{i - 1}$ , and on attributes of $X_{i}$ itself without forming a cycle (never on $X_{i + 1}, \dots, X_{n}$ , never on synthesized attributes of $A$ )	one depth-first, left-to-right traversal	top-down (LL) parsing directly; bottom-up parsing as well when the grammar is LL, using marker non-terminals

L-ATTRIBUTED CONDITION

X_{i} . inh = g (A . inh, X_{1} . any, \dots, X_{i - 1} . any), no dependence on X_{i + 1}, \dots, X_{n} or on A . syn

Also allowed: dependence on other attributes of $X_{i}$ itself, provided that creates no cycle. Not allowed: dependence on a synthesized attribute of the head $A$ . Synthesized attributes of $A$ may use any attribute in the production, including $A$ 's inherited attributes, provided no cycle results.

Every S-attributed definition is L-attributed, because with no inherited attributes the condition holds trivially. The converse is false. Both classes give an acyclic dependency graph on every parse tree: in an S-attributed definition every edge goes from a child up to its parent, and for an L-attributed definition acyclicity is part of the condition. A definition that makes an inherited attribute depend on a symbol to its right, or on a synthesized attribute of the head, is not L-attributed. It may still have a valid evaluation order if its dependency graph is acyclic, but a single depth-first, left-to-right traversal is no longer guaranteed to work.

WORKED EXAMPLE

For $A \to B C$ , decide for each rule set whether it is S-attributed, L-attributed (but not S), or neither. (i) $A . s = B . s + C . s$ . (ii) $C . i = B . s$ and $A . s = C . s$ . (iii) $B . i = C . s$ and $A . s = B . s$ .

Solution

(i) Only a synthesized attribute of $A$ is defined, from its children: S-attributed (hence also L-attributed).
(ii) $C . i$ is inherited and depends on $B . s$ , an attribute of the symbol to the left of $C$ : allowed. The definition has an inherited attribute, so it is not S-attributed. It is L-attributed.
(iii) $B . i$ is inherited and depends on $C . s$ , an attribute of the symbol to the right of $B$ : this violates the condition, so it is not L-attributed. The rules shown create no cycle, so the attributes can still be evaluated in some order, but not in a single left-to-right depth-first walk, which reaches $B$ before $C . s$ is known.

Answer: (i) S-attributed; (ii) L-attributed but not S-attributed; (iii) neither.

Evaluating attributes on a parse tree

Procedure to evaluate an SDD on a given tree

Draw the parse tree for the input using the grammar given (apply the productions in the order that gives the tree asked for).
List every attribute instance and, for each rule used at a node, note which instances it reads.
Start with attributes that need no inputs: token attributes from the lexical analyser (such as num.lexval) and any inherited attributes of the root that the SDD sets to given values.
Compute any attribute whose arguments are all known. For synthesized-only SDDs this is just post-order (leaves first).
With inherited attributes, move down the tree as soon as the parent's inputs are ready, then up again for synthesized ones; a left-to-right depth-first walk works if the SDD is L-attributed.
If at some point no attribute can be computed but some remain, the dependency graph has a cycle.

Take the grammar $E \to E_{1} + T ∣ T$ , $T \to T_{1} * F ∣ F$ , $F \to num$ with rules $E . val = E_{1} . val + T . val$ , $E . val = T . val$ , $T . val = T_{1} . val \times F . val$ , $T . val = F . val$ and $F . val = num.lexval$ . Since * sits lower in the grammar than +, it binds tighter, and the parse tree for 3 * 2 + 4 * 5 groups the two products first.

WORKED EXAMPLE

Using the SDD above, find $E . val$ at the root of the parse tree for 3 * 2 + 4 * 5.

Solution

The root uses $E \to E_{1} + T$ . Its left child $E_{1}$ derives 3 * 2 through $E_{1} \to T$ , $T \to T_{1} * F$ ; its right child $T$ derives 4 * 5 through $T \to T_{1} * F$ .
Leaves: the four $F . val$ values are 3, 2, 4, 5.
$T_{1} . val = 3$ (from $T_{1} \to F$ ), then the left product is $3 \times 2 = 6$ , so $E_{1} . val = 6$ .
On the right, $T_{1} . val = 4$ , so the right product is $4 \times 5 = 20$ .
Root: $E . val = 6 + 20 = 26$ .

Answer: 26

Inherited attributes in a declaration. Consider $D \to T L$ with $L . in = T . type$ ; $T \to int$ with $T . type = integer$ ; $L \to L_{1}, id$ with $L_{1} . in = L . in$ and $addType (id.entry, L . in)$ ; $L \to id$ with $addType (id.entry, L . in)$ . For int a, b, c, $T . type$ is computed first (synthesized), is copied to $L . in$ at the child of $D$ , and is then passed down the left-recursive chain of $L$ nodes to every id. Each inherited attribute depends on the parent's inherited attribute or on the left sibling $T$ , so the SDD is L-attributed but not S-attributed.

Translation schemes and semantic actions

A syntax-directed translation scheme (SDT) embeds program fragments called semantic actions, written in braces, in the right side of a production. An action runs at the point where it appears, once the parser has processed everything to its left in that production. This lets you control the order of side effects such as printing.

The order of actions is fixed by the parse tree. Treat each action as an extra leaf, placed among the children of its production at the position where it is written. Whatever the parsing method, the actions run in the order in which these leaves appear in a depth-first, left-to-right walk of the tree. A top-down parser and a bottom-up parser that implement the scheme correctly therefore produce the same output for the same parse tree.

Placement rules for actions (L-attributed scheme, one left-to-right pass)

Action computes	Where to place it
an inherited attribute of body symbol $X_{i}$	immediately before $X_{i}$ (and after the symbols whose attributes it reads)
a synthesized attribute of the head $A$	at the right end of the production
any attribute	after every symbol whose attributes it reads: an action never reads an attribute of a symbol to its right

Postfix SDT. If the grammar is LR and the SDD is S-attributed, put every action at the right end of its production. A bottom-up parser then runs each action exactly when it reduces by that production, so the order of side effects follows the order of reductions (the rightmost derivation in reverse). For an expression grammar, printing each operand at its reduction and each operator in the action at the end of its production produces postfix notation.

Postfix SDT on the parser stack. Each stack entry holds a grammar symbol (or state) and that symbol's synthesized attribute. When the parser reduces by $E \to E_{1} + T$ , the values of $E_{1}$ and $T$ are at $stack [top - 2] . val$ and $stack [top] . val$ . The action computes their sum, sets $top = top - 2$ , and stores the sum as the new $E . val$ at $stack [top]$ .

Embedded actions in an LR parse. To run an action in the middle of a production during bottom-up parsing, replace it by a new non-terminal $M$ with $M \to ε$ whose action is the original one. For example, $S \to a {} S b$ becomes $S \to a M S b$ and $M \to ε {}$ . The action then runs when $M$ is reduced: after a is shifted and before the next token is shifted (the parser has already seen that token as lookahead). Adding markers can create parsing conflicts, so the grammar with markers must itself be checked.

Top-down parse. For a predictive (LL) parser, actions run in the order of a depth-first, left-to-right walk of the parse tree: an action is executed when the walk reaches its position among the children of its node. Reading the actions left to right while expanding the leftmost non-terminal gives the output.

WORKED EXAMPLE

The scheme has productions $E \to E_{1} + T {print (’+’)}$ , $E \to T$ , $T \to T_{1} * F {print (’*’)}$ , $T \to F$ , $F \to num {print (num.lexval)}$ . What does a bottom-up parser print for 5 * 2 + 3?

Solution

All actions are at the right ends, so each runs at its reduction.
Reductions in order: $F \to 5$ prints 5; $T \to F$ ; $F \to 2$ prints 2; $T \to T * F$ prints *; $E \to T$ ; $F \to 3$ prints 3; $T \to F$ ; $E \to E + T$ prints +.
Collect the printed symbols in order.

Answer: 5 2 * 3 +

Syntax trees and type checking with an SDD

A syntax tree (abstract syntax tree) keeps the operators as interior nodes and the operands as children, and drops the grammar's chain productions and parentheses. An SDD builds it with a synthesized attribute node holding a pointer to the root of each sub-tree. Two helper functions are standard: Node(op, left, right) creates an interior node and Leaf(id, entry) or Leaf(num, val) creates a leaf; each returns a pointer.

SDD that builds a syntax tree

Production	Semantic rule
$E \to E_{1} + T$	$E . node = Node (’+’, E_{1} . node, T . node)$
$E \to E_{1} - T$	$E . node = Node (’-’, E_{1} . node, T . node)$
$E \to T$	$E . node = T . node$
$T \to (E)$	$T . node = E . node$
$T \to id$	$T . node = Leaf (id, id.entry)$
$T \to num$	$T . node = Leaf (num, num.val)$

WORKED EXAMPLE

Using the table above, how many nodes does the syntax tree for a - 4 + c have, and what is its root and its left child?

Solution

+ and - are left-associative (the rule $E \to E_{1} o p T$ is left-recursive), so the input groups as $(a - 4) + c$ .
Reductions create nodes in this order: Leaf(a), Leaf(4), Node(-), Leaf(c), Node(+).
Interior nodes: 2 (- and +). Leaves: 3 (a, 4, c). Total 5. The unit productions $E \to T$ add no nodes, and parentheses would not add any either (the rule for $T \to (E)$ only copies the pointer).
The root is the + node; its left child is the - node (with leaves a and 4) and its right child is the leaf c.

Answer: 5 nodes; root +, left child the - node, right child the leaf c.

DAG for an expression. If Node and Leaf first look for an existing node with the same operator (or token) and the same children, and return it instead of creating a new one, the same SDD builds a directed acyclic graph (DAG). A repeated sub-expression is then represented once, and its node has more than one parent.

WORKED EXAMPLE

With the table extended by a level for * (binding tighter than + and -, left-associative, rule $Node (’*’, \dots)$ ), how many nodes are in the syntax tree and in the DAG for a + a * (b - c) + (b - c) * d?

Solution

Grouping: $(a + (a * (b - c))) + ((b - c) * d)$ .
Syntax tree: interior nodes $b - c$ , $a * (b - c)$ , the first +, the second $b - c$ , $(b - c) * d$ and the root +, which is 6. Leaves a, a, b, c, b, c, d, which is 7. Total 13.
DAG: leaves a, b, c, d once each, which is 4. Interior: $b - c$ once (shared by both products), $a * (b - c)$ , the first +, $(b - c) * d$ and the root +, which is 5. Total 9.

Answer: Syntax tree 13 nodes; DAG 9 nodes.

Type checking. A type expression names a type (int, float, boolean, type_error) or is built with constructors such as arrays and function arrows. An SDD gives each expression a synthesized attribute type and checks operand types in the rule, producing type_error for a mismatch. A typical rule set for arithmetic, assuming implicit widening of int to float:

Type rules for $E \to E_1 + E_2$ (with implicit int-to-float widening)

$E_{1} . type$	$E_{2} . type$	$E . type$
int	int	int
int	float	float
float	int	float
float	float	float
any other combination		type_error

For declarations, the SDD of the previous section passes the declared type down through an inherited attribute and stores it in the symbol table; later uses of an identifier read their type from that table and combine it with the rules above. A rule for an array declaration, for example, builds the type expression array(n, T) from the element type $T$ and the size $n$ .

Traps and quick checks

EXAM TIP

Check the L-attributed condition production by production: an inherited attribute of a symbol may read only the head's inherited attributes, symbols to its left, and its own symbol's other attributes (without a cycle). One rule that reads a right sibling is enough to fail it.

EXAM TIP

An inherited attribute that reads a synthesized attribute of the head is not allowed in an L-attributed definition, even when no cycle results. Only the head's inherited attributes may be read.

EXAM TIP

An S-attributed definition is always L-attributed; an L-attributed definition with an inherited attribute is never S-attributed. Do not treat the two classes as disjoint.

EXAM TIP

For a printing scheme, list the productions in the order the tree is built. Bottom-up with every action at the right end gives the order of reductions; do not print in the order tokens are read. A mid-production action fires as soon as the symbols to its left have been processed.

EXAM TIP

Parse the string with the grammar given, not with the usual precedence you assume. Left recursion groups to the left, right recursion to the right, and the grammar's levels (not the operator symbols) decide which operator ends up deeper in the tree.

EXAM TIP

A dependency graph with a cycle means the SDD has no valid evaluation order for that tree. Before computing anything, look for attributes that are defined from each other, directly or through a chain of other attributes.

EXAM TIP

By convention, terminals have only synthesized attributes supplied by the lexical analyser; an inherited attribute is never attached to a token.

PREVIOUS-YEAR QUESTIONS

7 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2025 Set 2 · GATE CSE 2024 Set 1 · GATE CSE 2024 Set 2 · GATE CSE 2023 · GATE CSE 2022 · GATE CSE 2020

GATE 2026 CS1 Q.53

GATE 2026 · CS1Q.53 · 2 marks · MSQ

Consider the following two syntax-directed definitions SDD1 and SDD2 for type declarations.

SDD1, grammar G1 and semantic rules:
- $D \to T V$ : $D . type = T . type$ ; $V . type = T . type$
- $T \to int$ : $T . type = int$
- $T \to float$ : $T . type = float$
- $V \to V_{1} id$ : $V_{1} . type = V . type$ ; $put (id.entry, V . type)$
- $V \to id$ : $put (id.entry, V . type)$

SDD2, grammar G2 and semantic rules:
- $D \to D_{1} id$ : $D . type = D_{1} . type$ ; $put (id.entry, D_{1} . type)$
- $D \to T id$ : $D . type = T . type$ ; $put (id.entry, T . type)$
- $T \to int$ : $T . type = int$
- $T \to float$ : $T . type = float$

$D$ is the start symbol, and int, float and id are the three terminals. The non-terminal $V_{1}$ is the same as $V$ and the non-terminal $D_{1}$ is the same as $D$ . Here, the subscript is used to differentiate the grammar symbols on the two sides of a production. The function put updates the symbol table with the type information for an identifier.

Let P and Q be the languages specified by grammars G1 and G2, respectively.

Which of the following statements is/are true?

GATE 2026 CS1 question 53: Two side-by-side tables titled SDD1 and SDD2, each with columns Grammar (G1 or G2) and Semantic Rules, listing the… — Figure from the GATE 2026 CS1 paper. It is part of the question.

(A)
The languages P and Q are the same
(B)
SDD2 is S-attributed and contains only synthesized attributes
(C)
SDD1 is L-attributed and contains only inherited attributes
(D)
The specifications of SDD1 and SDD2 are such that the same entries get added to the symbol table

Answer and solution

GATE 2026 CS1 Q.53: answer and solution

GATE 2025 CS2 Q.22

GATE 2025 · CS2Q.22 · 1 mark · MCQ

Given the following syntax directed translation rules:

Rule 1: $R \to A B$ { $B . i = R . i - 1$ ; $A . i = B . i$ ; $R . i = A . i + 1$ ; }
Rule 2: $P \to C D$ { $P . i = C . i + D . i$ ; $D . i = C . i + 2$ ; }
Rule 3: $Q \to E F$ { $Q . i = E . i + F . i$ ; }

Which ONE is the CORRECT option among the following?

(A)
Rule 1 is S-attributed and L-attributed; Rule 2 is S-attributed and not L-attributed; Rule 3 is neither S-attributed nor L-attributed
(B)
Rule 1 is neither S-attributed nor L-attributed; Rule 2 is S-attributed and L-attributed; Rule 3 is S-attributed and L-attributed
(C)
Rule 1 is neither S-attributed nor L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed
(D)
Rule 1 is S-attributed and not L-attributed; Rule 2 is not S-attributed and is L-attributed; Rule 3 is S-attributed and L-attributed

Answer and solution

GATE 2025 CS2 Q.22: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS2 Q.22: answer and solution

GATE 2024 CS1 Q.37

GATE 2024 · CS1Q.37 · 2 marks · MCQ

Consider the following syntax-directed definition (SDD).

S \to D H T U D \to "M" D_{1} D \to ε H \to "L" H_{1} H \to ε T \to "C" T_{1} T \to ε U \to "K" {S . val = D . val + H . val + T . val + U . val;} {D . val = 5 + D_{1} . val;} {D . val = - 5;} {H . val = 5 * 10 + H_{1} . val;} {H . val = - 10;} {T . val = 5 * 100 + T_{1} . val;} {T . val = - 5;} {U . val = 5;}

Given "MMLK" as the input, which one of the following options is the CORRECT value computed by the SDD (in the attribute $S . val$ )?

GATE 2024 CS1 question 37: A table of eight productions with semantic actions: S -> D H T U S.val = D.val + H.val + T.val + U.val;; — Figure from the GATE 2024 CS1 paper. It is part of the question.

(A)
45
(B)
50
(C)
55
(D)
65

Answer and solution

GATE 2024 CS1 Q.37: answer and solution

GATE 2024 CS2 Q.29

GATE 2024 · CS2Q.29 · 1 mark · MSQ

Which of the following statements is/are FALSE?

(A)
An attribute grammar is a syntax-directed definition (SDD) in which the functions in the semantic rules have no side effects
(B)
The attributes in a L-attributed definition cannot always be evaluated in a depth-first order
(C)
Synthesized attributes can be evaluated by a bottom-up parser as the input is parsed
(D)
All L-attributed definitions based on LR(1) grammar can be evaluated using a bottom-up parsing strategy

Answer and solution

GATE 2024 CS2 Q.29: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS2 Q.29: answer and solution

GATE 2023 CS Q.60

GATE 2023 · CSQ.60 · 2 marks · NAT

Consider the syntax directed translation given by the following grammar and semantic rules. Here N, I, F and B are non-terminals. N is the starting non-terminal, and #, 0 and 1 are lexical tokens corresponding to input letters "#", "0" and "1", respectively. X.val denotes the synthesized attribute (a numeric value) associated with a non-terminal X. I1 and F1 denote occurrences of I and F on the right hand side of a production, respectively. For the tokens 0 and 1, 0.val = 0 and 1.val = 1.

N → I # F N.val = I.val + F.val
I → I1 B I.val = (2 I1.val) + B.val
I → B I.val = B.val
F → B F1 F.val = (1/2)(B.val + F1.val)
F → B F.val = (1/2) B.val
B → 0 B.val = 0.val
B → 1 B.val = 1.val

The value computed by the translation scheme for the input string 10#011 is ______. (Rounded off to three decimal places)

Answer and solution

GATE 2023 CS Q.60: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 CS Q.60: answer and solution

GATE 2022 CS Q.65

GATE 2022 · CSQ.65 · 2 marks · NAT

Consider the following grammar along with translation rules.

$S \to S_{1} # T {S . val = S_{1} . val * T . val}$
$S \to T {S . val = T . val}$
$T \to T_{1} % R {T . val = T_{1} . val \div R . val}$
$T \to R {T . val = R . val}$
$R \to i d {R . val = i d . val}$

Here # and % are operators and $i d$ is a token that represents an integer and $i d . val$ represents the corresponding integer value. The set of non-terminals is ${S, T, R, P}$ and a subscripted non-terminal indicates an instance of the non-terminal.

Using this translation scheme, the computed value of $S . val$ for root of the parse tree for the expression 20#10%5#8%2%2 is ______.

Answer and solution

GATE 2022 CS Q.65: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 CS Q.65: answer and solution

GATE 2020 CS Q.33

GATE 2020 · CSQ.33 · 2 marks · MCQ

Consider the productions A → PQ and A → XY. Each of the five non-terminals A, P, Q, X, and Y has two attributes: s is a synthesized attribute, and i is an inherited attribute. Consider the following rules.

Rule 1: P.i = A.i + 2, Q.i = P.i + A.i, and A.s = P.s + Q.s

Rule 2: X.i = A.i + Y.s and Y.i = X.s + A.i

Which one of the following is TRUE?

(A)
Both Rule 1 and Rule 2 are L-attributed.
(B)
Only Rule 1 is L-attributed.
(C)
Only Rule 2 is L-attributed.
(D)
Neither Rule 1 nor Rule 2 is L-attributed.

Answer and solution

GATE 2020 CS Q.33: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.33: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 11 mark · MCQ

For the production $A \to B C$ , which one of the following sets of semantic rules makes the SDD L-attributed but not S-attributed? Here $s$ denotes a synthesized and $i$ an inherited attribute.

(A)
$B . i = A . i$ , $C . i = B . s$ and $A . s = C . s$
(B)
$A . s = B . s + C . s$
(C)
$B . i = C . s$ and $A . s = B . s$
(D)
$C . i = A . s$ and $A . s = B . s$

Answer and solution

Answer: (A)

(B) defines only a synthesized attribute: S-attributed, so it is excluded.
(C) makes the inherited $B . i$ depend on $C . s$ , an attribute of the symbol to the right of $B$ : not L-attributed.
(D) makes the inherited $C . i$ depend on $A . s$ , a synthesized attribute of the head. The condition allows only the head's inherited attributes, so (D) is not L-attributed, even though these rules form no cycle.
(A): $B . i$ reads the head's inherited $A . i$ , $C . i$ reads $B . s$ from its left sibling, and $A . s$ is synthesized. It is L-attributed and has inherited attributes, so it is not S-attributed.

PRACTICE 22 marks · NAT

Consider the SDD with productions $L \to L_{1} B ∣ B$ and $B \to 0 ∣ 1$ . The rules are $L . val = 3 \times L_{1} . val + B . val$ for $L \to L_{1} B$ , $L . val = B . val$ for $L \to B$ , and $B . val$ equal to the digit it derives. What is $L . val$ at the root of the parse tree for the string 110101?

Answer and solution

Answer: $334$

The grammar is left-recursive, so the leftmost digit is at the bottom: $L \to B$ gives 1 for the first digit.
Digit 1: $3 \times 1 + 1 = 4$ .
Digit 0: $3 \times 4 + 0 = 12$ .
Digit 1: $3 \times 12 + 1 = 37$ .
Digit 0: $3 \times 37 + 0 = 111$ .
Digit 1: $3 \times 111 + 1 = 334$ (the string read as a base-3 number).

PRACTICE 32 marks · MCQ

A top-down parser uses the scheme $E \to T R$ , $R \to + T {print (’+’)} R ∣ ε$ , $T \to num {print (num.lexval)}$ . What is printed for the input 7 + 2 + 5?

(A)
7 2 + 5 +
(B)
7 2 5 + +
(C)
+ + 7 2 5
(D)
7 + 2 + 5

Answer and solution

Answer: (A)

$E \to T R$ : the first $T$ derives 7 and prints 7.
In $R \to + T {print (^{'} +^{'})} R$ : $T$ derives 2 and prints 2, then the action prints +.
The nested $R$ repeats this: $T$ prints 5, then + is printed.
The last $R \to ε$ prints nothing. Output: 7 2 + 5 +.

PRACTICE 42 marks · MSQ

Which of the following statements are TRUE?

(A)
Every S-attributed definition is also L-attributed.
(B)
An L-attributed definition can be evaluated in a single depth-first, left-to-right traversal of the parse tree.
(C)
An SDD that uses only synthesized attributes can be evaluated by a post-order traversal of the parse tree.
(D)
If the production $A \to B$ has the rules $A . s = B . i$ and $B . i = A . s + 1$ , the attributes can still be evaluated in some order.

Answer and solution

Answer: (A), (B), (C)

A: with no inherited attributes the L-attributed condition holds trivially, so A is true.
B: this is the defining property of L-attributed definitions, so B is true.
C: each synthesized attribute needs only its children's attributes (and the node's own), which post-order has already computed, so C is true.
D: $A . s$ needs $B . i$ and $B . i$ needs $A . s$ , so the dependency graph of any tree using this production has a cycle and there is no topological order; D is false.

PRACTICE 51 mark · NAT

A bottom-up parser uses an LR grammar and the following scheme, in which the action in the middle of the first production is implemented with a marker non-terminal: $S \to a {print (1)} S b {print (2)} ∣ c {print (3)}$ . The input is a a a c b b b. Write the printed digits, in the order printed, as a single integer (for example, printing 3, then 1, then 2 would give 312). What is that integer?

Answer and solution

Answer: $1113222$

With the marker the grammar is $S \to a M S b ∣ c$ , $M \to ε {print (1)}$ . After a is shifted, the only complete item in the state is $M \to \cdot$ and there is no terminal shift, so there is no conflict: the parser reduces by $M$ on the lookahead a or c.
Each a is shifted and its marker is reduced before the next token is shifted, so three 1's are printed first.
c is shifted and reduced by $S \to c$ , which prints 3.
Then each b is shifted and $S \to a M S b$ is reduced, printing 2, three times.
Printed in order: 1 1 1 3 2 2 2, so the integer is 1113222.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

syntax-directed translation

Preparing in Kolkata? IAE Academy's course for GATE CSE.