Здравствуйте, FR, Вы писали:

FR>Здравствуйте, Курилка, Вы писали:

К>>В том и смысл, что мощность машины Тьюринга избыточна, по меньшей мере для большинства задач.

FR>Есть куча задач где она недостаточна, ждем квантовые вычислители.
Т.е. есть более мощная вычислительная модель чем МТ?
Расскажи.
FR>Вообще прикольно математики уже сдаются, становятся "физиками" а CS'ники все еще барахтаются
Смысла предложения не понял

К>>Как пример — реальные машины не обладают бесконечной памятью (в отличие от классической МТ с бесконечной лентой)

FR>Ну для большинства задач вполне обладают.

Раскрой

Здравствуйте, Курилка, Вы писали:

FR>>Есть куча задач где она недостаточна, ждем квантовые вычислители.
К>Т.е. есть более мощная вычислительная модель чем МТ?
К>Расскажи.

Квантовые вычисления мощнее так как позволяют в общем случае проводить вычисления которые
невозможны в машине Тьюринга, за подробностями гугли Пенроуза.

FR>>Вообще прикольно математики уже сдаются, становятся "физиками" а CS'ники все еще барахтаются
К>Смысла предложения не понял

тут http://elementy.ru/lib/430319

Иными словами, при любом конечном наборе аксиом мы имеем бесконечное число истин, которые не могут быть доказаны с помощью этого набора.

Из неприводимости числа Ω следует, что всеобъемлющей математической теории существовать не может. Бесконечное множество битов Ω составляет бесконечное множество математических фактов (является ли каждый выбранный бит единицей или нулем), которые не могут быть выведены из каких бы то ни было принципов, более простых, чем сама последовательность битов. Значит, сложность математики бесконечна, тогда как любая отдельная теория «всего на свете» характеризуется конечной сложностью и, следовательно, не может охватить все богатство мира математических истин.

К>Раскрой

2^32 это очень не мало

Здравствуйте, FR, Вы писали:

FR>Здравствуйте, Курилка, Вы писали:

FR>>>Есть куча задач где она недостаточна, ждем квантовые вычислители.
К>>Т.е. есть более мощная вычислительная модель чем МТ?
К>>Расскажи.

FR>Квантовые вычисления мощнее так как позволяют в общем случае проводить вычисления которые
FR>невозможны в машине Тьюринга, за подробностями гугли Пенроуза.

Ммм, как-то не очень внятно, но допустим.

FR>>>Вообще прикольно математики уже сдаются, становятся "физиками" а CS'ники все еще барахтаются
К>>Смысла предложения не понял

FR>тут http://elementy.ru/lib/430319

FR>

FR>Иными словами, при любом конечном наборе аксиом мы имеем бесконечное число истин, которые не могут быть доказаны с помощью этого набора.

А также бесконечное число истин, которые могу быть доказаны

FR>

FR>Из неприводимости числа Ω следует, что всеобъемлющей математической теории существовать не может. Бесконечное множество битов Ω составляет бесконечное множество математических фактов (является ли каждый выбранный бит единицей или нулем), которые не могут быть выведены из каких бы то ни было принципов, более простых, чем сама последовательность битов. Значит, сложность математики бесконечна, тогда как любая отдельная теория «всего на свете» характеризуется конечной сложностью и, следовательно, не может охватить все богатство мира математических истин.

И в каком месте математики становятся "физиками"?

К>>Раскрой

FR>2^32 это очень не мало

Много и бесконечно — это довольно разные вещи.
Для вычисления "больших" задач бесконечная лента не нужна.

Здравствуйте, FR, Вы писали:

FR>>>Есть куча задач где она недостаточна, ждем квантовые вычислители.
К>>Т.е. есть более мощная вычислительная модель чем МТ?
К>>Расскажи.
FR>Квантовые вычисления мощнее так как позволяют в общем случае проводить вычисления которые
FR>невозможны в машине Тьюринга, за подробностями гугли Пенроуза.

Что-то я у Пенроуза видел только предположения, что может существовать вычислительный квантовый процесс, превосходящий МТ. Типа, что он сможет придумывать новые истинные аксиомы, как это делают люди. Но ничего конкретного.

Разрабатываемые (и мыслимые) сейчас квантовые компьютеры не превосходят МТ.

Здравствуйте, FR, Вы писали:

FR>Здравствуйте, Курилка, Вы писали:

FR>>>Есть куча задач где она недостаточна, ждем квантовые вычислители.
К>>Т.е. есть более мощная вычислительная модель чем МТ?
К>>Расскажи.

FR>Квантовые вычисления мощнее так как позволяют в общем случае проводить вычисления которые
FR>невозможны в машине Тьюринга, за подробностями гугли Пенроуза.

вики, конечно, стрёмный источник, но всёж:

Although quantum computers may be faster than classical computers, those described above can't solve any problems that classical computers can't solve, given enough time and memory (albeit possibly an amount that could never practically be brought to bear).

По-моему ты подмешиваешь к просто мощности вычислительной модели (т.е. вопрос принципиальной выразимости выч. задач) ещё её скорость. Конечно, с практической т.зр. вопрос очень важный, но речь вроде не о нём шла.
Плюс я не уверен, что принципы TFP не применимы к квантовым вычислениям (хотя зарекаться не буду, т.к. не очень в них разбираюсь)

Здравствуйте, Курилка, Вы писали:

К>Ммм, как-то не очень внятно, но допустим.

Внятнее тут http://ru.wikipedia.org/wiki/Алгоритмическая_неразрешимость

Важно отметить, что множество программ для этого исполнителя (например, множество машин Тьюринга при фиксированном алфавите входных и выходных данных) счётно. Поэтому вычислимых функций не более чем счётно. В то время как множество функций вида несчётно, если N счётно. Значит есть не вычислимые функции, причём их мощность больше, чем мощность вычислимых функций.

К>А также бесконечное число истин, которые могу быть доказаны

Смотри цитату выше, это разные бесконечности
Те которые можно доказать счетны, а недоказуемые (на данном наборе аксиом) нечетны, разница как между конечным и бесконечным.

К>И в каком месте математики становятся "физиками"?

В таком что математика такая же эксперементальная наука как и все остальные, с нее сняли корону

FR>>2^32 это очень не мало

К>Много и бесконечно — это довольно разные вещи.

Угу

К>Для вычисления "больших" задач бесконечная лента не нужна.

От задач зависит

Здравствуйте, FR, Вы писали:

FR>Смотри цитату выше, это разные бесконечности
FR>Те которые можно доказать счетны, а недоказуемые (на данном наборе аксиом) нечетны, разница как между конечным и бесконечным.

Не совсем так. Оба этих множества счетны, так как являются подмножествами счетного множества well-formed формул. Только множество доказуемых истин recursively enumerable, а недоказуемых — нет.

Здравствуйте, nikov, Вы писали:


N>Что-то я у Пенроуза видел только предположения, что может существовать вычислительный квантовый процесс, превосходящий МТ. Типа, что он сможет придумывать новые истинные аксиомы, как это делают люди. Но ничего конкретного.

Угу.

N>Разрабатываемые (и мыслимые) сейчас квантовые компьютеры не превосходят МТ.

А вот это не доказано, есть только тезис Тьюринга, который не больше чем гипотеза.

Здравствуйте, Курилка, Вы писали:

К>По-моему ты подмешиваешь к просто мощности вычислительной модели (т.е. вопрос принципиальной выразимости выч. задач) ещё её скорость. Конечно, с практической т.зр. вопрос очень важный, но речь вроде не о нём шла.
К>Плюс я не уверен, что принципы TFP не применимы к квантовым вычислениям (хотя зарекаться не буду, т.к. не очень в них разбираюсь)

Насколько я понимаю никто пока ни доказал что квантовые вычисления эквивалентны машине Тьюринга, обратное тоже не доказано.

А с практической точки зрения никакие квантовые вычислители не нужны, достаточно аппаратной реализации недетерминированной машины Тьюринга http://ru.wikipedia.org/wiki/Недетерминированная_машина_Тьюринга (котороая теоретически равномощна обычной машине)

Здравствуйте, Курилка, Вы писали:

GC>>Имеем O** = 3 * E + 2.

К>O** = 3 * 3 + 2 = 11

GC>>Число O** — тоже четное по тем же причинам.

К>11 — чётное?
К>(ну и хотелось бы услышать, что за "те же причины")

Да, здесь ошибка, признаю.

