Chapter 2

Syntax Directed Translation

LEARNING OBJECTIVES

 Syntax directed translation  S-attributed definition

 Syntax directed definition  L-attributed definitions
 Dependency graph  Synthesized attributes on the parser
 Constructing syntax trees for expressions  Syntax directed translation schemes
 Types of SDD’s  Bottom up evaluation of inherited attributes

SyntAx directed trAnSlAtion Notes:

1. Grammar symbols are associated with attributes.
To translate a programming language construct, a compiler may
2. Values of the attributes are evaluated by the semantic rules
need to know the type of construct, the location of the first instruc-
associated with production rules.
tion, and the number of instructions generated . . . etc. So, we have
to use the term ‘attributes’ associated with constructs.
An attribute may represent type, number of arguments, memory Notations for Associating Semantic Rules
location, compatibility of variables used in a statement which can-
There are two techniques to associate semantic rules:
not be represented by CFG alone.
So, we need to have one more phase to do this, i.e., ‘semantic
analysis’ phase. Syntax directed definition (SDD) It is high level specification for
translation. They hide the implementation details, i.e., the order in
which translation takes place.
Syntax
Semantic analysis
Semantically checked
Attributes + CFG + Semantic rules = Syntax directed definition
tree syntax tree (SDD).

In this phase, for each production CFG, we will give some seman- Translation schemes These schemes indicate the order in which
tic rule. semantic rules are to be evaluated. This is an input and output
mapping.
Syntax directed translation scheme
A CFG in which a program fragment called output action (seman-
tic action or semantic rule) is associated with each production is SyntAx directed definitionS
known as Syntax Directed Translation Scheme. A SDD is a generalization of a CFG in which each grammar sym-
These semantic rules are used to bol is associated with a set of attributes.
There are two types of set of attributes for a grammar symbol.
1. Generate intermediate code.
2. Put information into symbol table. 1. Synthesized attributes
3. Perform type checking. 2. Inherited attributes
4. Issues error messages. Each production rule is associated with a set of semantic rules.
6.28 | Unit 6  •  Compiler Design

Semantic rules setup dependencies between attributes Example: An inherited attribute distributes type informa-
which can be represented by a dependency graph. tion to the various identifiers in a declaration.
The dependency graph determines the evaluation order For the grammar
of these semantic rules. D → TL
Evaluation of a semantic rule defines the value of an
  T → int
attribute. But a semantic rule may also have some side
  T → real
effects such as printing a value.
  L → L1, id
Attribute grammar: An attribute grammar is a syntax   L → id
directed definition in which the functions in semantic rules
‘cannot have side effects’. That is, The keyword int or real followed by a list of
identifiers.
Annotated parse tree:  A parse tree showing the values of
In this T has synthesized attribute type: T.type. L has an
attributes at each node is called an annotated parse tree.
inherited attribute in L.in
The process of computing the attribute values at the
Rules associated with L call for procedure add type to the
nodes is called annotating (or decorating) of the parse tree.
type of each identifier to its entry in the symbol table.
In a SDD, each production A → ∝ is associated with a
set of semantic rules of the form:
b = f (c1, c2,… cn) where Production Semantic Rule
f : A function D → TL L.in = T.type
b can be one of the following: T → int T.type = integer
b is a ‘synthesized attribute’ of A and c1, c2,…cn are attrib-
utes of the grammar symbols in A → ∝. T → real T.type = real
The value of a ‘synthesized attribute’ at a node is com- L → L1, id addtype L1.in = L.in(id.entry, L.in)
puted from the value of attributes at the children of that
L → id addtype (id.entry, L.in)
node in the parse tree.
Example: The annotated parse tree for the sentence real id1, id2, id3 is
shown below:
Production Semantic Rule
D
expr → expr1 + term expr.t: = expr1.t||term.t||’+’
T⋅type = real L ⋅in = real
expr → expr1 – term expr.t: = expr1.t||term.t||’-‘

L ⋅in = real , id3

expr → term expr.t: = term.t real

term → 0 term.t: = ‘0’ L .in = real , id2

term → 1 term.t: = ‘1’
Id1
. . .

. . .

term → 9 term.t: = ‘9’

