Academic Integrity: tutoring, explanations, and feedback — we don’t complete graded work or submit on a student’s behalf.

here is question: convert the following 2 grammars intoLL(1) grammars 1) S --> S

ID: 3611567 • Letter: H

Question

here is question: convert the following 2 grammars intoLL(1) grammars 1) S --> S1 $ S1 -->S1 T | ab T --> a T b b | ab . 2) . S --> S1 $ S1 --> a A b | aAA |aB|bbA A --> a A b | ab B--> bBa | ba here is question: convert the following 2 grammars intoLL(1) grammars 1) S --> S1 $ S1 -->S1 T | ab T --> a T b b | ab . 2) . S --> S1 $ S1 --> a A b | aAA |aB|bbA A --> a A b | ab B--> bBa | ba S1 --> a A b | aAA |aB|bbA A --> a A b | ab B--> bBa | ba

Explanation / Answer

1) S --> S1 $ S1 -->S1 T |  ab                                          T --> a T b b | ab

Removing left-recursion:
S --> S1$
S1 --> abS'
S' --> TS' |
T --> aTbb | ab

Now left factoring gives:

S -->S1$
S1 --> abS'
S' -->TS' |
T -->aT'
T' -->Tbb | b

. 2) . S --> S1 $ S1 --> a A b |  aAA|aB|bbA                                          A --> a A b | ab B--> bBa | ba

There is no left recursion in this grammar
now left factoring gives

S --> S1 $ S1 --> aS' | bbA
S' --> AS'' |B
S'' --> b |A                                         A --> aA'
A' --> Ab | b B--> bB'
B'--> Ba | a

S1 --> a A b |  aAA|aB|bbA                                          A --> a A b | ab B--> bBa | ba

There is no left recursion in this grammar
now left factoring gives

S --> S1 $ S1 --> aS' | bbA
S' --> AS'' |B
S'' --> b |A                                         A --> aA'
A' --> Ab | b B--> bB'
B'--> Ba | a

S --> S1 $ S1 --> aS' | bbA
S' --> AS'' |B
S'' --> b |A                                         A --> aA'
A' --> Ab | b B--> bB'
B'--> Ba | a

S1 --> aS' | bbA
S' --> AS'' |B
S'' --> b |A                                         A --> aA'
A' --> Ab | b B--> bB'
B'--> Ba | a

Related Questions

Navigate

here is question.. 2) Create an employee_class that contains an employee\'s firs

here is some of my code. i am having trouble in the fractions. I wanted to creat

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