O = 2 * E + 1

где O — нечетное число,
четным здесь является 2 * E — по определению,
а вот само E может быть как четным, так и нет

O* я вычислил правильно, но вот O** — неправильно.

Не получилось доказать. Бывает.

Здравствуйте, nikov, Вы писали:

N>Не совсем так. Оба этих множества счетны, так как являются подмножествами счетного множества well-formed формул. Только множество доказуемых истин recursively enumerable, а недоказуемых — нет.

А разве общее множество всех формул не несчетно?

Здравствуйте, Tissot, Вы писали:

T>Здравствуйте, GhostCoders, Вы писали:

GC>>Реализовал транслятор простейшего языка программирования.
GC>>Для целей тестирования алгоритма, который определеят зависает ли определенная программа,
GC>>и если зависает то на каких наборах данных.

T>Проверьте вашей программой вашу же программу

Нельзя по одной причине. Скажем моя программа состоит из С байт выполнимого кода и D байт обрабатываемых данных.
Если ее натравить саму на себя мы должны весь код программы и ее все данные передавать как данные в саму себя, то есть

D* = C + D

D** = C + D**

то есть вывод такой сама себя она не может анализировать.

Здравствуйте, FR, Вы писали:

FR>Здравствуйте, nikov, Вы писали:

N>>Не совсем так. Оба этих множества счетны, так как являются подмножествами счетного множества well-formed формул. Только множество доказуемых истин recursively enumerable, а недоказуемых — нет.

FR>А разве общее множество всех формул не несчетно?

Ну по идее есть же Гёделева нумерация (базис доказательства теоремы Гёделя), так что вполне себе счётно.

GhostCoders wrote:

> Не получилось доказать. Бывает.
А зачем ты сам пытаешься доказать? У тебя же есть этот простейший язык. Или внутре его неонка?

Здравствуйте, ., Вы писали:

.>GhostCoders wrote:

>> Не получилось доказать. Бывает.
.>А зачем ты сам пытаешься доказать? У тебя же есть этот простейший язык. Или внутре его неонка?

Я хочу вам показать одну вещь.
Есть БОЛЬШАЯ разница между абстрактным алгоритмом вообще и его реализаией на реальной вычислительной машине.

Абстрактные алгоритмы используют понятие числа, переменной и т.д.
Но никто эти числа не ограничивает никак. В вычислителных машинах мы используем ограниченные области памяти для
хранения чисел — байты, слова, 32 битные значения, сейчас уже на 64 бит перешли.
Вот в этом и главная разница. Абстрактный алгоритм может уйти в бесконечность,
наш же реальный переполнится в какой-либо переменной, после максимального значения, переменная установиться в значение 0.

С помощью простейшего языка я методом перебора могу тебе дать гарантию что он не зависнит, например, на 10000 входных значений.

Здравствуйте, Курилка, Вы писали:

FR>>А разве общее множество всех формул не несчетно?

К>Ну по идее есть же Гёделева нумерация (базис доказательства теоремы Гёделя), так что вполне себе счётно.

Склероз мне подсказывает теорему Кантора
И этот же склероз подсказывает что Геделева нумерация как раз и выделяет счетное подмножество вычислимых формул из общего несчетного множества формул вообще (под формулой имеется в виду отображение счетного множества на четное же множество)

Выкладываю реализацию транслятора простейшего языка на С++
вместе с анализатором.

Код написал за 3-4 часа, качество, признаюсь УЖАСНОЕ, не до того было.
Он позволяет понять суть моего метода.

Это консольное приложение на С++. Аргументы командной строки следующие:
SimpleLanguageCompiler.exe имя_файла_на_простейшем_языке команда_что_делать

где
имя_файла_на_простейшем_языке — файл должен существовать и содержать в себе валидный текст на языке SL
команда_что_делать ключевое слово из следующих:
COMPILEONLY — транслирует входной текст на язык С++ (на выходе имеем файл с расширением .cpp),
который реализует данный алгоритм на SL
Этот файл можно откомпилировать компилятором MSVC (и думаю GCC тоже),
получить исполняемый .exe файл, который попросит у вас ввести все
значения для исходных переменных, начнет вычисление, и если алгортм не зависает,
в конце вычислений выдаст на экран значения результатов
(OUTPUT-переменные объявленные в заголовке программы)
Замечание. Компилировать этот .cpp файл можно из командной строки,
предварительно набрав: "%VS80COMNTOOLS%\vsvars32.bat"
что даст доступным компилятор cl.exe из командной строки,
потом вводим cl имя_файла.cpp
он компилируется, запускаем программу имя_файла.exe
и наслаждаемся результатом.

В этом режиме никаких проверок и анализов не производиться.

COMPILEWITHVALIDATE — подобно COMPILEONLY, только вставляется код для защиты от зависаний.
Если обнаружено зависание, на экран выведется соответствующее сообщение, и программа
терминирует.

TEST — получается файл, который тестирует программу на всех наборах значений. Выдает все значения
при которых программа зависает на экран. В конце выдает небольшую "статистику".


Хочется сказать, что многие программисты, изучая в институте машину Тьюринга,
конечно слышили о проблеме неразрешимости, так же как и о "вечном двигателе" и попытках создать его.
Но есть одно НО, машина Тьюринга бесконечна, для конечных машин, проблема зависания все же
РАЗРЕШИМА, хотя бы в теории. Про это обычно забывают, и в английской вики про это пишут,
что это распространенное заблуждение, что неразрешимость проблемы машины Тьюринга переносят
на конечные компьютеры. http://en.wikipedia.org/wiki/Halting_problem — сомтрите "Common pitfalls".

The halting problem is, in theory if not in practice, decidable for linear bounded automata (LBAs), or deterministic machines with finite memory. A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state:

"...any finite-state machine, if left completely to itself, will fall eventually into a perfectly periodic repetitive pattern. The duration of this repeating pattern cannot exceed the number of internal states of the machine..."(italics in original, Minsky 1967, p. 24)

Смысл в следующем. Что цикл зависания не может превосходить число внутренних состояний такой машины.

Ну а вот исходный текст АНАЛИЗАТОРА:

/*
* Copyright (c) 2009 by
* IP PETROV PETR PETROVICH.
* All Rights Reserved
*
* This software comprises unpublished confidential information
* including intellectual property of IP PETROV PETR PETROVICH.
* and may not be used, copied or made available to anyone, except in
* accordance with the licence under which it is furnished.
*
*/

#include "stdafx.h"

#define INT8 0
#define UINT8 1

int typec = 0; // 0 -compile. 1- validate, 2 — test

struct subprogram
{
std::string name;
std::vector<std::string> inputNames;
std::set<std::string> sinputNames;
std::vector<int> inputTypes;
std::vector<std::string> outputNames;
std::set<std::string> soutputNames;
std::vector<int> outputTypes;
std::vector<std::string> varNames;
std::set<std::string> svarNames;
std::vector<int> varTypes;
};

std::vector<subprogram> subprograms;
std::vector<subprogram> programs;
std::set<std::string> subprogram_names;
std::set<std::string> program_names;
std::string curContext;

int counter = 0;

void _fillstate(FILE* f,FILE* o)
{
counter++;

subprogram * sp = 0;

for(size_t i=0;i<subprograms.size();i++)
{
if (subprograms[i].name == curContext)
{
sp = &(subprograms[i]);
break;
}
}
for(size_t i=0;i<programs.size();i++)
{
if (programs[i].name == curContext)
{
sp = &(programs[i]);
break;
}
}
fprintf(o,"\t_curstate.line = %d;\n",counter++);

fprintf(o,"\t_curstate.variables.clear();\n",counter++);
for(size_t i=0;i<sp->inputNames.size();i++)
{
fprintf(o,"\t_curstate.variables.push_back(%s);\n",sp->inputNames[i].c_str());
}
for(size_t i=0;i<sp->outputNames.size();i++)
{
fprintf(o,"\t_curstate.variables.push_back(%s);\n",sp->outputNames[i].c_str());
}
for(size_t i=0;i<sp->varNames.size();i++)
{
fprintf(o,"\t_curstate.variables.push_back(%s);\n",sp->varNames[i].c_str());
}
}

void __check(FILE* f,FILE* o)
{
if (0 != typec)
{
_fillstate(f,o);
fprintf(o,"\t__check(&_curstate);\n");
}
}

