<L>
, то получим правила грамматики в виде:
- Г1. 15: <L>
® a<R>,
- <R> ® a<R>,
<R> ® $.
2) В предыдущей задаче предполагалось, что список <L>
должен содержать хотя бы один элемент. Если же допустить, что множество цепочек, порожденных правилами грамматики, может включать пустой символ, то к построенным правилам нужно добавить еще одно правило <L>
® $ . В этом случае набор правил имеет вид :
- Г1. 16: <L> ® a<R>,
- <R> ® a<R>,
- <R> ® $,
<L> ® $.
3) Рассмотрим построение списка, между элементами которого должны стоять разделители. Выберем в качестве разделителя запятую. Простейший список, как и в предыдущем случае, состоит из одного элемента, а построение списка из нескольких элементов может быть выполнено приписыванием к уже построенной части списка разделителя с элементом списка. Правила, соответствующие этому построению, имеют вид:
Г1. 17: <L> ® a<R>,
- <R> ® ,a<R>,
<R> ® $.
4) Если список с разделителями может быть пустым, то приведенный выше набор правил нужно дополнить еще одним правилом с пустой правой частью. В результате получим:
- Г1. 18: <L> ® a<R>,
- <R> ® ,a<R>,
<R> ® $,
<L> ® $.
В общем случае, если описано множество цепочек, представляющих собой некоторый язык, и требуется построить грамматику, порождающую это множество цепочек, то следует поступать так:
1) Выписать несколько примеров из заданного множества цепочек.
2) Проанализировать структуру цепочек, выделяя начало, конец, повторяющиеся символы или группы символов.
3) Ввести обозначения для сложных структур, состоящих из групп символов. Такие обозначения являются нетерминальными символами искомой грамматики.
4) Построить правила для каждой из выделенных структур, используя для задания повторяющихся структур рекурсивные правила.
5) Объединить все правила.
6) Проверить с помощью выводов возможность получения цепочек с разной структурой.
Пред.Страница След.Страница Раздел Содержание
