ТВП ЛР3 Фатьков 4936. Отчет защищен с оценкой преподаватель ассистент Кочин Д. А. подпись, дата отчет о лабораторной работе 3 Алгоритмическая система Поста По дисциплине теория вычислительных процессов работу
 Скачать 389.77 Kb.
|
|
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Государственное образовательное учреждение высшего профессионального образования САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ Кафедра компьютерных технологий и программной инженерии (№43) ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ ПРЕПОДАВАТЕЛЬ ассистент ________________________ Кочин Д. А. подпись, дата ОТЧЕТ О ЛАБОРАТОРНОЙ РАБОТЕ №3 Алгоритмическая система Поста По дисциплине: ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ РАБОТУ ВЫПОЛНИЛ СТУДЕНТ ГР. № 4936 4.11.2022 Фатьков Т. В. подпись, дата фамилия, инициалы Санкт-Петербург, 2022 Лабораторная работа №3 «Алгоритмическая система Поста» I. Цель работы Изучить принципы функционирования алгоритмической системы Поста. II. Основные сведения из теории Алгоритмическая система Поста оперирует цепочками символов, и базируется на введенном американским математиком Эмилем Постом понятием формальной системы. Теория формальных систем (ФС) рассматривает только синтаксические свойства изучаемых объектов - слов в некотором абстрактном языке – т.е. математические объекты в ФС понимаются как последовательности символов в некотором фиксированном алфавите, а операции над математическими объектами – операции над символами. Определение: Каноническая система Поста – это кортеж 𝐹𝑆 𝑝 = 𝐴, 𝑋, 𝐴 1 , 𝑅 , где: 𝐴 – собственный алфавит (алфавит констант): 𝐴 = 𝑎 1 , 𝑎 2 , …, 𝑎 𝑚 ; 𝑋 – алфавит переменных: 𝑋 = 𝑥 1 , 𝑥 2 , …, 𝑥 𝑛 ; 𝐴 1 – конечное множество аксиом в алфавите 𝐴 ∪ 𝑋; 𝑅 1 – конечное множество продукций (или правил вывода): 𝛾 1 , …, 𝛾 𝑛 → 𝛿 Определение: Слово 𝛼 получается применением некоторой аксиомы 𝜔 , в том случае, если вместо переменных в 𝜔 подставляются слова из 𝐴 ∗ Определение: Слово 𝛼 непосредственно выводимо из слов 𝛼 1 , …, 𝛼 𝑛 применением продукции 𝑅 𝑖 с 𝑛 -посылок если найдется такая подстановка слов вместо переменных в 𝑅 𝑖 , которая посылки в 𝑅 𝑖 превратит в 𝛼 1 , …, 𝛼 𝑛 , а заключение 𝑅 𝑖 – в слово 𝛼 Определение: Последовательность слов называется доказательством в канонической системе 𝐹𝑆 𝑝 , если каждое слово в этой последовательности: либо результат применения аксиомы, либо непосредственно выводимо из предыдущих слов последовательным применением некоторой продукции системы. Определение: Слово называется доказуемым (или теорией) если оно является последним словом некоторого доказательства. Вычисления в формальной системе Поста как и любые другие вычисления носят дискретный характер. Вычисление в ФС Поста – последовательный вывод с использованием правил (последовательное применение правил). Вычисление происходит до тех пор, пока возможно применить какое-либо правило. Применение правил: Правила выбираются по одному; Каждое правило анализируется на возможность его применения; Если ни одно правило применить нельзя, вычисления прекращаются. Правила должны быть составлены таким образом, что на каждом шаге вычисления, было возможно применить лишь одно правило. Когда найдено правило, которое возможно применить вычисляются значения переменных входящих в левую часть правила. На основе вычисленных значений переменных формируется строка по правой части правила. После того как значения переменных вычислены, в исходной строке происходит замена вычисленной левой части правила на вычисленную правую часть правила. III. Постановка задачи В данной лабораторной работе требуется: Построить формальную систему Поста 𝐹𝑆 𝑝 , реализующую вычисление заданной арифметической функции. Написать программу на языке высокого уровня имитирующую (эмулирующую) вычисления на основе выводимости в формальной системе Поста. Программа должна работать на любых входных данных из заданного множества. Программа должна удовлетворять предъявляемым требованиям. Вариант задания: 40 𝑦 1 − 𝑦 2 ∗ 𝑥 IV. Листинг программы на языке высокого уровня с комментариями Файл main.cpp: #include #include #include #include }); return result; } // Заменяет один паттерн в строке на другой std :: string replace( const std :: string & source, const std :: string & before, const std :: string & after ) { std :: string result{source}; result.replace(result.find(before), before.size(), after); return result; } // Возвращает символы, соответствующие пересечению двух строк std :: string intersect(std::string a, std::string b) { std :: string intersection{}; std ::sort( std ::begin(a), std ::end(a)); std ::sort( std ::begin(b), std ::end(b)); std ::set_intersection( std ::begin(a), std ::end(a), std ::begin(b), std ::end(b), std ::back_inserter(intersection) ); return intersection; } // Возвращает длину самой длинной последовательности одинаковых символов Number longestSequence( char symbol, const std::string& source) { std :: vector 1u l : 0u l}; std ::for_each( std ::cbegin(source), std ::cend(source), [&]( char c) { if (symbol == c) lengths.back()++; else lengths.push_back({}); }); return * std ::max_element( std ::cbegin(lengths), std ::cend(lengths)); } // Функциональный объект, проверяющий строку на соответствие паттерну class StructureMatcher { std :: string mIgnored{}; public : StructureMatcher( const std :: string & ignored) : mIgnored{ignored} {} bool operator() ( const std::string& source, const std::string& pattern) const { std :: string given{}, expected{}; std ::copy_if( std ::cbegin(source), std ::cend(source), std ::back_inserter(given), [&]( char c) { return mIgnored.find(c) == std :: string ::npos; } ); std ::copy_if( std ::cbegin(pattern), std ::cend(pattern), std ::back_inserter(expected), [&]( char c) { return mIgnored.find(c) == std :: string ::npos; } ); return given.find(expected) != std :: string ::npos; } }; // Функциональный объект, находящий значения переменных в строке по паттерну class VariableMatcher { std :: string mNames{}; // Имена переменных // Значения переменных находятся перебором - поиском комбинации class Combination { Variables mVars{}; Number mLimit{}; public : Combination( const std :: string & varNames, Number limit) : mLimit{limit} { std ::for_each( std ::cbegin(varNames), std ::cend(varNames), [&]( const auto & varName) { mVars.insert({varName, 1u l}); } ); } auto current() const { return mVars; } auto next() { (* std ::begin(mVars)).second++; std ::for_each( std ::begin(mVars), std ::end(mVars), [&, carry = false ]( auto & keyValue) mutable { if (carry) { keyValue.second++; carry = false ; } if (keyValue.second > mLimit) { keyValue.second = 1u l; carry = true ; } } ); } auto exhausted() const { return std ::all_of( std ::cbegin(mVars), std ::cend(mVars), [&]( const auto & keyValue) { return keyValue.second >= mLimit; } ); } }; public : VariableMatcher( const std :: string & names) : mNames{names} {} Variables operator() ( const std :: string & source, const std :: string & pattern, Number limit = 128u l ) { Variables v{}; for (Combination c{mNames, limit}; !c.exhausted(); c.next()) if (source.find(fill(pattern, c.current())) != std :: string ::npos) v = c.current(); return v; } }; struct Rule { std :: string before{}, after{}; }; class PostSystem { std :: string mAlphabet{}, mVariables{}, mAxioms{}; std :: vector void validateInput( const std::string& source) { // Проверка на наличие символов не из алфавита в исходной строке if ( auto i = std ::find_if( std ::cbegin(source), std ::cend(source), [&]( char c) { return mAlphabet.find(c) == std :: string ::npos; } ); i != std ::cend(source)) { throw std ::logic_error{ "В исходной строке найден символ \'" + std :: string {*i} + "\', не входящий в алфавит" }; }; } void validateAxioms() { // Проверка на наличие символов не из алфавита в исходной строке auto valid = mAlphabet + mVariables; if ( auto i = std ::find_if( std ::cbegin(mAxioms), std ::cend(mAxioms), [&]( char c) { return valid.find(c) == std :: string ::npos; } ); i != std ::cend(mAxioms)) { throw std ::logic_error{ "В аксиомах найден символ \'" + std :: string {*i} + "\', " + "не входящий в алфавиты констант или переменных" }; }; } void validateRules() { // Проверка на наличие переменных не из множества переменных auto valid = mAlphabet + mVariables; if ( auto i = std ::find_if( std ::cbegin(mRules), std ::cend(mRules), [&]( const auto & rule) { return std ::find_if( std ::cbegin(rule.before), std ::cend(rule.before), [&]( char c) { return valid.find(c) == std :: string ::npos; } ) != std ::cend(rule.before) || std ::find_if( std ::cbegin(rule.after), std ::cend(rule.after), [&]( char c) { return valid.find(c) == std :: string ::npos; } ) != std ::cend(rule.after); } ); i != std ::cend(mRules)) { throw std ::logic_error{ "В правиле \'" + i->before + " -> " + i->after + "\' найден символ, " + "не входящий в алфавиты констант или переменных" }; } } public : PostSystem( const std :: string & alphabet, const std :: string & variables, const std :: string & axioms, const std :: vector ) : mAlphabet{alphabet}, mVariables{variables}, mAxioms{axioms}, mRules{rules} {} // Вычисляет функцию для заданной исходной строки std :: string operator() (std::string source, std::ostream&& out) { validateInput(source); validateAxioms(); validateRules(); auto working = true ; while (working) { working = false ; for ( const auto & rule : mRules) { if (StructureMatcher{mVariables + mAxioms}(source, rule.before)) { if ( auto vars = VariableMatcher{ intersect(mVariables, rule.before) }(source, rule.before, longestSequence( '1' , source)); !vars.empty() ) { out << source << '\n' ; out << rule.before << " -> " << rule.after << '\n' ; source = replace(source, fill(rule.before, vars), fill(rule.after, vars) ); out << source << "\n\n" ; working = true ; } } } } return source; } }; // Структура с входными даными struct InputData { std :: string alphabet{}, variables{}, axioms{}; std :: vector }; // Монструозный парсер текстового файла с входными данными InputData parseInput(std::ifstream&& input) { InputData result{}; auto parseLine = []( const auto & text, auto & current) { std ::copy_if( std ::find( std ::cbegin(text), std ::cend(text), '{' ) + 1 , std ::find( std ::cbegin(text), std ::cend(text), '}' ), std ::back_inserter(current), []( char c) { return ! std :: isspace (c) && c != ',' ; } ); }; std :: string text{ std ::istreambuf_iterator< char >{input}, {}}; parseLine(text, result.alphabet ); text.erase( 0u l, text.find( '\n' ) + 1 ); parseLine(text, result.variables); text.erase( 0u l, text.find( '\n' ) + 1 ); parseLine(text, result.axioms ); text.erase( 0u l, text.find( '\n' ) + 1 ); text.erase( 0u l, text.find( '{' ) + 1 ); text.erase(text.find( '}' )); text.erase( std ::remove_if( std ::begin(text), std ::end(text), []( char c ) { return std :: isspace (c); } ), std ::end(text)); enum class RuleState { Before, After } ruleState{}; for ( auto i = std ::cbegin(text), j = std ::cbegin(text) + 1 ; i != std ::cend(text); ++i, ++j ) { if (*i == '-' && *j == '>' ) { ++i, ++j; ruleState = RuleState::After; } else if (*i == ',' ) { result.rules.push_back({}); ruleState = RuleState::Before; } else { switch (ruleState) { case RuleState::Before: { result.rules.back().before += *i; } break ; case RuleState::After: { result.rules.back().after += *i; } break ; } } } return result; } int main( int argc, char ** argv) { if (argc != 4 ) { std :: cout << "Использование программы:\n" << argv[ 0 ] << " <файл с входными данными> <исходная строка> " << "<имя файла с результатами вычисления>\n" ; return 1 ; } InputData input{}; try { input = parseInput( std ::ifstream{argv[ 1 ]}); } catch (...) { std :: cerr << "При чтении входного файла произошла ошибка\n" << "Проверьте синтаксическую корректность содержимого файла\n" ; return 1 ; } PostSystem postSystem{input.alphabet, input.variables, input.axioms, input.rules}; try { auto result = postSystem(argv[ 2 ], std ::ofstream{argv[ 3 ]}); std :: cout << "Вычисление прошло успешно с результатом: " << result << '\n' ; } catch ( std ::exception& e) { std :: cerr << "В ходе вычисления произошла ошибка:\n" << e.what() << '\n' ; return 1 ; } return 0 ; } Использовался компилятор GCC версии 11.3.0, и компиляция происходила по скрипту: Файл compile.sh: #! /bin/sh g++ main.cpp \ -Wall -Wextra -Wpedantic -Wconversion -Werror \ -std=c++17 \ -o tvp03 -O2 IV. Содержимое входного файла согласно заданию Файл in.txt: A = { 1, *, -, = }; X = { x, y, z }; A1 = { 1 }; R = { x-1y*z= -> x-y*z=z, x-1*z= -> =x-z, =xy-y -> =x }; V. Примеры результатов выполнения Сначала продемонстрируем поведение программы при корректных входных данных: Скомпилируем программу: $ ./compile.sh Для начала запустим ее без аргументов, чтобы получить инструкцию по пользованию: $ ./tvp03 Согласно варианту нужно вычислить функцию 𝑦 1 − 𝑦 2 ∗ 𝑥 Пусть 𝑥 = 3 = 111 1 , 𝑦 1 = 7 = 1111111 1 , 𝑦 2 = 2 = 11 1 . Тогда исходная строка: 1111111-11*111= Запустим программу, указав ей входной файл, исходную строку, а также имя выходного файла: $ ./tvp03 in.txt 1111111-11*111= out.txt Посмотрим на выходной файл out.txt: Строки 1-8 Строки 9-12 1111111-11*111= x-1y*z= -> x-y*z=z 1111111-1*111=111 1111111-1*111=111 x-1*z= -> =x-z =1111111-111111 =1111111-111111 =xy-y -> =x =1 Пусть 𝑥 = 9 = 111111111 1 , 𝑦 1 = 12 = 111111111111 1 , 𝑦 2 = 1 = 1 1 . Тогда исходная строка: 111111111111-1*111111111= Запустим программу, указав ей входной файл, исходную строку, а также имя выходного файла: $ ./tvp03 in.txt 111111111111-1*111111111= out.txt Посмотрим на выходной файл out.txt: Строки 1-8 111111111111-1*111111111= x-1*z= -> =x-z =111111111111-111111111 =111111111111-111111111 =xy-y -> =x =111 Пусть 𝑥 = 4 = 1111 1 , 𝑦 1 = 18 = 111111111111111111 1 , 𝑦 2 = 4 = 11111 1 . Тогда исходная строка: 111111111111111111-1111*1111= Запустим программу, указав ей входной файл, исходную строку, а также имя выходного файла: $ ./tvp03 in.txt 111111111111111111-1111*1111= out.txt Посмотрим на выходной файл out.txt: Строки 1-12 Строки 12-20 111111111111111111-1111*1111= x-1y*z= -> x-y*z=z 111111111111111111-111*1111=1111 111111111111111111-111*1111=1111 x-1y*z= -> x-y*z=z 111111111111111111-11*1111=11111111 111111111111111111-11*1111=11111111 x-1y*z= -> x-y*z=z 111111111111111111-1*1111=111111111111 111111111111111111-1*1111=111111111111 x-1*z= -> =x-z =111111111111111111-1111111111111111 =111111111111111111-1111111111111111 =xy-y -> =x =11 Теперь проверим поведение программы при некорректных входных данных.\ Не меняя содержимого входного файла in.txt, впишем в исходную строку символ «!», не входящий ни в алфавит констант, ни в алфавит переменных: $ ./tvp03 in.txt 11111-11*11!= out.txt Изменим содержимое входного файла in.txt – впишем в аксиомы символ «?», не входящий ни в алфавит констант, ни в алфавит переменных: Файл in2.txt: A = { 1, *, -, = }; X = { x, y, z }; A1 = { 1, ? }; R = { x-1y*z= -> x-y*z=z, x-1*z= -> =x-z, =xy-y -> =x }; Запустим программу: $ ./tvp03 in2.txt 11111-11*11= out.txt Наконец, во входном файле укажем в правилах символ, не входящий ни в алфавит констант, ни в алфавит переменных: Файл in3.txt: A = { 1, *, -, = }; X = { x, y, z }; A1 = { 1 }; R = { x-1y*z= -> x-y*z=$, x-1*z= -> =x-z, =xy-y -> =x }; Запустим программу: $ ./tvp03 in3.txt 11111-11*11= out.txt VI. Вывод В результате выполнения данной лабораторной работы я изучил принципы функционирования функционирования алгоритмической системы Поста. |