consider the CFG with productions S --> S 1 $ S 1 --> S 1 + T | T T --> T * F |

Question

consider the CFG with productions S --> S1 $ S1--> S1 + T | T T --> T * F | F F --> (S1) | a a) write the CFG obtained from this one byeliminating left recursion. b) Give a transition table for a DPDA that acts as atop-down parser for this language. consider the CFG with productions S --> S1 $ S1--> S1 + T | T T --> T * F | F F --> (S1) | a a) write the CFG obtained from this one byeliminating left recursion. b) Give a transition table for a DPDA that acts as atop-down parser for this language.

Explanation / Answer

(a)

  

S -- S1 $

  -- S1+T $

  -- T+T $

   -- T* F +T *

   -- F * F + T $

  -- F * F + F $

   -- a * F + T $

   -- a * a + F $

   -- a * a + a $

(b)

                                   

Working-String Generation

S -- S1 $

S -- S1 + T$

S -- T +T$

S -- T * F + T $

S -- T * F + F $

S -- F * F + F $

S -- a * F + F $

S -- a * a + F $

S -- a * a + a $

Production Used

S -- S1 $

S1-- S1 + T

S1-- T

T-- T * F

T-- F

T-- F

F-- a

F-- a

F-- a

Working-String Generation

S -- S1 $

S -- S1 + T$

S -- T +T$

S -- T * F + T $

S -- T * F + F $

S -- F * F + F $

S -- a * F + F $

S -- a * a + F $

S -- a * a + a $

Production Used

S -- S1 $

S1-- S1 + T

S1-- T

T-- T * F

T-- F

T-- F

F-- a

F-- a

F-- a

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.