1.5.8. Грамматики, описывающие условные операторы и операторы цикла

Допустим, что рассматриваются условные операторы, аналогичные используемым в языке Паскаль, с разделителями 'if', 'then', 'else'. В качестве условия в таких операторах разрешается использовать отношения, состоящие из двух идентификаторов, соединенных знаками = и <. Структура такого оператора определяется двумя видами  последовательностей фиксированной длины, для описания которых можно воспользоваться простым перечислением компонентов. Первая последовательность определяет полный и сокращенный условные операторы, а вторая - конструкцию "отношение". Схема грамматики, задающая эти последовательности, может быть изображена так:  

Г_{1. 28} : R = {  <V> ® .if.<R4><C2>,

<C2> ® .then.<S><C3>, <C3> ® .else.<S>, <C3> ® $, <R4> ® <I><R3>, <R3> ® < <I>, <R3> ® = <I> } .

 

В этой грамматике <S> определяется схемой грамматики Г_{1. 27} . Рассмотрим описание операторов цикла, подобных используемым в языке Паскаль, с разделителями 'while', 'do', 'repeat', 'until'. Каждый оператор может быть описан в виде простой последовательности ограниченной длины, в которой используются построенные ранее грамматика Г_{1. 28} и грамматика Г_{1. 27} . На практике часто встречаются ситуации, когда удобнее работать с грамматикой, правая часть правил которой  начинается терминальным символом. Построение подобных грамматик сводится к тому, что для каждого терминального символа заданной конструкции языка строится отдельное правило. Для рассматриваемых операторов цикла такие схемы грамматик с использованием определенных ранее нетерминальных символов  имеют вид:

Г_{1. 29}:    R = { <W> ® .while. <R4><C4>,

<C4> ® .do. <S> }

Г_{1. 30}:    R = { <W1> ® .repeat.<S><C5>,

 <C5> ® .until.<R4> }.

1.5.9. Резюме

Задача построения формальной грамматики заключается в том, что по заданному описанию множества цепочек требуется определить словарь нетерминальных символов и построить схему грамматики. Эта задача относится к классу эвристических задач, не имеющих общих алгоритмов решения. На практике поиск решения выполняется с применением структурного анализа заданных цепочек. В результате такого анализа выявляются структурные компоненты цепочек, обозначения которых входят в нетерминальный словарь грамматики, а порядок следования компонентов в цепочках служит основой построения правил грамматики.

2. Автоматные грамматики и распознаватели

Формальные грамматики можно рассматривать как инструмент, позволяющий строить цепочки языка согласно правилам, которые зафиксированы в схеме грамматики. Другими словами, если задана грамматика, определяющая язык, то всегда можно построить любую цепочку этого языка. Для практических применений большое значение имеет другая задача, которую называют задачей распознавания. Она формулируется следующим образом. Задана цепочка, состоящая из терминальных символов, и формальная грамматика, требуется определить, принадлежит ли заданная цепочка языку, порождаемому заданной грамматикой.

В общем случае эта задача может быть решена при помощи непосредственного использования правил грамматики. Нужно находить в заданной цепочке фрагменты, совпадающие с правыми частями правил грамматики, и заменять эти части символами левых частей правил. Операцию замены части заданной цепочки, совпадающей с правой частью какого – либо правила, левой частью этого правила называют непосредственным сворачиванием. Если после выполнения последовательности непосредственных сворачиваний удается получить начальный символ грамматики, то заданная цепочка принадлежит языку, порождаемому грамматикой.

Допустим, что задана грамматика, схема которой имеет вид:

R = {<I>→ a <B> x, B → b <B>, <B> → y},

и цепочка символов abyx. Выполнив операцию сворачивания с помощью третьего правила, получим цепочку a b <B> x. Теперь выполним сворачивание с помощью второго правила и получим цепочку a <B> x. Наконец, выполним сворачивание с использованием первого правила. Получим начальный символ грамматики, следовательно, заданная цепочка принадлежит языку, порождаемому заданной грамматикой.

Если схема грамматики содержит много правил, и если задана длинная цепочка, то процедура сворачивания становится трудоемкой, поскольку после каждого сворачивания нужно многократно просматривать цепочку, чтобы определить, какие из правил можно применить на очередном шаге сворачивания. Если можно применить несколько правил, то следует принять решение, какое из правил выбрать для выполнения операции. Может возникнуть ситуация, когда на очередном шаге нельзя применить ни одно из правил. В этом случае нужно выбрать другое правило и повторить попытку.

Существенно то, что для некоторых классов контекстно – свободных грамматик и для автоматных грамматик эту процедуру удается существенно упростить и, более того, построить устройства, выполняющие процедуру распознавания автоматически. Такие устройства в общем случае называют распознавателями. Соответствие между автоматными грамматиками и распознавателями рассматривается в настоящей главе. В ней обсуждаются проблемы построения распознавателей для грамматик автоматного типа. Такие распознаватели в литературе часто называют автоматами без выходного преобразователя или просто автоматами без выходов. Вначале приводится определение автоматного распознавателя и обсуждается возможности построения детерминированных распознавателей такого типа. Затем рассматриваются способы построения распознавателей для конечных языков и приемы минимизици и числа состояний без выходов.