Пример выполнения контрольной работы

1. Постановка задачи: разработать программу распознавания символьных цепочек заданного языка.

2. Исходные данные:

Формула языка: AB  CD  ACD  CB²

Алфавит терминальных символов: {a, b, c, d, e, f, g, h}

Обязательные нетерминальные конструкции языка:

A = {a, d}; B = {b, h}; C = {f, g}; D = {с, e}.

В соответствии с заданной формулой языка допустимыми промежуточными формами являются:

AB; CD; ACD; CB²; ABCD; ABACD; ABCB²; CDACD; CDCB²; ACDCB²;

ABCDACD; ABCDCB²; ABACDCB²; CDACDCB²; ABCDACDCB².

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

<Z>::= <E> | <F> | <EF>

<E>::= <AB> | <CD> | <ABCD>

<F>::= <ACD> | <CBB> | <ACDCBB>

<A>::= a | d

<B>::= b | h

<C>::= f | g

<D>::= c | e

4. Один из вариантов алгоритма распознавания допустимой цепочки заданного языка:

1º. Ввести распознаваемую символьную цепочку.

2º. H = 0; I = 1 (H – счетчик символов в цепочке, I – номер позиции в цепочке).

3º. Считать I-й терминальный символ из символьной цепочки.

4º. Найти в правой части правил подстановки этот символ. Если неудача – переход к п. 16º.

5º. Подставить вместо него символ из левой части правила подстановки.

6º. H = H + 1; I = I + 1.

7º. Если справа есть терминальный символ, то переход к п. 3º.

8º. I = 1; F = 0 (F – дополнительный счетчик нетерминальных символов в цепочке).

9º. J = 6. Если I + J > H, то J = H – I.

10º. Считать J символов, начиная с I-й позиции.

11º. Найти в правой части правил подстановки эту подцепочку нетерминальных символов. Если неудача – переход к п. 14º.

12º. Подставить вместо этой подцепочки символ из левой части правила подстановки.

13º. F = F + 1; I = I + J. Если I > H, то переход к п. 15º. Иначе – переход к п. 9º.

14º. J = J – 1. Если J > 0, то переход к п. 10º. Иначе – переход к п. 16º.

15º. H = F. Если H = 1, то вывести на экран сообщение: “Данная цепочка корректна” и переход к п. 17º.

16º. Вывести на экран сообщение: “Данная цепочка некорректна”.

17º. Сохранить протокол распознавания (цепочка – результат распознавания).

18º. Вывести на экран запрос на ввод следующей цепочки.

19º. Если ответ “Да”, то переход к п. 1º.

20º. Конец работы.

5. Распечатка исходного текста программы распознавания символьных цепочек.

6. Распечатка протокола распознавания 7–10 символьных цепочек (включая некорректные).

7. Выводы по работе (желательно).

47