Hlavní navigace

Kategoriální gramatika a sémantika

7. 10. 2013 0:47 zboj

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, λyx.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 φ=λyx.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).

Sdílet

Žádné názory