Hlavní navigace

Turingovsky úplná bezkontextová gramatika

14. 8. 2013 10:45 (aktualizováno) zboj

Sofistikovaná syntaktická analýza si často nevystačí s prostou bezkontextovou gramatikou, proto vznikla její různá rozšíření. Jedním opravdu zajímavým je použití feature logic (FL) doplňující reprezentace v podobě syntaktických stromů.

FL pracuje s termy. Každý term je buď konstanta nebo má tvar ft, kde f je (unární) funkční symbol a t term. Atomické formule mají tvar s≈t, kde s a t jsou termy. Formule se skládají rekurzivně pomocí běžných logických spojek (vystačíme s negací a disjunkcí).

Jak je vidět, je FL speciálním případem logiky prvního řádu. Kromě bežných axiomů navíc platí s≈t → φ≈φ[s/t]. FL je rozhodnutelná a pochopitelně korektní a úplná (tedy T φ ↔ T φ, nicméně modelům FL se zde nevěnuji). V tomto článku se omezíme na formule, jež jsou konjunkcí atomických formulí.

Máme-li bezkontextovou gramatiku, lze každému preterminálu přiřadit formuli v FL a v pravidlech každému neterminálu rovněž. Říkáme, že takováto gramatika přijímá slovo α, pokud jej přijímá ona bezkontextová gramatika sama o sobě a navíc je formule přiřazená počátečnímu symbolu splnitelná.

Takto definovaná gramatika je turingovsky úplná, tj. rozpoznává rekurzivně spočetné jazyky. Při splnění některých vesměs „rozumných“ podmínek rozpoznává rekurzivní jazyky. Uveďme si jednoduchý příklad.

Mějme gramatiku pro analýzu aritmetických výrazů. Preterminál N pro číselné terminály mějmě asociován s formulí fan, kde a je unikátní konstanta (z lexikální analýzy) a n konkrétní číslo ze vstupu. Analýzou řetězce „3“ tedy získáme formuli fa3, již lze přímo interpretovat nebo kompilovat.

Pro operaci sčítání mějme pravidlo E → E Op N, kde Op je neterminál pro operaci, v tomto případě s formulí fb+ (+ je konstanta reprezentující sčítání). Nechť E, Op, N na pravé straně pravidla mají formule s konstantami a, b, c a E na levé straně pravidla nechť má konstantu d. Potom neterminály na pravé straně pravidla budou asociovány s formulemi gda, db a hdc. Například pro výraz „2+3“ přímočaře dostaneme reprezentaci fd+  fgd≈2  fhd≈3, již lze považovat (protože se jedná o splnitelnou formuli) za abstraktní syntaktický strom a dále zpracovat (interpretem či kompilátorem).

Je zřejmé, že strom generovaný bezkontextovou gramatikou reprezentuje konkrétní syntaktický strom, kdežto formule přiřazené uzlům tohoto stromu reprezentují abstraktní syntaktický strom (v obecném případě se pochopitelně nejedná o strom, ale orientovaný acyklický graf).

Že bezkontextová gramatika ve spojení s FL přijímá i jazyky, jež bezkotextové nejsou, se lze snadno přesvědčit konstrukcí pravidel, jež přijímají jazyky {anbncn : nN} nebo {ak : k=2n, nN}.

Sdílet