Množina FOLLOW

V této části si vysvětlíme význam množiny FOLLOW pro deterministickou syntaktickou analýzu a budeme se věnovat způsobu jejího výpočtu. Množina FOLLOW nám umožní provádět deterministický rozklad jazyků, jejichž gramatiky obsahují $\varepsilon$-přechody tj. mohou obsahovat i prázdné řetězce.

Množina FOLLOW je formálně definována takto:

Definice:
Pro neterminální symbol X v bezkontextové gramatice G=(N,T,P,S) platí:


Hodnotou funkce FOLLOW(X) je množina, která obsahuje všechny terminální symboly, které mohou následovat bezprostředně za symbolem X. V případě, že se neterminál X vyskytne na konci některé větné formy, pak množina FOLLOW(X) obsahuje rovněž prázdný řetězec.
Při deterministické syntaktické analýze jazyků generovaných LL(1) gramatikami se využívají informace o nejbližším symbolu v dosud nepřečtené části vstupního řetězce. To znamená, že podle tohoto výhledu se provádí výběr pravidla gramatiky (tj. který parser v alternativní kompozici má být aplikován). Při něm se obvykle používá nějaká forma rozkladové tabulky, ve které jsou uvedeny potřebné informace.



Subsections

dvorka 2013-12-31