int _subprogram(FILE* f,FILE* o,bool is_subprogram = true)
{
subprogram newSubprogram;
char name[5000] = { 0 };
fscanf(f,"%s",name);
if (subprogram_names.find(std::string(name)) != subprogram_names.end())
{
printf("error: subprogram %s is always defined\n",name);
return 0;
}
if (program_names.find(std::string(name)) != program_names.end())
{
printf("error: subprogram %s is always defined\n",name);
return 0;
}
curContext = std::string(name);
newSubprogram.name = std::string(name);
char next[5000] = { 0 };
fscanf(f,"%s",next);
while(strcmp(next,"BEGIN"))
{
if (!strcmp(next,"INPUT"))
{
char iname[5000] = { 0 };
fscanf(f,"%s",iname);
if (newSubprogram.sinputNames.find(std::string(iname)) != newSubprogram.sinputNames.end())
{
printf("error: input argument's name %s is always used\n",iname);
return 0;
}
if (newSubprogram.soutputNames.find(std::string(iname)) != newSubprogram.soutputNames.end())
{
printf("error: input argument's name %s is always used\n",iname);
return 0;
}
if (newSubprogram.svarNames.find(std::string(iname)) != newSubprogram.svarNames.end())
{
printf("error: input argument's name %s is always used\n",iname);
return 0;
}
newSubprogram.sinputNames.insert(std::string(iname));
newSubprogram.inputNames.push_back(std::string(iname));
char typeKeyword[5000] = { 0 };
fscanf(f,"%s",typeKeyword);
if (strcmp(typeKeyword,"TYPE"))
{
printf("error: TYPE keyword is absent\n");
return 0;
}
char _typename[5000] = { 0 };
fscanf(f,"%s",_typename);
if (!strcmp(_typename,"int8"))
{
newSubprogram.inputTypes.push_back(INT8);
}else
if (!strcmp(_typename,"uint8"))
{
newSubprogram.inputTypes.push_back(UINT8);
}else
{
printf("error: unknown type %s\n",_typename);
return 0;
}
}else
if (!strcmp(next,"OUTPUT"))
{
char oname[5000] = { 0 };
fscanf(f,"%s",oname);
if (newSubprogram.sinputNames.find(std::string(oname)) != newSubprogram.sinputNames.end())
{
printf("error: output argument's name %s is always used\n",oname);
return 0;
}
if (newSubprogram.soutputNames.find(std::string(oname)) != newSubprogram.soutputNames.end())
{
printf("error: output argument's name %s is always used\n",oname);
return 0;
}
if (newSubprogram.svarNames.find(std::string(oname)) != newSubprogram.svarNames.end())
{
printf("error: output argument's name %s is always used\n",oname);
return 0;
}
newSubprogram.soutputNames.insert(std::string(oname));
newSubprogram.outputNames.push_back(std::string(oname));
char typeKeyword[5000] = { 0 };
fscanf(f,"%s",typeKeyword);
if (strcmp(typeKeyword,"TYPE"))
{
printf("error: TYPE keyword is absent\n");
return 0;
}
char _typename[5000] = { 0 };
fscanf(f,"%s",_typename);
if (!strcmp(_typename,"int8"))
{
newSubprogram.outputTypes.push_back(INT8);
}else
if (!strcmp(_typename,"uint8"))
{
newSubprogram.outputTypes.push_back(UINT8);
}else
{
printf("error: unknown type %s\n",_typename);
return 0;
}
}else
if (!strcmp(next,"VAR"))
{
char vname[5000] = { 0 };
fscanf(f,"%s",vname);
if (newSubprogram.sinputNames.find(std::string(vname)) != newSubprogram.sinputNames.end())
{
printf("error: variable's name %s is always used\n",vname);
return 0;
}
if (newSubprogram.soutputNames.find(std::string(vname)) != newSubprogram.soutputNames.end())
{
printf("error: variable's name %s is always used\n",vname);
return 0;
}
if (newSubprogram.svarNames.find(std::string(vname)) != newSubprogram.svarNames.end())
{
printf("error: variable's name %s is always used\n",vname);
return 0;
}
newSubprogram.svarNames.insert(std::string(vname));
newSubprogram.varNames.push_back(std::string(vname));
char typeKeyword[5000] = { 0 };
fscanf(f,"%s",typeKeyword);
if (strcmp(typeKeyword,"TYPE"))
{
printf("error: TYPE keyword is absent\n");
return 0;
}
char _typename[5000] = { 0 };
fscanf(f,"%s",_typename);
if (!strcmp(_typename,"int8"))
{
newSubprogram.varTypes.push_back(INT8);
}else
if (!strcmp(_typename,"uint8"))
{
newSubprogram.varTypes.push_back(UINT8);
}else
{
printf("error: unknown type %s\n",_typename);
return 0;
}
}else
if (strcmp(next,"BEGIN"))
{
printf("error: waiting for BEGIN token\n");
return 0;
}
fscanf(f,"%s",next);
}

if (is_subprogram)
{
subprograms.push_back(newSubprogram);
subprogram_names.insert(std::string(name));
}else
{
programs.push_back(newSubprogram);
program_names.insert(std::string(name));
}

fprintf(o,"void %s (",name);
for(size_t i=0;i<newSubprogram.inputNames.size();i++)
{
if (newSubprogram.inputTypes[i] == INT8)
{
fprintf(o,"char ");
}else
if (newSubprogram.inputTypes[i] == UINT8)
{
fprintf(o,"unsigned char ");
}
fprintf(o,"&%s",newSubprogram.inputNames[i].c_str());
fprintf(o,", ");
}
for(size_t i=0;i<newSubprogram.outputNames.size();i++)
{
if (newSubprogram.outputTypes[i] == INT8)
{
fprintf(o,"char ");
}else
if (newSubprogram.outputTypes[i] == UINT8)
{
fprintf(o,"unsigned char ");
}
fprintf(o,"&%s",newSubprogram.outputNames[i].c_str());
fprintf(o,", ");
}

fprintf(o,"void* __dummy)\n");
fprintf(o,"{\n");

for(size_t i=0;i<newSubprogram.varNames.size();i++)
{
if (newSubprogram.varTypes[i] == INT8)
{
fprintf(o,"\tstatic char ");
}else
if (newSubprogram.varTypes[i] == UINT8)
{
fprintf(o,"\tstatic unsigned char ");
}
fprintf(o,"%s = 0;\n",newSubprogram.varNames[i].c_str());
}
for(size_t i=0;i<newSubprogram.outputNames.size();i++)
{
fprintf(o,"\t%s = 0;\n",newSubprogram.outputNames[i].c_str());
}
return 0;
}

void _inco(FILE* f,FILE *o)
{
__check(f,o);

char vname[5000] = { 0 };
fscanf(f,"%s",vname);

fprintf(o,"\t%s++;\n",vname);

}

void _deco(FILE* f,FILE *o)
{
__check(f,o);

char vname[5000] = { 0 };
fscanf(f,"%s",vname);

fprintf(o,"\t%s--;\n",vname);
}

void _mulo(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
char vname3[5000] = { 0 };
fscanf(f,"%s",vname3);

fprintf(o,"\t%s = %s * %s;\n",vname1,vname2,vname3);
}

void _set(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
fprintf(o,"\t%s = %s;\n",vname1,vname2);
}

void _let(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
fprintf(o,"\t%s = %s;\n",vname1,vname2);
}


void _divo(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
char vname3[5000] = { 0 };
fscanf(f,"%s",vname3);

fprintf(o,"\t%s = %s / %s;\n",vname1,vname2,vname3);
}

void _modo(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
char vname3[5000] = { 0 };
fscanf(f,"%s",vname3);

fprintf(o,"\t%s = %s %% %s;\n",vname1,vname2,vname3);
}

void _addo(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
char vname3[5000] = { 0 };
fscanf(f,"%s",vname3);

fprintf(o,"\t%s = %s + %s;\n",vname1,vname2,vname3);
}

void _subo(FILE *f,FILE* o)
{
__check(f,o);

char vname1[5000] = { 0 };
fscanf(f,"%s",vname1);
char vname2[5000] = { 0 };
fscanf(f,"%s",vname2);
char vname3[5000] = { 0 };
fscanf(f,"%s",vname3);

fprintf(o,"\t%s = %s — %s;\n",vname1,vname2,vname3);
}

void _label(FILE *f,FILE* o)
{
__check(f,o);

char name[5000] = { 0 };
fscanf(f,"%s",name);

fprintf(o,"label_%s_%s:\n",curContext.c_str(),name);
}