Synthesized Attribute
The value of a synthesized attribute at a node is computed
expr⋅t = 95 − 2+
from the value of attributes at the children of that node in a
term⋅t = 2 parse tree. Consider the following grammar:
expr⋅t = 95 −
L → En
expr⋅t = 9 term⋅t = 5 E → E1 + T
E→T
term⋅t = 9
T → T1*F
T→F
9 − 5 + 2 F → (E)
b is an ‘inherited attribute’ of one of the grammar symbols F → digit.
on the right side of the production. Let us consider synthesized attribute value with each of the
An ‘inherited attribute’ is one whose value at a node is non-terminals E, T and F.
defined in terms of attributes at the parent and/or siblings of Token digit has a synthesized attribute lexical supplied
that node. It is used for finding the context in which it appears. by lexical analyzer.
 Chapter 2  •  Syntax Directed Translation  |  6.29

Production Semantic Rule Dependency Graph

L → En print (E.val) The interdependencies among the attributes at the nodes
E → E1 + T E.val: = E1.val + T.val
in a parse tree can be depicted by a directed graph called
dependency graph.
E→T E.val: = T1.val
•• Synthesized attributes have edges pointing upwards.
T → T1*F T.val: = T1.val*F.val •• Inherited attributes have edges pointing downwards and/
T→F T.val: = F.val or sidewise.
F → (E) F.val: = E.val Example 1: A.a:= f (X.x, Y.y) is a semantic rule for A →
XY. For each semantic rule that consists of a procedure call:
F → digit F.val: = digit.lexval A⋅a

X⋅x Y⋅y
The Annotated parse tree for the expression 5 + 3 * 4 is
shown below: Example 2:
val
D E

E⋅val = 17 return
E2
E⋅val = 5 + T⋅val = 12 E1 +
val val
T⋅val = 5 T⋅val = 3 * F ⋅val = 4 Example 3: real p, q;
L⋅in = real
F⋅val = 5 F⋅val = 3 digit⋅lexval = 4
T ⋅type = real add type (q⋅real)
digit⋅lexval = 5 L1⋅in = real
digit⋅lexval = 3
id⋅entry = q
add type (P⋅real)
Example 1: Consider an example, which shows semantic
rules for Infix to posfix translation: id⋅entry = p

Production Semantic Rules

Evaluation order
expr → expr1 + term expr.t: = expr1.t||term.t||’+’ A topological sort of directed acyclic graph is an ordering
expr → expr1 – term expr.t: = expr1.t||term.t ||‘-‘ m1, m2, . . . mk of nodes of the graph S. t edges go from nodes
expr → term expr.t: = term.t earlier in the ordering to later nodes.
term → 0 term.t: = ‘0’ mi → mj means mi appears before mj in the ordering.
If b: = f (c1, c2, …, ck), the dependent attributes c1, c2,...ck are
. . .

. . .

available at node before f is evaluated.

term→ 9 term.t := ‘9’
Abstract syntax tree
Example 2: Write a SDD for the following grammar to It is a condensed form of parse tree useful for representing
determine number.val. language constructs.
number → number digit digit.val := ‘0’ Example
digit→ 0|1| . . . 9 digit.val := ‘1’  if-then-else
 
 
   B S1 S1
digit.val = ‘9’ 

number.val:=number.val * 10 + digit.val Constructing Syntax Trees

Annotated tree for 131 is for Expressions
131 Each node in a syntax tree can be implemented as a record
with several fields.
number⋅val = 13∗10 + number⋅val = 1
In the node for an operator, one field identifies the opera-
number⋅val∗10 + number⋅val digit⋅val = 1
tor and the remaining fields contain pointers to the nodes for
the operands.
digit⋅val digit⋅val 1. mknode (op, left, right)
2. mkleaf (id, entry). Entry is a pointer to symbol table.
1 3 3. mkleaf (num, val)
6.30 | Unit 6 • Compiler Design

Example: State Val

Production Semantic Rules
E→E1+T E.nptr := mknode (‘+’, E1.nptr, T.nptr) Top → Z Z.z
E→E1 – T E.nptr := mknode (‘-‘, E1.nptr, T.nptr) Y Y.y
E→T E.nptr := T.nptr
X X.x
T→ (E) T.nptr := E.nptr
T→id T.nptr := mkleaf(id, id.entry)
T→num T.nptr := mkleaf(num, num.val) Example: Consider the following grammar:

Construction of a syntax tree for a – 4 + c S→E$ {print(E.val)}

E⋅nptr E→E+E {E.val := E.val + E.val}

