Méně známé skutečnosti o C a C++: Proč nemůže existovat LL(k) gramatika pro jazyk C

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.

LL gramatiky a parsery

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ůvod

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.

Závěrečné poznámky

• Výše uvedená gramatika je LR(1) (třída jazyků definovaná LR(1) gramatikami je striktně větší než třída obsahující všechny LL(k) jazyky pro libovolné k). LR parsery s tímto problém nemají.
• Ryze technicky (formálně) nemůže pro jazyk C existovat žádná bezkontextová gramatika, protože se jedná o jazyk kontextový (nelze zachytit sémantiku a sémantické kontroly na úrovni bezkontextové gramatiky). Toto se ale v praxi neuvažuje, protože sémantická kontrola je řešena na úrovní parseru.
• Výše zmíněný problém s konstrukcí 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).