[ri4pp:2006] - Re: LR(1) by "Jovan Popovic" <jovan@etf.bg.ac.yu>

Kratko objasnjenje za LR(1):

Ako u stanju imate smenu u kojoj te tacka ispred neterminala - *<X>
1. Dodajte sve smene u kojima je <X> na levoj strani i stavite im tacke na
pocetak
2. U smeni u kojoj je tacka ispred neterminala *<X> odredite First skup
gramatickih simobla koji su iza <X> u toj smeni i dodajte na to
predikcione simbole iz te smene ako se iza <X> ne nalazi nista ili ako je
skup simbola iza <X> ponistiv. Ako je smena obilka <nesto> -> <nesto> *<X>
ALFA, {pred}.
Gde je ALFA neki niz terminala i neterminala iza <X> a {pred} skup
predikcionih simbola u toj smeni predikcioni skup za nove smena je
FIRST(ALFA {pred}) - pazite ne radi se o uniji ALFa i {pred} nego o
konkatenaciji {pred} ce biti u skupu samo ako je ALFA ponistiv. Taj
dobijeni skup je skup predikcionih simbola za nove konfiguracije.

U LR(1) automatima se u predikcione skupove ne dodaju follow skupovi nego
samo nizovi simbola koji su iza neterminala u toj smeni.

Kada odredjujete da li treba da se izvrsi REDUCE ili REJECT za
konfiguraciju u kojoj je tacka na kraju reduce vrsite samo ako je na ulazu
simbol iy predikcionog skupa te smene.

Mozda sam ovo malo konfuzno objasnio ali pogledajte predavanja ili vezbe
za detalje.

Pozdrav,
Jovan



> Imam nekoliko problema sa LR(1) gramatikama, molim sve za pomoc, a
> pogotovo profesora i asistenta.
>
> Radi se o zadatku koji je primer za kreiranje parsera LR(1) gramatike sa
> predavanja u dokumentu RI4PP_BUP2.doc (strana 4 pa nadalje).
>
> 1. Zanimaju me neki detalji o konstruciji karakteristicnog automata
> (SLIKA na str. 5), tj. kako se odredjuju predikiconi simboli u pojedinim
> konfiguracijama nekog stanja? Da li su to svi simboli iz FOLLOW skupa
> neterminala sa leve strane smene? Ako je tako zasto onda u stanju
> trouglic i stanju ax nema markera kraja kao predikcionog simbola u
> konfiguracijama <A>-> *a,a i <A>->a*,a. Zar ne bi trebalo da ove
> konfiguracije budu <A>->*a,{a,-|} i <A>->a*, {a,-|}?
>
> 2. Ako su ove konfiguracije koje sam naveo na kraju 1. tacne tj. sadrze
> -|, kako se onda odredjuje da li se u kontrolnoj tabeli za stanje ax i
> kolonu -| pise REDUCE(3) (na osnovu <S>->a*,-|)ili REDUCE(4) (na osnovu
> <A>->a*, {a,-|}?
>
> 3. Kako se u ovom zadatku doslo do toga da je ACCEPT u vrsti -|0 i
> koloni -|, tj. kako se uopste doslo do toga da je ovde REDUCE(0), posto
> je za stanje -|0 konf. <S'>-><S>-|*, {epsilon} , a ne
> <S'>-><S>-|*, {-|}?
>
> Hvala unapred na pomoci.
>
> Rade
>
> -----------------------------------------------------------------
> unsubscribe:
>    minimalist@titan.etf.bg.ac.yu?subject=unsubscribe%20ri4pp
> -----------------------------------------------------------------
>
>