Razlika između inačica stranice »Pojednostavljenje gramatike«
(Bot: Automatski unos stranica) |
m (bnz) |
||
Redak 1: | Redak 1: | ||
Pojednostavljenje [[formalna gramatika|gramatike]]''' je skupni naziv za postupke odbacivanja beskorisnih [[završni i nezavršni znakovi|znakova]] i produkcija, odnosno za postupke transformacije zapisa gramatike u neki oblik pogodniji za obradu. Za danu formalnu gramatiku gradimo istovjetnu gramatiku (tj. gramatiku koja generira isti jezik) bez zalihosnih znakova i produkcija. | |||
== Odbacivanje znakova == | == Odbacivanje znakova == |
Trenutačna izmjena od 21:09, 23. ožujka 2022.
Pojednostavljenje gramatike je skupni naziv za postupke odbacivanja beskorisnih znakova i produkcija, odnosno za postupke transformacije zapisa gramatike u neki oblik pogodniji za obradu. Za danu formalnu gramatiku gradimo istovjetnu gramatiku (tj. gramatiku koja generira isti jezik) bez zalihosnih znakova i produkcija.
Odbacivanje znakova
Ako se znak X gramatike [math]\displaystyle{ G = (V,T,P,S) }[/math] koristi u postupku generiranja [math]\displaystyle{ S \Rightarrow \alpha X\beta \Rightarrow w }[/math], gdje su [math]\displaystyle{ \alpha ,\beta \in (V \cup T)* }[/math] i [math]\displaystyle{ w \in T* }[/math], onda je znak x koristan. U suprotnom, znak je beskoristan.
Dva su vida beskorisnosti: znak može biti mrtav ili nedohvatljiv, Ako iz znaka X nije moguće generirati niz završnih znakova, tj. ne postoji postupak generiranja [math]\displaystyle{ X \Rightarrow w_X }[/math], gdje je [math]\displaystyle{ w_X \in T* }[/math], tada je znak X mrtav. Nije li znak mrtav, kaže se da je živ. Ako se znak X ne nalazi ni u jednom nizu koji se generira iz početnog nezavršnog znaka, tj. ne postoji postupak generiranja [math]\displaystyle{ S \Rightarrow \alpha X\beta }[/math], tada je znak X nedohvatljiv.
Odbacivanje mrtvih znakova
Neka dana kontekstno neovisna gramatika [math]\displaystyle{ G = (V,T,P,S) }[/math] generira neprazni jezik, tj. [math]\displaystyle{ L(G) \ne \emptyset }[/math]. Moguće je izgraditi istovjetnu gramatiku [math]\displaystyle{ G' = (V',T',P',S) }[/math] koja nema mrtvih znakova, odnosno za bilo koji [math]\displaystyle{ A \in V' }[/math] vrijedi [math]\displaystyle{ A \Rightarrow w,w \in T* }[/math].
Algoritam traženja živih znakova zasniva se na sljedećem svojstvu: Ako su živi svi znakovi [math]\displaystyle{ X_1 ,X_2 ,...,X_n }[/math] desne strane produkcije
- [math]\displaystyle{ A \to X_1 X_2 ...X_n }[/math]
onda je živ i nezavršni znak A lijeve strane produkcije.
Algoritam traženja živih znakova izvodi se u tri koraka:
- U listu živih znakova stave se lijeve strane produkcija koje na desnoj strani nemaju nezavršnih znakova.
- Ako su na desnoj strani produkcije isključivo živi znakovi, onda se nezavršni znak lijeve strane produkcije doda u listu živih znakova.
- Ako nije moguće proširiti listu živih znakova, algoritam se zaustavlja. Svi znakovi koji nisu u listi živih znakova su mrtvi znakovi.
Pseudokod opisanog algoritma jest sljedeći:
StaraListaŽivih = [math]\displaystyle{ \emptyset }[/math]; NovaListaŽivih = [math]\displaystyle{ \left\{ {A|A \to w} ,\mathrm{i\ }w \in T* \right\} }[/math];
dok (StaraListaŽivih [math]\displaystyle{ \ne }[/math] NovaListaŽivih) { StaraListaŽivih = NovaListaŽivih; NovaListaŽivih = NovaListaŽivih [math]\displaystyle{ \cup \left\{ {A|A \to \alpha ,\alpha \in (T \cup StaraListaZivih)*} \right\} }[/math]; }
ListaŽivih = NovaListaŽivih;
Odbacivanje nedohvatljivih znakova
Moguće je izraditi gramatiku [math]\displaystyle{ G' = (V',T',P',S) }[/math] koja je istovjetna kontekstno neovisnoj gramatici [math]\displaystyle{ G = (V,T,P,S) }[/math] i koja nema nedohvatljivih znakova, tj. za bilo koji [math]\displaystyle{ X \in V' \cup T' }[/math] vrijedi [math]\displaystyle{ S \Rightarrow \alpha X\beta }[/math], gdje je [math]\displaystyle{ \alpha ,\beta \in (V' \cup T')* }[/math].
Algoritam traženja dohvatljivih znakova zasniva se na sljedećem svojstvu:
Ako je dohvatljiv nezavršni znak A lijeve strane produkcije:
- [math]\displaystyle{ A \to \alpha _1 |\alpha _2 |...|\alpha _n }[/math]
tada su dohvatljivi svi završni i nezavršni znakovi u nizovima [math]\displaystyle{ \alpha _1 }[/math], [math]\displaystyle{ \alpha _2 }[/math] ... i [math]\displaystyle{ \alpha _n }[/math] desne strane produkcije.
Algoritam traženja dohvatljivih znakova izvodi se u tri koraka:
- U listu dohvatljivih znakova stavi se početni nezavršni znak gramatike.
- Ako je znak lijeve strane produkcije u listi dohvatljivih znakova, onda se svi znakovi desne strane produkcije dodaju u listu dohvatljivih znakova.
- Ako listu dohvatljivih znakova nije moguće proširiti, algoritam se zaustavlja. Svi znakovi koji nisu u listi dohvatljivih znakova su nedohvatljivi.
Pseudokod opisanog algoritma jest sljedeći:
StaraListaDohvatljivih = [math]\displaystyle{ \emptyset }[/math]; NovaListaDohvatljivih = [math]\displaystyle{ \left\{ {S|S} \mathrm{\ je\ pocetni\ nezavrsni\ znak\ } \right\} }[/math];
dok (StaraListaDohvatljivih [math]\displaystyle{ \ne }[/math] NovaListaNedohvatljivih) { StaraListaDohvatljivih = NovaListaDohvatljivih; NovaListaDohvatljivih = StaraListaDohvatljivih [math]\displaystyle{ \cup \left\{ {X|X \mathrm{\ je\ u\ nizu\ }\alpha _i ,A \to \alpha _i \wedge A \in StaraListaDohvatljivih} \right\} }[/math]; }
ListaDohvatljivih = NovaListaDohvatljivih;
Odbacivanje beskorisnih znakova
Primjenom algoritma odbacivanja mrtvih znakova, a potom algoritma odbacivanja nedohvatljivih znakova, iz gramatike se odbacuju svi beskorisni znakovi. Primjena algoritma obrnutim redoslijedom neće nužno odbaciti sve beskorisne znakove, s obzirom da tad neki znakovi mogu ostati dohvatljivi primjenom mrtvih znakova.
Odbacivanje produkcija
Produkcije oblika [math]\displaystyle{ A \to B }[/math] su jedinične produkcije. Sve ostale produkcije, uključujući i produkcije oblika [math]\displaystyle{ A \to a }[/math] i [math]\displaystyle{ A \to \epsilon }[/math], nazivaju se nejedinične produkcije.
Produkcije oblika [math]\displaystyle{ A \to \epsilon }[/math] nazivaju se [math]\displaystyle{ \epsilon }[/math]-produkcije. Njihovo korištenje je moguće izbjeći ukoliko prazni niz nije element jezika kojeg gramatika generira.
Odbacivanje [math]\displaystyle{ \epsilon }[/math]-produkcija
Neka gramatika [math]\displaystyle{ G = (V,T,P,S) }[/math] generira kontekstno neovisni jezik [math]\displaystyle{ L(G) - \left\{ \varepsilon \right\} }[/math]. Tada je moguće izgraditi istovjetnu gramatiku [math]\displaystyle{ G' = (V',T',P',S) }[/math] koja nema [math]\displaystyle{ \epsilon }[/math]-produkcija.
Algoritam odbacivanja [math]\displaystyle{ \epsilon }[/math]-produkcija se izvodi u dva osnovna koraka:
- Pronađu se svi nezavršni znakovi koji generiraju prazni niz. Prazni znakovi su oni znakovi za koje vrijedi [math]\displaystyle{ A \Rightarrow \epsilon }[/math]. Prazni se znakovi traže sljedećim iterativnim algoritmom:
- U listu prazni znakova se stave lijeve strane svih [math]\displaystyle{ \epsilon }[/math]-produkcija.
- Ako su svi znakovi desne strane neke od produkcija zapisani u listu praznih znakova, tada se lista praznih znakova nadopuni lijevom stranom te produkcije.
- Ako više nije moguće proširiti listu praznih znakova, algoritam se zaustavlja.
- Skup produkcija gramatike [math]\displaystyle{ G' }[/math] se gradi na sljedeći način. Ako je:
[math]\displaystyle{ A \to X_1 X_2 ...X_n }[/math]
produkcija gramatike G, tada se u skup produkcija gramatike [math]\displaystyle{ G' }[/math] dodaju produkcije oblika:
[math]\displaystyle{ A \to \xi _1 \xi _2 ...\xi _n }[/math]
Oznake [math]\displaystyle{ \xi _i }[/math] poprimaju sljedeće vrijednosti:
a) Ako znak [math]\displaystyle{ X_i }[/math] nije prazni znak, onda je oznaka [math]\displaystyle{ \xi _i }[/math] jednaka [math]\displaystyle{ X_i }[/math].
b) Ako je znak [math]\displaystyle{ X_i }[/math] prazni znak, onda je oznaka [math]\displaystyle{ \xi _i }[/math] jednaka [math]\displaystyle{ \epsilon }[/math] ili [math]\displaystyle{ X_i }[/math].
Produkcije se grade na temelju svih mogućih kombinacija oznaka [math]\displaystyle{ \xi _1 \xi _2 ...\xi _n }[/math]. Ako sve oznake [math]\displaystyle{ \xi _i }[/math] poprime vrijednost [math]\displaystyle{ \epsilon }[/math], tada nastaje [math]\displaystyle{ \epsilon }[/math]-produkcija i ona se ne dodaje u skup produkcija gramatike [math]\displaystyle{ G' }[/math]. Time se odbace sve [math]\displaystyle{ \epsilon }[/math]-produkcije iz zadane gramatike G.
Općenito će ovim algoritmom, ukoliko produkcija na desnoj strani ima k praznih znakova, biti potrebno izgraditi najviše [math]\displaystyle{ 2^k }[/math] novih produkcija. Ako je na desnoj strani barem jedan znak koji nije prazan, tada je potrebno dodati točno [math]\displaystyle{ 2^k }[/math] novih produkcija. Ako su na desnoj strani svi znakovi prazni, tada je potrebno dodati [math]\displaystyle{ 2^k - 1 }[/math] novih produkcija (produkcija [math]\displaystyle{ A \to \epsilon\epsilon...\epsilon }[/math] se ne dodaje u skup produkcija).
Odbacivanje jediničnih produkcija
Neka gramatika [math]\displaystyle{ G = (V,T,P,S) }[/math] generira kontekstno neovisni jezik [math]\displaystyle{ L(G)\backslash \left\{ \varepsilon \right\} }[/math]. Moguće je izgraditi istovjetnu gramatiku [math]\displaystyle{ G' = (V',T',P',S) }[/math] koja nema jediničnih produkcija oblika [math]\displaystyle{ A \to B }[/math].
Istovjetna gramatika [math]\displaystyle{ G' }[/math] koja nema jediničnih produkcija gradi se na sljedeći način:
- U skup produkcija gramatike [math]\displaystyle{ G' }[/math] stave se sve produkcije gramatike G koje nisu jedinične.
- Neka se postupkom generiranja iz nezavršnog znaka A dobije nezavršni znak B, tj. [math]\displaystyle{ A \Rightarrow B }[/math], gdje su A i B nezavršni znakovi gramatike G. Za sve produkcije [math]\displaystyle{ B \to \alpha }[/math] koje nisu jedinične grade se nove produkcije [math]\displaystyle{ A \to \alpha }[/math].