ВУЗ:
Составители:
13
Основой создания правил грамматики является способ выделения структу-
ры заданного множества цепочек. Этот способ предполагает действия по сле-
дующему сценарию:
1) Выписать несколько примеров из заданного множества цепочек.
2) Проанализировать структуру цепочек, выделяя начало, конец, повторяю-
щиеся символы или группы символов.
3) Ввести обозначения для сложных структур, состоящих из групп симво-
лов. Такие обозначения являются нетерминальными символами искомой
грамматики.
4) Построить правила для каждой из выделенных структур, используя для
задания повторяющихся структур рекурсивные правила.
5) Объединить все правила.
6) Проверить с помощью выводов возможность получения цепочек с разной
структурой.
Чтобы показать, каким образом структура цепочек отображается в правила
грамматики, рассмотрим следующие примеры:
1. Цепочке, состоящей из заданных символов abc, соответствует правило:
A → abc.
2. Цепочке, начинающейся с заданного символа a, соответствует правило:
A → aB.
3. Цепочке, заканчивающейся заданным символом a, соответствует правило:
A → Ba.
4. Цепочке, начинающейся и заканчивающейся заданными символами a, b, со-
ответствует правило: A → aBb.
5. Цепочке, содержащей в середине символ a, соответствует правило: A → BaC.
6. Цепочке заданной длины l =2 соответствуют правила:
A → aB и B → a.
7. Цепочке, состоящей из повторяющихся символов a, соответствуют правила:
A → aA и A → a.
8. Цепочке, состоящей из чередующихся символов a и b, соответствуют
правила: A → aB и B → bA.
Описание списков
В качестве первых примеров рассмотрим построение грамматик для по-
следовательностей символов и последовательностей символов с разделителями.
Такие последовательности часто называют списками.
Обозначим элемент последовательности a. Простейшая последователь-
ность может состоять из одного элемента a. Все другие последовательности мо-
гут быть получены путем приписывания к уже построенной последовательно-
сти еще одного элемента. Если обозначить построенную часть последователь-
ности нетерминальным символом R, а последовательность символом L, то по-
лучим правила грамматики в виде:
L → aR
R → aR
R → λ.
Страницы
- « первая
- ‹ предыдущая
- …
- 9
- 10
- 11
- 12
- 13
- …
- следующая ›
- последняя »
