интерпретатор программного кода (на C++)
Модератор: Olej
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
интерпретатор программного кода (на C++)
Вот такая вот учебная, но отнюдь не простая задачка: написать на C++ интерпретатор программных кодов, написанных на максимально упрощённом C-подобном языке.
Такая задача куда проще решалась бы на ... скажем, Python ... или Lisp, Ocaml и т.д.
Но задача стоит именно C++ - "мы не ищем лёгких путей".
Относительно "максимально упрощённого C-подобного языка"? - здесь каждый может сам сузить до интуитивно понятного минимуму...
Но, как минимум, в таком языке должны допускаться:
- типы данных ... как минимум, скажем, int и string ...
- именованные и типизированные переменные...
- операции ... и по разному толкуемые для разных типов: + - это сложение для int и конкатенация для string
- выражения, с произвольной глубиной скобочной записи
- функции ... как минимум read( x ) - ввода данных и write( x, y, z ) - вывода списка данных
- метки и оператор goto
- что-то типа if ... then ... else
- что-то из циклов
Обязательная часть такого интерпретатора - вычисление выражений - уже начала описываться раньше в отдельной теме обратная польская запись.
Такая задача куда проще решалась бы на ... скажем, Python ... или Lisp, Ocaml и т.д.
Но задача стоит именно C++ - "мы не ищем лёгких путей".
Относительно "максимально упрощённого C-подобного языка"? - здесь каждый может сам сузить до интуитивно понятного минимуму...
Но, как минимум, в таком языке должны допускаться:
- типы данных ... как минимум, скажем, int и string ...
- именованные и типизированные переменные...
- операции ... и по разному толкуемые для разных типов: + - это сложение для int и конкатенация для string
- выражения, с произвольной глубиной скобочной записи
- функции ... как минимум read( x ) - ввода данных и write( x, y, z ) - вывода списка данных
- метки и оператор goto
- что-то типа if ... then ... else
- что-то из циклов
Обязательная часть такого интерпретатора - вычисление выражений - уже начала описываться раньше в отдельной теме обратная польская запись.
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: интерпретатор программного кода (на C++)
Вот первый (собственно, 28-й - это версия) работающий вариант к рассмотрению: интерпретатор языка Z (zero, нулевой, никакой ).Olej писал(а):Вот такая вот учебная, но отнюдь не простая задачка: написать на C++ интерпретатор программных кодов, написанных на максимально упрощённом C-подобном языке.
Можно уже брать и экспериментировать.
Вся программа заключается в операторные скобки: program { <здесь код программы> }.Olej писал(а): Относительно "максимально упрощённого C-подобного языка"? - здесь каждый может сам сузить до интуитивно понятного минимуму...
Глупость, но так было в формулировке, которая мне первоначально попала в руки ... кроме того такому интерпретатору не получится скормить всё что попало: просто .txt файл ... или даже бинарный.
Это всё уже там есть.Olej писал(а): Но, как минимум, в таком языке должны допускаться:
- типы данных ... как минимум, скажем, int и string ...
- именованные и типизированные переменные...
- операции ... и по разному толкуемые для разных типов: + - это сложение для int и конкатенация для string
- выражения, с произвольной глубиной скобочной записи
- функции ... как минимум read( x ) - ввода данных и write( x, y, z ) - вывода списка данных
- метки и оператор goto
А этого ещё нет.Olej писал(а): - что-то типа if ... then ... else
- что-то из циклов
- Вложения
-
- z211.tgz
- (9.12 КБ) 110 скачиваний
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: интерпретатор программного кода (на C++)
Olej писал(а):работающий вариант к рассмотрению
Код: Выделить всё
[olej@dell 2]$ tar -czvf z211.tgz z211.28
z211.28/
z211.28/errors.h
z211.28/ops.h
z211.28/ppn.cc
z211.28/ppn.h
z211.28/string.cc
z211.28/string.h
z211.28/z211.cc
z211.28/Makefile
z211.28/z211.4.hist
errors - это фиксатор ошибок выполнения ... как синтаксического разбора, так и этапа выполнения/интерпретации, раскиданный по всему коду, на основе исключений:
Код: Выделить всё
class syn_exception : exception {
string what;
public:
syn_exception( const string& s ) : what( s ) {}
operator const char*() { return what.c_str(); }
};
Код: Выделить всё
typedef string (*op_func)( type_t, const string&, const string& );
class opers { // реализуемые вычислителем операции
static map<string,op_func> ops;
static string noop( void ) {
throw syn_exception( "недопустимая операция для этого типа" );
return ""; // фиктивный возврат
}
public:
static op_func find( const string& s ) {// поиск операции по её изображению
try { return ops.at( s ); }
catch(...) { return NULL; } // исключение если операция не найдена
}
};
map<string,op_func> opers::ops = {
{ "<", []( type_t type, const string& o1, const string& o2 ) -> string {
return ( 0 == type ? stoll( o1 ) < stoll( o2 ) : o1 < o2 ) ? "1" : "0";
}
},
{ ">", []( type_t type, const string& o1, const string& o2 ) -> string {
return ( 0 == type ? stoll( o1 ) > stoll( o2 ) : o1 > o2 ) ? "1" : "0";
}
},
{ "+", []( type_t type, const string& o1, const string& o2 ) -> string {
return 0 == type ? to_string( stoll( o1 ) + stoll( o2 ) ) : o1 + o2;
}
},
{ "-", []( type_t type, const string& o1, const string& o2 ) -> string {
return 0 == type ? to_string( stoll( o1 ) - stoll( o2 ) ) : noop();
}
},
{ "*", []( type_t type, const string& o1, const string& o2 ) -> string {
if( 0 == type )
return to_string( stoll( o1 ) * stoll( o2 ) );
int n = stoll( o2 );
string sm( o2 );
while( --n ) sm += o2;
return sm;
}
},
{ "/", []( type_t type, const string& o1, const string& o2 ) -> string {
if( 0 == stoll( o2 ) )
throw syn_exception( "деление на 0" );
return 0 == type ? to_string( stoll( o1 ) / stoll( o2 ) ) : noop();
}
},
{ "^", []( type_t type, const string& o1, const string& o2 ) -> string {
if( type != 0 ) noop(); // не числовая операция
long long n = stoll( o2 );
if( n < 0 ) return "0";
if( 0 == n ) return "1";
long long p = stoll( o1 ), r = p;
while( --n ) r *= p;
return to_string( r );
}
},
};
z211.cc - это и есть сам интерпретатор.
... всё остальное - это мелочёвка мало значимая.
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: интерпретатор программного кода (на C++)
Там много ... 497 строк кода, на сегодня ... но ничего там мудрёного, кроме громоздкости нет:Olej писал(а):z211.cc - это и есть сам интерпретатор.
- таблица размещённых переменных
Код: Выделить всё
map<string,variable*> var_table;
variable* find_var( const string& s ) { // поиск переменной в таблице
try { return var_table.at( s ); }
catch(...) { return NULL; } // исключение если не найдена переменная
}
Код: Выделить всё
map<string,unsigned> lbl_table; //************** таблица меток строк
int find_lbl( const string& s ) { // поиск позиции помеченного оператора
try { return lbl_table.at( s ); }
catch(...) { return -1; } // исключение если не найдена метка
}
Код: Выделить всё
vector<vector<string>> output; //************** внутреннее представление кода
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: интерпретатор программного кода (на C++)
Работа интерпретатора:Olej писал(а):Остальное всё достаточно элементарно...
Код: Выделить всё
[olej@dell 2]$ ./z211
.?
версия 0.27
.h
допустимые команды: t i v g s b r l ? e q h
.q
Остальные команды:
.t - текст (в несколько модифицированном виде ... разделённый пооператорно на строки, убраны комментарии);
.i - внутреннее представление (постфиксное);
.v - содержимое таблицы переменных;
.g - содержимое таблицы меток;
.s - шаг выполнения;
.b - начать выполнение с начала;
.r - выполнять полностью;
.l - перезагрузить файл программы;
.? - версия;
.e , .q - завершение;
.h - справка (перечисление команд);
(на такую структуру навеяло рассмотрение работы Cling интерпретатора C++ из проекта LLVM )
Вот примерно так:
Код: Выделить всё
[olej@dell 2]$ ./z211 tests.z/an.z
.t
aaa = 7, bbb = 0
write( aaa/bbb )
.i
aaa bbb / write
.v
aaa int <7>
bbb int <0>
.r
выполнение - деление на 0
.s
выполнение - достигнут конец программы
.q
Файлы тестов (по именам) 2-х видов: a*.z - это правильные программы, которые должны выполняться (даже с ошибками выполнения, как пример выше) и b*.z - это синтаксически неправильные программы, в которых эта неправильность должна распознаваться и диагностироваться.
- Вложения
-
- tests.z.tgz
- (2.56 КБ) 107 скачиваний
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: интерпретатор программного кода (на C++)
Как-то вот так:Olej писал(а): В архивчике - 48 (пока) тестовых программ *.z, на которых проверяется и отлаживается работа интерпретатора.
Файлы тестов (по именам) 2-х видов: a*.z - это правильные программы, которые должны выполняться (даже с ошибками выполнения, как пример выше) и b*.z - это синтаксически неправильные программы, в которых эта неправильность должна распознаваться и диагностироваться.
Код: Выделить всё
[olej@dell 2]$ ./z211 tests.z/a2_5.z
.t
a = 7, b= 5 , c = -2, d =4, e
a = b = c = e = a + ( b - c ) * d
write( a, b )
.r
35
35
.q
Код: Выделить всё
[olej@dell 2]$ ./z211 tests.z/a4.z
.t
a = 7, b = 5 , c = -2, d =4, e
write( a + b - c * d, a - b, 22 / a )
.r
20
2
3
.q
Код: Выделить всё
[olej@dell 2]$ ./z211 tests.z/b2_4.z
синтаксис - не соответствует тип константы: string 1234
.q
Код: Выделить всё
[olej@dell 2]$ ./z211 tests.z/b2_5.z
синтаксис - не определеная переменная: e
.q
Код: Выделить всё
[olej@dell 2]$ ./z211 tests.z/bl2.z
.s
.s
8
.s
выполнение - не найдена метка: l1
.q
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: интерпретатор программного кода (на C++)
Отвлекли меня немного от этой задачи разборки с вот этим cборка приложений Go...Olej писал(а):А этого ещё нет.Olej писал(а): - что-то типа if ... then ... else
- что-то из циклов
Появилось у меня такое намерение ... откатиться назад, и сделать разбор и первичную трансляцию лексем в промежуточный код на основе ... регулярных выражений, которые в стандарте C++ 2011г. обеспечиваются библиотекой libpcre.so (API в заголовочных файлах #include <regex>) ... в самом стандарте C++ это реализуется на базе шаблонов и контейнерных классов STL (детальное описание см. Регулярные выражения C/C++).
Это оказалось довольно хлопотно ... но плодотворно: в приведенном прототипе всего 246 строк C++ кода, а он обеспечивает а). лексический разбор с б). трансляцией в промежуточный линейный код при в). произвольной глубиной вложенности синтаксических конструкций:
а). описаний переменных;
б). линейных операторов (присвоений, произвольных 2-местных операций +, -, *, /, % ... отношений <, > ...);
в). циклических конструкций while( ... ) { ... }
г). в). циклических конструкций do { ... } while( ... )
Доделать туда, по аналогии, обработку (трансляцию) if(...) { ... } else { ... } и for( ...; ...; ... ) - это уже вопрос рутины ... 1/2 дня работы ...
- Вложения
-
- reglex.v1.tgz
- (7.57 КБ) 112 скачиваний
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: интерпретатор программного кода (на C++)
Выглядит это примерно так:Olej писал(а):в приведенном прототипе всего 246 строк C++ кода, а он обеспечивает а). лексический разбор с б). трансляцией в промежуточный линейный код при в). произвольной глубиной вложенности синтаксических конструкций:
Код: Выделить всё
[olej@dell reglex]$ ./reglex -v aw3.z
program {
int a = 7, b=5 , c=-2, d = +4, e; ;
while( ( a + c ) > ( b - d ) ) {
while( d * b < ( a + 3) ) {
{};
d = d / b;
}
{ a = a - 1; }
d = 2 * b;
{ e = e + 1; }
};
}
aw3.z - итог трансляции:
int a = 7, b=5 , c=-2, d = +4, e
B0001: ( a + c ) > ( b - d ) ifn F0001
B0002: d * b < ( a + 3) ifn F0002
d = d / b
goto B0002
F0002:
a = a - 1
d = 2 * b
e = e + 1
goto B0001
F0001:
Код: Выделить всё
[olej@dell reglex]$ ./reglex -v ad*.z
program {
int a = 7, b=5 , c=-2, d = +4, e; ;
do {
a = a - 1;
b = b / 2;
} while( a > 0 );
}
ad1.z - итог трансляции:
int a = 7, b=5 , c=-2, d = +4, e
B0001:
a = a - 1
b = b / 2
a > 0 if B0001
program {
int a = 7, b=5 , c=-2, d = +4, e; ;
do {
while ( b < c ) {
b = b - 1;
}
b = b / 2;
} while( a > 0 )
}
ad2.z - итог трансляции:
int a = 7, b=5 , c=-2, d = +4, e
B0002:
B0003: b < c ifn F0003
b = b - 1
goto B0003
F0003:
b = b / 2
a > 0 if B0002
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: интерпретатор программного кода (на C++)
Весь синтаксис языка Z при этом содержится в одной структуре ... точнее в массиве таких структур соответствующих типам лексем:Olej писал(а): ... откатиться назад, и сделать разбор и первичную трансляцию лексем в промежуточный код на основе ... регулярных выражений, которые в стандарте C++ 2011г. обеспечиваются библиотекой libpcre.so (API в заголовочных файлах #include <regex>) ... в самом стандарте C++ это реализуется на базе шаблонов и контейнерных классов STL (детальное описание см. Регулярные выражения C/C++).
Код: Выделить всё
...
struct { // структура описания лексемы
string s; // регулярное выражение выделения лексемы
string (*f)( smatch& ); // функция трансляции лексемы
string d; // наименование (для отладки)
} static pats[] = {
/*описание*/ { R"(^(int|string)\s+([^;]*);{1}(.*)$)", eval_var, "описание" },
/*блок*/ { R"(^\s*(\{.*)$)", eval_block, "блок" },
/*пусто*/ { R"(^\s*;(.*)$)", []( smatch& m )->string { return m[ 1 ].str(); }, "пусто" },
/*while*/ { R"(^\s*(while\s*\()(.*)$)", eval_while, "while" },
/*do*/ { R"(^\s*(do\s*)(\{.*)while\s*(\(.*)$)", eval_do, "do" },
/*оператор*/ { R"(^\s*([^;]*);{1}(.*)$)", eval_single, "оператор" },
/*???*/ { R"(^(.*)$)", eval_norel, "не реализовано" }
};
...
s - распознающее регулярное выражение;
f - функция предобработки-трансляции этой лексемы;
А дальше остаётся только весь исходный код Z-программы (какой бы большой он не было) прогонять в цикле сквозь эту структуру, до тех пор, пока весь исходный код не исчерпается.
- Olej
- Писатель
- Сообщения: 21338
- Зарегистрирован: 24 сен 2011, 14:22
- Откуда: Харьков
- Контактная информация:
Re: интерпретатор программного кода (на C++)
Вот для анализа подобный интерпретатор языка SMALL BASIC, написанный на языке C: ИНТЕРПРЕТАТОРЫ ЯЗЫКА.Olej писал(а): Такая задача куда проще решалась бы на ... скажем, Python ... или Lisp, Ocaml и т.д.
Но задача стоит именно C++ - "мы не ищем лёгких путей".
(Как сам интерпретатор он мне неинтересен ... хотя там приведен полностью законченный код для экспериментирования. А вот общие обсуждения отдельных сторон там, по ходу - интересные.)
Кто сейчас на конференции
Сейчас этот форум просматривают: нет зарегистрированных пользователей и 14 гостей