Skip to content
GATETECH
Official PYQ · 2005Q83aParsing (LL, LR)MCQ1 mark

GATE CS 2005 Q83a — Parsing (LL, LR)

Explain with AI

Statement for Linked Answer Questions 83a & 83b:

Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production. E→numberE.val=number.val∣ E  ‘+’ EE(1).val=E(2).val+E(3).val∣ E  ‘×’ EE(1).val=E(2).val×E(3).val\begin{array}{l|l} E\rightarrow number & E.val = {number.val} \\\qquad \mid \ E \ \ ‘+\text{'} \ E & E^{(1)}.val = E^{(2)}.val + E^{(3)}.val \\\qquad \mid \ E \ \ ‘\times\text{'} \ E & E^{(1)}.val = E^{(2)}.val \times E^{(3)}.val \end{array}

The above grammar and the semantic rules are fed to a yaac tool (which is an LALR(1) parser generator) for parsing and evaluating arithmetic expressions. Which one of the following is true about the action of yaac for the given grammar?

Choose one option
View worked solution

Answer: C

The given grammar is ambiguous:

E→number∣E+E∣E×EE \rightarrow \text{number} \mid E + E \mid E \times E

When an ambiguous grammar is fed to yacc (an LALR(1) parser generator), it generates conflicts in the parsing table:

  • Shift-Reduce Conflicts: For an input like id + id + id, after parsing the first id + id, the parser can either reduce E + E to E, or shift the next + operator.

By default, yacc resolves these conflicts using the following built-in disambiguation rules:

  1. Shift-Reduce Conflict: Resolved in favor of the shift action (which makes operators right-associative by default unless precedence declarations are specified).
  2. Reduce-Reduce Conflict: Resolved by choosing the production rule that appears first in the grammar specification.

Therefore, yacc detects a shift-reduce conflict and resolves it in favor of a shift over a reduce action.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Parsing (LL, LR) questions