void _goto(FILE *f,FILE* o)
{
__check(f,o);

char name[5000] = { 0 };
fscanf(f,"%s",name);

fprintf(o,"\tgoto label_%s_%s;\n",curContext.c_str(),name);
}

void _ifequal(FILE *f,FILE* o)
{
__check(f,o);

char a1[5000] = { 0 };
fscanf(f,"%s",a1);
char a2[5000] = { 0 };
fscanf(f,"%s",a2);

fprintf(o,"\tif( %s == %s ) {\n\t",a1,a2);

char gotoK[5000] = { 0 };
fscanf(f,"%s",gotoK);
if (strcmp(gotoK,"GOTO"))
{
printf("error: waiting for GOTO keyword\n");
}

_goto(f,o);
fprintf(o,"\t}\n");

char e[5000] = { 0 };
fscanf(f,"%s",e);
if (!strcmp(e,"ELSE"))
{
fprintf(o,"\telse { \n\t");
_goto(f,o);
fprintf(o,"\t}\n");
}else
{
}
}

void _ifgreat(FILE *f,FILE* o)
{
__check(f,o);

char a1[5000] = { 0 };
fscanf(f,"%s",a1);
char a2[5000] = { 0 };
fscanf(f,"%s",a2);

fprintf(o,"\tif( %s > %s ) {\n\t",a1,a2);

char gotoK[5000] = { 0 };
fscanf(f,"%s",gotoK);
if (strcmp(gotoK,"GOTO"))
{
printf("error: waiting for GOTO keyword\n");
}

_goto(f,o);
fprintf(o,"\t}\n");

char e[5000] = { 0 };
fscanf(f,"%s",e);
if (!strcmp(e,"ELSE"))
{
fprintf(o,"\telse { \n\t");
_goto(f,o);
fprintf(o,"\t}\n");
}else
{
}
}

void _ifless(FILE *f,FILE* o)
{
__check(f,o);

char a1[5000] = { 0 };
fscanf(f,"%s",a1);
char a2[5000] = { 0 };
fscanf(f,"%s",a2);

fprintf(o,"\tif( %s < %s ) {\n\t",a1,a2);

char gotoK[5000] = { 0 };
fscanf(f,"%s",gotoK);
if (strcmp(gotoK,"GOTO"))
{
printf("error: waiting for GOTO keyword\n");
}

_goto(f,o);
fprintf(o,"\t}\n");

char e[5000] = { 0 };
fscanf(f,"%s",e);
if (!strcmp(e,"ELSE"))
{
fprintf(o,"\telse { \n\t");
_goto(f,o);
fprintf(o,"\t}\n");
}else
{
}
}

