Jaka jest ta gramatyka LL (1)?


To pytanie z Dragon Book. Oto gramatyka:


Pytanie dotyczy tego, jak pokazać, że jest to LL (1), ale nie SLR (1).

Aby udowodnić, że jest to LL (1), próbowałem zbudować jego tabelę analizującą, ale otrzymuję wiele produkcji w komórce, co jest sprzecznością.

Powiedz, jak to jest LL (1) i jak to udowodnić?

Nie znam się dobrze na gramatyce, ale wydaje się, że język tej gramatyki jest skończony. L={ab,ba}

@Nejc: Tak, wydaje się, że tak!
Vinayak Garg,



Po pierwsze, dajmy swoim produkcjom numer.

1 2 3 4SAaAb

Obliczmy pierwszy i najpierw wykonajmy zestawy. W przypadku takich małych przykładów wystarczy intuicyjna obsługa tych zestawów.


Teraz obliczmy tabelę . Z definicji, jeśli nie dostaniemy konfliktów, gramatyka to .LL(1)LL(1)

    a | b |
S | 1 | 2 |
A | 3 | 3 |
B | 4 | 4 |

Ponieważ nie ma konfliktów, gramatyka to .LL(1)

Teraz tabela . Po pierwsze, automat .SLR(1)LR(0)

state 0SAaAbSBbBaABA1B5
state 1SAaAba2
state 2SAaAbAA3
state 3SAaAbb4
state 4SAaAbb
state 5SBbBab6
state 6SBbBaBB7
state 7SBbBaa8
state 8SBbBa

And then the SLR(1) table (I assume S can be followed by anything).

    a     | b     | A | B |
0 | R3/R4 | R3/R4 | 1 | 5 |
1 | S2    |       |   |   |
2 | R3    | R3    | 3 |   |
3 |       | S4    |   |   |
4 | R1    | R1    |   |   |
5 |       | S4    |   |   |
6 | R4    | R4    |   | 7 |
7 | S8    |       |   |   |
8 | R2    | R2    |   |   |

There are conflicts in state 0, so the grammar is not SLR(1). Note that if LALR(1) was used instead, then both conflicts would be resolved correctly: in state 0 on lookahead a LALR(1) would take R3 and on lookahead b it would take R4.

This gives rise to the interesting question whether there is a grammar that is LL(1) but not LALR(1), which is the case but not easy to find an example of.

Thanks! I had constructed the First & Follow correctly, but I made a mistake in constructing the table.
Vinayak Garg


If you are not asked, you don't have to construct the LL(1) table to prove that it is an LL(1) grammar. You just compute the FIRST/FOLLOW sets as Alex did:


And then, by definition an LL(1) grammar has to:

  1. If Aa and Ab are two different rules of the grammar, then it should be that FIRST(a)FIRST(b)=. Hence, the two sets haven't any common element.
  2. If for any non-terminal symbol A you have Αε, then it should be that FIRST(A)FOLLOW(A)=. Hence, if there is a zero production for a non-terminal symbol, then the FIRST and FOLLOW sets can't have any common element.

So, for the given grammar:

  1. We have FIRST(AaAb)FIRST(BbBa)= since FIRST(AaAb)={a} while FIRST(BbBa)={b} and they don't have any common elements.
  2. FIRST(A)FOLLOWA)= since FIRST(A)={a,b} while FOLLOW(A)=, and now FIRST(B)FOLLOW(B)= since FIRST(B)={ε} while FOLLOW(B)={a,b}.

As for the SLR(1) analysis I think it is flawless!

Welcome! In order to improve this answer, why don't you apply what you state to the grammar at hand?

Happy to be here!! Answered your request and I think I gave a thorough explanation!

Thanks! Note that we can use LaTeX here, as I did edit in for your maths.

Wow Thanks! this is a great explanation. But I think there is some mistake in the application. Isn't First(A) = {epsilon}? I think you swapped the FIRST and FOLLOW.
Vinayak Garg

FIRST(A) is indeed epsilon but since you are looking to calculate the whole right member's FIRST set, A -> ε just shows that we have an empty production and the first terminal symbol you see (and therefore the FIRST set of it) is terminal symbol a. Hope this helped!


Search for a sufficient condition which makes a grammar LL(1) (hint: look at the FIRST sets).

Search for a needed condition which all SLR(1) grammars must meet (hint: look at the FOLLOW sets).

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.