Analiza składniowa

Przykład analizy składniowej (parsingu) wyrażeń matematycznych

Analiza składniowa (ang. parsing) – proces analizy tekstu, w celu ustalenia jego struktury gramatycznej i zgodności z gramatyką języka. Słowo parsing pochodzi od (łac.) pars (ōrātiōnis), które oznacza część mowy. Analiza składniowa najczęściej poprzedzona jest analizą leksykalną.

Języki naturalne

W systemach analizy języka naturalnego (np. tłumaczenie automatyczne) stosuje się programy komputerowe do rozwiązywania problemów związanych z językami używanymi przez ludzi. Automatyzacja tłumaczenia czy analizy składniowej jest zagadnieniem trudnym ze względu na charakter języków naturalnych – ich reguły często są skomplikowane, zawierają liczne wyjątki, a znaczenie poszczególnych fraz w wielu wypadkach zależy od kontekstu. Wybór gramatyki, która będzie używana dla danego języka, zależy od specyfiki konkretnego języka i rozpatrywanego zagadnienia, liczą się też względy obliczeniowe. Niektóre systemy analizy używają gramatyk funkcjonalnych, ale generalnie analiza z ich wykorzystaniem jest problemem NP-zupełnym.

Większość współczesnych parserów jest przynajmniej częściowo oparta na statystyce. Najpierw analizie statystycznej poddawane korpus języka, co pozwala systemowi zgromadzić informacje o częstości występowania poszczególnych wyrazów i fraz w różnych kontekstach (zobacz: uczenie maszynowe). Wykorzystuje się przy tym metody takie, jak PCFG, badanie entropii oraz sieci neuronowe. Większość wiodących systemów używa statystyk leksykalnych (porównują podobieństwo części mowy i poszczególnych słów). Takie systemy podlegają jednak zjawisku nadmiernego dopasowania i wymagają pewnych korekt.

Algorytmy analizy składniowej dla języków naturalnych nie mogą polegać na tak „ładnych” gramatykach jak te stworzone ręcznie dla języków programowania. Tak, jak było wspomniane wcześniej niektóre gramatyki formalne są bardzo skomplikowane obliczeniowo w parsingu; generalnie, nawet jeśli chciana struktura nie jest bezkontekstowa, jakieś bezkontekstowe przybliżenie jest używane aby wykonać pierwsze dopasowanie. Algorytmy które używają gramatyk bezkontekstowych często bazują na pewnej odmianie algorytmu CYK, zwykle z jakąś heurystyką żeby odrzućić mało prawdopodobne dopasowania, co oszczędza czas. Niektóre systemy rezygnują z dokładności na rzecz szybkości, np. liniowa wersja metody przesunięcie-redukcja.

Języki programowania

Parser jest najczęściej używany jako część kompilatora albo interpretera. Analizuje kod źródłowy programu napisanego w języku programowania, żeby móc przedstawić go w swojej wewnętrznej formie. Języki programowania zazwyczaj są tak projektowane gramatyką bezkontekstową, gdyż mogą być wtedy stosowane szybkie i efektywne parsery. Ponieważ ogólne metody analizy języków bezkontekstowych mają złożoność $O(n^{3}),$ często są to pewne podklasy gramatyk bezkontekstowych (np. LALR).

Przeważnie gramatyką bezkontekstową nie da się wyrazić wszystkich reguł projektowanego języka. Nieformalnie mówiąc, powodem jest to że pamięć takiego języka jest ograniczona. Gramatyka nie może pamiętać obecności konstrukcji dla bardzo długiego wyrażenia; jest to niezbędne dla języków w których np. nazwa (nazwa zmiennej) musi być zadeklarowana zanim się do niej odwoła. Bardziej złożone gramatyki potrafią sprawdzać takie zasady, jednak wtedy analiza składni nie jest już tak efektywna. Powszechną strategią jest tworzenie mniej restrykcyjnych parserów dla gramatyk bezkontekstowych, dopuszczających pewne nieprawidłowe konstrukcje, które są filtrowane w późniejszym etapie (analiza semantyczna).

Metody analizy składniowej

Analiza możne być przeprowadzana różnymi metodami, np.:

	Analiza zstępująca (ang. top-down)	Analiza wstępująca (ang. bottom-up)
Metody niekierunkowe	Parser Ungera	Algorytm CYK
Metody kierunkowe	przeszukiwanie wszerz przeszukiwanie w głąb metoda zejść rekurencyjnych z powrotami LL(k)	Algorytm Earleya Metoda przesunięcie-redukcja Metoda ograniczonego kontekstu BC(k,l) Oparte na pierwszeństwie Metoda pierwszeństwa operatorów Metoda prostego pierwszeństwa Metody LR (kanoniczne) LR(k), – szczególnie istotne LR(0) i LR(1) SLR(k) LALR(k) – bardzo popularna LALR(1) LA(k)LR(l) – pośrednie pomiędzy LR(l) i LALR(k) GLR

