ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 09.06.2019
Просмотров: 134
Скачиваний: 2
Лабораторная работа № 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 |
|
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.Вывод: выработал навыки эквивалентного преобразования порождающих грамматик их минимизация, определения их типа; построение КА– или МП–распознавателей для этих грамматик.