Syntaktická analýza shora dolů

Technology

12 hours ago

Author

Syntaktická analýza shora dolů je jednou z metod syntaktické analýzy v rámci přirozeného jazyka. Tato metoda se zaměřuje na parseování vět od kořene ke koncovým uzlům. Vzhledem k tomu, že se jedná o deterministický algoritmus, syntaktická analýza shora dolů se používá především pro analýzu bezkontextových jazyků, kde je stromová struktura jednoznačně určená. Metoda začíná analýzou celé věty jako celku a postupuje postupným rozkladem věty na jednotlivé podčásti. Při rozkladu se využívá různých pravidel a algoritmů, které slouží k identifikaci a popisu jednotlivých syntaktických prvků věty. Výsledkem syntaktické analýzy shora dolů je stromová struktura nazývaná syntaktický strom, která reprezentuje vztahy mezi slovy ve větě. Syntaktická analýza shora dolů je jedním z důležitých nástrojů při automatizovaném zpracování přirozeného jazyka, například při tvorbě syntaktických parserů nebo strojovém překladu.

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. +more 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. +more 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í. +more 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. +more 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. +more 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