Analizator sterowany składnią
Diagram składni stanowi schemat blokowy programu dokonującego rozbioru zdań i akceptującego zdania poprawne, który nazywany jest analizatorem składniowym. Jego celem jest sprawdzanie poprawności składni programu i generowanie komunikatów o ewentualnych błędach. Konstrukcja analizatora składniowego polega na zastępowaniu kolejnych fragmentów diagramu składni odpowiednimi instrukcjami według odpowiednich reguł. Budujemy w ten sposób program analizatora dla konkretnego języka. Można jednak stworzyć ogólny program rozbioru odpowiedni dla każdej gramatyki. Jest to analizator składniowy sterowny składnią. Aby tego dokonać, w pierwszej kolejności należy przejść od konkretnej gramatyki, reprezentowanej za pomocą diagramów składni, do struktury danych dynamicznych. Polega to na wprowadzeniu dla każdego symbolu jednego węzła struktury i powiązaniu tych węzłów za pomocą wskaźników.
Rekord realizujący węzeł struktury możemy przedstawić graficznie w następujący sposób:
A jego definicja w pseudokodzie Pascala ma postać:
type wskaźnik = ↑ węzeł;
węzeł =
rekord nast, człalt: wskaźnik;
case końcowy: boolean of
true: ( ksym: char );
false: ( psym: poczwsk )
end
Należy także zdefiniować węzeł początkowy, który graficznie możemy przedstawić w następujący sposób:
Aby przejść od diagramu składni do struktury danych, stosujemy następujące reguły:
W miarę możliwości zredukować liczbę diagramów, stosując odpowiednie podstawienia.
Każdy diagram należy zastąpić odpowiednią strukturą danych zgodnie z dalszymi regułami.
Ciąg elementów przedstawionych poniżej:
Zastępujemy listą węzłów danych:
Połączenie członów alternatywy:
zastępujemy poprzez listę alternatywną:
Pętlę:
Zastępujemy następującą strukturą danych:
Rozważmy przykładowy diagram składni pokazany na poniższym rysunku:
Struktura danych dynamicznych będzie wyglądała następująco:
Ponieważ komputer nie jest w stanie czytać diagramów, dlatego należy wczytać gramatykę do programu w trybie tekstowym, np. w notacji RBNF, która jest rozszerzeniem notacji BNF.
Podstawowe różnice pomiędzy notacjami przedstawia poniższa tabela:
| : : = | = |
| | | , |
| { | [ |
| } | ] |
Każda produkcja w notacji RBNF zakończona jest kropką.
Program analizatora wczytuje produkcje w notacji RBNF i na ich podstawie tworzy odpowiadające im struktury danych dynamicznych, zgodnie z gramatyką definiującą produkcje składniowe:
< produkcja > : : = < symbol > = < wyrażenie >
< wyrażenie > : : = < składnik > {,< składnik >}
< składnik > : : = < czynnik {< czynnik >}
< czynnik > : : = < symbol > | [< składnik >]
Sposób zastąpienia odpowiednich procedur produkcji w notacji RBNF strukturami danych dynamicznych pokazano na poniższych rysunkach:
Czynniki:
1. <symbol>
2. [<składnik>]
Składniki:
< czynnik - 1 > ... < czynnik - n >
Wyrażenia:
< składnik - 1 > < składnik - 2 > ... < składnik - n >
Analiza składniowa sterowana strukturą danych dynamicznych jest uniwersalna i może być stosowana dla wielu języków formalnych, dla których zdefinowana jest gramatyka formalna w notacji RBNF.