Gramatyka regularna

Gramatyka regularnagramatyka formalna, za pomocą której można opisać język regularny.

Istnieją dwa rodzaje gramatyk regularnych: gramatyka lewostronna, gramatyka prawostronna. Istnieje ścisły związek gramatyki lewostronnej oraz deterministycznego automatu skończonego, taki że gramatyka generuje dokładnie taki język jaki akceptuje automat. Stąd gramatyki lewostronne generują dokładnie wszystkie języki regularne.

Gramatyka regularna to albo prawo albo lewostronna.

Ważne ograniczenia postaci regułEdytuj

  • Po lewej stronie występuje zawsze dokładnie jeden symbol nieterminalny (tak samo jak w gramatykach bezkontekstowych)
  • Po prawej stronie występuje nie więcej niż jeden symbol nieterminalny i dowolny łańcuch symboli terminalnych. W gramatykach prawostronnie regularnych symbol terminalny występuje przed nieterminalnym (jeśli ten się tam znajduje), a w lewostronnie regularnych na odwrót[1].

PrzykładyEdytuj

poprawne regułyEdytuj

 
 
 
 
 
 
  (reguła z gramatyki lewostronnie regularnej)

reguły niepoprawneEdytuj

  (dwa symbole nieterminalne z lewej strony)
  (dwa symbole nieterminalne z prawej strony)

Przykład gramatykiEdytuj

Jako przykład z zakresu języków programowania może posłużyć gramatyka opisująca ciągi znaków będące zapisem liczb zmiennoprzecinkowych. Poniżej przedstawiono gramatykę G ze zbiorem reguł N = {S,A,B,C,D,E,F} i alfabetem Σ = {0,1,2,3,4,5,6,7,8,9,+,-,.,e}. Symbol S jest symbolem startowym, zaś przez ε oznaczamy ciąg pusty.

S → +A       A → 0A       B → 0C       C → 0C       D → +E       E → 0F       F → 0F
S → -A A → 1A B → 1C C → 1C D → -E E → 1F F → 1F
S → A A → 2A B → 2C C → 2C D → E E → 2F F → 2F
A → 3A B → 3C C → 3C E → 3F F → 3F
A → 4A B → 4C C → 4C E → 4F F → 4F
A → 5A B → 5C C → 5C E → 5F F → 5F
A → 6A B → 6C C → 6C E → 6F F → 6F
A → 7A B → 7C C → 7C E → 7F F → 7F
A → 8A B → 8C C → 8C E → 8F F → 8F
A → 9A B → 9C C → 9C E → 9F F → 9F
A →.B C → eD F → ε
A → B C → ε

Łączenie gramatykEdytuj

Za pomocą łączenia prawo i lewostronnych gramatyk można tworzyć języki, które niekoniecznie będą regularne, z definicji jednak, tego typu gramatyki nie będą już regularne.

Zaostrzanie zasad tworzenia regułEdytuj

Reguły te można zaostrzyć bez straty mocy, pozwalając na co najwyżej jeden symbol terminalny z prawej strony. Wprowadza się w tym celu kilka stanów pomocniczych   i każdą regułę postaci:

 

Można przepisać do zestawu reguł:

 
 
 
 
 

Analogicznie przepisuje się reguły postaci:

 

Drugim często nakładanym ograniczeniem jest zabranianie reguł które zmieniają stan bez czytania żadnych symboli:

 

Algorytm pozbywania się ich jest następujący:

  • Wybieramy jedną regułę postaci   której nie oznaczyliśmy jeszcze jako zbędnej
  • Dla każdej reguły postaci   dodajemy do zbioru reguł regułę postaci   chyba że taka już istnieje
  • Jeśli B było akceptujące, A natomiast nie było, zaznaczamy A jako akceptujące
  • Zaznaczamy wybraną regułę jako zbędną – każde słowo w którego wyprowadzeniu były użyte reguły   możemy teraz wyprowadzić samym   Jeśli natomiast wyprowadzenie słowa kończyło się   gdzie B było akceptujące, możemy to wyprowadzenie zakończyć na   które teraz również jest akceptujące.
  • Jeśli wszystkie reguły postaci   są zaznaczone jako zbędne, usuwamy je i kończymy. Jeśli nie, wykonujemy kolejną iterację.

