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

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

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

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

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

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

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

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

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

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

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

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

Пример 1.4.

КС-грамматика действительного числа, то есть цепочек от полного представления числа, типа -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.5. Автоматная грамматика действительного числа.

Число может начинаться с "+" или "-", и тогда оставшуюся часть числа резонно назвать числом без знака. Число также может начаться любой цифрой (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", т.е. цепочек без целой и дробной частей. На данном этапе проигнорируем этот факт, чтобы не усложнять грамматику.

Поиск по сайту: