Syntaktická analýza (někdy též parsing
) je proces, při
němž řetězec (ASCII) znaků převádíme na datovou
strukturu vhodnou k dalšímu programovému zpracování.
Například máme-li program pro aritmetické výpočty
používající datovou strukturu Vyraz:
data Vyraz = Cislo Int | Soucet Vyraz Vyraz | Soucin Vyraz Vyraz
chtěli bychom, syntaktickou analýzou ze vstupu:
7*3+1
odvodit výraz:
Soucet (Soucin (Cislo 7) (Cislo 3)) (Cislo 1)
Syntaktická analýza obecně není jednoduchý problém. Vše záleží na definici toho, co je jazykem vstupních výrazů určených k analýze. Tento jazyk se dá vyjádřit třeba gramatikou. Např. jazyk vstupních výrazů z našeho příkladu by mohl být zadán takto:
V ::= cislo | V + V | V * V
Slovům z gramatiky začínajícím velkým písmenem říkáme neterminály, ostatním terminály, za chvíli uvidíme proč. Zde máme jen jeden neterminál (V) a tři terminály (cislo, + a *). Význam zápisu gramatikou je intuitivní: vstupní výraz musí být možné odvodit pomocí přepisovacích pravidel z tzv. počátečního neterminálu (zde je jasné, že jediný, a tudíž i počatéční je V). Pravidla mají vlevo přepisovaný neterminál, pak oddělovač (zde ::=) a za ním řetězec terminálů a neterminálů, na který je možné původní neterminál přepsat. Ve výše uvedené gramatice jsou ve skutečnosti pravidla tři, avšak ve zkrácené formě, kde levá strana je pro všechny stejná a pravé strany jsou odděleny znaky |.
Řetězec obsahující terminály nebo neterminály se nazývá větná forma.
Obsahuje-li pouze terminály, říká se mu věta a nelze z něj již podle
pravidel gramatiky nic odvodit, proces odvozování tedy vždy větou
končí, cizím slovem terminuje -- proto se užívá výrazu
terminály
.
Zkusme si nyní odvodit podle naší gramatiky výraz
7*3+1. Začneme s počátečním terminálem:
V
Vidíme, že výraz lze rozdělit na 7*3 + 1:
V ⇒ V + V
Úprava levého výrazu dále pokračuje rozdělením na 7 * 3:
V ⇒ V + V ⇒ V * V + V
Nakonec se ve třech krocích přepíší neterminály na terminály. Všimněte si, že pro strukturu výrazu nejsou konkrétní hodnoty čísel v něm důležité, proto máme pro všechna čísla jediný neterminál.
V ⇒ V + V ⇒ V * V + V ⇒ V * V + cislo ⇒ V * cislo + cislo ⇒ cislo * cislo + cislo
Takto jsme ověřili, že vstupní řetězec má správný tvar a měl by určovat
strukturu typu Vyraz.
Budování této struktury ale znamená právě hledání správného
pořadí pravidel k odvození vstupního řetězce z gramatiky.
Schválně si ještě jednou porovnejte
definici datového typu Vyraz a jednořádkový zápis všech
tří pravidel naší gramatiky. Zkuste se zamyslet, jak souvisí
výraz
Soucet (Soucin (Cislo 7) (Cislo 3)) (Cislo 1)
s výše uvedeným odvozením. Označíme-li pravidla po řadě jako c, + a *, pak strom odvození vypadá takto:
a strom reprezentující výraz
Soucet (Soucin (Cislo 7) (Cislo 3)) (Cislo 1)
je tento:
Nyní je již vidět, že pořadí, ve kterém se použijí pravidla gramatiky,
je důležité. Všimněte si, že při odvozování věty 7*3+1
jsme mohli prohodit pořadí použití pravidel +
a *
.
Takové odvození by ovšem odpovídalo výrazu
Soucin (Cislo 7) (Soucet (Cislo 3) (Cislo 1))
který se od původního zřejmě liší. Navíc intuitivní význam prvního
výrazu je (7*3)+1, zatímco druhého 7*(3+1)
a pouze první odpovídá běžnému vnímání priority operátorů
v původním 7*3+1.
Vidíme, že gramatika není jednoznačná, je ji tedy třeba upravit. To se dá zařídit buď výslovným stanovením priority operátorů, nebo elegantněji za užití stejných prostředků jako dosud -- pravidel gramatiky. Například takto:
V ::= V + V | T T ::= cislo | T * T | (V)
Nyní již není možné provést odvození neodpovídající
prioritě operátorů + a *, ale gramatika pořád není jednoznačná.
Například výraz 1+2+3 v ní lze odvodit
způsobem odpovídajícím (1+2)+3 nebo
1+(2+3). Vzhledem k asociativitě operátoru
sčítání je to vzhledem k běžnému významu znaku +
jedno, ale už pro zjednoznačnění odvozování můžeme
gramatiku dále upravit takto:
V ::= V + T | T T ::= T * F | F F ::= cislo | (V)
což odpovídá asociování zleva, tj. odvození výrazu 1+2+3
bude odpovídat (1+2)+3.
Zbývá otázka, jak takové odvozování a vytváření výrazu odpovídajícího stromu odvození automatizovat. Pro určité typy gramatik to je možné, a to docela efektivně, jak uvidíme v následujícím textu a odkazované literatuře. Navíc nám funkcionálním programování nabízí obzvláště intuitivní způsob, jak takové odvozování naprogramovat.
V
učebním textu
k formálům se dozvíte, co jsou to bezkontextové gramatiky.
Intuitivně jsou to gramatiky, ve kterých když můžete
přepsat nějaký neterminál X na větnou formu α, tak
tak můžete učinit nezávisle na okolí X (tj. kontextu).
Dozvíte se také, jak se dá jednoduše syntaktická
analýza CF jazyků (jazyků zadaných bexkontextovými, Context
Free gramatikami) realizovat nedeterministickým
zásobníkovým automatem (a zároveň se tam dozvíte i co
je to zásobníkový automat :) ).
Spíše až v navazujícím kurzu IA006 Vybrané kapitoly z teorie automatů
se pak dozvíte, jakými algoritmy (stále vystavěnými na modelu
zásobníkových automatů, ale deterministických) lze provádět
analýzu gramatik s jednoznačným odvozením (u nejednoznačných
se situace řeší přidáním kritérií pro výběr z možných voleb).
Kromě toho se dozvíte, jak psát gramatiky tak, aby algoritmy
pro jejich odvozování mohly být co nejjednodušší, neboť i mezi
třídou bezkontextových gramatik lze vyčlenit podtřídy gramatik
pro něž známe snazší postup syntaktické analýzy než pro ostatní.
Častý postup totiž je navrhnout gramatiku tak, aby jí rozuměl člověk,
a pak ji prohnat
úpravami tak, aby definovala stále stejný
jazyk, ale přitom šly věty podle ní odvozené lehce algoritmicky
rozeznávat.
Pro jazyky C a C++ bylo generování syntaktických analyzátorů (parserů) bezkontextových gramatik a jejich podtříd zautomatizováno např. v podobě nástojů Yacc a Bison. Pro Haskell je podobným nástrojem Happy. V jeho dokumentaci najdete popis, jak jej používat i s jednoduchými příklady.
Poněkud specifičtějším přístupem pro funkcionální programování je však použití tzv. monadických parserů. Ty umožňují funkcionální popis gramatiky, který se zároveň stane jejím parserem -- kouzlo funkcionálního programování, jemuž podobné byste ve světě imperativního programování těžko hledali. Více se o tom dozvíte v článku Grahama Huttona a Erika Meijera