@9 A. Preterminál je neterminál nad terminálem (není mezi nimi jiný neterminál).
B. Velmi dobrá poznámka. Problém je obecně NP úplný. Praktické použití ovšem většinou má max. složitost O(n^3). Naivní algoritmus opravdu vytvoří všechny syntaktické stromy a potom testuje splnitelnost přiřazené formule. K tomu naštěstí existuje relativně efektivní algoritmus (založený na kongruenčních uzávěrech). V praxi se používá tzv. "interleaved" metoda, jež již během parsingu podle pravidel testuje splnitelnost formulí. Protože proces tvorby formulí je monotonní (jen přidáváme další konjunkce), nesplnitelná formule implikuje nesplnitelnost jakékoliv své nadformule, a tedy není třeba v aktuální větvi derivace pokračovat. V praxi tedy na konci (pokud se dostaneme až k počátečnímu symbolu) máme jen ty stromy, ke kterým existuje alespoň jedna splnitelná formule. Zde je zajímavé, že zatímco jakákoliv bezkontextová gramatika se dá zpracovat pro libovolný vstup v čase O(n^3) (jednoznačné gramatiky v O(n^2)), ve spojení s FL je proces analýzy obecně NP úplný. Nicméně praktické úlohy popisují nanejvýš "mildly context sensitive" jazyky a tedy parsing bývá polynomiální.
ČLÁNKY DO MAILU