retagged by
9,249 views
19 votes
19 votes

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. $ has higher precedence and is left associative; # is right associative
  2. # has higher precedence and is left associative; $ is right associative
  3. $ has higher precedence and is left associative; # is left associative
  4. $ has higher precedence and is right associative; # is left associative
retagged by

4 Answers

Best answer
27 votes
27 votes

Inorder $:\{a\#[((b\$c)\$d)\#(e\#f)]\}$ (given in question) 

If we observe, first evaluation is $ b\$c$
So,  (\$) has higher priority.
Therefore, either option (A) or (C) is correct

$\underline{\text{Option A}}$
$\$$ has higher precedence and $\#$ is right associative.

From tree, it is clear that $(e\#f)$ is evaluating first which is to the right side of the root.
Therefore, $\#$ is Right Associative.
So, Option A is correct

$\underline{\text{Option C}}$
$\$$ has higher precedence and $\#$ is left associative.
This is wrong.

Correct Answer: A.

edited by
19 votes
19 votes

We can write the grammar and easily find the associativity.

Option A is correct.

edited by
18 votes
18 votes

$ is the highest precedence with left associative(since evaluated first) and # is right associative.

A is answer

15 votes
15 votes

In expression tree

  • Highest Precedence Operator is at the lowest level in the tree so that it is evaluated first.
  • For unambiguous grammar, we can get precedence and associativity directly from production or expression tree.
  • Left Associativity => Left Linear Grammar or in expression, tree it should expand on left child for the same operator and vice versa

Here at the lowest level, we have $ so it has the highest precedence.

# is right associative and $ is left associative.

Hence (A) is correct.

Answer:

Related questions