Контекстно-свободные языки. Свойства и распознаватели КС-языков. Преобразование КС-грамматик. КС-грамматики в нормальной форме

Глава 3  Контекстно-свободные языки

3.1  Свойства и распознаватели КС-языков

3.1.1  Автоматы с магазинной памятью
– распознаватели КС-языков

Распознаватели, определяющие КС-языки, моделируются автоматами с магазинной памятью (МПА). Дадим строгое определение такого автомата.

Автомат с магазинной памятью (МПА) – это семерка P=(Q,V,Z,d,q₀,z₀,F), где

§  Q – множество состояний УУ автомата;

§  V – конечный входной алфавит (множество допустимых символов);

§  Z – специальный конечный алфавит магазинных символов автомата (обычно в него входят терминальные и нетерминальные символы грамматики, но могут использоваться и другие символы), VÍZ;

§  d – функция переходов, отображающая множество Q´(VÈ{l})´Z на конечное множество подмножеств множества (Q´Z^*);

§  q₀ – начальное состояние автомата: q₀ÎQ;

§  z₀ – начальный символ магазина: z₀ÎZ;

§  F – множество конечных состояний автомата: FÍQ, F¹Æ.

В отличие от конечного автомата (КА), рассмотренного в предыдущей главе, МП-автомат имеет «стек» магазинных символов, который играет роль дополнительной, или внешней памяти. Переход МПА из одного состояния в другое зависит не только от входного символа и текущего состояния, но и от содержимого стека. Таким образом, конфигурация МПА определяется уже тремя параметрами: состоянием автомата, текущим символом входной цепочки и содержимым стека.

Итак, конфигурация, или мгновенное описание (МО) МПА – это тройка (q,w,a)ÎQ´V^*´Z^*, где q – текущее состояние УУ, w – непрочитанная часть входной цепочки, a – содержимое магазина. Если w=l, считается, что цепочка прочитана; если a=l, то магазин считается пустым.

Начальная конфигурация МПА определяется как (q₀,w,z₀), wÎV^*. Множество конечных конфигураций – как (q,l,z), где qÎF, zÎZ^*.

Такт работы МП-автомата будем обозначать отношением ├─  на множестве конфигураций и описывать в виде (q,aw,ta)├─ (q¢,w,ga), если (q¢,g)Îd(q,a,t), где q,q¢ÎQ, aÎVÈ{l}, wÎV^*, tÎZ, g,a ÎZ*. При выполнении такта автомат, находясь в состоянии q, считывает символ входной цепочки ‘a’ и сдвигает входную головку на одну ячейку вправо, а из магазина удаляет верхний символ, соответствующий условию перехода, и заменяет цепочкой согласно правилу перехода. Первый символ цепочки становится вершиной стека. Состояние автомата изменяется на q¢. Допускаются переходы, при которых считывающая головка не сдвигается и входной символ игнорируется, тогда он становится входным символом при следующем такте, но состояние УУ и содержимое стека может измениться. Такие переходы называются l–тактами. Автомат может проделывать l–такты, когда уже прочёл входную цепочку или же в процессе её прочтения; но, если магазин пуст, следующий такт невозможен.

Итак, находясь в состоянии q и наблюдая символ входной ленты x, МПА на одном такте работы может проделать со стеком в зависимости от правил перехода одно из следующих действий:

1)  Дописать в стек c верхним символом a символ x: d(q,x,a)={(q,xa)}. В общем случае может быть дописан другой символ, отличный от прочитанного.

2)  Удалить из стека верхний символ a: d(q,x,a)={(q,l)}.

3)  Оставить содержимое стека без изменений: d(q,x,a)={(q,a)}.

МПА допускает цепочку символов w, если, получив эту цепочку на вход, он может перейти в одну из конечных конфигураций, когда по окончании цепочки автомат находится в одном из конечных состояний: (q₀,w,z₀)├─^*(q,l,z), где qÎF, zÎZ^*. После окончания цепочки автомат может проделать некоторое количество l–тактов.

Язык, определяемый МП-автоматом P – это множество всех цепочек символов, допускаемых этим автоматом: L(P). Два автомата P₁ и P₂ эквивалентны, если они определяют один и тот же язык: L(P₁)=L(P₂).

Говорят, что МПА допускает цепочку символов с опустошением магазина, если при окончании разбора цепочки автомат находится в одном из своих конечных состояний, а стек пуст, т.е. получена конфигурация (q,l,l), qÎF. Язык, заданный автоматом P, допускающим цепочки с опустошением стека, обозначается как L_l (P). Для любого МП-автомата всегда можно построить эквивалентный ему МПА, допускающий цепочки с опустошением стека: " МПА P  $ МПА P¢ ½ L(P)=L_l (P¢).

Кроме обычного МПА, существует понятие расширенного МПА. Расширенный МПА может заменять не один символ в вершине стека, а цепочку символов конечной длины, на некоторую другую цепочку символов. Для любого расширенного МПА всегда можно построить эквивалентный ему обычный МП-автомат. Следовательно, классы МПА и расширенных МПА эквивалентны.

Утверждение

1.  Для произвольной КС-грамматики всегда можно построить МП-автомат, распознающий задаваемый этой грамматикой язык.

2.  Для произвольного МП-автомата всегда можно построить КС-грамматику, которая будет задавать язык, распознаваемый этим автоматом.

МПА называется недетерминированным, если из одной и той же его конфигурации возможен более чем один следующий переход.

МПА называется детерминированным, если из любой его конфигурации возможно не более одного следующего такта. Класс ДМП-автоматов и соответствующих языков заметно уже, чем весь класс КС-языков и соответственно, МП-автоматов. В отличие от КА, не для каждого МПА возможно построить эквивалентный ему ДМП-автомат.

ДМП-автоматы определяют особый подкласс среди КС-языков, называемый детерминированными КС-языками. Все языки, относящиеся к этому классу, могут быть построены с помощью однозначных КС-грамматик, следовательно, они играют особую роль в теории языков программирования. Поэтому ДМПА необходимы при создании компиляторов. На основе ДМПА может быть построен синтаксический распознаватель любого языка программирования.