Consider the following parse tree for the expression a#b$c$d#e#f, involving…

2018

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?

  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

Attempted by 71 students.

Show answer & explanation

Correct answer: A

Key insight: $ has higher precedence than #; $ is left-associative; # is right-associative.

  1. Look at the root of the parse tree: the top operator is # with left child a and right child another #. This structure groups the # operators to the right (i.e., an expression of the form x # y # z is parsed as x # (y # z)), so # is right-associative.

  2. Examine the left part of the right subtree: there are two nested $ nodes combining b, c and then d, giving ((b $ c) $ d). This shows $ groups left-to-right, so $ is left-associative.

  3. Because the $ nodes occur deeper in the tree (they are evaluated before the # nodes that appear higher), $ has higher precedence than #.

Final parenthesized grouping implied by the tree: a # ( ((b $ c) $ d) # (e # f) ).

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…