интерпретатор программного кода (на C++)

[Olej]

Вот такая вот учебная, но отнюдь не простая задачка: написать на C++ интерпретатор программных кодов, написанных на максимально упрощённом C-подобном языке.

Такая задача куда проще решалась бы на ... скажем, Python ... или Lisp, Ocaml и т.д.
Но задача стоит именно C++ - "мы не ищем лёгких путей".

Относительно "максимально упрощённого C-подобного языка"? - здесь каждый может сам сузить до интуитивно понятного минимуму...
Но, как минимум, в таком языке должны допускаться:
- типы данных ... как минимум, скажем, int и string ...
- именованные и типизированные переменные...
- операции ... и по разному толкуемые для разных типов: + - это сложение для int и конкатенация для string
- выражения, с произвольной глубиной скобочной записи
- функции ... как минимум read( x ) - ввода данных и write( x, y, z ) - вывода списка данных
- метки и оператор goto
- что-то типа if ... then ... else
- что-то из циклов

Обязательная часть такого интерпретатора - вычисление выражений - уже начала описываться раньше в отдельной теме обратная польская запись.

[Olej]

Вот такая вот учебная, но отнюдь не простая задачка: написать на C++ интерпретатор программных кодов, написанных на максимально упрощённом C-подобном языке.

Вот первый (собственно, 28-й - это версия) работающий вариант к рассмотрению: интерпретатор языка Z (zero, нулевой, никакой ).
Можно уже брать и экспериментировать.

Относительно "максимально упрощённого C-подобного языка"? - здесь каждый может сам сузить до интуитивно понятного минимуму...

Вся программа заключается в операторные скобки: program { <здесь код программы> }.
Глупость, но так было в формулировке, которая мне первоначально попала в руки ... кроме того такому интерпретатору не получится скормить всё что попало: просто .txt файл ... или даже бинарный.

Но, как минимум, в таком языке должны допускаться:
- типы данных ... как минимум, скажем, int и string ...
- именованные и типизированные переменные...
- операции ... и по разному толкуемые для разных типов: + - это сложение для int и конкатенация для string
- выражения, с произвольной глубиной скобочной записи
- функции ... как минимум read( x ) - ввода данных и write( x, y, z ) - вывода списка данных
- метки и оператор goto

Это всё уже там есть.

- что-то типа if ... then ... else
- что-то из циклов

А этого ещё нет.

[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

ppn - это разборщик выражений в реверсную (постфиксную) польскую запись.
errors - это фиксатор ошибок выполнения ... как синтаксического разбора, так и этапа выполнения/интерпретации, раскиданный по всему коду, на основе исключений:

Код: Выделить всё

class syn_exception : exception {
   string what;
public:
   syn_exception( const string& s ) : what( s ) {}
   operator const char*() { return what.c_str(); }
};

ops - это описание всех операций (+, -, *, /, ^, <, > ...) выполняемых в выражениях языка и то как их выполнять - ни одна операция не "зашита" в код интерпретатора, всё что угодно (==, !=, %, &, && и т.д.) можно добавлять просто вписав реализацию в структуру:

Код: Выделить всё

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 );
          } 
   },
};

Всё это описано в терминах анонимных функций ... и вообще, весь код написан в расширениях стандарта C++11 (2011 года).
z211.cc - это и есть сам интерпретатор.
... всё остальное - это мелочёвка мало значимая.

[Olej]

z211.cc - это и есть сам интерпретатор.

Там много ... 497 строк кода, на сегодня ... но ничего там мудрёного, кроме громоздкости нет:
- таблица размещённых переменных

Код: Выделить всё

   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]

Остальное всё достаточно элементарно...

Работа интерпретатора:

Код: Выделить всё

[olej@dell 2]$ ./z211 
.?
версия 0.27
.h
допустимые команды: t i v g s b r l ? e q h
.q

Имя файла исполнимой программы можете задать хоть параметром запуска, хоть позже командой загрузки .l (эл).
Остальные команды:
.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

В архивчике - 48 (пока) тестовых программ *.z, на которых проверяется и отлаживается работа интерпретатора.
Файлы тестов (по именам) 2-х видов: a*.z - это правильные программы, которые должны выполняться (даже с ошибками выполнения, как пример выше) и b*.z - это синтаксически неправильные программы, в которых эта неправильность должна распознаваться и диагностироваться.

[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]

- что-то типа if ... then ... else
- что-то из циклов

А этого ещё нет.

Отвлекли меня немного от этой задачи разборки с вот этим cборка приложений Go...
Появилось у меня такое намерение ... откатиться назад, и сделать разбор и первичную трансляцию лексем в промежуточный код на основе ... регулярных выражений, которые в стандарте C++ 2011г. обеспечиваются библиотекой libpcre.so (API в заголовочных файлах #include <regex>) ... в самом стандарте C++ это реализуется на базе шаблонов и контейнерных классов STL (детальное описание см. Регулярные выражения C/C++).

Это оказалось довольно хлопотно ... но плодотворно: в приведенном прототипе всего 246 строк C++ кода, а он обеспечивает а). лексический разбор с б). трансляцией в промежуточный линейный код при в). произвольной глубиной вложенности синтаксических конструкций:
а). описаний переменных;
б). линейных операторов (присвоений, произвольных 2-местных операций +, -, *, /, % ... отношений <, > ...);
в). циклических конструкций while( ... ) { ... }
г). в). циклических конструкций do { ... } while( ... )
Доделать туда, по аналогии, обработку (трансляцию) if(...) { ... } else { ... } и for( ...; ...; ... ) - это уже вопрос рутины ... 1/2 дня работы ...

[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]

... откатиться назад, и сделать разбор и первичную трансляцию лексем в промежуточный код на основе ... регулярных выражений, которые в стандарте C++ 2011г. обеспечиваются библиотекой libpcre.so (API в заголовочных файлах #include <regex>) ... в самом стандарте C++ это реализуется на базе шаблонов и контейнерных классов STL (детальное описание см. Регулярные выражения C/C++).

Весь синтаксис языка Z при этом содержится в одной структуре ... точнее в массиве таких структур соответствующих типам лексем:

Код: Выделить всё

...
   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]

Такая задача куда проще решалась бы на ... скажем, Python ... или Lisp, Ocaml и т.д.
Но задача стоит именно C++ - "мы не ищем лёгких путей".

Вот для анализа подобный интерпретатор языка SMALL BASIC, написанный на языке C: ИНТЕРПРЕТАТОРЫ ЯЗЫКА.
(Как сам интерпретатор он мне неинтересен ... хотя там приведен полностью законченный код для экспериментирования. А вот общие обсуждения отдельных сторон там, по ходу - интересные.)