Техника построения КС- и А- грамматик

Классификация грамматик по Хомскому

Грамматика G называется грамматикой типа 3, регулярной, праволинейной или автоматной грамматикой(А-грамматикой), если каждое правило из R имеет вид:

A ® xA (праволинейное правило)

или

A ® x (заключительное правило),

где A ÎV_N, x ÎV_T.

То есть каждое правило такой грамматики содержит единственный нетерминал в левой части, всегда один терминал в правой части, за которым может следовать один нетерминал. Для таких грамматик мы в дальнейшем будем пользоваться термином автоматная (А-) грамматика.

Грамматика G называется грамматикой типа 2, бесконтекстной или контекстно - свободной (КС-) грамматикой, если ее правила имеют вид:

A ® a,

где A ÎV_N, a Î (V_NÈ V_T) ^*.

То есть в каждом правиле такой грамматики имеют место единственный нетерминал слева и произвольная цепочка из терминалов и нетерминалов справа, возможно и пустая. Замена A на a в сентенциальной форме не зависит от того, в каком окружении, в каком контексте находится A.

Грамматика G называется грамматикой типа 1, контекстной, нормальных составляющих (НС-) или контекстно - зависимой (КЗ-) грамматикой, если ее правила имеют вид:

jAy ® jay, где A ÎV_N, j, y Î (V_NÈ V_T) ^* и a Î (V_NÈ V_T)⁺, то есть в каждом правиле нетерминал A в контексте j и y заменяется на непустую цепочку a в том же контексте.

Грамматика G называется грамматикой типа 0, грамматикой с фразовой структурой или рекурсивно перечислимой грамматикой, если ее правила имеют вид:

a®b,

где на левую и правую части правил не наложено никаких ограничений. “

Нетрудно заметить, что грамматики типа i одновременно являются грамматиками типа i -1. Исключение составляют укорачивающие КС (УКС) - грамматики, то есть грамматики, содержащие аннулирующие правила типа

A ® e

которые не являются КЗ-грамматиками.

Язык, определяемый грамматикой типа i называется языком типа i.

Тип 0

Тип 1

Тип 2

Тип 3

Из примеров 1.2 и 1.3 следует, что языки чисел и идентификаторов являются КС-языками (тип 2).

Тот факт, что язык определяется грамматикой типа i, еще не означает, что его нельзя породить менее мощной грамматикой типа i+1.

Например, КС- грамматика с правилами

S®AS ç e

A ® 0 ç 1

порождает язык { 0,1 }^*, который, конечно же, можно определить А-грамматикой

S ® 0S ç 1S ç 0 | 1

Рассмотрим ряд примеров грамматик.

Пример 1.4. Автоматная грамматика идентификатора.

S ® aA ç bA ç cA ç ... ç yA ç zA

A ® aA ç bA ç cA ç ... ç yA ç zA ç 0A ç 1A ç... ç 8A ç 9A

A ® a ç b ç c ç ... ç y ç z ç 0 ç 1 ç ... ç 8 ç 9.

Данная грамматика имеет на самом деле 72 правила, но для краткости часть из них заменена многоточием. ™

Пример 1.5. Грамматика типа 0 для цепочек вида x ⁿ y ⁿ z ⁿ, где n > 0.

(1) S ® xyASz

(2) S ® Q

(3) yAQ ® Qy

(4) yAx®xyA

(5) xQ®x.

Покажем, что данная грамматика порождает цепочки x ⁿ y ⁿ z ⁿ и никаких других.

1). Новые символы порождаются только первым правилом. При этом получается одинаковое количество символов x, y и z, символы z в нужном месте и порядке. То есть, применяя n раз правило (1), получим вывод:

S Þ xyASz Þ xyAxyASzz Þ ^* (xyA) ⁿ Sz ⁿ.

2). После применения правила (2) дальнейшее порождение новых символов невозможно. Получаем (xyA) ⁿ Sz ⁿ Þ (xyA) ⁿ Qz ⁿ.

3). Правила (3) и (4) применяются поочередно. При этом А устраняется правилом (3), когда правее него в сентенциальной форме нет х. Получаем

