Analiza składniowa

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

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

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 wielokrotnie są skomplikowane, zawierają rozliczne 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 oraz rozpatrywanego zagadnienia, liczą się też względy obliczeniowe. Pewne systemy analizy używają gramatyk funkcjonalnych, ale generalnie analiza z ich wykorzystaniem jest problemem NP-zupełnym.

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

Algorytmy analizy składniowej dla języków naturalnych nie potrafią opierać się na tak "ładnych" gramatykach jak te zbudowane ręcznie dla języków programowania. Tak, jak było wspomniane wcześniej pewne 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 wielokrotnie bazują na pewnej odmianie algorytmu CYK, zwykle z jakąś heurystyką żeby odrzućić mało prawdopodobne dopasowania, co oszczędza czas. Pewne 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ąstka 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 zwykle są tak projektowane gramatyką bezkontekstową, albowiem bywają wtedy stosowane szybkie oraz efektywne parsery. Gdyż ogólne metody analizy języków bezkontekstowych posiadają złożoność , wielokrotnie 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 umieją sprawdzać takie zasady, jednak wtedy analiza składni nie jest już tak efektywna. Powszechną strategią jest wykonywanie 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 (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ą oraz pośrednią rekursją lewostronną oraz może wymagać wykładniczego czasu oraz przestrzeni przy gramatykach niejednoznacznych, bardziej zaawansowane algorytmy używane do analizy zstępującej, zbudowane przez Frosta, Hafiza oraz Callaghana rozwiązują problem lewostronej rekursji oraz niejednoznaczności w czasie wielomianowym. Ten algorytm może generować zarówno lewe jak oraz 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)

 Osobny artykuł: Analizator składniowy.

Analizator składniowy albo parser to program odpowiedzialny za przeprowadzenie analizy składniowej. Zazwyczaj, jest jedną z części translatora albo interpretera , która sprawdza składnię oraz buduje strukturę danych – wielokrotnie jest to odmiana drzewa składni, drzewa AST albo innej struktury gramatycznej. Parser może pracować na pojedynczych znakach tekstu, lecz wielokrotnie 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 albo analizatorem leksykalnym. Parsery bywają wykonywane 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 oraz 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" oraz 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 składają się na dopuszczalne wyrażenie. To zwykle 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 potrafią zostać wyrażone przy pomocy czystej gramatyki bezkontekstowej, dla przykładu zgodność typów oraz właściwa deklaracja identyfikatorów. Te zasady potrafią zostać formalnie wyrażone za pomocą gramatyki atrybutywnej.

Faza końcowa to analiza semantyczna, która opracowuje znaczenie dopiero co zweryfikowanego wyrażenia oraz 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 bywa także użyta gramatyka atrybutywna.

Bibliografia

• Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Kompilatory : reguły, metody oraz narzędzia. Warszawa: WNT, 2002. ISBN 83-204-2656-1. 

• Seppo Sippu, Eljas Soisalon-Soininen: Parsing Theory. Berlin oraz inne: Springer-Verlag. ISBN 3-540-51732-4.