Parsowanie

Parsowanie to proces analizy danych wejściowych w celu zrozumienia ich struktury i znaczenia na podstawie określonej gramatyki. W informatyce parsowanie najczęściej polega na przetworzeniu ciągu znaków na reprezentację zrozumiałą dla programu, na przykład na drzewo syntaktyczne lub abstrakcyjne drzewo składniowe (AST). W przetwarzaniu języka naturalnego parsowanie służy do identyfikowania struktur gramatycznych i zależności między wyrazami.

Nazwa parsowanie pochodzi od angielskiego parse; w polskim używa się formy parsowanie, odnoszącej się do procesu analizy składniowej. W praktyce termin ten obejmuje zarówno rozpoznawanie składniowe, jak i semantyczne integralności analizowanego tekstu, zależnie od kontekstu.

Zastosowania parsowania obejmują m.in. kompilatory i interpretery programów, narzędzia do przetwarzania języka naturalnego (NLU/NLP), a także obsługę formatów danych takich jak JSON, XML czy YAML. W tych ostatnich przypadkach parsowanie prowadzi do strukturalnej reprezentacji danych, którą można łatwo przetwarzać programowo. W przetwarzaniu strumieniowym często stosuje się specjalne parsery, które analizują dane na bieżąco bez konieczności ładowania całego dokumentu do pamięci.

Proces parsowania składa się z kilku kroków. Najpierw odbywa się tokenizacja (skanowanie) wejścia na podstawowe jednostki zwane tokenami. Następnie następuje analiza składniowa, która na podstawie gramatyki generuje drzewo parse lub AST. Gramatyki używane w praktyce często są kontekstowo bezkontekstowe (CFG), a stosowane algorytmy to m.in. top-down LL oraz bottom-up LR (w tym LALR, LR(1)).

Wyzwania obejmują niejednoznaczność gramatyk, błędy składniowe oraz ograniczenia związane z złożonością obliczeniową i deterministycznością parsowania.