Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Syntaktická analýza

Definice (Syntaktická analýza)

Syntaktická analýza je část překladače, zodpovědná za:

1. rozhodnutí, zda dané slovo (vstup) patří do zpracovávaného jazyka
2. syntaxí řízený překlad
3. stavbu derivačního stromu (nalezení přepisovacích pravidel ze startovacího neterminálu gramatiky na vstupní posloupnost tokenů - terminálů)

Většina programovacích jazyků je bezkontextová, proto je syntaktická analýza představována zásobníkovým automatem. Syntaktická analýza operuje s gramatikou daného jazyka (snaží se o přepis abstraktních neterminálů na terminály - tokeny jazyka).

Definice (Derivační strom)

Derivační strom je grafická reprezentace slova vstupního jazyka, nebo spíše derivací, které bylo potřeba provést, aby se v gramatice startovací symbol přepsal na dané slovo (posloupnost terminálů). Uzly takového grafu jsou neterminály i terminály gramatiky jazyka (v listech ale jsou jen terminály, ve vnitřních uzlech neterminály). Hrany grafu představují přepsání podle pravidla gramatiky - vedou od neterminálu který se přepisuje, ke všem neterminálům nebo terminálům na které se přepisuje (mluvíme o bezkontextových gramatikách, takže na levé straně stojí jen jeden neterminál).

Přepsání v gramatice bohužel nemusí být jednoznačné (tj. pro stejnou posloupnost neterminálů existuje více platných derivačních stromů). Přikladem je problém dangling else z jazyků typu Pascal nebo C - mám-li za sebou 2x `if-then` a pak jedno `else`, nemusí být (z gramatiky) jasné, ke kterému `if-then` ono `else` patří. Takové problémy lze (a je nutné) odstranit převodem na jednoznačnou gramatiku (např. přes další neterminál).

Levá rekurze, levá faktorizace, nebezkontextovost

Levá rekurze v gramatice se objevuje, pokud je v ní neterminál , pro který platí pro nějaké . Tj. přes je možné projít kolikrát chci a vytvořit posloupnost . Pokud parser začíná u startovacího neterminálu a hledá derivace na na terminály shora dolů (to jeden z druhů scannerů dělá), neví jakou hloubku rekurze má použít. Proto je nutné i levou rekurzi, stejně jako nejednoznačnosti, z gramatiky napřed odstranit její úpravou (zde opět pomůže přechod přes nový neterminál).

Problémem je i levá faktorizace - případ, kdy se v gramatice vyskytují pravidla jako a zároveň . I ten je možné řešit úpravou gramatiky (přenos rozhodnutí na pozdější dobu, kdy bude známo, který ze symbolů si vybrat).

Může se také i pro běžné konstrukce z programovacích jazyků stát, že nevyhovují bezkontextovým gramatikám - např. kontrola deklarace identifikátoru před použitím, kontrola počtu parametrů funkce apod. Zde syntaktická analýza bezkontextovým způsobem nestačí a tyto případy je třeba řešit jinak.

Definice (Názvosloví gramatik, FIRST a FOLLOW)

Gramatiky se v teorii překladačů označují dvěma až třemi znaky a číslem v závorce, obecně ve tvaru , kde:

- je směr čtení vstupu (V našem případě vždy , tj. zleva doprava),
- jsou druhy derivace ( – levé, – pravé derivace),
- označuje prefix (ještě jemnější dělení na třídy u některých gramatik) a
- představuje výhled (lookahead), každý parser totiž vidí jen na jeden nebo několik tokenů dopředu a další neuvažuje. Obvykle je to celé číslo, většinou 1, ale také 0 nebo obecně .

Příklady:

Množiny FIRST a FOLLOW představují množinu použitelných neterminálů na urč. místech (začátky řetězců derivovaných z nějakého pravidla, resp. řetězce které mohou následovat po nějakém neterminálu) a používají se pro konstrukci parserových automatů pro nějakou gramatiku.

TODO: formalizovat FIRST a FOLLOW, neni to moc slozite?

Definice (Analýza shora dolů)