Zostają wtedy jedynie reguły postaci:

 
 
 

Z takich reguł bardzo łatwo już przejść do niedeterministycznego automatu skończonego.

Łagodzenie zasad budowania regułEdytuj

Można też pozwolić na łagodniejsze reguły – kierując się w stronę wyrażeń regularnych. Bez zmiany mocy gramatyk regularnych wolno dodać alternatywę, przy czym na symbole nieterminalne po prawej stronie nakłada się ograniczenie, że muszą one się znajdować na końcu dowolnej ścieżki wyboru alternatyw, np.:

 

Przejście do tradycyjnych gramatyk regularnych dokonuje się rozbijając każdą alternatywę na parę regułek, aż pozbędziemy się ostatniej:

 
 
 
 

Można też dodać gwiazdkę, oznaczającą powtórzenie fragmentu dowolnie wiele razy, o ile wewnątrz niej znajdują się tylko symbole terminalne, np.:

 

Każdej gwiazdki pozbywa się wprowadzając nieterminalnych symbol pomocniczy   i dla regułki postaci   tworzymy regułki:

 
 
 

Na przykład:

 
 
 
 
 
 

Używając (z podanymi wyżej ograniczeniami) gwiazdki i alternatywy możemy mieszać gramatyki regularne i wyrażenia regularne. Można też dla każdej gramatyki regularnej zbudować odpowiadające jej wyrażenie regularne. Konstrukcja jest następująca:

  • Przepisujemy gramatykę z użyciem alternatywy, tak żeby dla każdego symbolu nieterminalnego o regułkach       pozostała tylko jedna regułka  
  • Wybieramy jeden symbol nieterminalny, oprócz symbolu startowego:
    • Jeśli w jego definicji znajduje się odwołanie do niego samego, przestawiamy te alternatywy do postaci   i zamieniamy jego definicję na  
    • Skoro w definicji A nie ma już żadnych odwołań do samego siebie, podstawiamy definicję A w miejsce wszystkich wystąpień A w innych regułkach. Otrzymujemy w ten sposób układ zawierający o jeden symbol mniej.
  • Na końcu zostaje nam tylko symbol startowy. Jeśli zawiera odwołanie do samego siebie, musimy go przekształcić zgodnie z tą samą procedurą.
  • Gramatyka jest postaci  

Na przykład weźmy gramatykę słów nad alfabetem   nie zawierających podciągu   Gramatyka taka może mieć postać:

  – jak dotąd   nie wystąpiło
  – jak dotąd   nie wystąpiło, podejrzany prefiks to  
  – jak dotąd   nie wystąpiło, podejrzany prefiks to  
  – jak dotąd   nie wystąpiło, podejrzany prefiks to  
  – jak dotąd   nie wystąpiło, podejrzany prefiks to  
  – jak dotąd   nie wystąpiło
  – jak dotąd   nie wystąpiło, podejrzany prefiks to  
  – możemy skończyć jeśli nie ma podejrzanego prefiksu
  – możemy skończyć jeśli podejrzany prefiks to  
  – możemy skończyć jeśli podejrzany prefiks to  
  – możemy skończyć jeśli podejrzany prefiks to  

Można ją przepisać do układu równań gramatycznych:

 
 
 
 

Łatwo można się pozbyć  

 
 
 

I  

 
 

  musiby sprowadzić do wygodnej postaci:

 

I pozbyć się odniesienia do siebie samego:

 

Możemy teraz podstawić do  

 

Teraz już tylko grupujemy samo-odniesienia:

 

I usuwamy je:

 

W ten sposób mechanicznie stworzyliśmy wyrażenie regularne, którego ręczne zbudowanie byłoby znacznie trudniejsze.

PrzypisyEdytuj

  1. {title}, kompilatory.agh.edu.pl [dostęp 2017-11-23].