(xyA) ⁿ Qz ⁿ = (xyA) ^n-1 xyAQz ⁿ Þ (xyA) ^n-2 xyAxQyz ⁿ Þ (xyA) ^n-2 xxyAQyz ⁿ Þ

(xyA) ^n-3 xyAxxQyyz ⁿ Þ (xyA) ^n-3 xxyAxQyyz ⁿ Þ (xyA) ^n-3 xxxyAQyyz ⁿ Þ⁺ x ⁿ Qy ⁿ z ⁿ

4). x ^n-1 xQy ⁿ z ⁿ Þ x ⁿ y ⁿ z ⁿ.

Применить правило (5) можно только на последнем шаге, в противном случае в цепочке останутся нетерминалы A. ™

Пример 1.6. КЗ-грамматика для цепочек x ⁿ y ⁿ z ⁿ, где n>0.

(1) S ® xYz

(2) Yz ® XYYzz

(3) YX ® YA

(4) YA ® XA

(5) XA ® XY

(6) xX ® xx

(7) Y ® y.

Здесь правила (3) - (5) заменяют правило YX ® XY, относящееся к типу 0. Взяв дополнительный нетерминал A, мы получили три КЗ-правила. Рассмотрим вывод цепочки x³y³z³ по этой грамматике.

S Þ xYz Þ xXYYzz Þ xXYXYYzzz Þ xXYAYYzzz Þ xXXAYYzzz Þ xXXYYYzzz Þ

xxXYYYzzz Þ xxxYYYzzz Þ xxxyYYzzz Þ xxxyyYzzz Þ xxxyyyzzz = x³y³z³. ™

Что можно сказать о выделенных классах грамматик и языков в целом? Идеальными с теоретической и практической точек зрения являются А-грамматики и языки. Но их класс слишком узок. Даже язык арифметических выражений не является A язы­ком. Тем не менее, теория автоматных языков повсеместно используется при построении трансляторов. Класс языков типа 0, напротив, очень широк и неразрешим в общем случае. Все остальные языки (тип 1 - тип 3), которые обобщенно называют контекстными, разрешимы. Для них существуют алгоритмы, определяющие принадлежность или непринадлежность цепочек языку за конечное число шагов.

Теорема 1.1. Любой контекстный язык разрешим

Доказательство. Для любого контекстного языка L существует порождающая его грамматика G в удлиняющей форме, у которой для всех правил вывода a®b выполняется условие ç a ½ < ç b ÷. (Доказательство этого факта будет дано позже. В общем случае для контекстной грамматики без аннулирующих правил выполняется условие ç a ÷ £ ç b ÷). Возьмем анализируемую терминальную цепочку h. Длина исследуемой цепочки должна быть конечной. Тогда, если

h Î L,то существует вывод S = x₁ Þ x₂ Þ... Þ x _n-1 Þ x _n = h, то есть вывод S Þⁿ h, где çh÷ ³ n, так как каждый шаг вывода удлиняет цепочку не менее чем на единицу. Число выводов с длиной не более n конечно. Поэтому достаточно проверить выводится ли h одним из них. Если h совпадает с одной из терминальных цепочек, выводимых по заданной грамматике G, не более чем за n шагов, то h Î L(G), если нет - h Ï L(G). ™

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

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

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

Пример 1.7. КС-грамматика пассажирского поезда.

< поезд > ® < локомотив > < вагоны>

< локомотив > ® паровоз ï тепловоз ï электровоз

< вагоны > ® <вагон> ï <вагон> <вагоны>

< вагон > ® купейный ô плацкартный ô общий ô СВ ô ресторан

Здесь терминалами мы считаем объекты типа " электровоз ", " ресторан " и т.п., хотя могли спуститься и до стоп-крана и колесных пар. ™

Отметим еще раз, что для получения цепочки типа "один или много a", где количество a не ограничено сверху, необходимо использовать рекурсивные правила:

< один или много a > ® a ï a< один или много a >

или

< один или много a > ® a ï < один или много a >a

или

< один или много a > ® a ï < один или много a >< один или много a >

Дата добавления: 2014-01-11