Drzewa wywodu
Historię wyprowadzeń słowa w danej gramatyce możemy zapisać za pomocą
drzewa wywodu. Korzeniem w tym drzewie jest aksjomat gramatyki, a jeśli została do symbolu pomocniczego \( X \), który jest węzłem w drzewie, zastosowana produkcja \( X::=x_1,\ldots,x_n \), to synami węzła \( X \) stają się elementy \( x_1,\ldots,x_n \). Oto przykład wyprowadzenia słowa abba w gramatyce \( G_2 \).
\begin{Rysunek}[rys1-abba] \end{Rysunek} </p>
Moglibyśmy to wyprowadzenie przedstawić w wersji liniowej
\( S arrow aSa arrow abSba arrow abba \),
jednak drzewo wywodu daje nam dokładnie taką informację, o jaką nam chodzi, zamazując niepotrzebne szczegóły. Przyjrzyjmy się bliżej różnicom w reprezentacji historii wywodu. Rozważmy gramatykę
\( G=\langle \{S\},\{a,b\},\{S::= SaS | b\},S \rangle \).
Za pomocą tej gramatyki możemy wygenerować dowolną naprzemienną sekwencję liter \( b \) oraz \( a \) zaczynającą się i kończącą na literę \( b \). Na ile sposobów można otrzymać słowo \( babab \)? W notacji liniowej tych sposobów jest sporo, przykładowo:
\( S arrow SaS arrow SaSaS arrow SaSab arrow baSab arrow babab \).
Albo inaczej
\( S arrow SaS arrow Sab arrow SaSab arrow Sabab arrow babab \).
Ćwiczenie
Na ile sposobów można liniowo zapisać wywód słowa \( babab \)?
Ile jest drzew wywodu tego słowa? Okazuje się, że tylko dwa. Poniżej przykład ilustrujący powstawanie wspomnianych drzew.
animacja
Można gramatykę tak skonstruować, żeby słowo babab, podobnie jak i każde inne generowane przez powyższą gramatykę, miało tylko jedno drzewo wywodu. Oto ta gramatyka:
\( G_3=\langle \{S\},\{a,b\},\{S::=\varepsilon, S::=baS | b\},S \rangle \)
Taka gramatyka ma już tylko jedno drzewo wywodu dla słowa babab. Oto ono:
\begin{Rysunek}[rys3-babab-jedno] \end{Rysunek}
Podobnie każde inne słowo wyprowadzalne z tej gramatyki ma jedno drzewo wywodu.
Powiemy, że gramatyka \( G \) jest jednoznaczna, jeśli każde słowo wyprowadzalne z \( G \) ma tylko jedno drzewo wywodu. Własność jednoznaczności jest niezwykle ważna – będziemy starali się tak zdefiniować język programowania, aby drzewo wywodu każdego programu było jednoznaczne. To pozwoli nam określić semantykę języka programowania jako funkcję obliczaną na podstawie drzewa wywodu.
Powiemy, że gramatyka \( G \) jest zgodna z językiem \( L\in T^* \), jeśli każde słowo wyprowadzalne z \( G \) należy do \( L \). Powiemy, że gramatyka \( G \) jest pełna względem języka \( L \), jeśli wszystkie słowa należące do \( L \) są wyprowadzalne z \( G \). Rzecz jasna każda gramatyka G jest zarówno zgodna, jak i pełna względem swojego języka \( L(G) \).