Analizator składniowy

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Przykład analizy składniowej (parsingu) wyrażeń matematycznych

Analizator składniowy lub parser – program dokonujący analizy składniowej danych wejściowych w celu określenia ich struktury gramatycznej w związku z określoną gramatyką formalną. Analizator składniowy umożliwia przetworzenie tekstu czytelnego dla człowieka w strukturę danych przydatną dla oprogramowania komputera. Wynikiem analizy składni, dokonywanej przez parser, najczęściej jest drzewo składniowe nazywane czasami drzewem wyprowadzenia[1].

Przed przystąpieniem do analizy składniowej, wymagany jest podział kodu źródłowego na części (tzw. leksemy), którym zajmuje się analizator leksykalny[2]. Nazwa analizator składniowy podkreśla analogię z analizą składniową stosowaną w gramatyce i językoznawstwie. Parsery wielu języków programowania bazują na gramatykach typu LALR. Najczęściej stosowane są własne standardy notacji oparte na notacji BNF. Gdy kod źródłowy nie jest zgodny z gramatyką języka, parser może zasygnalizować błąd składniowy.

Zastosowanie[edytuj | edytuj kod]

Najczęstszym zastosowaniem parserów jest analiza języków programowania. Mają one, zwykle, prostą gramatykę z nielicznymi wyjątkami. Jednakże gramatyki bezkontekstowe mają ograniczone zastosowanie, gdyż mogą one opisać jedynie ograniczony zestaw języków. Analizator składniowy może być także użyty do statycznej analizy programu, formatowania kodu lub jako część edytora tekstu takiego jak Emacs lub zaawansowane IDE jak np. Visual Studio Code[3].

Ręczne pisanie parsera, szczególnie dla dużych języków, jest zajęciem dosyć żmudnym, dlatego powstały generatory parserów. Jednym z popularniejszych generatorów jest yacc, pozwalający na generowanie parserów w języku C. Jego odpowiednikiem rozprowadzanym na zasadach wolnego oprogramowania jest stworzony przez Free Software Foundation bison. Wśród przykładów generatorów parserów dla innych języków jest ocamlyacc dla języka OCaml oraz JavaCC i SableCC dla Javy.

Przykłady parserów[edytuj | edytuj kod]

Przykłady parserów używających analizy zstępującej:

  • Rekurencyjny analizator syntaktyczny
  • Parser LL (Left-to-right, Leftmost derivation)
  • X-SAIGA - eXecutable SpecificAtIons of GrAmmars. Zawiera publikacje dotyczące algorytmów analizy zstępującej.

Przykłady parserów używających analizy wstępującej:

Przypisy[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • J.E. Hopcroft, R. Motwani, J.D. Ullman: Wprowadzenie do Teorii automatów, języków i obliczeń. Warszawa: Wydawnictwo Naukowe PWN, 2005. ISBN 83-01-14502-1.
  • Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman: Kompilatory. Wydawnictwo Naukowe PWN SA, 2002. ISBN 83-204-2656-1.