V tomto příspěvku naznačím důvod, proč nemůže pro jazyk C existovat LL(k) gramatika pro libovolné konečné k. Příspěvek si asi užijí jen ti, kteří mají určité základy z oblasti teorie formálních jazyků a překladačů, ale do žádných složitých detailů se pouštět nebudu.
Nejdříve pár ujasnění na úvod. Neformálně, LL(k) gramatika je taková gramatika, pro kterou lze vytvořit LL tabulku, která pro každý nonterminál (který bude na vrcholu zásobníku u LL parseru) a k terminálů (tokenů ze vstupu) obsahuje nejvýše jedno pravidlo, které se má aplikovat. Konstantě k se říká lookahead (bez překladu) a znamená počet tokenů, které jsou načteny ze vstupu k tomu, aby se mohl parser rozhodnout, které pravidlo použít. Obvykle se používají LL(1) gramatiky, kdy se rozhodujeme pouze podle jednoho aktuálního tokenu na vstupu (historicky především z důvodu nižší paměťové náročnosti; dnes už existují pokročilejší techniky, kdy lze uvažovat i větší k). Lze dokázat, že třída jazyků definovaná LL(k) gramatikami je vlastní podtřída třídy jazyků definovaná LL(k+1) gramatikami. Ale to jen tak na okraj.
Důvodem je problém známý pod názvem "dangling else" (bez překladu). Obecně jde o to, že k fragmentu kódu
if a if b printf("b") else printf("!b")
je možné vygenerovat dva derivační stromy v závislosti na tom, ke kterému if
příkazu se váže větev else
. Tento problém je v jazyce C řešen tak, že se else
větev váže na poslední otevřený if
. To lze podchytit následující gramatikou:
selection_statement: IF '(' expression ')' statement | IF '(' expression ')' statement ELSE statement ;
Tato gramatika ale není LL(1), protože pro nonterminál selection_statement
a token IF
máme dvě pravidla. Jako řešení by se nabízelo použít vytýkání (factorization), které ale nic nevyřeší, protože výsledná gramatika opět nebude LL(1). K tomu, abychom tento problém vyřešili, by bylo třeba načíst dostatečný počet tokenů ze vstupu, abychom se podle toho mohli rozhodnout, zda bude následovat else
větev či ne a podle toho zvolit pravidlo (neboli zvolit dostatečně velké k). Po krátkém zamyšlení ale přijdete na to, že podmínka a tělo podmíněného příkazu může mít teoreticky neomezenou velikost, takže bychom potřebovali nekonečné k. Tato idea tedy ukazuje důvod, proč pro jazyk C nemůže existovat LL(k) gramatika pro konečné k.
if/else
lze vyřešit hackem do vytvořené LL tabulky, což je ale ryze implementační řešení (naznačení pro zájemce).
Přidat komentář