Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

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



 

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

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

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

 




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

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.