IAE Academy

GATE 2018 CS Q.38: solution and answer

GATE 2018 · CSQ.38 · 2 marks · MCQ

Consider the following parse tree for the expression a#b$c$d#e#f, involving two binary operators $ and #.

Which one of the following is correct for the given parse tree?

GATE 2018 CS question 38: Parse tree.Tap to open full size
Figure from the GATE 2018 CS paper. It is part of the question.
Figure description

Parse tree. Root node # has two children: leaf a (left) and an internal node # (right). That right # node has two children: an internal node (left) and an internal # node (right). The left node has two children: an internal node (left) whose children are leaves b and c, and leaf d (right). The right # node has two children: leaf e (left) and leaf f (right). Leaves read left to right: a, b, c, d, e, f.

  1. (A)

    $ has higher precedence and is left associative; # is right associative

  2. (B)

    # has higher precedence and is left associative; $ is right associative

  3. (C)

    $ has higher precedence and is left associative; # is left associative

  4. (D)

    # has higher precedence and is right associative; $ is left associative

Answer and solution

ANSWER

Option (A): $ has higher precedence and is left associative; # is right associative.

Official answer: ASource: Official answer key, GATE 2018 CS (IIT Guwahati)

  1. Read the tree as a bracketing. The root # has left child a and right child another # node, so the whole expression is a # (rest) with rest = b$c$d#e#f.

  2. The inner # node has as its left subtree a $ node over b, c, d, and as its right subtree the node e # f. The $ node itself has a left child $ over b, c and a right child d. So the full bracketing is a # ( ((b $ c) $ d) # (e # f) ).

  3. Precedence: the $ operations sit lower in the tree than the # operators that combine their results, so they are evaluated first. Hence $ has higher precedence than #. This rules out (B) and (D).

  4. Associativity of $: the chain b $ c $ d is grouped as (b $ c) $ d, so the expansion continues down the left operand. Hence $ is left associative.

  5. Associativity of #: the # operators at the top, in the order a, b$c$d, e, f, are grouped as a # ((b$c$d) # (e # f)), so the expansion continues down the right operand. Hence # is right associative. This rules out (C).

  6. Therefore $ has higher precedence and is left associative, and # is right associative, which is option (A).

KEY IDEA

Read precedence from depth: operators lower in the parse tree bind tighter. Read associativity from which side the chain of the same operator grows: growth down the left child means left associative, down the right child means right associative.

WATCH OUT FOR

Judging associativity from where the leaves sit rather than from which child holds the repeated operator, or reading the higher node in the tree as the higher-precedence operator. The root # is the last to be evaluated, so # has the lower precedence.

From the GATE 2018 CS paper. Every question of this paper · Download the full paper · All 13 Parsing questions, with notes

More Parsing questions