[ri4pp:2007] - Re: Pitanje by "Љубомир Самарџић" <ljubex@gmail.com>

Postoji onaj algoritam u zbirci (strana 269). U principu, ide ovako:
prvo napises stanje koje te zanima (to je onaj skup konfiguracija). I
za nulto stanje za ovu gramatiku koju si dao skup konfiguracija je
tacno taj koji si dao.

Gramatika:
1.    <S> -> <A> <S>
2.    <S> -> E
3.    <A> -> <B> b <B> c
4.    <A> -> <C> c <B>
5.    <B> -> a <D>
6.    <C> -> a <D>
7.    <D> -> E

Nulto stanje:
k1. <S'> -> ·<S>–|, {}
k2. <S> -> ·<A><S>, –|
k3. <S> -> E·, –|
k4. <A> -> ·<B>b<B>c, {a, –|}
k5. <A> -> ·<C>c<B>, {a, –|}
k6. <B> -> ·a<D>, b
k7. <C> -> ·a<D>, c

Fora je sto za svaku konfiguraciju (ja sam ih ovde oznacio od k1 -
k7), gledas sta moze da dodje iza neterminala koji je sa leve strane u
toj konfiguraciji. Dakle, ako je:
<P> -> .....
gledaces sta sve moze da stoji iza tog <P> u ostalim konfiguracijama,
ali samo posmatrajuci one <P>-ove koji u drugim konfiiguracijama imaju
tacku ispred sebe!!

E sad redom:

<S'> -> ·<S>–|, {}
Iza <S'> ne moze da dodje nista.

<S> -> ·<A><S>, –|
Iza <S> moze da dodje samo –|

<S> -> E·, –|
Ponovo, iza <S> moze samo da dodje –|

<A> -> ·<B>b<C>c, {a, –|}
Iza <A> moze da dodje "a" zato sto je "a" u stvari FIRST(S) (vidi
smenu 1). Takodje iza <A> moze da dodje "–|" zato sto je <S> ponistivo
(jer kad je <S> -> E, tj kad ga nema, iza <A> dolazi upravo –|)

<A> -> ·<C>c<B>, {a, –|}
Opet ista logika kao gore

<B> -> ·a<D>, b
Iza <B> moze da dodje (opste govoreci) b, c i FOLLOW(A) (jer se 4.
smena zavrsava sa <B>), medjutim nama su interesantni samo oni
neterminali koji ispred sebe imaju tacku. Dakle pitanje glasi: sta
dolazi iza onog <B> u konfiguraciji k4. Dakle samo b, i to upravo
vidis iz k4.

<C> -> ·a<D>, c
Iza <C> dolazi samo c (vidi k5).


E sad sve ovo ponovis za sva stanja, tj skupove konfiguracija koje si napravio.