Грамматики синтаксического уровня

Грамматики синтаксического уровня – наиболее разработанная часть и с точки зрения лингвистики, и с точки зрения их обеспечения формализмами. Все они основаны на порождающей грамматике Хомского. Порождающая грамматика Хомского представляет собой упорядоченную систему Г =(V,W,J,R), где V и W – непересекающиеся конечные множества – основное (терминальное) и вспомогательное (нетерминальное), J – элемент W, называемый начальным символом и R – конечное множество правил вида j(r)y, где j и y – цепочки (конечные последовательности) из основных и вспомогательных символов. Множество тех цепочек из основных символов, которые выводимы в Г из ее начального символа, называют языком, порождаемым грамматикой Г и обозначают L(Г). Если все правила Г имеют вид caw(r)cyw , где a – вспомогательный символ, y – непустая цепочка, c и w – произвольные цепочки, то Г называется грамматикой составляющих или грамматикой непосредственно составляющих (ГНС). Укажем основные типы грамматик и реализующих их алгоритмов.

Цепочечная грамматика фиксирует порядок следования элементов, т.е. линейные структуры предложения, задавая их в терминах грамматических классов слов (существительное+предлог...) или в терминах функциональных элементов (подлежащее+сказуемое). Примером реализации такой языковой модели является предсказуемостный синтаксический анализ: идентифицированная грамматическая категория слова предсказывает (с определенной долей вероятности) появление грамматической категории следующего за ним слова.

Грамматика составляющих (или грамматика непосредственно составляющих – ГНС) фиксирует лингвистическую информацию о группировке грамматических элементов, например, именная группа (состоит из существительного, прилагательного и других модификаторов), предложная группа (состоит из предлога и именной группы) и т.д. до уровня предложения. Грамматика строится как набор правил подстановки, или исчисление продукций вида А →В→...С. ГНС представляют собой грамматики порождающего типа и могут использоваться как при анализе, так и при синтезе: – предложения языка порождаются многократным применением таких правил. В грамматиках составляющих на каждом шаге вывода заменяется только один символ, поэтому в них с каждым выводом ассоциируется так называемое дерево вывода. Корень дерева отвечает начальному символу. Каждому символу цепочки, на которую заменяется начальный символ на первом шаге вывода, ставится в соответствие узел дерева, и к нему проводится дуга из корня. Для тех из полученных узлов, которые помечены вспомогательными символами, делается аналогичное построение и т.д. Дерево вывода, рассматриваемое как дерево составляющих предложения, задает на нем систему составляющих. Это делает грамматики составляющих хорошим инструментом для описания естественных и искусственных языков. Чаще всего основные символы интерпретируются как слова, вспомогательные – как символы грамматических категорий, начальный символ – как символ категории «предложение».

Грамматика зависимостей задает иерархию отношений элементов предложения (главное слово определяет форму зависимых). Анализатор в такой грамматике основан на идентификации хозяев и их зависимых (слуг). Главным в предложении является глагол в личной форме, так как он определяет число и характер зависимых существительных. Стратегия анализа в грамматике зависимостей: сверху вниз, т.е. сначала идентифицируются хозяева, затем слуги; или снизу вверх, т.е. хозяева определяются процессом подстановки.

Появление исчисления высказываний, или «булевой алгебры», предоставило математический аппарат для определения значений истинности сложных утверждений на основании значений составляющих его простых компонентов, если они объединены с помощью логических связок И, ИЛИ, НЕ, импликации, тождества. Исчисление высказываний бедно выразительными средствами и не позволяет описывать дедуктивные рассуждения. Естественным развитием исчисления высказываний является исчисление предикатов.