E → E*E {E.val := E.val * E.val}
E⋅nptr +
T⋅nptr E → (E) {E.val := E.val}
− + E→I {I.val := I.val * 10 + digit}
E⋅nptr T⋅nptr id I → I digit
T⋅nptr num I → digit {I.val := digit}
−
id id
Implementation
id num 4 to entry for c
S→E$ print (val [top])
to entry for a E→E+E val[ntop] := val[top] + val[top-2]
E → E*E val[ntop] := val[top] * val[top-2]
typeS of Sdd’S E → (E) val[ntop] := val[top-1]
Syntax Directed definitions (SDD) are used to specify syn- E→I val[ntop] := val[top]
tax directed translations. There are two types of SDD. I → I digit val[ntop] := 10*val[top] + digit
1. S-Attributed Definitions
I → digit val[ntop] := digit
2. L-Attributed Definitions.

S-attributed definitions L-attributed Definitions

• Only synthesized attributes used in syntax direct definition.
A syntax directed definition is L-attributed if each inherited
• S-attributed grammars interact well with LR (K) parsers
attribute of Xj, 1≤ j ≤ n, on the right side of A → X1 X2…Xn,
since the evaluation of attributes is bottom-up. They do
depends only on
not permit dependency graphs with cycles.
1. The attributes of symbols X1, X2, . . ., Xj-1 to the left of
L-attributed definitions Xj in the production.
• Both inherited and synthesized attribute are used. 2. The inherited attributes of A.
• L-attributed grammar support the evaluation of attributes
associated with a production body, dependency–graph Every S-attributed definition is L-attributed, because the
edges can go from left to right only. above two rules apply only to the inherited attributes.
• Each S-attributed grammar is also a L-attributed grammar.
• L-attributed grammars can be incorporated conveniently
in top down parsing.
• These grammars interact well with LL (K) parsers (both
SyntAx directed trAnSlAtion
table driven and recursive descent). SchemeS
A translation scheme is a CFG in which attributes are asso-
Synthesized Attributes on the ciated with grammar symbols and semantic actions are
Parser Stack enclosed between braces { } are inserted within the right
A translator for an S-attributed definition often be imple- sides of productions.
mented with LR parser generator. Here the stack is imple- Example: E → TR
mented by a pair of array state and val.
R → op T {print (op.lexeme)} R1|∈
• Each state entry is pointed to a LR (1) parsing table.
• Each val[i] holds the value of the attributes associated T → num {print (num.val)}
with the node. For A → xyz, the stack will be: Using this, the parse tree for 9 – 5 + 2 is
 Chapter 2  •  Syntax Directed Translation  |  6.31

E Thus we will evaluate all semantic actions during reductions,

and we find a place to store an inherited attribute. The steps are
T R
1. Remove an embedding semantic action Si, put new
9 −
R1 non-terminal Mi instead of that semantic action.
T {print(‘−’)}
{print(‘9’)} 2. Put Si into the end of a new production rule Mi → ∈.
+ R1
3. Semantic action Si will be evaluated when this new
T {print(‘+’)}
5 ∈
production rule is reduced.
2
{print(‘5’)} {print(‘2’)}
4. Evaluation order of semantic rules is not changed. i.e., if

A → {S1} X1{S2}X2…{Sn}Xn
If we have both inherited and synthesized attributes then we
have to follow the following rules: After removing embedding semantic actions:
1. An inherited attribute for a symbol on the right side A → M1X1M2X2…MnXn
of a production must be computed in an action before M1 → ∈{S1}
that symbol.
M2 → ∈{S2}
2. An action must not refer to a synthesized attribute of

