Analizator składniowy

Analizator składniowy, parserprogram komputerowy 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].

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

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

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 bison stworzony przez Free Software Foundation. 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

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

Bibliografia

edytuj
  • 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.