Syntaktická analýza shora dolů

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 překlad 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[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

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.

Literatura[editovat | editovat zdroj]

  • VAVREČKOVÁ, Šárka. Programování překladačů. Opava : Slezská univerzita, 2008. 218 s. ISBN 978-80-7248-493-5.  

Související články[editovat | editovat zdroj]