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?
- A.
$ has higher precedence and is left associative; # is right associative
- B.
# has higher precedence and is left associative; $ is right associative
- C.
$ has higher precedence and is left associative; # is left associative
- 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.
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.
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.
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.