Приемы построения грамматик




 

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

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

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

1) Цепочке, состоящей из заданных символов a, b, c, соответствует правило

S ® a b c.

 

2) Цепочке, начинающейся с заданного символа a, соответствует правило

S ® a A.

 

3) Цепочке, заканчивающейся заданным символом a, соответствует правило

S ® A a.

 

4) Цепочке, начинающейся и заканчивающейся соответственно заданными символами a, b, соответствует правило

S ® a A b.

5) Цепочке, содержащей в середине символ a, соответствует правило

S ® A a B.

 

6) Цепочке заданной длины l =2 соответствуют правила:

A ® a B

B ® a.

7) Цепочке, состоящей из повторяющихся символов a, соответствует рекурсивное правило и правило, завершающее рекурсию:

A ® a A

A ® a.

8) Цепочке, состоящей из чередующихся символов a и b, соответствуют правила:

A ® a B

B ® b A.

 

Контрольная работа.

Задание 1. Регулярные языки.

Дан регулярный язык, описать его с помощью грамматики и автомата.

Варианты.

1) Язык описания чисел в двоичной (десятичной) системе счисления.

 

2) Язык идентификаторов в языке программирования, т.е. язык в котором допустимыми являются все цепочки в алфавите цифр и строчных латинских букв, которые начинаются только с буквы и имеют длину не больше шести символов.

 

3) Язык, в котором допустимыми являются все цепочки нулей и единиц, содержащие два стоящих рядом нуля.

 

4) Язык, в котором допустимыми являются все цепочки в алфавите {1,2,3}, у которых последний символ цепочки уже появлялся в ней раньше.

 

5) Язык, в котором допустимыми являются все цепочки в алфавите {0,1}, в которых число нулей делится без остатка на 3.

 

6) Язык, в котором допустимыми являются все цепочки в алфавите {0,1}, имеющие четное число нулей и единиц.

 

Задание 2. Контекстно-свободные языки.

Дан КС-язык, описать его с помощью грамматики и автомата.

Варианты.

 

1) Язык, в котором допустимыми являются все цепочки в алфавите {0,1}, имеющие одинаковое число нулей и единиц.

 

2) Язык, в котором допустимыми являются все цепочки в алфавите {0,1}, имеющие число нулей в два раза больше единиц.

 

3) Язык L={ R | }, R обозначает запись цепочки в обратном порядке.

 

4) Язык L={0n10n | n>0}.

 

5) Язык L={0n1m0k | n>0, m>0, k>0}.

 

6) Язык L={0n1n2 | n>0}.

 

Литература

1. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1 Синтаксический анализ. – М.: Мир, 1978. – 612 с.

2. Хантер Р. Проектирование и конструирование компиляторов. М.: Финансы и статистика, 1984.

3. Д.Грис. Конструирование компиляторов для цифровых вычислительных машин. М.: Мир, 1975. – 544 с.

4. В.Н.Касьянов, И.В. Поттосин. Методы построения трансляторов. Новосибирск, Наука, 1986.– 343с.



Поделиться:




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

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-04-28 Нарушение авторских прав и Нарушение персональных данных


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