Ještě před objevením frázových gramatik se jazyky popisovaly gramatikou kategoriální (KG), kterou v současné podobě vypracoval začátkem 50. let minulého století Yehoshua Bar-Hillel. Co do generativní síly je základní KG ekvivalentní bezkontextovým gramatikám. Výhoda KG spočívá v její jednoduché rozšiřitelnosti o sémantickou komponentu (což jde sice u bezkontextových gramatik také, ale ne tak elegantně). Umožňují tak zakomponovat sémantickou interpretaci výrazů nějakého formálního jazyka přímo do popisu gramatiky.
K položkám lexikonu v KG se přidávají pro popis sémantiky λ-výrazy. Například:
⟨N, n⟩ ⊲ n (kde n je číslo)
⟨(E\E)/N, λy.λx.div(x,y)⟩ ⊲ /
N a E jsou atomické typy. Jsou-li X a Y typy, X/Y a X\Y jsou (komplexní) typy. Parsing používá jen dvě pravidla (tzv. funkční aplikaci):
X/Y, Y ⊢ X
Y, X\Y ⊢ X
Jednodušší typ se považuje za argument komplexnějšího, což je základem pro „skládání“ λ-výrazů. Například výraz 1/2 se redukuje na kategorii E (je tedy syntakticky správný, jinak řečeno je přijímán gramatikou) a jako sémantickou formu dostaneme φ=λy.λx.div(x,y)(2)(1) (což lze zjednodušit na div(1,2)).
Výhoda KG je zřejmá: zajišťuje nám nejen syntaktickou správnost výrazu, ale také sémantickou interpretaci. Pokud bychom měli výraz 2/0, zjistíme, že je také syntakticky správně utvořen a jeho sémantickou formou je φ=div(2,0). Pokud bychom použili nějakou teorii Σ pro základní aritmetiku, můžeme ověřit, že teorie Σ∪{φ} není splnitelná. Existuje tedy automatická procedura, s jejíž pomocí můžeme zjistit nejen syntaktickou správnost výrazu, ale také jeho sémantickou akceptovatelnost („smysluplnost“) vzhledem k nějaké teorii Σ.
Uvedený případ je pochopitelně triviální, ale k objasnění principu KG stačí. Složitějším praktickým příkladem je například ověření, že proměnná použitá ve výrazu je v daném kontextu deklarovaná (tj. že např. print(x) předchází kupříkladu int x=1234).
