Семинар лаборатории ПОИС: Формальные грамматики после Карибского кризиса

На очередном заседании нашего семинара выступил А.С. Охотин, Университет Турку, Финляндия. Тема его доклада : «Формальные грамматики после Карибского кризиса» («Formal grammars after the Cuban missile crisis»)

Аннотация. Формальные грамматики появились в конце 50-х гг. XX века, когда развитие
вычислительной техники потребовало строго определить синтаксис языков
программирования, а также подало надежду на машинную обработку
естественных языков. К октябрю 1962 г. были в первом приближении
разработаны основные понятия новой теории и получены некоторые
результаты, определившие первоначальное представление о формальных
грамматиках. Это представление продолжает воспроизводиться и в
современных учебниках по информатике.

Исследования в области грамматик продолжались, однако, и после
Карибского кризиса, и за прошедшие полвека представление о том, что
такое формальная грамматика, несколько изменилось. Ошибочные понятия
(такие как контекстно-зависимые грамматики Хомского и многочисленные
производные модели) постепенно сошли на нет, и с их уходом устарели и
породившие их принципы классификации. Новые виды грамматик принесли с
собой представление о формальных грамматиках как о специализированной
логике для описания синтаксиса и о синтаксическом анализе как
доказательстве теорем в этой логике; важную роль в этом сыграла работа
Раундса (1988), описавшего различные виды грамматик как фрагменты логики
первого порядка над позициями в строке. Цель данного доклада ---
рассказать, как изменилось понятие о формальных грамматиках за полвека,
какие виды грамматик известны сегодня, как они соотносятся друг с
другом, и что с ними делать дальше.