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

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

В 1956 году Н.Хомским было предложено классифицировать грамматики по виду их правил, по ограничениям, накладываемым на правила.

Грамматика G по Хомскому - это традиционная четверка множеств

G = (N, S, R, S),

где N - множество нетерминалов, S - множество терминалов, R - множество продукций, S - аксиома грамматики.

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

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

или

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

где A Î N, x Î S.

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

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

A ® a,

где A Î N, aÎ (NÈS) ^*.

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

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

jAy ® jay,

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

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

a®b,

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

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

A ® e

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

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

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

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

S®AS ç e

A ® 0 ç 1

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

S ® 0S ç 1S ç e

Рассмотрим ряд примеров грамматик. В большинстве случаев мы опускаем описания множеств N, S, S в силу их очевидности и ограничиваемся множеством правил грамматики R.

Пример 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 ÷. (Доказательство этого факта будет дано в разделе 4.5.) В общем случае для контекстной грамматики без аннулирующих правил выполняется условие ç 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 >

Пример 1.8. КС-грамматика действительного числа, то есть цепочек от полного представления числа, типа -123.567Е-21, до вырожденных: 0. или .1, т.е. в этом числе обязательна точка и хотя бы одна цифра в целой или дробной части. Терминалами здесь являются знаки - " + " и " - ", цифры от " 0 " до " 9 ", десятичная точка - ". " и символ " E ". То есть S = {+, -, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,., E }. В цепочке < число > можно выделить следующие основные компоненты: знак числа, целую часть, точку - ". ", дробную часть, символ " E ", знак порядка и само значение порядка. Отдельные компоненты или их группы могут отсутствовать. При таком разложении ". " и " E " - терминалы, а все остальное нетерминалы, требующие дальнейшей декомпозиции. Так < целая часть > - это одна цифра или несколько цифр, а < знак > - " + " или " - ". Нетрудно видеть, что знаки числа и порядка ничем не отличаются друг от друга и для них можно ограничиться одним понятием - знак. С точки зрения синтаксиса нет разницы и между целой частью, дробной частью и порядком и их вполне можно определить одно через другое. В результате имеем грамматику:

(1) < число > ® < знак >< целая часть >.< дробная часть > Е < знак > < порядок >

(2) < число > ® < целая часть >. < дробная часть > Е < знак > < порядок >

(3) < число > ® < знак >. < дробная часть > Е < знак > < порядок >

(4) < число > ® < знак > < целая часть >. Е < знак > < порядок >

(5) < число > ® < знак > < целая часть >. < дробная часть > Е < порядок >

(6) < число > ® < знак > < целая часть >. < дробная часть >

(7) < число > ®. < дробная часть > Е < знак > < порядок >

(8) < число > ® < целая часть >. Е < знак > < порядок >

(9) < число > ® < целая часть >. < дробная часть > Е < порядок >

(10) < число > ® < знак > < целая часть >. Е < порядок >

(11) < число > ® < знак >. < дробная часть > Е < порядок >

(12) < число > ® < целая часть >. < дробная часть >

(13) < число > ® < знак >. < дробная часть >

(14) < число > ® < знак > < целая часть >.

(15) < число > ® < целая часть >. Е < порядок >

(16) < число > ®. < дробная часть > Е < порядок >

(17) < число > ® < целая часть >.

(18) < число > ®. < дробная часть >

(19) < целая часть > ® < цифра > < целая часть >

(20) < целая часть > ® < цифра >

(21) < дробная часть > ® < целая часть >

(22) < порядок > ® < целая часть >

(23) < цифра > ® 0

(24) < цифра > ® 1

(25) < цифра > ® 2

.......

(32) < цифра > ® 9

(33) < знак > ® +

(34) < знак > ® -

Используя БНФ (альтернативу и факультатив), эти 34 правила можно переписать в виде:

< число > ® [ < знак > ] < целая часть >. [ <дробная часть > ][ Е [ < знак > ] < порядок > ]ô

[ < знак > ][ < целая часть > ] .< дробная часть > [ Е [ < знак > ] < порядок > ]

< целая часть > ® < цифра > [ < целая часть > ]

< дробная часть > ® < целая часть >

< порядок > ® < целая часть >

< цифра > ® 0 ô 1 ô 2 ô 3 ô 4 ô 5 ô 6 ô 7 ô 8 ô 9

< знак > ® + ô - ™

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

Пример 1.9. Автоматная грамматика действительного числа.

Число может начинаться с " + " или " - " и тогда оставшуюся часть числа резонно назвать числом без знака. Число также может начаться любой цифрой (0 - 9) и остаток цепочки будет тем же числом без знака. Наконец число может начаться десятичной точкой ". " и остаток такой цепочки уже иной. Если число без знака может в качестве продолжения содержать цифры и должно завершиться той же точкой, то после точки идет фрагмент цепочки, который точки уже не содержит. Есть смысл назвать этот фрагмент дробной частью и порядком. Рассуждая аналогичным образом мы получим А-грамматику, где использованы следующие сокращения для имен нетерминалов: чис - число, чбз - число без знака, дчп - дробная часть и порядок, пор - порядок, пбз - порядок без знака

< ч > ® +< чбз > ô -< чбз > ô 0< чбз > ô 1< чбз > ô ... ô 9< чбз > ô .< дчп >

< чбз > ® 0< чбз > ô 1< чбз > ô ... ô 9< чбз > ô .< дчп > ô.

< дчп > ® 0< дчп > ô 1< дчп > ô ... ô 9< дчп > ô 0 ô 1 ô ... ô 9 ô E< пор >

< пор > ® +< пбз > ô -< пбз > ô 0< пбз > ô 1< пбз > ô ... ô 9< пбз > ô 0 ô 1 ô ... ô 9

< пбз > ® 0< пбз > ô 1< пбз > ô ... ô 9< пбз > ô 0 ô 1 ô ... ô 9

Данная грамматика допускает порождение совсем уж вырожденных цепочек, типа " -. " или " .Е1 ", т.е. цепочек без целой и дробной частей. На данном этапе проигнорируем этот факт, чтобы не усложнять грамматику. ™

Дата добавления: 2015-06-27