Analizator składniowy

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

Analizator składniowy, parser – program 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].

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

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

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:

• Parsery oparte na pierwszeństwie
  • Operator-precedence parser
  • Metoda prostego pierwszeństwa (ang.) simple precedence parser
• Metoda ograniczonego kontekstu (ang.) bounded-context parsing
• Parser LR (Left-to-right, Rightmost derivation)
  • Parser SLR
  • Parser LALR
  • Kanoniczny parser LR
  • Parser GLR
• Parser CYK

Przypisy

Bibliografia

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