Už jsem zde stručně představil unifikační gramatiky. Také jsem uvedl, že algoritmus pro parsing podle takové gramatiky je NP-úplný (tj. v nejhorším případě zřejmě exponenciální). Typická unifikační gramatika má generativní sílu větší než bezkontextové gramatiky a dokonce větší než mírně kontextové (angl. mildly context-sensitive), tzn. že délka slova při aplikaci pravidel roste více než lineárně (např. exponenciálně).
Vzhledem k velké výpočetní i prostorové složitosti algoritmu se používá pro parsing dynamické programování. Speciální datová struktura chart reprezentuje dílčí zpracované podřetězce, čímž výrazně zvyšuje rychlost parsingu (omezením backtrackingu, algoritmus ovšem i nadále zůstane exponenciální).
Chart parsing je typu bottom-up, takže nemá problém s levou rekurzí a v případě zkracujících pravidel vždy skončí (takové gramatiky ovšem nejsou v praxi běžné). Časová náročnost algoritmu není u reálných gramatik až tak strašná, vzhledem k používání dalších omezujících podmínek (subkategorizace) je parsing většinou polynomiální. Spolehnout se na to ale nelze.
Koho problematika zajímá, snadno na internetu najde články k tématu např. od Hanse Uszkoreita.
