GATE CSE 1996 | Question: 20

Question

Consider the syntax-directed translation schema (SDTS) shown below:

• $E\rightarrow E + E$ {print “+”}
• $E\rightarrow E * E$ {print “.”}
• $E\rightarrow id$ {print id.name}
• $E\rightarrow (E)$

An LR-parser executes the actions associated with the productions immediately after a reduction by the corresponding production. Draw the parse tree and write the translation for the sentence.

$(a+b)*(c+d)$, using SDTS given above.

Answer 1

$\mathbf{ab+cd+.}$

Comments

nice explanation jayendra

---

my question is that this grammar is ambigious and LR-parsers can parse only unambigious grammars.
Here do we assume that we have removed the ambiguity from the grammar and only then passed it to the parser?

---

@Doraemon

$just\ a\ thought\ that\ maybe\ we\ can\ make\ use\ of\ operator\ precedence\ parser !!$

---

Though the grammar is ambiguous, the input string given in the question has only one possible derivation in the grammar (because of the presence of parenthesis), so the parser doesn’t encounter any problem for this particular instance. Another way to put it is that while parsing the input, the parser doesn’t visit the multiply defined entries, i.e., the entries where one than one production rule is present.

Answer 2

ab+cd+.      its a basic SDT, used to find the postfix expression.