Consider the grammar G: S → Aa | bAc | dc | bda A → e Construct the CLR(1)…

Consider the grammar G:

S → Aa | bAc | dc | bda

A → e

Construct the CLR(1) (Canonical LR(1)) parser for this grammar.
Let N denote the total number of entries in its CLR(1) parsing table, where the total count includes all cells for ACTION and GOTO.

The value of N is ______.

Answer: 77Key result: The total number of entries N in the CLR(1) parsing table is 77. Steps to obtain this result: Augment the grammar: add S' → S. The original…

Attempted by 2 students.

Show answer & explanation

Correct answer: 77

Key result: The total number of entries N in the CLR(1) parsing table is 77.

Steps to obtain this result:

  • Augment the grammar: add S' → S. The original productions are S → A a, S → b A c, S → d c, S → b d a and A → ε.

  • Terminals and nonterminals: terminals = {a, b, c, d}, nonterminals = {S, A}.

  • Table columns per state: ACTION columns = terminals plus end-marker = 4 + 1 = 5. GOTO columns = number of nonterminals = 2. Total columns per state = 5 + 2 = 7.

  • Canonical LR(1) collection size: constructing the CLR(1) canonical collection (closure and goto on LR(1) items) for this grammar produces 11 states (denoted I0 through I10). The presence of the nullable nonterminal A and the different lookaheads for items originating from S → A a and S → b A c yields distinct LR(1) item sets, leading to 11 distinct states.

  • Final count: number of states × columns per state = 11 × 7 = 77. Therefore N = 77.

Note: The detailed listing of all LR(1) item sets and the full ACTION/GOTO table is omitted for brevity; the crucial points used are the terminal/nonterminal counts, the inclusion of the end-marker column, and the canonical collection size of 11 states, which yields the stated total.

A video solution is available for this question — log in and enroll to watch it.

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…