Parser
Z Wikipedii
Spis treści |
[edytuj] Definicja
Parser (inaczej analizator składniowy) w informatyce program dokonujący analizy danych wejściowych w celu określenia ich gramatycznej struktury w związku z formalną gramatyką. Nazwa analizator składniowy podkreśla analogię zastosowania programu do analizy stosowanej w gramatyce i lingwistyce. Dzięki temu procesowi komputery są w stanie przetworzyć czytelny dla człowieka tekst w strukturę danych przydatną do dalszej obróbki.
Parsery wielu języków programowania bazują na gramatykach typu LALR. Najczęściej stosowane są własne standardy notacji oparte o BNF.
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.
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.
[edytuj] Przykłady parserów
[edytuj] Parsery zstępujące (top-down)
Niektóre parsery używające parsowania zstępującego:
- Rekurencyjny analizator syntaktyczny
- Parser LL (Left-to-right, Leftmost derivation)
- X-SAIGA - eXecutable SpecificAtIons of GrAmmars. Zawiera publikacje dotyczące algorytmów parsowania zstępującego.
[edytuj] Parsery wstepujące (bottom-up)
Niektóre parsery używające parsowania wstepującego:
- Parsery oparte na pierwszeństwie
- Parsowanie BC (bounded context)
- Parser LR (Left-to-right, Rightmost derivation)
- Parser SLR
- Parser LALR
- Kanoniczny parser LR
- Parser GLR
- Parser CYK