Analýza shora dolů je technika parserů, kdy se parser snaží najít nejlevější derivaci pro vstupní řetězec. Pokouší se tedy zkonstruovat derivační strom pro daný vstup počínaje kořenem a přidáváním uzlů do stromu - rozhoduje se, podle kterého pravidla gramatiky přepíše. Pravidlo pro odstranění nejednoznačnosti je provádění jen levých derivací, proto pak automatům vadí levá rekurze a musí se odstraňovat. Techniky pro nalezení přepisovacího pravidla jsou:

- Rekurzivní sestup pomocí procedur - pro každý neterminál existuje jedna procedura, která se rozhodne, které pravidlo použije na základě výhledu. Pro rozhodování se sestavují množiny FIRST a FOLLOW každého neterminálu. Potom musí zkontrolovat, jestli pravá strana tohoto pravidla odpovídá vstupu (přičemž výskyt neterminálu na pravé straně znamená zavolání jemu příslušné procedury).
- Nerekurzivní analýza s predikcí - je implementováno automatem s explicitním zásobníkem: ten má parsovací tabulku, která se liší podle gramatiky (sama práce automatu je vždy stejná) - jsou v ní řádky odpovídající neterminálům a sloupce terminálům, v políčkách jsou přepisovací pravidla nebo chyby. Na zásobník automatu se ukládají symboly gramatiky a ze vstupu se čtou (lineárně terminály). V každém kroku se automat rozhodne podle vstupu a vrcholu zásobníku - je-li tam terminál, vyhodí se a ukazatel vstupu se posune (nebo se skončí); je-li na zásobníku neterminál, rozhoduje se podle tabulky (položka určená vstupem a neterminálem, buďto se použije přepisovací pravidlo nebo skončí chybou). Konstrukce tabulky je opět závislá na množinách FIRST a FOLLOW.

Analýza shora dolů je používána v parserech jednoduchých jazyků ( gramatiky s řešením konfliktů zvětšením výhledu na terminálů) - v generátorech parserů ANTLR a Coco/R, například.

Definice (Analýza zdola nahoru, LR automat)

Parsery s analýzou zdola nahoru se pokoušejí najít pozpátku nejpravější derivaci pro vstupní řetězec - zkonstruovat derivační strom pro daný vstup počínaje listy a stavěním zespodu až po kořen stromu. V jednom redukčním kroku je tak podřetězec odpovídající pravé straně pravidla gramatiky nahrazen neterminálem z levé strany pravidla. Analýza zdola nahoru se používá ve např. v generátoru parserů Bison -– je schopná vytvořit parsery pro gramatiky, které jsou oproti parserům silnější (Třída rozpoznávaných jazyků LR(1) je vlastní nadmnožina LL(1)), všechny běžné programovací jazyky zapsatelné bezkontextovou gramatikou sem patří. Navíc se dá implementovat zhruba stejně efektivně jako metoda shora dolů.

V analýze zdola nahoru se používá nějaký zásobníkový automat (LR automat) čtoucí ze vstupu, parametrizovaný tabulkami ACTION a GOTO. Na zásobníku se pak uchovávají stavy a symboly gramatiky (nebo jen stavy). Vrchol zásobníku představuje aktuální stav. V počáteční konfiguraci je pointer vstupu nastavený na začátek a na zásobníku je počáteční stav. V každém kroku podle stavu a tokenu na vstupu adresuji tabulku ACTION a získám akci k provedení:

- SHIFT - posune vstup o 1 terminál, který přidá na zásobník spolu s novým stavem .
- REDUCE - zruší ze zásobníku tolik dvojic stavů a symbolů, jak dlouhé je , na zásobník dá a stav, který najde v tabulce GOTO na pozici odpovídající neterminálu a aktuálnímu stavu
- ACCEPT - generuje nějaký výstup, slovo je úspěšně rozpoznáno
- ERROR - zahlásí chybu

V LR automatech v klidu projdou i gramatiky s levou rekurzí. Obecně se v nich používají nějaké gramatiky, většinou rozšířené - doplněné o tečky, ukazatele pozice v pravidlech, které pomáhají s rozpoznáním konce vstupu. Ke konstrukci tabulek ACTION a GOTO jsou opět potřeba množiny FIRST a FOLLOW, nyní rozšířené na symbolů.

TODO: přidat popis LR(1) a LALR(1) gramatik?