W tym rozdziale poznasz różne metody rozbioru gramatycznego w językach formalnych.
Rozbiór zdań
Wszyscy znamy ze szkoły podstawowej pojęcie rozbioru gramatycznego,którego dokonywaliśmy wyznaczając części mowy wchodzące w skład danego wypowiedzenia. Rozbiór stosujemy również w językach sztucznych. Zapiszmy więc formalną definicję:
Jeżeli forma α wyprowadza formę β,to rozbiorem formy β do α nazywamy ciąg numerów produkcji stosowanych w kolejnych krokach aby zredukować formę β do α.
Definicja brzmi dość formalnie,zobaczmy więc jak to wygląda na prostym przykładzie.
Przykład
mamy następującą gramatykę G = <{E},{i,+,*},{E::=E+E|E*E|(E)|i},E>
czyli
alfabet nieterminalny:N ={E}
alfabet terminalny:V ={i,+,*}
zbiór reguł produkcji:P ={E::= E+E|E*E|(E)|i}
symbol początkowy:S = E
Zdanie i+i*i należy do języka L(G) generowanego przez taką gramatykę. Przykładowe wywody dla tego zdania:
E =>E + E =>E + E * E =>i + E * E =>i + i * E =>i + i * iE =>E + E =>E + E * E =>E + E * i =>E + i * i =>i + i * iE =>E * E =>E + E * E =>i + E * E =>i + i * E =>i + i * i
Dla każdego wyprowadzenia istnieje dokładnie jedno drzewo syntaktyczne. Dla wywodów 1 oraz 2 drzewa są identyczne,co oznacza,że te wywody są równoważne:
Dla wywodu 3 możemy stworzyć następujące drzewo syntaktyczne:
Gramatyka ta jest wieloznaczna,ponieważ nie wiemy czy w przypadku formy zdaniowej E + E * E nie wiemy czy najpierw wykonujemy działanie E + E czy E * E (oba te argumenty są równoprawne).
Gramatyka wieloznaczna to gramatyka,której język zawiera przynajmniej jedno zdanie wieloznaczne. Gramatyka nie zawierająca zdania wieloznacznego to gramatyka jednoznaczna.
Zdanie wieloznaczne to zdanie,dla którego istnieje więcej niż jedno drzewo syntaktyczne wyprowadzania takiego zdania.
Cechę jednoznaczności lub wieloznaczności przypisujemy gramatyce,a nie językowi przez nią generowanemu. Często dla danego języka możemy wyprowadzić zarówno gramatykę wieloznaczną,jak i jednoznaczną. Istnieją jednak także języki,dla których zdefiniowanie gramatyki jednoznacznej nie jest możliwe. Nazywamy je językami istotnie wieloznacznymi.
Możemy rozróżnić następujące metody rozbioru gramatycznego:
- metody prawostronne i lewostronne
- metoda generacyjna
- metoda redukcyjna
W metodzie prawostronnej analizujemy symbole z prawej strony. Analogicznie w metodzie lewostronnej analizie poddawane są symbole od lewej strony. Metoda ta jest bardziej naturalna.
Rozbiorem kanonicznym nazywamy rozbiór,który zawsze rozpoczyna się od lewej strony redukowanej formy zdaniowej,tzn. w pierwszej kolejności redukowane są lewostronne symbole formy
Metoda generacyjna
W metodzie generacyjnej rozpoczynamy analizę od wyróżnionego symbolu gramatyki,stosując kolejno odpowiednie produkcje do najbardziej na lewo położonego symbolu nieterminalnego.
Przykład
Mamy gramatykę G postaci G = <N,V,P,S>
N ={N,D}
V ={0,1,2,3,4,5,6,7,8,9}
P ={N ->ND|D,D->0|1|2|3|4|5|6|7|8|9}
S = N
oraz wygenerowane zdanie:35
rozbiór metodą generacyjną:
N =>ND =>DD =>3D =>35
Metoda redukcyjna
W metodzie redukcyjnej z kolei poprzez kolejne redukcje analizowanej na danym etapie formy zdaniowej dochodzimy ostatecznie do symbolu wyróżnionego gramatyki.
rozbiór metodą redukcyjną:
35 <= D5 <=N5 <= ND <= N
Przy rozbiorze metodą generacyjną pojawia się problem,jaką produkcję zastosować spośród wielu produkcji mających po lewej stronie ten sam symbol nieterminalny. Z kolei w przypadku metody redukcyjnej istotne jest wyznaczenie kolejnego argument aktualnej formy zdaniowej i zdecydowanie do jakiego symbolu go zredukować. Istnieją różnorodne metody postępowania:wybór po kolei,albo wybór losowy.
Pytania sprawdzające
Kiedy dwa wyprowadzenia są równoważne?- Czy w gramatyce jednoznacznej mogą występować wypowiedzenia,dla których możemy wygenerować więcej niż jedno drzewo syntaktyczne?
- Czym różni się metoda redukcyjna od metody generacyjnej?
Jeżeli masz wątpliwości,zapoznaj się jeszcze raz z powyższymi informacjami.
