Лабораторная работа № 4

(№ 9 по списку и инд. вариант t= 0 )

Студента группы ИТ 14-1

Красовский Абхай Владленович

Формальные языки и порождающие грамматики

Цель работы: выработка навыков эквивалентного преобразования порождающих грамматик их минимизация, определения их типа; построение КА– или МП–распознавателей для этих грамматик.

Ход работы

Выполнить эквивалентные преобразования заданной порождающей грамматики с целью ее минимизации (упрощения) (исключить правила, содержащие недостижимые и непродуктивные нетерминальные символы, при необходимости – устранить левостороннюю рекурсию). Определить тип полученной грамматики и построить автомат для ее распознания (КА– или МП–распознаватель); реализовать автомат–распознаватель в виде программы на С++.

Для этого:

1 Проверить нетерминальные символы исходной грамматики на достижимость (все правила, в которые входят недостижимые нетерминалы исключить из множества правил).

2 Проверить нетерминальные символы полученной после выполнения п.1 грамматики на продуктивность (все правила, в которые входят непродуктивные нетерминальные символы исключить); к продуктивным на начальном этапе следует отнести также нетерминалы, для которых в множестве правил есть эпсилон–правила (нетерминал преобразуется в пустую цепочку).

3 Если в множестве правил есть правила с левосторонней рекурсией (правила вида A  Aab), выполнить эквивалентное преобразование по устранению левосторонней рекурсии.

4 Определить с обоснованием тип и вид полученной после выполнения предыдущих пунктов грамматики.

5 В соответствии с известными алгоритмами построить автомат-распознаватель для полученной грамматики и реализовать его в виде программы на языке С++.

№ варианта	Грамматика
0	G[S] = ( VT = {a, b}; VN = { S, A, B, C, D }; P = { S  abAa; S  bS; A  baB; A  aCb; D  a; B  b } )

1.Минимизация грамматики

А) Писк непродуктивных нетерминалов

{B,D} {B,D,A} {B,D,A,S}

Нетерминал С непродуктивен.

Б) Поиск недостижимых нетерминалов

{S} {S,A} {S,A,B}

Нетерминал D недостижим.

G[S] = {VN = {S,A,B}; VT = {a,b}; P = {

S  abAa;

S  bS;

A  baB;

B  b } )

2.Определяем тип и вид грамматики

А) Тип:

Т.к. во всех правилах только по одному нетерминалу и правые части этих правил начинаются с терминальных символов, то это грамматика второго типа(контекстно – свободная).

Б) Вид:

Т.к. в данной грамматике нет правила с концом цепочки в правой части, то это s - грамматика.

3.Управляющая таблица

4.Полное описание

Начальные конфигурации – (, S )

Допускающие конфигурации – (, )

= {VT, ˧} = {a,b, ˧}

= {VN,VT, } = {S,A,B,a,b, }

= {}

Управляющая таблица в пункте №3

5. Проверка работы

Необраб. Часть цепи	Вход. симв.	Верхн. символ маг.	Содерж. маг.	Действия с маг.
bbabbabb˧	b	S	S	0
babbabb ˧	b	S	S	0
abbabb ˧	a	S	S	↕bAa
bbabb ˧	b	b	bAa	↑b
babb ˧	b	A	Aa	↕aB
abb ˧	a	a	aBa	↑a
bb ˧	b	B	Ba	0
b ˧	b	B	Ba	0
˧	˧	B	Ba	↑B, ↑a (да)

---

6.Блок-схема

7.Код

#include "string.h"

#include "conio.h"

#include "iostream"

#define N 100

using namespace std;

void main()

{

setlocale(LC_ALL, "Russian");

char input[N], Vmp[N] = "S#", buf[N]; int i = 0, n = 0;

cout << "Enter a string for grammar checking membership: " << endl;

cin >> input;

for (i = 0; strlen(input); i++)

{

if (input[i] == 'a' && Vmp[0] == 'S') //Символ а в маг верх симв #

{

Vmp[0] = 'b';

Vmp[1] = 'A';

Vmp[2] = 'a';

Vmp[3] = '#';

}

else

if (input[i] == 'b' && Vmp[0] == 'S') //Символ b в маг в.с. S

{

// Ничего не делаем

}

else

if (input[i] == 'b' && Vmp[0] == 'A') //Символ а в маг в.с. А

{

strcpy(buf, Vmp); //Вталкиваем aB

Vmp[0] = 'a';

Vmp[1] = 'B';

for (n = 1; buf[n] != '\0'; n++)

Vmp[n + 1] = buf[n];

}

else

if (input[i] == 'b' && Vmp[0] == 'B') //Символ b в маг в.с. B

{

// Ничего не делаем

}

else

if (input[i] == 'a' && Vmp[0] == 'a') //Символ а в маг в.с. B

{

strcpy(buf, Vmp); //Выталкиваем a

for (n = 1; buf[n] != '\0'; n++)

Vmp[n - 1] = buf[n];

}

else

if (input[i] == 'b' && Vmp[0] == 'b') //Символ b в маг в.с. B

{

strcpy(buf, Vmp); //Выталкиваем b

for (n = 1; buf[n] != '\0'; n++)

Vmp[n - 1] = buf[n];

}

else

if (input[i] == '\0' && Vmp[0] == 'B')

{

strcpy(buf, Vmp);

for (n = 1; buf[n] != '\0'; n++)

Vmp[n - 1] = buf[n];

strcpy(buf, Vmp);

for (n = 1; buf[n] != '\0'; n++)

Vmp[n - 1] = buf[n];

}

else break;

}

if (Vmp[0] == '#') //Если в маг пусто цепочка допущена

cout << endl << "Цепочка допущена" << endl;

else

cout << "Цепочка не допущена" << endl;

_getch();

}

8 .Результат

9.Вывод: выработал навыки эквивалентного преобразования порождающих грамматик их минимизация, определения их типа; построение КА– или МП–распознавателей для этих грамматик.

---

Смотрите также файлы

• Lab1.docx

• Lab2.docx

• Lab3.docx

• Lab4.docx

• Lab5.docx