Analiza zstępująca (top-down)

Może być postrzegana jako próba znalezienia lewego wyprowadzenia (ang. leftmost derivation) strumienia wejściowego, przez szukanie drzew wyprowadzenia, wykorzystując zstępujące rozwijanie zgodnie z daną gramatyką. Znaki są przeglądane od lewej do prawej strony. Parsery LL oraz rekurencyjnie zstępujące są przykładami parserów top-down, które nie radzą sobie z lewostronnie rekurencyjnymi produkcjami. Chociaż uważa się, że prosta implementacja analizy zstępującej nie radzi sobie z bezpośrednią i pośrednią rekursją lewostronną oraz może wymagać wykładniczego czasu i przestrzeni przy gramatykach niejednoznacznych, bardziej zaawansowane algorytmy używane do analizy zstępującej, stworzone przez Frosta, Hafiza oraz Callaghana rozwiązują problem lewostronej rekursji i niejednoznaczności w czasie wielomianowym. Ten algorytm może generować zarówno lewe, jak i prawe wyprowadzenie.

Analiza wstępująca (bottom-up)

Parser próbuje przepisywać wejście, poprzez zastępowanie znalezionych prawych stron produkcji gramatyki ich lewymi stronami, aż do uzyskania tylko symbolu startowego. Przykładami parserów wstępujących są parsery LR

Analizator składniowy (parser)

Analizator składniowy lub parser to program odpowiedzialny za przeprowadzenie analizy składniowej. Zazwyczaj, jest jedną z części translatora lub interpretera, która sprawdza składnię oraz buduje strukturę danych – często jest to rodzaj drzewa składni, drzewa AST lub innej struktury gramatycznej. Parser może pracować na pojedynczych znakach tekstu, lecz często wygodniej jest pracować na całych słowach (podczas analizy zdania). Do wstępnego podzielenie tekstu na słowa (ang. token) używany jest osobny moduł nazywany lekserem lub analizatorem leksykalnym. Parsery mogą być tworzone ręcznie, lecz częściej są generowane przez generatory parserów (np. Yacc) na podstawie opisu gramatyki.

Przykład

Następujący przykład prezentuje typowy przypadek przeprowadzania analizy składniowej prostego języka wyrażeń arytmetycznych, z dwoma poziomami gramatyki: leksykalnym i składniowym.

Faza pierwsza jest generacją tokenów (analizą leksykalną), w trakcie której strumień wejściowy jest dzielony na znaczące symbole, określone przez gramatykę wyrażeń regularnych. Na przykład program kalkulatora mógłby przetwarzać ciąg znaków taki jak „12*(3+4)^2” i dzielić to na symbole 12, *, (, 3, +, 4, ), ^, 2, gdzie każdy coś oznacza w kontekście wyrażenia arytmetycznego. Lekser mógłby zawierać reguły, które mówiłyby, że znaki *, +, ^, (, ) zaznaczają początek nowego znaku, tak że ciągi bez znaczenia jak „12*” albo „(3” nie byłyby brane pod uwagę.

Następna faza to analiza składni (analiza syntaktyczna), która sprawdza czy symbole tworzą dopuszczalne wyrażenie. To zazwyczaj jest robione w oparciu o gramatykę bezkontekstową, która definiuje rekurencyjnie komponenty tworzące wyrażenie oraz ich kolejność. Jednakże nie wszystkie zasady, definiujące języki programowania mogą zostać wyrażone przy pomocy czystej gramatyki bezkontekstowej, na przykład zgodność typów oraz właściwa deklaracja identyfikatorów. Te zasady mogą zostać formalnie wyrażone za pomocą gramatyki atrybutywnej.

Faza końcowa to analiza semantyczna, która opracowuje znaczenie dopiero co zweryfikowanego wyrażenia i podejmuje odpowiednie działania. W przypadku kalkulatora, zadaniem jest obliczenie wyrażenia. Kompilator mógłby w tym miejscu generować kod wynikowy. Do definiowana tych akcji może być również użyta gramatyka atrybutywna.

Bibliografia

• Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Kompilatory. Reguły, metody i narzędzia. Warszawa: WNT, 2002. ISBN 83-204-2656-1.brak strony w książce
• Seppo Sippu, Eljas Soisalon-Soininen: Parsing Theory. Berlin i inne: Springer-Verlag, 1988. ISBN 0-387-51732-4. ISBN 3-540-51732-4.brak strony w książce