Syntaktická analýza shora dolů
Syntaktická analýza shora dolů je jednou z metod syntaktické analýzy. Syntaktická analýza se snaží zkonstruovat derivační strom pro danou větu (vstup syntaktického analyzátoru, posloupnost symbolů). Metoda shora dolů (Top-Down) se nejprve zabývá nejvyšší úrovní derivačního stromu a postupně prochází derivační strom dolů s využitím formálních pravidel gramatiky. To znamená, že derivační strom věty konstruujeme od kořene (je ohodnocen startovacím symbolem gramatiky) směrem dolů k listům, zleva doprava, podle levé derivace. Syntaktickou analýzu shora dolů používají pro svou práci LL syntaktické analyzátory.
Syntaktickou analýzu shora dolů můžeme také popsat jako hledání levé derivace vstupního řetězce a lze ji realizovat jako metodu „pokusu a omylu“, kdy se snažíme v určitém bodě překladu aplikovat postupně jednotlivá pravidla gramatiky. Když je aplikace určitého pravidla neúspěšná, navrátíme se do bodu, odkud lze pokračovat dál volbou jiné varianty. Tento postup se nazývá „analýza s návraty“. Je pro syntaktickou analýzu (což je pouze část překladu či překladače) programovacích jazyků nevhodný, protože je značně neefektivní, ale naštěstí většina běžných konstrukcí v programovacích jazycích umožňuje přímočarou analýzu bez návratu. Další možností je použití deterministické analýzy, ve které při výběru pravidla využíváme ještě další informace. Například se můžeme dívat dále do vstupní posloupnosti symbolů a řídit se tím, co dostaneme později na vstupu, nebo kontrolovat zásobník (nestačí nám jen symbol, který vyjímáme, ale chceme vidět i ty pod ním). U metody analýzy shora dolů se ve většině případů používá deterministická analýza.
Postup analýzy
- začínáme startovacím symbolem
- pokračujeme podle levé derivace (vždy nejlevějším symbolem)
- pravidla gramatiky: ve stromě z neterminálu tvoříme podřetězec, na který se přepisuje
- strom konstruujeme podle derivace zleva doprava
- vstup čteme zleva doprava
Příklad
Slovo aabbcc odvozené v gramatice s pravidly:
S → AB 1 A → aAb|ab 2, 3 B → cB|c 4, 5
Použijeme levou derivaci:
S ⇒ AB ⇒ aAbB ⇒ aabbB ⇒ aabbcB ⇒ aabbcc
Začínáme startovacím symbolem S (pravidlo 1), kde se na pravé straně vyskytují neterminály AB. Podle levé derivace a přepisovacího pravidla 2 přepíšeme na aAbB. Dále aplikujeme pravidlo 3, přičemž se výstup změní na aabbB a dále pokračujeme s aplikací pravidel až do doby, kdy zbudou jen terminální symboly.
Tento příklad můžeme také popsat pomocí levého rozkladu věty v gramatice, což je posloupnost čísel pravidel použitých v levé derivaci této věty v gramatice. Pro výstupní slovo aabbcc z příkladu vypadá následovně:
Levý rozklad slova aabbcc je posloupnost pravidel 1, 2, 3, 4, 5.
Uvedení levého rozkladu na pravou míru
Je vhodné podotknout, že LL analýza se týká bezkontextových jazyků. Pro regulární jazyky jde o zbytečně komplikované řešení. Pro obecnější jazyky (kontextové a pod.) nemáme derivační strom, ale něco obecnějšího.
Konkurenční způsob je syntaktická analýza zdola nahoru, zvaná taky LR. Ke stromu vydává pravý rozklad pozpátku. Je dobré si uvědomit, že ve skutečnosti z výsledků analýzy, tj. posloupnosti, stavíme derivační strom.
Výstup
Co se týče výstupu, tak nejen příklad uvedený výše se dá popsat pomocí levého rozkladu, ale každá věta z jazyka. Je to standardní způsob výstupu.
Nedeterminismus a programovací jazyky
Je vhodné rozlišit přirozené jazyky a umělé počítačové jazyky. Ve skutečnosti se v přirozených jazycích vyskytují jevy, které nelze popsat bezkontextovou gramatikou. Když se omezíme na bezkontextovou gramatiku, tak se v ní vyskytuje nedeterminismus. Proto potřebujeme při zpracování obecně "pokusy a omyly", jak bylo vzpomenuto výše.
Počítačové jazyky jsou navrženy člověkem a tak je může navrhnout a navrhuje deterministicky. To má kromě rychlejší a jednodušší analýzy tu nezanedbatelnou výhodu, že jedné syntaktické větě (přesněji jejímu stromu) odpovídá jeden sémanticky význam - jinak by stejný program mohl počítat více věcí.
Pro deterministické rozhodování, které pravidlo použít, se používá výhled na k symbolů dopředu, pak se mluví o LL(k) analyzátorech. Při dobrém návrhu jazyka stačí LL(1).
- generování LL analyzátorů
- oprava chyb, v praxi
Literatura
- VAVREČKOVÁ, Šárka. Programování překladačů. Opava: Slezská univerzita, 2008. 218 s. ISBN 978-80-7248-493-5.