. . .
a symbol on the right side of the action.
3. A synthesized attribute for the non–terminal on the left Mn→ ∈ {Sn}
can only be computed after all attributes it references, For example,
have been computed.
E → TR
Note: In the implementation of L-attributed definitions dur- R → +T {print (‘+’)} R1
ing predictive parsing, instead of syntax directed transla- R→∈
tions, we will work with translation schemes. T → id {print (id.name)}
⇓ remove embedding semantic actions
Eliminating left recursion from E → TR
translation scheme R → +TMR1
Consider following grammar, which has left recursion R→∈
E → E + T {print (‘+’) ;} T → id {print (id.name)}
M → ∈ {print (‘+’)}
When transforming the grammar, treat the actions as if they
were terminal symbols. After eliminating recursion from
the above grammar. Translation with inherited attributes
E → TR Let us assume that every non-terminal A has an inherited
R → +T {print (‘+’);} R attribute A.i and every symbol X has a synthesized attribute
R→∈ X.s in our grammar.
For every production rule A → X1, X2 . . . Xn, introduce
Bottom-up Evaluation new marker non-terminals
M1, M2, . . . Mn and replace this production rule with A →
of Inherited Attributes M1X1M2X2 . . . MnXn
•• Using a bottom up translation scheme, we can implement The synthesized attribute of Xi will not be changed.
any L-attributed definition based on LL (1) grammar. The inherited attribute of Xi will be copied into the syn-
•• We can also implement some of L-attributed definitions thesized attribute of Mi by the new semantic action added at
based on LR (1) using bottom up translations scheme. the end of the new production rule
•• The semantic actions are evaluated during the reductions. Mi → ∈
•• During the bottom up evaluation of S-attributed defi-
nitions, we have a parallel stack to hold synthesized Now, the inherited attribute of Xi can be found in the
attributes. synthesized attribute of Mi.
Where are we going to hold inherited attributes? A → {B.i = f1(. .) B { c.i = f2(. .)} c {A.s = f3(. .)}
We will convert our grammar to an equivalent grammar to
⇓
guarantee the following:
•• All embedding semantic actions in our translation scheme A → {M1.i = f1(. .)} M1 {B.i = M1.s} B {M2.i = f2(. .)}M2
will be moved to the end of the production rules. {c.i = M2.S} c {A.s = f3 (. .)}
•• All inherited attributes will be copied into the synthesized M1 → ∈ {M1.s = M1.i}
attributes (may be new non-terminals). M2 → ∈ {M2.s = M2.i}
6.32 | Unit 6 • Compiler Design

exerciSeS
Practice Problems 1 3. Which of the following productions with transla-
Directions for questions 1 to 13: Select the correct alterna- tion rules converts binary number representation into
tive from the given choices. decimal.
1. The annotated tree for input ((a) + (b)), for the rules (A) Production Semantic Rule
given below is
B→0 B.trans = 0
Production Semantic Rule
B→1 B.trans = 1
E→E+T $ $ = mknode (‘+’, $1, $3)
B → B0 B1.trans = B2.trans*2
E → E-T $ $ = mknode (‘-’, $1, $3)
B → B1 B1.trans = B2.trans * 2 + 1
E→T $ $ = $1;
T → (E) $ $ = $2;
(B) Production Semantic Rule
T → id $ $ = mkleaf (id, $1)
B→0 B.trans = 0
T → num $ $ = mkleaf (num, $1)
B → B0 B1.trans = B2.trans*4
(A) E (B) E

T (C) Production Semantic Rule

T
( E ) B→1 B.trans = 1
( E )
B → B1 B1.trans = B2.trans*2
E + T
E + T
T
( E )
(D) None of these
T id = b 4. The grammar given below is
( E ) T
( E ) Production Semantic Rule
T id = b

id = a id = a A → LM L.i := l(A. i)

M.i := m(L.s)
(C) E (D) None of these A.s := f(M.s)

E + T A → QR R.i := r(A.i)

T id = b Q.i := q(R.s)

A.s := f(Q.s)
id = a

(A) A L-attributed grammar

2. Let synthesized attribute val give the value of the binary (B) Non-L-attributed grammar
number generated by S in the following grammar. (C) Data insufficient
S→LL (D) None of these
S→L 5. Consider the following syntax directed translation:
L → LB S → aS {m := m + 3; print (m);}
L→B |bS {m: = m*2; print (m) ;}
B→0 |∈ {m: = 0 ;}
B→1 A shift reduce parser evaluate semantic action of a pro-
Input 101.101, S.val = 5.625 duction whenever the production is reduced.
use synthesized attributes to determine S.val
Which of the following are true? If the string is = a a b a b b then which of the following
(A) S → L1.L2 {S.val = L1.val + L2.val/ (2**L2.bits) is printed?
|L {S.val = L.val; S.bits = L.bits} (A) 0 0 3 6 9 12 (B) 0 0 0 3 6 9 12
(B) L → L1 B {L.val = L1.val*2 + B.val; (C) 0 0 0 3 6 9 12 15 (D) 0 0 3 9 6 12
L.bits = L1.bits + 1} 6. Which attribute can be evaluated by shift reduce parser
|B {L.val = B.val; L.bits = 1} that execute semantic actions only at reduce moves but
(C) B → 0 {B.val = 0} never at shift moves?
|1 {B.val = 1} (A) Synthesized attribute (B) Inherited attribute
(D) All of these (C) Both (a) and (b) (D) None of these
 Chapter 2  •  Syntax Directed Translation  |  6.33

7. Consider the following annotated parse tree: If Input = begin east south west north, after evaluating

A A⋅num = y⋅num + z⋅num this sequence what will be the value of S.x and S.y?
(A) (1, 0) (B) (2, 0)
B⋅num = num B + C C⋅num = num (C) (-1, -1) (D) (0, 0)
11. What will be the values s.x, s.y if input is ‘begin west
num num south west’?
(A) (–2, –1)
Which of the following is true for the given annotated (B) (2, 1)
tree? (C) (2, 2)
(A) There is a specific order for evaluation of attribute (D) (3, 1)
on the parse tree.
(B) Any evaluation order that computes an attribute 12. Consider the following grammar:
‘A’ after all other attributes which ‘A’ depends on,  S → E S.val = E.val
is acceptable.
(C) Both (A) and (B) E.num = 1
(D) None of these. E → E*T E1.val = 2 * E2.val + 2 * T.val
Common data for questions 8 and 9:  Consider the fol- E2.num = E1.num + 1
lowing grammar and syntax directed translation. T.num = E1.num + 1
E → T E.val = T.val
E→E+T E1.val = E2.val + T.val
T.num = E.num + 1
E→T E.val = T.val
 T → T + P T1.val = T2.val + P.val
T → T*P T1.val = T2.val * P.val *
P.num T2.num = T1.num + 1
P.num = T1.num + 1
T→P T.val = P.val * P.num
T → P T.val = P.val
P → (E) P.val = E.val
P.num = T.num + 1
P→0 P.num = 1
P → (E) P.val = E.val
P.val = 2
P→1 P.num = 2  E .num = P.num 
P → i  
P.val = 1  P.val = I | P.num 
Which attributes are inherited and which are synthe-
8. What is E.val for string 1*0? sized in the above grammar?
(A) 8 (B) 6
(A) Num attribute is inherited attribute. Val attribute is
(C) 4 (D) 12
synthesized attribute.
9. What is the E.val for string 0 * 0 + 1?
(B) Num is synthesized attribute. Val is inherited at-
(A) 8 (B) 6
tribute.
(C) 4 (D) 12
(C) Num and val are inherited attributes.
10. Consider the following syntax directed definition: (D) Num and value are synthesized attributes.
Production Semantic Rule 13. Consider the grammar with the following translation
S→b S.x = 0
rules and E as the start symbol.
S.y = 0 E → E1@T {E.value = E1.value*T.value}
S → S1 I S.x = S1.x + I.dx
S.y = S1.y + I.dy
|T {E.value = T.value}
I → east I.dx = 1 T → T1 and F {T.value = T1.value + F.value}
I.dy = 0
|F {T.value = F.value}
I → north I.dx = 0
I.dy = 1 F → num  {F.value = num.value}
I → west I.dx = -1
Compute E.value for the root of the parse tree for the
I.dy = 0
expression: 2 @ 3 and 5 @ 6 and 4
I → south I.dx = 0
I.dy = -1 (A) 200 (B) 180
(C) 160 (D) 40
6.34 | Unit 6  •  Compiler Design

Practice Problems 2 (C) Action translating expression represents postfix

Directions for questions 1 to 10:  select the correct alterna- notation.
tive from the given choices. (D) None of these
1. Consider the following Tree: 4. In the given problem, what will be the result after eval-
uating 9 – 5 + 2?
Production Meaning
(A) + - 9 5 2 (B) 9 – 5 + 2
E → E1 + T E.t = E1.t*T.t (C) 9 5 – 2+ (D) None of these
E → E1 – T E.t = E1.t + T.t
5. In a syntax directed translation, if the value of an attrib-
E→T E.t = T.t ute node is a function of the values of attributes of chil-
t→0 T.t = ‘0’ dren, then it is called:
(A) Synthesized attribute (B) Inherited attribute
t→5 T.t = ‘5’
(C) Canonical attributes (D) None of these
t→2 T.t = ‘2’
6. Inherited attribute is a natural choice in:
t→4 T.t = ‘4’
(A) Keeping track of variable declaration
E (B) Checking for the correct use of L-values and R-
values.
E + T (C) Both (A) and (B)
(D) None of these
E - T
7. Syntax directed translation scheme is desirable because
(A) It is based on the syntax
T 2
4 (B) Its description is independent of any implementa-
5 tion.
After evaluation of the tree the value at the root will be: (C) It is easy to modify
(A) 28 (B) 32 (D) All of these
(C) 14 (D) 7 8. A context free grammar in which program fragments,
2. The value of an inherited attribute is computed from the called semantic actions are embedded within right side
values of attributes at the _______ of the production is called,
(A) Sibling nodes (B) Parent of the node (A) Syntax directed translation
(C) Children node (D) Both (A) and (B) (B) Translation schema
(C) Annotated parse tree
3. Consider an action translating expression:
(D) None of these
expr → expr + term {print (‘+’)}
expr → expr - term {print (‘-’)} 9. A syntax directed definition specifies translation of
expr → → term construct in terms of:
term → 1 {print (‘1’)} (A) Memory associated with its syntactic component
term → 2 {print (‘2’)} (B) Execution time associated with its syntactic com-
term → 3 {print (‘3’)} ponent
(C) Attributes associated with its syntactic component
Which of the following is true regarding the above (D) None of these
translation expression?
(A) Action translating expression represents infix 10. If an error is detected within a statement, the type
notation. assigned to the Statement is:
(B) Action translating expression represents prefix (A) Error type (B) Type expression
notation. (C) Type error (D) Type constructor

Previous Years’ Questions

Common data for questions 1 (A) and 1 (B): Consider 1. (A) The above grammar and the semantic rules are fed
the following expression grammar. The semantic rules for to a yacc tool (which is an LALR (1) parser gener-
expression evaluation are stated next to each grammar pro- ator) for parsing and evaluating arithmetic expres-
duction:[2005] sions. Which one of the following is true about the
E → number E.val = number.val action of yacc for the given grammar?
(A) It detects recursion and eliminates recursion
|E ‘+’ E E (1).val = E (2).val + E (3).val
(B) It detects reduce-reduce conflict, and resolves
|E → E E (1).val = E (2).val × E (3).val
 Chapter 2  •  Syntax Directed Translation  |  6.35

(C) It detects shift-reduce conflict, and resolves the (C) The maximum number of successors of a node
conflict in favor of a shift over a reduce action. in an AST and a CFG depends on the input pro-
(D) It detects shift-reduce conflict, and resolves the gram.
conflict in favor of a reduce over a shift action. (D) Each node in AST and CFG corresponds to at
(B) Assume the conflicts in Part (A) of this question most one statement in the input program.
are resolved and an LALR (1) parser is gener- 3. Consider the following Syntax Directed Translation
ated for parsing arithmetic expressions as per the Scheme (SDTS), with non-terminals {S, A} and ter-
given grammar. Consider an expression 3 × 2 minals {a, b}.[2016]
+ 1. What precedence and associativity proper- S → aA { print 1 }
ties does the generated parser realize?
S → a { print 2 }
(A) Equal precedence and left associativity; expres-
sion is evaluated to 7 A → Sb { print 3 }
(B) Equal precedence and right associativity; expres- Using the above SDTS, the output printed by a bot-
sion is evaluated to 9 tom-up parser, for the input aab is:
(C) Precedence of ‘×’ is higher than that of ‘+’, and (A)  1 3 2 (B)  2 2 3
both operators are left associative; expression is (C)  2 3 1 (D)  syntax error
evaluated to 7 4. Which one of the following grammars is free from left
(D) Precedence of ‘+’ is higher than that of ‘×’, and recursion?[2016]
both operators are left associative; expression is (A) S → AB
evaluated to 9 A → Aa|b
2. In the context of abstract-syntax-tree (AST) and B → c
control-flow-graph (CFG), which one of the follow- (B) S → Ab|Bb|c
A → Bd|ε
ing is TRUE?[2015]
B → e
(A) In both AST and CFG, let node N2 be the suc- (C) S → Aa|B
cessor of node N1. In the input program, the code A → Bb|Sc|ε
corresponding to N2 is present after the code cor- B → d
responding to N1. (D) S → Aa|Bb|c
(B) For any input program, neither AST nor CFG A → Bd|ε
will contain a cycle. B → Ae|ε

Answer Keys
Exercises
Practice Problems 1
1. A 2. D 3. A 4. B 5. A 6. A 7. B 8. C 9. B 10. D
11. A 12. A 13. C

Practice Problems 2
1. A 2. D 3. C 4. C 5. A 6. C 7. D 8. B 9. C 10. C

Previous Years’ Questions

1. (a) C (b) B 2. C 3. C 4. A