GATE CS 2011 Q.27 (CS Q.27): Parsing and Syntax Analysis (LL and LR)

Consider two binary operators ' $\uparrow$ ' and ' $\downarrow$ ' with the precedence of operator $\downarrow$ being lower than that of operator $\uparrow$ . Operator $\uparrow$ is right associative while operator $\downarrow$ is left associative. Which one of the following represents the parse tree for expression $(7 \downarrow 3 \uparrow 4 \uparrow 3 \downarrow 2)$ ?

Option A parse tree with root down-arrow having left child 7 and right-leaning subtree

Option B parse tree with root down-arrow having left child down-arrow and right child 2

Option C parse tree with root down-arrow having left child 7 and right child down-arrow

Option D parse tree with root down-arrow having left child up-arrow and right child 2

Official answer and solution

Official answer: B
From: Official GATE 2011 answer key

Solution

Apply operator precedence and associativity to construct the unique parse tree for the expression.

The expression to parse is $7 \downarrow 3 \uparrow 4 \uparrow 3 \downarrow 2$ .

Precedence rule: $\uparrow$ has higher precedence than $\downarrow$ , so subexpressions involving $\uparrow$ bind tighter.

Associativity rule for $\uparrow$ : Right-associative. The subexpression $3 \uparrow 4 \uparrow 3$ parenthesizes as $(3 \uparrow (4 \uparrow 3))$ .

Associativity rule for $\downarrow$ : Left-associative with lower precedence. The full expression parenthesizes as:

((7 \downarrow (3 \uparrow (4 \uparrow 3))) \downarrow 2)

In the parse tree:

The root is the lowest-precedence leftmost operator $\downarrow$ with left subtree $(7 \downarrow (3 \uparrow (4 \uparrow 3)))$ and right child $2$ .
The left subtree has root $\downarrow$ with left child $7$ and right child $(3 \uparrow (4 \uparrow 3))$ .
This matches parse tree B exactly.

Final answer

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2011 Computer Science and Information Technology (CS)
Question: 27 of 65, printed as CS Q.27
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source