Zpracování přirozeného jazyka patří k nejsložitějším algoritmickým úlohám. V přirozených jazycích se střetává tendence vyjádřit co nejvíce co nejpřesněji s ekonomickým principem, tedy tendencí slovní vyjádření redukovat (neformálně můžeme mluvit o lenosti). Lidské jazyky jsou proto (narozdíl od formálních) víceznačné na všech úrovních, které jazykověda rozlišuje (tvarosloví, syntax, sémantika), čehož důsledkem jsou problémy s formálním popisem jazyka a jeho strojovým zpracováním.
Když Noam Chomsky představil vědecké obci své formální gramatiky (předtím byla formální jazykověda výrazně strukturální nebo funkcionální), znamenalo to malou revoluci (kromě jazykovědy i v informatice). Chomsky se při popisu jazyka (téměř výlučně angličtiny) zaměřil na gramatiky bezkontextové, byť se záhy ukázalo, že většina jazyků bezkontextová není. Navíc Kenneth Hale ukázal, že mnohé jazyky nejsou konfigurační (včetně jazyků slovanských, tedy i češtiny), a složková (frázová) syntax tak zachycuje pouze slovosled.
Z Chomského generativní gramatiky vyšlo mnoho moderních teorií popisu jazyka. V dalším článku se zaměřím na LFG (Lexical Functional Grammar), v tomto na X'-teorii (čti: X bar theory). Jako českou kuriozitu lze zmínit Funkční generativní popis prof. Sgalla, o tom ale jindy.
X'-teorie vychází z předpokladu, že věty a fráze mají téměř vždy hlavu, tj. element, jenž nějakým způsobem dominuje zbytek fráze. Ve jmenných frázích je touto hlavou podstatné jméno, ve větách sloveso (finitní) apod. Zavádí proto úrovně neterminálů, které označuje znakem ' (proto X'). Maximální projekce neterminálu X se označuje XP (ekvivalent k X'', obvykle je nejvyšší úrovní ta třetí). Bezkontextová pravidla jsou pak omezena na typ
Xn+1 → Xn YP
a
XP → YP Xmax-1
přičemž YP v prvním pravidle se nazývá komplement a v druhém specifikátor (angl. specifier). Projekce kategorie X je pak hlavou pravidla.
Je zřejmé, že se jedná o běžnou bezkontextovou gramatiku s obyčejnými neterminály, jejíž pravidla jsou však pouze specifického typu. Stále se jedná o způsob zápisu jazyků orientovaný na angličtinu, a tedy nevhodný pro nekonfigurační jazyky. O vhodnějším modelu pro mnohem širší spektrum jazyků (a jeho implementaci v C++) přístě.
