Межрегиональный центр переподготовки специалистов
Лабораторная работа №3
По дисциплине:
«Теория языков программирования и методы трансляции»
Выполнил:
Группа: ПБВ-89
Вариант: 8
Проверил: Бах О.А.
Новосибирск, 2018 г
Постановка задачи
Перевод с помощью МП-преобразователя
Пусть дан преобразователь с магазинной памятью; написать программу, которая будет выполнять перевод цепочек с одного языка на другой с помощью заданного преобразователя (теоретический материал раздела 4.2). При невозможности выполнить перевод (цепочка не принадлежит исходному языку) необходимо выводить на экран соответствующее сообщение.
Исходный преобразователь вводить с клавиатуры в соответствии с определённым форматом. Ввод цепочек также производить с клавиатуры, выполняя его до тех пор, пока не возникнет желание закончить работу. Процесс перевода цепочки в виде последовательной смены конфигураций отображать на экране.
Рекомендуется за основу взять программу лабораторной работы №3, дополнив исходные данные выходным алфавитом, функцию переходов – в соответствии с определением преобразователя, а конфигурации – выходными цепочками.
Проверить работу программы на примерах из лекций и задачах из контрольных вопросов.
Дополнительно:
Предоставить пользователю возможность не только вводить данные с клавиатуры, но и загружать преобразователь из файла (аналогично лабораторной работе №2).
Описание входных данных программы и её результатов
На вход программы подаётся ДМП-преобразователь (множество состояний, алфавиты входного и выходного языков, алфавит магазина, начальное состояние, начальное содержимое стека, множество заключительных состояний, функция переходов в виде списка правил) и проверяемая цепочка символов (аналогично лаб. раб. №3).
На выход: отображение на экране процесса перевода цепочки в виде последовательной смены конфигураций преобразователя, результат перевода – полученная цепочка.
Описание основных переменных, а также основных блоков и подпрограмм
Q - множество состояний.
Vin - множество символов входного алфавита.
Vout - множество символов выходного алфавита.
Z - множество символов магазина.
int F - множество конечных состояний.
nF - число заключительных состояний.
q0 - начальное состояние.
z0 - начальный символ магазина.
nQ - количество состояний.
nVin - количество символов входного алфавита.
nVout - количество символов выходного алфавита.
nZ - количество символов магазина.
Stack - магазин.
struct ConfMod - структура изменения конфигурации.
function ConfMod - функция переходов.
function SymbolSearch - ищет символ, указатель которого ей передается в качестве параметра Symb, в массиве M[][MAX_SYMB_LENGHT].
function SymbolIdentify - читает строку по указателю Str и ищет совпадения с символами, находящимися в массиве M[][MAX_SYMB_LENGHT].
function StackMod - заменяет верхний символ в цепочке магазина на цепочку символов по указателю g, определенную в правиле перехода.
function TranslateString без параметров. Запрашивает ввод цепочки и осуществляет перевод введенной цепочки с входного языка на выходной по алгоритму решения задачи.
Алгоритм решения задачи
Устанавливается начальное состояние преобразователя, в магазин добавляется начальный символ и указатель устанавливается на первый символ цепочки. Алгоритм проверки и перевода цепочки заключается в чтении символа из входной цепочки и, в зависимости от полученной тройки состояние/символ цепочки/символ магазина, по правилу перехода определяется новое состояние автомата, символ магазина заменяется на цепочку, в правиле и к выходной цепочке присоединяется цепочка, определенная в правиле перехода. Если правило для какой-либо конфигурации состояние/символ цепочки/символ магазина не определено, может совершаться пустой такт, т.е. правило перехода для комбинации состояние/пустой символ/символ магазина.
Процесс осуществляется в цикле до тех пор, пока:
1. не закончатся символы в цепочке;
2. прочитан неизвестный символ;
3. для полученной комбинации состояние/символ цепочки/символ магазина значение функции не определено и для пустого такта значение не определено;
4. магазин опустеет до прочтения всей цепочки.
Цепочка будет считаться успешно переведенной, если будут прочитаны все символы цепочки, и автомат окажется в одном из заключительных состояний.
Текст программы:
(main.cpp)
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include "main.h"
struct ConfMod // структура изменения конфигурации
{
int q; // новое состояние
char *g; // цепочка для магазина
char *y; // выходная цепочка
};
char Q [MAX_SYMB_COUNT][MAX_SYMB_LENGTH],// множество состояний
Vin[MAX_SYMB_COUNT][MAX_SYMB_LENGTH], // множество входного алфавита
Vout[MAX_SYMB_COUNT][MAX_SYMB_LENGTH], // множество выходного алфавита
Z[MAX_SYMB_COUNT][MAX_SYMB_LENGTH]; // множество символов магазина
int F[MAX_SYMB_COUNT], // множество конечных состояний
nF, // число заключительных состояний
q0, // начальное состояние
z0, // начальный символ магазина
nQ, // количество состояний
nVin, // количество символов входного алфавита
nVout, // количество символов выходного алфавита
nZ; // количество символов магазина
char Stack[MAX_STR_LENGTH]; // магазин
ConfMod func[MAX_SYMB_COUNT][MAX_SYMB_COUNT][MAX_SYMB_COUNT];
int main ()
{
while(true)
{
system("cls");
puts("1 - Ввод ДМП-преобразователя");
puts("2 - Выход");
switch(_getch())
{
case '1':
{
EnterAutomate();
bool end = false;
while(!end)
{
system("cls");
puts("1 - Перевести цепочку");
puts("2 - Назад");
switch(_getch())
{
case '1':
{
RulesView();
int Result = TranslateString();
ResultMessage(Result);
}
break;
case '2':
end = true;
}
}
}
break;
case '2':return 1;
}
}
}
int SymbolSearch(char M[][MAX_SYMB_LENGTH], int Size, char *Symb)
{
int i = 0;
while (i< Size)
{
if (strcmp(M[i], Symb) == 0) break;
i++;
}
return i;
}
int EnterScores(char M[][MAX_SYMB_LENGTH], int max)
{
char Str[MAX_STR_LENGTH];
char *pNextToken = NULL;
int i = 0;
printf("Введите через запятую множество:\n>> ");
gets_s(Str, MAX_STR_LENGTH-1);
char * pToken = strtok_s(Str, ", ", &pNextToken);
while (pToken)
{
strcpy_s(M[i], pToken);
i++;
if(i == max) break;
pToken = strtok_s('\0', ", ", &pNextToken);
}
return i;
}
// Ввод множества конечных состояний
int EnterFinalStates()
{
bool end = false;
char Symb[MAX_SYMB_COUNT][MAX_SYMB_LENGTH];
int i;
while (!end)
{
end = true;
i = 0;
EnterScores(Symb, MAX_SYMB_LENGTH);
if ((F[i] = SymbolSearch(Q, nQ, Symb[i])) == nQ)
{
printf("Символ %s не принадлежит множеству состояний!\n", Symb[i]);
end = false;
}
i++;
}
return i;
}
// Ввод символа
int ControlEnterSymbol(char M[][MAX_SYMB_LENGTH], int Size)
{
char Str[MAX_SYMB_LENGTH];
int index;
while (true)
{
printf(">> ");
gets_s(Str, MAX_SYMB_LENGTH-1);
if ((index = SymbolSearch(M, Size, Str)) == Size)
printf("%s - недопустимый символ!\n", Str);
else break;
}
return index;
}
// Функция возвращает указатель на созданную строку
char *ControlEnterString(char M[][MAX_SYMB_LENGTH], int Size)
{
char Str[MAX_STR_LENGTH];
char *pStr;
bool end = false;
while(!end)
{
printf(">> ");
end = true;
pStr = gets_s(Str, MAX_STR_LENGTH-1);
if(strcmp(Str, "lam") == 0) *pStr = '\0';
while(*pStr)
if(SymbolIdentify(M, Size, &pStr) == Size)
{
puts("В строке присутствуют недопустимые символы!");
end = false;
break;
}
}
pStr = (char *)malloc(strlen(Str)+1);
if(!pStr) return NULL;
strcpy_s(pStr, strlen(Str)+1, Str);
return pStr;
}
// Идентификация первого символа в строке
int SymbolIdentify(char M[][MAX_SYMB_LENGTH], int Size, char **Str)
{
char Symb[MAX_SYMB_LENGTH];
int ind = Size;
if(!**Str) return ind-1;
char *pNextSymb = *Str;
for(unsigned char i=1; (i<=strlen(*Str))&&(i < MAX_SYMB_LENGTH); i++)
{
strncpy_s(Symb, MAX_SYMB_LENGTH, *Str, i);
if(SymbolSearch(M, Size, Symb) < Size)
{
ind = SymbolSearch(M, Size, Symb);
pNextSymb = *Str + i;
}
}
*Str = pNextSymb;
return ind;
}
// Ввод правил переходов
void EnterRules()
{
char Triple [3][MAX_SYMB_LENGTH];
int q, a, z;
memset(func, -1, sizeof(ConfMod)*MAX_SYMB_COUNT*MAX_SYMB_COUNT*MAX_SYMB_COUNT);
system("cls");
do
{
puts("Введите тройку q, a, z для которой создать правило.\nlam - пустая цепочка символов.");
while (true)
{
EnterScores(Triple, 3);
q = SymbolSearch(Q, nQ, Triple[0]);
a = SymbolSearch(Vin, nVin, Triple[1]);
z = SymbolSearch(Z, nZ, Triple[2]);
if ((q==nQ) || (a==nVin) || (z==nZ))
puts("Допущена ошибка! Проверьте, чтобы символы принадлежали своим множествам и повторите ввод.");
else break;
}
puts("Введите новое состояние q' для данного правила.");
func[q][a][z].q = ControlEnterSymbol(Q, nQ);
puts("Введите цепочку магазина");
func[q][a][z].g = ControlEnterString(Z, nZ);
puts("Введите выходную цепочку");
func[q][a][z].y = ControlEnterString(Vout, nVout);
RulesView();
puts("Правило успешно создано");
puts("1 - Ввести новое правило");
puts("2 - Завершить ввод правил");
}
while (_getch()!= '2');
}
// Вывод списка правил на экран
void RulesView()
{
system("cls");
for(int q=0; q<nQ; q++)
for(int a=0; a<nVin; a++)
for(int z=0; z<nZ; z++)
if(func[q][a][z].q!= -1)
{
printf("f(%s, %s, %s) = ", Q[q], Vin[a], Z[z]);
printf("{(%s, ",Q[func[q][a][z].q]);
if(*func[q][a][z].g)
printf("%s, ", func[q][a][z].g);
else printf("lam, ");
if(*func[q][a][z].y)
printf("%s)}\n", func[q][a][z].y);
else printf("lam)}\n");
}
puts("");
}
// Ввод ДМПП с клавиатуры
void EnterAutomate()
{
system("cls");
puts("Ввод состояний");
nQ = EnterScores(Q,MAX_SYMB_COUNT);
puts("Начальное состояние");
q0 = ControlEnterSymbol(Q, nQ);
puts("Ввод конечных состояний");
nF = EnterFinalStates();
puts("Ввод алфавита входного языка");
nVin = EnterScores(Vin, MAX_SYMB_COUNT);
strcpy_s(Vin[nVin], MAX_SYMB_LENGTH, "lam");
nVin++;
puts("Ввод алфавита выходного языка");
nVout = EnterScores(Vout, MAX_SYMB_COUNT);
puts("Ввод алфавита магазина");
nZ = EnterScores(Z, MAX_SYMB_COUNT);
puts("Начальный символ магазина");
z0 = ControlEnterSymbol(Z, nZ);
puts("Ввод правил перехода");
EnterRules();
}
// Вывод мгновенного описания автомата
void PrintConfig(char *w, int q, char *y)
{
printf("(%s, ", Q[q]);
if(!*w) printf("lam, ");
else printf("%s, ", w);
if (!*Stack) printf("lam, ");
else printf("%s, ", Stack);
if(!*y) printf("lam)\n");
else printf("%s)\n", y);
}
// Замена верхнего символа магазина цепочкой из правила перехода
void StackMod(char *g, char *Next)
{
char Buf[MAX_STR_LENGTH];
strcpy_s(Buf, MAX_STR_LENGTH, Next);
strcpy_s(Stack, MAX_STR_LENGTH, g);
strcat_s(Stack, MAX_STR_LENGTH, Buf);
}
// Функция проверки цепочки
int TranslateString()
{
char StrIn[MAX_STR_LENGTH], StrOut[MAX_STR_LENGTH];
StrOut[0] = '\0';
puts("Введите цепочку символов для перевода:");
gets_s(StrIn, MAX_STR_LENGTH-1);
int a, z;
int q = q0; // устанавливаем начальное состояние
strcpy_s(Stack, MAX_STR_LENGTH, Z[z0]); // в магазин помещаем начальный символ
char *w = StrIn; // головку на первый символ цепочки
while(true)
{
PrintConfig(w, q, StrOut); // печатаем МО
if(!*Stack) break; // если магазин опустел - заканчиваем анализ
char *pr = w; // запоминаем текущее расположение головки
// читаем символ, и смещаем головку вправо
if((a = SymbolIdentify(Vin, nVin, &w)) == nVin) return UNDEFINED_SYMBOL; // если не удалось распознать символ цепочки, она не допускается
char *StNext = Stack;
z = SymbolIdentify(Z, nZ, &StNext); // читаем символ магазина
ConfMod NewConf = func[q][a][z];
if(NewConf.q == -1)
{
NewConf = func[q][nVin-1][z];
w = pr; // возвращаем головку на прочтенный символ
if(NewConf.q == -1) return UNDEFINED_STATE;
printf("lam-step: ");
}
q = NewConf.q;
StackMod(NewConf.g, StNext);
strcat_s(StrOut, MAX_STR_LENGTH, NewConf.y);
}
if(*w)return STACK_EMPTY;
for(int i=0; i<nF; i++)
if(q == F[i]) return SUCCESS;
return NO_FINAL_STATE;
}
// Вывод результатов анализа
void ResultMessage(int Result)
{
if(Result!= SUCCESS)
{
puts("Цепочка не принадлежит языку, определяемому данным автоматом! Причина:");
switch(Result)
{
case UNDEFINED_SYMBOL:
puts("Недопустимый символ.");
break;
case UNDEFINED_STATE:
puts("Неопределенное значение для функции перехода.");
break;
case NO_FINAL_STATE:
puts("Автомат не пришел в конечное состояние.");
break;
case STACK_EMPTY:
puts("Опустошение магазина.");
}
}
else puts("Цепочка переведена успешно!");
system("pause");
}
Результаты работы программы
Выполнение перевода τ = {(x,y)| x = 0k1k, y= a2kb2k | k>0}
Ввод преобразователя P =({q0,q1,q2},{0,1},{0,z0},{a,b},δ,q0,z0,{q2})
Ввод списка правил:
Ввод цепочки и результат:
Ввод другой цепочки:
Контрольные вопросы
1. Как поведёт себя преобразователь, если поданная на его вход цепочка не может быть распознана (не принадлежит к заданному языку)?
Ответ: если поданная на вход преобразователя цепочка не может быть распознана, то выйдет предупреждающее сообщение и перевод прекратиться.
2. Как соотносятся алфавиты исходного языка и того, на который выполняется перевод (должны совпадать, различаться…)? Поясните ответ.
Ответ: входной и выходной алфавиты могут полностью совпадать, могут полностью различаться, могут пересекаться. Потому-что при переводе символы входного и выходного алфавита никак не смешиваются (как, например, терминальные и нетерминальные символы грамматики при выводе цепочек), так как перевод осуществляется в отдельную цепочку символов.
3. Как поведёт себя Ваша программа при некорректном вводе? Например, функция переходов задана не в том формате, определена не для того количества параметров, использует алфавит, отличный от заданных…
Ответ: при некорректном вводе программа предложит повторный ввод. Поскольку программа полностью контролирует ввод правил перехода, принадлежность введенных символов своим множествам.
1. Замечание то же, что в работе №2.
2. Плюс к этому следовало проверить программу на контрольных вопросах – этого не сделано. Добавьте скриншоты с решением контрольного вопроса №6 из соответствующего раздела теории.
1. Дан МП-преобразователь: P = ({q},{a,+,*},{+,*,E},{a,+,*},δ, q,E,{q}), где δ определяется равенствами:
| δ(q, *, E) = {(q, EE*, l)} δ(q, l, +) = {(q, l, +)} | δ(q, a, E) = {(q, l, a)} δ(q, +, E) = {(q, EE+, l)} | δ(q, l, *) = {(q, l, *)} |
Выполнить перевод цепочек: а) ’++aaa’; б) ’*+aaa’; в) ’*+aaa’; г) ’+a*aa’.
Федеральное агентство связи
Сибирский Государственный Университет Телекоммуникаций и Информатики