void _call(FILE *f,FILE* o)
{
__check(f,o);

char fname[5000] = { 0 };
fscanf(f,"%s",fname);

if (subprogram_names.find(std::string(fname)) != subprogram_names.end() )
{
for(size_t i=0;i<subprograms.size();i++)
{
if (subprograms[i].name == std::string(fname))
{
int ac = subprograms[i].inputNames.size() + subprograms[i].outputNames.size();
fprintf(o,"\t%s ( ",fname);
for(int k=0;k<ac;k++)
{
char an[5000] = { 0 };
fscanf(f,"%s",an);
fprintf(o,"%s,",an);
}
fprintf(o,"0);\n");

break;
}
}
}else
{
printf("error: subprogram is not founded %s\n",fname);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
printf("Simple Language Translator 1.0\n");
printf("Copyright (c) 2009 by\n");
printf("IP PETR PETROV PETROVICH.\n");
printf("All Rights Reserved.\n\n");

if (argc < 3)
{
printf("Usage: inputfilename.sl ACTION\n");
printf("\there ACTION can be the following:\n");
printf("\tCOMPILEONLY: A Simple Language Program will be compiled to C++ only\n");
printf("\tCOMPILEWITHVALIDATE: A Simple Language Program will be compiled to C++ with Halt-detection code\n");
printf("\tTEST: A simple Language Program will be tested (analised)\n");
return 0;
}

if (!strcmp(argv[2],"COMPILEONLY"))
{
typec = 0;
}else
if (!strcmp(argv[2],"COMPILEWITHVALIDATE"))
{
typec = 1;
}else
if (!strcmp(argv[2],"TEST"))
{
typec = 2;
}else
{
printf("error: incorrect mode\n");
return 0;
}


FILE *f = fopen(argv[1],"rt");
if (0 == f)
{
printf("Could not open input file.\n");
return 0;
}

std::string outfilename = std::string(argv[1]) + std::string(".cpp");
FILE *o = fopen(outfilename.c_str(),"wt");

if (0 == o)
{
printf("Could not create output file.\n");
return 0;
}

fprintf(o,"// This file was generated by Simple Language Translator 1.0\n");
fprintf(o,"// DO NOT EDIT THIS FILE\n\n");

fprintf(o,"#include <stdio.h>\n\n");

//!!!!
if (0 != typec)
{
fprintf(o,"#include <vector>\n\n");
fprintf(o,"struct _state{\n");
fprintf(o,"\tstd::vector<int> variables;\n");
fprintf(o,"\tint line;\n");
fprintf(o,"};\n\n");

fprintf(o,"std::vector<_state> _states;\n\n");

fprintf(o,"bool __compare(_state* s1,_state* s2)\n");
fprintf(o,"{\n");
fprintf(o,"\tif (s1->variables.size() != s2->variables.size()) return false;\n");
fprintf(o,"\tif (s1->line != s2->line) return false;\n");
fprintf(o,"\tfor(size_t i=0;i<s1->variables.size();i++)\n");
fprintf(o,"\t{\n");
fprintf(o,"\t\tif (s1->variables[i] != s2->variables[i]) return false;\n");
fprintf(o,"\t}\n");
fprintf(o,"\treturn true;\n");
fprintf(o,"}\n");

fprintf(o,"void __check(_state* s)\n");
fprintf(o,"{\n");
fprintf(o,"\tfor(size_t i=0;i<_states.size();i++)\n");
fprintf(o,"\t{\n");
fprintf(o,"\t\tif (__compare(s,&_states[i])) {\n");
if (1 == typec)
{
fprintf(o,"\t\t\tprintf(\"program has halted!\\n\");\n");
fprintf(o,"\t\t\texit(1);\n");
}else
if (2 == typec)
{
fprintf(o,"\t\t\tthrow int(1);\n");
}
fprintf(o,"\t\t}\n");
fprintf(o,"\t}\n");
fprintf(o,"\t_states.push_back(*s);\n");
fprintf(o,"}\n\n");
fprintf(o,"_state _curstate;\n");
}

bool comment = false;
bool wasprogram = false;
while(!feof(f))
{
char buff[5000] = { 0 };
fscanf(f,"%s",buff);

if (!strcmp(buff,"*"))
{
comment = !comment;
}else
{
if (!comment)
{
if (!strcmp(buff,"SUBPROGRAM"))
{
_subprogram(f,o,true);
}else
if (!strcmp(buff,"PROGRAM"))
{
if (!wasprogram)
{
_subprogram(f,o,false);
wasprogram = true;
}else
{
printf("error: a program must be one in file\n");
return 0;
}
}else
if (!strcmp(buff,"INC"))
{
_inco(f,o);
}else
if (!strcmp(buff,"DEC"))
{
_deco(f,o);
}else
if (!strcmp(buff,"MUL"))
{
_mulo(f,o);
}else
if (!strcmp(buff,"DIV"))
{
_divo(f,o);
}else
if (!strcmp(buff,"MOD"))
{
_modo(f,o);
}else
if (!strcmp(buff,"ADD"))
{
_addo(f,o);
}else
if (!strcmp(buff,"SUB"))
{
_subo(f,o);
}else
if (!strcmp(buff,"LABEL"))
{
_label(f,o);
}else
if (!strcmp(buff,"GOTO"))
{
_goto(f,o);
}else
if (!strcmp(buff,"IFEQUAL"))
{
_ifequal(f,o);
}else
if (!strcmp(buff,"IFGREAT"))
{
_ifgreat(f,o);
}else
if (!strcmp(buff,"IFLESS"))
{
_ifless(f,o);
}else
if (!strcmp(buff,"CALL"))
{
_call(f,o);
}else
if (!strcmp(buff,"SET"))
{
_set(f,o);
}else
if (!strcmp(buff,"LET"))
{
_let(f,o);
}else
if (!strcmp(buff,"END"))
{
fprintf(o,"\t;\n}\n");
}
}
}

//fprintf(o,"//%s\n",buff);
}

fprintf(o,"int main(int argc,char **argv)\n");
fprintf(o,"{\n");

if (0 == programs.size())
{
printf("error: no program\n");
return 0;
}

if (2 != typec)
{
fprintf(o,"\tint __temporary_var = 0;\n");
}

for(size_t i=0;i<programs[0].inputNames.size();i++)
{
if (programs[0].inputTypes[i] == INT8)
{
fprintf(o,"\tstatic char ");
}else
if (programs[0].inputTypes[i] == UINT8)
{
fprintf(o,"\tstatic unsigned char ");
}
if (2 == typec)
{
fprintf(o,"%s = 0, %s_copy = 0;\n",programs[0].inputNames[i].c_str(),programs[0].inputNames[i].c_str());
}else
{
fprintf(o,"%s = 0;\n",programs[0].inputNames[i].c_str());
}
if (2 != typec)
{
fprintf(o,"\tprintf(\"enter input variable %s:\\n\");\n",programs[0].inputNames[i].c_str());
fprintf(o,"\tscanf(\"%%d\",&__temporary_var);\n");

if (programs[0].inputTypes[i] == INT8)
{
fprintf(o,"\t%s = (char)__temporary_var;\n",programs[0].inputNames[i].c_str());
}else
if (programs[0].inputTypes[i] == UINT8)
{
fprintf(o,"\t%s = (unsigned char)__temporary_var;\n",programs[0].inputNames[i].c_str());
}
}

}

int c1 = 0;
if (2 == typec)
{
fprintf(o,"\tint __total = 0;\n");
fprintf(o,"\tint __total_halt = 0;\n");
for(size_t i=0;i<programs[0].inputNames.size();i++)
{
if (programs[0].inputTypes[i] == INT8)
{
c1++;
fprintf(o,"\tfor(int i%d=0;i%d<=255;i%d++)\n",c1,c1,c1);
fprintf(o,"\t{\n");
fprintf(o,"\t%s = (char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
fprintf(o,"\t%s_copy = (char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
}else
if (programs[0].inputTypes[i] == UINT8)
{
c1++;
fprintf(o,"\tfor(int i%d=-128;i%d<=127;i%d++)\n",c1,c1,c1);
fprintf(o,"\t{\n");
fprintf(o,"\t%s = (unsigned char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
fprintf(o,"\t%s_copy = (unsigned char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
}
}
}

for(size_t i=0;i<programs[0].outputNames.size();i++)
{
if (programs[0].outputTypes[i] == INT8)
{
fprintf(o,"\tstatic char ");
}else
if (programs[0].outputTypes[i] == UINT8)
{
fprintf(o,"\tstatic unsigned char ");
}
fprintf(o,"%s = 0;\n",programs[0].outputNames[i].c_str());
}

if (2 == typec)
{
fprintf(o,"\ttry { \n");
fprintf(o,"\t__total++;\n");
fprintf(o,"\t_states.clear();\n");
}

fprintf(o,"\t%s (",programs[0].name.c_str());
for(size_t i=0;i<programs[0].inputNames.size();i++)
{
fprintf(o,"%s,",programs[0].inputNames[i].c_str());
}
for(size_t i=0;i<programs[0].outputNames.size();i++)
{
fprintf(o,"%s,",programs[0].outputNames[i].c_str());
}
fprintf(o,"0);\n");

if (2 == typec)
{
fprintf(o,"\t} catch(int r){ \n");
fprintf(o,"\tif (1 == r) \n");
fprintf(o,"\t __total_halt++;\n");
fprintf(o,"\t printf(\"HALT HAS BEEN DETECTED.\\n\");\n");
fprintf(o,"\t printf(\"INPUT VARIABLES:\\n\");\n");

for(size_t i=0;i<programs[0].inputNames.size();i++)
{
fprintf(o,"\tprintf(\"%s = %%d\\n\",(int)%s_copy);\n",programs[0].inputNames[i].c_str(),programs[0].inputNames[i].c_str());
}

fprintf(o,"\t}\n");

for(size_t i=0;i<programs[0].inputNames.size();i++)
{
fprintf(o,"\t}\n");
}
}

if (2 != typec)
{
fprintf(o,"\tprintf(\"RESULTS:\\n\");\n");
for(size_t i=0;i<programs[0].outputNames.size();i++)
{
fprintf(o,"\tprintf(\"%s = %%d\",(int)%s);\n",programs[0].outputNames[i].c_str(),programs[0].outputNames[i].c_str());
}
}else
{
fprintf(o,"\tprintf(\"RESULTS:\\n\");\n");
fprintf(o,"\tprintf(\"total : %%d\\n\",__total);\n");
fprintf(o,"\tprintf(\"halted: %%d\\n\",__total_halt);\n");
fprintf(o,"\tprintf(\"passed: %%d\\n\",__total — __total_halt);\n");
fprintf(o,"\tprintf(\"Q = %%f\\n\",(double)__total_halt / (double)__total);\n");
}


/*fprintf(o,"\tprintf(\"RESULTS (inputs):\\n\");\n");
for(size_t i=0;i<programs[0].inputNames.size();i++)
{
fprintf(o,"\tprintf(\"%s = %%d\",(int)%s);\n",programs[0].inputNames[i].c_str(),programs[0].inputNames[i].c_str());
}*/

fprintf(o,"}\n\n");

fclose(f);
fclose(o);

return 0;
}

С Уважением,
Петр Петров

Да, забыл форматирования для исходного кода сделать, вот:

/*
 * Copyright (c) 2009 by
 * IP PETROV PETR PETROVICH.
 * All Rights Reserved
 *
 * This software comprises unpublished confidential information
 * including intellectual property of IP PETROV PETR PETROVICH.
 * and may not be used, copied or made available to anyone, except in
 * accordance with the licence under which it is furnished.
 *
 */

#include "stdafx.h"

#define INT8  0
#define UINT8 1

int typec = 0; // 0 -compile. 1- validate, 2 - test

struct subprogram
{
    std::string name;
    std::vector<std::string> inputNames;
    std::set<std::string> sinputNames;
    std::vector<int> inputTypes;
    std::vector<std::string> outputNames;
    std::set<std::string> soutputNames;
    std::vector<int> outputTypes;
    std::vector<std::string> varNames;
    std::set<std::string> svarNames;
    std::vector<int> varTypes;
};

std::vector<subprogram> subprograms;
std::vector<subprogram> programs;
std::set<std::string> subprogram_names;
std::set<std::string> program_names;
std::string curContext;

int counter = 0;

void _fillstate(FILE* f,FILE* o)
{
    counter++;

    subprogram * sp = 0;

    for(size_t i=0;i<subprograms.size();i++)
    {
        if (subprograms[i].name == curContext)
        {
            sp = &(subprograms[i]);
            break;
        }
    }
    for(size_t i=0;i<programs.size();i++)
    {
        if (programs[i].name == curContext)
        {
            sp = &(programs[i]);
            break;
        }
    }
    fprintf(o,"\t_curstate.line = %d;\n",counter++);

      fprintf(o,"\t_curstate.variables.clear();\n",counter++);
      for(size_t i=0;i<sp->inputNames.size();i++)
      {
          fprintf(o,"\t_curstate.variables.push_back(%s);\n",sp->inputNames[i].c_str());
      }
      for(size_t i=0;i<sp->outputNames.size();i++)
      {
          fprintf(o,"\t_curstate.variables.push_back(%s);\n",sp->outputNames[i].c_str());
      }
      for(size_t i=0;i<sp->varNames.size();i++)
      {
          fprintf(o,"\t_curstate.variables.push_back(%s);\n",sp->varNames[i].c_str());
      }
}

void __check(FILE* f,FILE* o)
{
    if (0 != typec)
    {
        _fillstate(f,o);
        fprintf(o,"\t__check(&_curstate);\n");
    }
}

int _subprogram(FILE* f,FILE* o,bool is_subprogram = true)
{
  subprogram newSubprogram;
  char name[5000] = { 0 };
  fscanf(f,"%s",name);
  if (subprogram_names.find(std::string(name)) != subprogram_names.end())
  {
      printf("error: subprogram %s is always defined\n",name);
      return 0;
  }
  if (program_names.find(std::string(name)) != program_names.end())
  {
      printf("error: subprogram %s is always defined\n",name);
      return 0;
  }
  curContext = std::string(name);
  newSubprogram.name = std::string(name);
  char next[5000] = { 0 };
  fscanf(f,"%s",next);
  while(strcmp(next,"BEGIN"))
  {
      if (!strcmp(next,"INPUT"))
      {
            char iname[5000] = { 0 };
            fscanf(f,"%s",iname);
            if (newSubprogram.sinputNames.find(std::string(iname)) != newSubprogram.sinputNames.end())
            {
                printf("error: input argument's name %s is always used\n",iname);
                return 0;
            }
            if (newSubprogram.soutputNames.find(std::string(iname)) != newSubprogram.soutputNames.end())
            {
                printf("error: input argument's name %s is always used\n",iname);
                return 0;
            }
            if (newSubprogram.svarNames.find(std::string(iname)) != newSubprogram.svarNames.end())
            {
                printf("error: input argument's name %s is always used\n",iname);
                return 0;
            }
            newSubprogram.sinputNames.insert(std::string(iname));
            newSubprogram.inputNames.push_back(std::string(iname));
            char typeKeyword[5000] = { 0 };
            fscanf(f,"%s",typeKeyword);
            if (strcmp(typeKeyword,"TYPE"))
            {
                printf("error: TYPE keyword is absent\n");
                return 0;
            }
            char _typename[5000] = { 0 };
            fscanf(f,"%s",_typename);
            if (!strcmp(_typename,"int8"))
            {
                newSubprogram.inputTypes.push_back(INT8);
            }else
            if (!strcmp(_typename,"uint8"))
            {
                newSubprogram.inputTypes.push_back(UINT8);
            }else
            {
                printf("error: unknown type %s\n",_typename);
                return 0;                
            }
      }else
      if (!strcmp(next,"OUTPUT"))
      {
            char oname[5000] = { 0 };
            fscanf(f,"%s",oname);
            if (newSubprogram.sinputNames.find(std::string(oname)) != newSubprogram.sinputNames.end())
            {
                printf("error: output argument's name %s is always used\n",oname);
                return 0;
            }
            if (newSubprogram.soutputNames.find(std::string(oname)) != newSubprogram.soutputNames.end())
            {
                printf("error: output argument's name %s is always used\n",oname);
                return 0;
            }
            if (newSubprogram.svarNames.find(std::string(oname)) != newSubprogram.svarNames.end())
            {
                printf("error: output argument's name %s is always used\n",oname);
                return 0;
            }
            newSubprogram.soutputNames.insert(std::string(oname));
            newSubprogram.outputNames.push_back(std::string(oname));
            char typeKeyword[5000] = { 0 };
            fscanf(f,"%s",typeKeyword);
            if (strcmp(typeKeyword,"TYPE"))
            {
                printf("error: TYPE keyword is absent\n");
                return 0;
            }
            char _typename[5000] = { 0 };
            fscanf(f,"%s",_typename);
            if (!strcmp(_typename,"int8"))
            {
                newSubprogram.outputTypes.push_back(INT8);
            }else
            if (!strcmp(_typename,"uint8"))
            {
                newSubprogram.outputTypes.push_back(UINT8);
            }else
            {
                printf("error: unknown type %s\n",_typename);
                return 0;                
            }
      }else
      if (!strcmp(next,"VAR"))
      {
            char vname[5000] = { 0 };
            fscanf(f,"%s",vname);
            if (newSubprogram.sinputNames.find(std::string(vname)) != newSubprogram.sinputNames.end())
            {
                printf("error: variable's name %s is always used\n",vname);
                return 0;
            }
            if (newSubprogram.soutputNames.find(std::string(vname)) != newSubprogram.soutputNames.end())
            {
                printf("error: variable's name %s is always used\n",vname);
                return 0;
            }
            if (newSubprogram.svarNames.find(std::string(vname)) != newSubprogram.svarNames.end())
            {
                printf("error: variable's name %s is always used\n",vname);
                return 0;
            }
            newSubprogram.svarNames.insert(std::string(vname));
            newSubprogram.varNames.push_back(std::string(vname));
            char typeKeyword[5000] = { 0 };
            fscanf(f,"%s",typeKeyword);
            if (strcmp(typeKeyword,"TYPE"))
            {
                printf("error: TYPE keyword is absent\n");
                return 0;
            }
            char _typename[5000] = { 0 };
            fscanf(f,"%s",_typename);
            if (!strcmp(_typename,"int8"))
            {
                newSubprogram.varTypes.push_back(INT8);
            }else
            if (!strcmp(_typename,"uint8"))
            {
                newSubprogram.varTypes.push_back(UINT8);
            }else
            {
                printf("error: unknown type %s\n",_typename);
                return 0;                
            }
      }else
      if (strcmp(next,"BEGIN"))
      {
         printf("error: waiting for BEGIN token\n");
         return 0;                
      }
      fscanf(f,"%s",next);
  }

  if (is_subprogram)
  {
    subprograms.push_back(newSubprogram);
    subprogram_names.insert(std::string(name));
  }else
  {
    programs.push_back(newSubprogram);
    program_names.insert(std::string(name));
  }

  fprintf(o,"void %s (",name);
  for(size_t i=0;i<newSubprogram.inputNames.size();i++)
  {
      if (newSubprogram.inputTypes[i] == INT8)
      {
        fprintf(o,"char ");
      }else
      if (newSubprogram.inputTypes[i] == UINT8)
      {
        fprintf(o,"unsigned char ");
      }
      fprintf(o,"&%s",newSubprogram.inputNames[i].c_str());
      fprintf(o,", ");
  }
  for(size_t i=0;i<newSubprogram.outputNames.size();i++)
  {
      if (newSubprogram.outputTypes[i] == INT8)
      {
        fprintf(o,"char ");
      }else
      if (newSubprogram.outputTypes[i] == UINT8)
      {
        fprintf(o,"unsigned char ");
      }
      fprintf(o,"&%s",newSubprogram.outputNames[i].c_str());
      fprintf(o,", ");
  }

  fprintf(o,"void* __dummy)\n");
  fprintf(o,"{\n");

  for(size_t i=0;i<newSubprogram.varNames.size();i++)
  {
      if (newSubprogram.varTypes[i] == INT8)
      {
        fprintf(o,"\tstatic char ");
      }else
      if (newSubprogram.varTypes[i] == UINT8)
      {
        fprintf(o,"\tstatic unsigned char ");
      }
      fprintf(o,"%s = 0;\n",newSubprogram.varNames[i].c_str());
  }
  for(size_t i=0;i<newSubprogram.outputNames.size();i++)
  {
      fprintf(o,"\t%s = 0;\n",newSubprogram.outputNames[i].c_str());
  }
  return 0; 
}

void _inco(FILE* f,FILE *o)
{
    __check(f,o);

    char vname[5000] = { 0 };
    fscanf(f,"%s",vname);

    fprintf(o,"\t%s++;\n",vname);

}

void _deco(FILE* f,FILE *o)
{
    __check(f,o);

    char vname[5000] = { 0 };
    fscanf(f,"%s",vname);

    fprintf(o,"\t%s--;\n",vname);
}

void _mulo(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    char vname3[5000] = { 0 };
    fscanf(f,"%s",vname3);

    fprintf(o,"\t%s = %s * %s;\n",vname1,vname2,vname3);
}

void _set(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    fprintf(o,"\t%s = %s;\n",vname1,vname2);
}

void _let(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    fprintf(o,"\t%s = %s;\n",vname1,vname2);
}


void _divo(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    char vname3[5000] = { 0 };
    fscanf(f,"%s",vname3);

    fprintf(o,"\t%s = %s / %s;\n",vname1,vname2,vname3);
}

void _modo(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    char vname3[5000] = { 0 };
    fscanf(f,"%s",vname3);

    fprintf(o,"\t%s = %s %% %s;\n",vname1,vname2,vname3);
}

void _addo(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    char vname3[5000] = { 0 };
    fscanf(f,"%s",vname3);

    fprintf(o,"\t%s = %s + %s;\n",vname1,vname2,vname3);
}

void _subo(FILE *f,FILE* o)
{
    __check(f,o);

    char vname1[5000] = { 0 };
    fscanf(f,"%s",vname1);
    char vname2[5000] = { 0 };
    fscanf(f,"%s",vname2);
    char vname3[5000] = { 0 };
    fscanf(f,"%s",vname3);

    fprintf(o,"\t%s = %s - %s;\n",vname1,vname2,vname3);
}

void _label(FILE *f,FILE* o)
{
    __check(f,o);

    char name[5000] = { 0 };
    fscanf(f,"%s",name);

    fprintf(o,"label_%s_%s:\n",curContext.c_str(),name);
}

void _goto(FILE *f,FILE* o)
{
    __check(f,o);

    char name[5000] = { 0 };
    fscanf(f,"%s",name);

    fprintf(o,"\tgoto label_%s_%s;\n",curContext.c_str(),name);
}

void _ifequal(FILE *f,FILE* o)
{
    __check(f,o);

    char a1[5000] = { 0 };
    fscanf(f,"%s",a1);
    char a2[5000] = { 0 };
    fscanf(f,"%s",a2);

    fprintf(o,"\tif( %s == %s ) {\n\t",a1,a2);

    char gotoK[5000] = { 0 };
    fscanf(f,"%s",gotoK);
    if (strcmp(gotoK,"GOTO"))
    {
        printf("error: waiting for GOTO keyword\n");
    }

        _goto(f,o);
    fprintf(o,"\t}\n");

    char e[5000] = { 0 };
    fscanf(f,"%s",e);
    if (!strcmp(e,"ELSE"))
    {
        fprintf(o,"\telse { \n\t");
        _goto(f,o);
        fprintf(o,"\t}\n");
    }else
    {
    }
}

void _ifgreat(FILE *f,FILE* o)
{
    __check(f,o);

    char a1[5000] = { 0 };
    fscanf(f,"%s",a1);
    char a2[5000] = { 0 };
    fscanf(f,"%s",a2);

    fprintf(o,"\tif( %s > %s ) {\n\t",a1,a2);

    char gotoK[5000] = { 0 };
    fscanf(f,"%s",gotoK);
    if (strcmp(gotoK,"GOTO"))
    {
        printf("error: waiting for GOTO keyword\n");
    }

        _goto(f,o);
    fprintf(o,"\t}\n");

    char e[5000] = { 0 };
    fscanf(f,"%s",e);
    if (!strcmp(e,"ELSE"))
    {
        fprintf(o,"\telse { \n\t");
        _goto(f,o);
        fprintf(o,"\t}\n");
    }else
    {
    }
}

void _ifless(FILE *f,FILE* o)
{
    __check(f,o);

    char a1[5000] = { 0 };
    fscanf(f,"%s",a1);
    char a2[5000] = { 0 };
    fscanf(f,"%s",a2);

    fprintf(o,"\tif( %s < %s ) {\n\t",a1,a2);

    char gotoK[5000] = { 0 };
    fscanf(f,"%s",gotoK);
    if (strcmp(gotoK,"GOTO"))
    {
        printf("error: waiting for GOTO keyword\n");
    }

        _goto(f,o);
    fprintf(o,"\t}\n");

    char e[5000] = { 0 };
    fscanf(f,"%s",e);
    if (!strcmp(e,"ELSE"))
    {
        fprintf(o,"\telse { \n\t");
        _goto(f,o);
        fprintf(o,"\t}\n");
    }else
    {
    }
}

void _call(FILE *f,FILE* o)
{
    __check(f,o);

    char fname[5000] = { 0 };
    fscanf(f,"%s",fname);    

    if (subprogram_names.find(std::string(fname)) != subprogram_names.end() )
    {
        for(size_t i=0;i<subprograms.size();i++)
        {
            if (subprograms[i].name == std::string(fname))
            {
                int ac = subprograms[i].inputNames.size() + subprograms[i].outputNames.size();
                fprintf(o,"\t%s ( ",fname);
                for(int k=0;k<ac;k++)
                {
                    char an[5000] = { 0 };
                    fscanf(f,"%s",an);    
                    fprintf(o,"%s,",an);
                }
                fprintf(o,"0);\n");

                break;
            }
        }
    }else
    {
        printf("error: subprogram is not founded %s\n",fname);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
  printf("Simple Language Translator 1.0\n");
  printf("Copyright (c) 2009 by\n");
  printf("IP PETR PETROV PETROVICH.\n");
  printf("All Rights Reserved.\n\n");

  if (argc < 3)
  {
      printf("Usage: inputfilename.sl ACTION\n");
      printf("\there ACTION can be the following:\n");
      printf("\tCOMPILEONLY: A Simple Language Program will be compiled to C++ only\n");
      printf("\tCOMPILEWITHVALIDATE: A Simple Language Program will be compiled to C++ with Halt-detection code\n");
      printf("\tTEST: A simple Language Program will be tested (analised)\n");
      return 0;
  }

  if (!strcmp(argv[2],"COMPILEONLY"))
  {
      typec = 0;
  }else
  if (!strcmp(argv[2],"COMPILEWITHVALIDATE"))
  {
      typec = 1;
  }else
  if (!strcmp(argv[2],"TEST"))
  {
      typec = 2;
  }else
  {
      printf("error: incorrect mode\n");
      return 0;
  }


  FILE *f = fopen(argv[1],"rt");
  if (0 == f)
  {
      printf("Could not open input file.\n");
      return 0;
  }

  std::string outfilename = std::string(argv[1]) + std::string(".cpp");
  FILE *o = fopen(outfilename.c_str(),"wt");

  if (0 == o)
  {
      printf("Could not create output file.\n");
      return 0;
  }

  fprintf(o,"// This file was generated by Simple Language Translator 1.0\n");
  fprintf(o,"// DO NOT EDIT THIS FILE\n\n");

  fprintf(o,"#include <stdio.h>\n\n");  

  //!!!!
  if (0 != typec)
  {
  fprintf(o,"#include <vector>\n\n");  
  fprintf(o,"struct _state{\n");  
  fprintf(o,"\tstd::vector<int> variables;\n");  
  fprintf(o,"\tint line;\n");  
  fprintf(o,"};\n\n");  

  fprintf(o,"std::vector<_state> _states;\n\n");  

  fprintf(o,"bool __compare(_state* s1,_state* s2)\n");  
  fprintf(o,"{\n");  
  fprintf(o,"\tif (s1->variables.size() != s2->variables.size()) return false;\n");  
  fprintf(o,"\tif (s1->line != s2->line) return false;\n");  
  fprintf(o,"\tfor(size_t i=0;i<s1->variables.size();i++)\n");  
  fprintf(o,"\t{\n");  
  fprintf(o,"\t\tif (s1->variables[i] != s2->variables[i]) return false;\n");  
  fprintf(o,"\t}\n");  
  fprintf(o,"\treturn true;\n");  
  fprintf(o,"}\n");  

  fprintf(o,"void __check(_state* s)\n");  
  fprintf(o,"{\n");  
  fprintf(o,"\tfor(size_t i=0;i<_states.size();i++)\n");  
  fprintf(o,"\t{\n");  
  fprintf(o,"\t\tif (__compare(s,&_states[i])) {\n");  
  if (1 == typec)
  {
  fprintf(o,"\t\t\tprintf(\"program has halted!\\n\");\n");
  fprintf(o,"\t\t\texit(1);\n");
  }else
  if (2 == typec)
  {
  fprintf(o,"\t\t\tthrow int(1);\n");
  }
  fprintf(o,"\t\t}\n");  
  fprintf(o,"\t}\n");  
  fprintf(o,"\t_states.push_back(*s);\n");  
  fprintf(o,"}\n\n");  
  fprintf(o,"_state _curstate;\n");  
  }

  bool comment = false;
  bool wasprogram = false;
  while(!feof(f))
  {
      char buff[5000] = { 0 };
      fscanf(f,"%s",buff);

      if (!strcmp(buff,"*"))
      {
        comment = !comment;
      }else
      {
          if (!comment)
          {
              if (!strcmp(buff,"SUBPROGRAM"))
              {
                 _subprogram(f,o,true);
              }else
              if (!strcmp(buff,"PROGRAM"))
              {
                  if (!wasprogram)
                  {
                    _subprogram(f,o,false);
                    wasprogram = true;
                  }else
                  {
                      printf("error: a program must be one in file\n");
                      return 0;
                  }
              }else
              if (!strcmp(buff,"INC"))
              {
                  _inco(f,o);
              }else
              if (!strcmp(buff,"DEC"))
              {
                  _deco(f,o);
              }else
              if (!strcmp(buff,"MUL"))
              {
                  _mulo(f,o);
              }else
              if (!strcmp(buff,"DIV"))
              {
                  _divo(f,o);
              }else
              if (!strcmp(buff,"MOD"))
              {
                  _modo(f,o);
              }else
              if (!strcmp(buff,"ADD"))
              {
                  _addo(f,o);
              }else
              if (!strcmp(buff,"SUB"))
              {
                  _subo(f,o);
              }else
              if (!strcmp(buff,"LABEL"))
              {
                  _label(f,o);
              }else
              if (!strcmp(buff,"GOTO"))
              {
                  _goto(f,o);
              }else
              if (!strcmp(buff,"IFEQUAL"))
              {
                  _ifequal(f,o);
              }else
              if (!strcmp(buff,"IFGREAT"))
              {
                  _ifgreat(f,o);
              }else
              if (!strcmp(buff,"IFLESS"))
              {
                  _ifless(f,o);
              }else
              if (!strcmp(buff,"CALL"))
              {
                  _call(f,o);
              }else
              if (!strcmp(buff,"SET"))
              {
                  _set(f,o);
              }else
              if (!strcmp(buff,"LET"))
              {
                  _let(f,o);
              }else
              if (!strcmp(buff,"END"))
              {
                  fprintf(o,"\t;\n}\n");
              }
          }
      }
      
      //fprintf(o,"//%s\n",buff);
  }

  fprintf(o,"int main(int argc,char **argv)\n");
  fprintf(o,"{\n");

  if (0 == programs.size())
  { 
      printf("error: no program\n");
      return 0;
  }

  if (2 != typec)
  {
    fprintf(o,"\tint __temporary_var = 0;\n");
  }

  for(size_t i=0;i<programs[0].inputNames.size();i++)
  {
      if (programs[0].inputTypes[i] == INT8)
      {
        fprintf(o,"\tstatic char ");
      }else
      if (programs[0].inputTypes[i] == UINT8)
      {
        fprintf(o,"\tstatic unsigned char ");
      }
      if (2 == typec)
      {
        fprintf(o,"%s = 0, %s_copy = 0;\n",programs[0].inputNames[i].c_str(),programs[0].inputNames[i].c_str());
      }else
      {
        fprintf(o,"%s = 0;\n",programs[0].inputNames[i].c_str());
      }
      if (2 != typec)
      {
          fprintf(o,"\tprintf(\"enter input variable %s:\\n\");\n",programs[0].inputNames[i].c_str());
          fprintf(o,"\tscanf(\"%%d\",&__temporary_var);\n");

          if (programs[0].inputTypes[i] == INT8)
          {
            fprintf(o,"\t%s = (char)__temporary_var;\n",programs[0].inputNames[i].c_str());
          }else
          if (programs[0].inputTypes[i] == UINT8)
          {
            fprintf(o,"\t%s = (unsigned char)__temporary_var;\n",programs[0].inputNames[i].c_str());
          }
      }
   
  }

  int c1 = 0;
  if (2 == typec)
  {
      fprintf(o,"\tint __total = 0;\n");
      fprintf(o,"\tint __total_halt = 0;\n");
      for(size_t i=0;i<programs[0].inputNames.size();i++)
      {
          if (programs[0].inputTypes[i] == INT8)
          {
              c1++;
             fprintf(o,"\tfor(int i%d=0;i%d<=255;i%d++)\n",c1,c1,c1);
             fprintf(o,"\t{\n");
             fprintf(o,"\t%s = (char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
             fprintf(o,"\t%s_copy = (char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
          }else
          if (programs[0].inputTypes[i] == UINT8)
          {
              c1++;
             fprintf(o,"\tfor(int i%d=-128;i%d<=127;i%d++)\n",c1,c1,c1);
             fprintf(o,"\t{\n");
             fprintf(o,"\t%s = (unsigned char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
             fprintf(o,"\t%s_copy = (unsigned char)i%d;\n",programs[0].inputNames[i].c_str(),c1);
          }
      }
  }

  for(size_t i=0;i<programs[0].outputNames.size();i++)
  {
      if (programs[0].outputTypes[i] == INT8)
      {
        fprintf(o,"\tstatic char ");
      }else
      if (programs[0].outputTypes[i] == UINT8)
      {
        fprintf(o,"\tstatic unsigned char ");
      }
      fprintf(o,"%s = 0;\n",programs[0].outputNames[i].c_str());
  }

  if (2 == typec)
  {
      fprintf(o,"\ttry { \n");
      fprintf(o,"\t__total++;\n");
      fprintf(o,"\t_states.clear();\n");
  }

  fprintf(o,"\t%s (",programs[0].name.c_str());
  for(size_t i=0;i<programs[0].inputNames.size();i++)
  {
      fprintf(o,"%s,",programs[0].inputNames[i].c_str());
  }
  for(size_t i=0;i<programs[0].outputNames.size();i++)
  {
      fprintf(o,"%s,",programs[0].outputNames[i].c_str());
  }
  fprintf(o,"0);\n");

  if (2 == typec)
  {
      fprintf(o,"\t} catch(int r){ \n");
      fprintf(o,"\tif (1 == r) \n");
      fprintf(o,"\t __total_halt++;\n");
      fprintf(o,"\t printf(\"HALT HAS BEEN DETECTED.\\n\");\n");
      fprintf(o,"\t printf(\"INPUT VARIABLES:\\n\");\n");

  for(size_t i=0;i<programs[0].inputNames.size();i++)
  {
      fprintf(o,"\tprintf(\"%s = %%d\\n\",(int)%s_copy);\n",programs[0].inputNames[i].c_str(),programs[0].inputNames[i].c_str());
  }

      fprintf(o,"\t}\n");

      for(size_t i=0;i<programs[0].inputNames.size();i++)
      {
          fprintf(o,"\t}\n");
      }
  }

  if (2 != typec)
  {
      fprintf(o,"\tprintf(\"RESULTS:\\n\");\n");
      for(size_t i=0;i<programs[0].outputNames.size();i++)
      {
          fprintf(o,"\tprintf(\"%s = %%d\",(int)%s);\n",programs[0].outputNames[i].c_str(),programs[0].outputNames[i].c_str());
      }
  }else
  {
      fprintf(o,"\tprintf(\"RESULTS:\\n\");\n");
      fprintf(o,"\tprintf(\"total : %%d\\n\",__total);\n");
      fprintf(o,"\tprintf(\"halted: %%d\\n\",__total_halt);\n");
      fprintf(o,"\tprintf(\"passed: %%d\\n\",__total - __total_halt);\n");
      fprintf(o,"\tprintf(\"Q =  %%f\\n\",(double)__total_halt / (double)__total);\n");
  }


  /*fprintf(o,"\tprintf(\"RESULTS (inputs):\\n\");\n");
  for(size_t i=0;i<programs[0].inputNames.size();i++)
  {
      fprintf(o,"\tprintf(\"%s = %%d\",(int)%s);\n",programs[0].inputNames[i].c_str(),programs[0].inputNames[i].c_str());
  }*/

  fprintf(o,"}\n\n");

  fclose(f);
  fclose(o);

    return 0;
}

Здравствуйте, FR, Вы писали:

FR>Здравствуйте, Курилка, Вы писали:

FR>>>А разве общее множество всех формул не несчетно?

К>>Ну по идее есть же Гёделева нумерация (базис доказательства теоремы Гёделя), так что вполне себе счётно.

FR>Склероз мне подсказывает теорему Кантора
А толку?
FR>И этот же склероз подсказывает что Геделева нумерация как раз и выделяет счетное подмножество вычислимых формул из общего несчетного множества формул вообще (под формулой имеется в виду отображение счетного множества на четное же множество)
Ничего она не выделяет, какие-то это твои домыслы. А счётное множество счётных множеств (наверное, ты это имел в виду под отображением) ровно также счётно. Тебя ведь не удивляет тот факт, что мощность множества рациональных чисел счётно?

Здравствуйте, FR, Вы писали:

FR>Здравствуйте, GhostCoders, Вы писали:

FR>>>Про пи не знаю но тот же Аттрактор Лоренца не требует дополнительной памяти и при этом псевдослучаен. Да и теже детерминированные фракталы тоже можно вычислять на ограниченой памяти.

GC>>Только ПСЕВдослучаен.

FR>Угу, только есть пробема чтобы узнать эту псевдослучайную последовательность ее надо вычислять, а сходимость в заисимости от начальных условий, на современых машинах, у тех же аттракторов может быть от долей секунд до миллиардов лет.

Можете дать ссылку на такой Аттрактор? Очень интересно