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

[Olej]

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

Я не настолько мастак в регулярных выражениях - это для особо продвинутых (подвинутых ... мозгами ), чтобы рекурсию разбора вложенных выражений (скобок) реализовать непосредственно в регулярных выражениях - рекурсия вызова сделана в вызывающем C++ коде, который применяет регулярное выражение на своём уровне вызова.

Но продвинутый народ (в расширенном синтаксисе регулярных выражений, например в Ruby) проделывает рекурсивный разбор прямо из регулярного выражения. Каковой предмет заслуживает отдельного заинтересованного рассмотрения (в другой раз ):
Рекурсия в регулярных выражениях

23 марта 2011, 18:58

Рекурсия в регулярных выражениях

изменён 13 авг '12 в 18:10
(?R) означает рекурсивную ссылку на само регулярное выражение, где можно найти обработчик регулярных выражений, поддерживающих такие рекурсии для Java или Python ?
...
https://pypi.python.org/pypi/regex
Альтернативный движок для регулярных выражений питона с поддержкой рекурсий.

Памятка по регулярным выражениям PCRE в PHP

31.07.2012, 21:40.

Это, конечно, PHP ... который никому всерьёз и на фиг не нужен ("неуловимый Джо" ) + и большинство расширенных там конструкций неприменимо в вашем используемом языке ... но уж очень обширный там обзор...

Рекурсивные выражения
...

[Olej]

в приведенном прототипе

Там же - тестер (отработки) регулярных выражений для лексем языка regs.cc, которые потом использованы в разборщике. Без этого разработка оказалась практически невозможной:
- нужно регулярное выражение, которое точно соответствует синтаксису интерпретируемого языка ...
- записанное именно в той выбранной грамматике регулярных выражений библиотеки regex C++ (а там их как минимум 5, не считая нюансов) ...
- и ещё так, чтобы текущее правило не попадало под ранее (выше в массиве) определённое для другого типа лексем.

В конечном счёте это выглядит так:
- есть набор последовательных правил (регулярных выражений), записанных в любой файл, ниже например это 2.pat
- в набор можно вписать их хоть 1000000, потому что комментарий # в начальной позиции строки "закрывает" правило, чтобы не перегружать вывод и анализ
- в программе regs мы можем вкидывать любые разбираемые (тестовые) выражения и наблюдать как они отождествляются (или нет) и раскидываются на группы

Примерно всё это выглядит так:

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

[olej@dell reglex]$ ./regs 2.pat 
#1:	^(int|string)\s+([^;]*);{1}(.*)$
#2:	^\s*([^;]*);{1}(.*)$
#3:	^\s*(\{.*)$
#4:	^\s*(while\s*\()(.*)$
#5:	^\s*(do\s*)(\{.*)while\s*(\(.*)$
#6:	^\s*if\s*\((.*)$
#7:	^\s*for\s*(^\))(.*)$
#8:	^(program)\s*\{\s*(.*)\}\s*$
-------------------------------------------
>    if ( x )    {  yy }  ;   zzzz ;
#2 [3]:    if ( x )    {  yy }  ;   zzzz ; => <if ( x )    {  yy }  >[3:21] | <   zzzz ;>[25:9]
#6 [2]:    if ( x )    {  yy }  ;   zzzz ; => < x )    {  yy }  ;   zzzz ;>[7:27]
>    if (   x   ) {    yyy }  else   {   ssss   }   ;
#2 [3]:    if (   x   ) {    yyy }  else   {   ssss   }   ; => <if (   x   ) {    yyy }  else   {   ssss   }   >[3:47] | <>[51:0]
#6 [2]:    if (   x   ) {    yyy }  else   {   ssss   }   ; => <   x   ) {    yyy }  else   {   ssss   }   ;>[7:44]
>    for   (  i = 5    ; i   < 10   ;   i = i + 1   )  { a  =   a + 1;   b = b - 1 }  ; zzzzzz   ;
#2 [3]:    for   (  i = 5    ; i   < 10   ;   i = i + 1   )  { a  =   a + 1;   b = b - 1 }  ; zzzzzz   ; => <for   (  i = 5    >[3:18] | < i   < 10   ;   i = i + 1   )  { a  =   a + 1;   b = b - 1 }  ; zzzzzz   ;>[22:74]
> ^C

Когда отрабатываемое правило для текущей лексемы нас устраивает:
- само выражение из 2.pat переписывается в код reglex.cc в качестве распознавателя ...
- а выведенная строка разбиения служит прямой базой (я копирую её прямо туда в качестве правила-руководства) для написания C++ кода транслирующей функции
ХитрО

P.S. Кому надо - увидит всё это в архиве ... а кому не надо - не заморачивайтесь с этим, не задерживайтесь в этом месте ...

[Olej]

Или вот так:

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

[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

А потом всё это подаётся на вход вычислителя-интерпретатора, который показывался выше...

Ещё один шаг в тему:
- поскольку такой вот транслятор первичного кода в промежуточный - это чисто символьная обработка, ничего применительно к интерпретации конкретного языка здесь нет ... это символьный препроцессор;
- и для того, чтобы не переписывать код по 3 раза, я хочу этот препроцессор reglex.cc и использовать в неизменном виде как дочерний процесс ... который просто прокинет транслированный исходный код в тот исполняющий интерпретатор, который приводился выше:

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

- интерпретатор конечно, придётся изменить, но очень незначительно - только в части ввода исходного кода.

[Olej]

- интерпретатор конечно, придётся изменить, но очень незначительно - только в части ввода исходного кода.

А для того, чтобы, забегая вперёд, спрогнозировать этот читающий код - сделал такое автономное приложение, которое и осуществляет такой ввод простейшим способом (необходимым, но вполне достаточным ):

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

#include <iostream>
#include <fstream>
#include <unistd.h>
using namespace std;

int debug_level = 0;

int main( int argc, char *argv[] ) {
   char sopt[] = "v", c;
   while( -1 != ( c = getopt( argc, argv, sopt ) ) )
      switch( c ) {
         case 'v':
            debug_level++;
            break;
         default :
            cerr << "формат команды: допустимы только опции: -" << sopt << endl;
            return 1;
      }
   if( optind == argc ) {
       cerr << "формат: " << argv[ 0 ] << " <файлы кода...>" << endl;
       return 2;
   }
   string command( "./reglex -s " );
   if( debug_level ) 
      command += "-" + string( debug_level, 'v' ) + " ";
   for( int i = optind; i < argc; i++ )
      command += string( argv[ i ] ) + " ";
   FILE *pipe = popen( command.c_str(), "r" );
   if( !pipe ) {
      cerr << "не может быть запущен: "<< command << endl;
      return 3;
   }
   int n = 0;   
   cout << "получено от транслятора:" << endl;
   char buf[ 200 ];
   while( fgets( buf, sizeof( buf ), pipe ) )  
        cout << ++n << ": " << buf;
   n = pclose( pipe );
   return WEXITSTATUS( n ); 
}

Вот и всё!
Этого вполне достаточно для вкидывания транслированного исходного кода от дочернего процесса в исполняющий интерпретатор:

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

[olej@dell reglex]$ ./reglex a2.z 
int a = 7, b= 5 , c = -2, d =4, e
e = a + ( b - c ) * d
write( a + b - c * d, 22 / a )

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

[olej@dell reglex]$ ./exec  a2.z 
получено от транслятора:
1: int a = 7, b= 5 , c = -2, d =4, e
2: e = a + ( b - c ) * d
3: write( a + b - c * d, 22 / a )

[Olej]

Выглядит это примерно так:

А теперь ещё и циклы for (при любой взаимной вложенности for, while, do) ... ну и ещё всякие разные улучшения.
И вы глядит это примерно так:

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

[olej@dell reglex]$ ./reglex -v af2.z
program {    
   int i, j, b = 1;
   for( i = 0; i < 5; i = i + 1 ) { 
      for( j = 0; j < 5; j = j + 1 ) {
         b = b + i * j;
      }
   }
}
af2.z - итог трансляции:
int i, j, b = 1
i = 0
B0001: i < 5 ifn F0001
j = 0
B0002: j < 5 ifn F0002
b = b + i * j
j = j + 1 
goto B0002
F0002:
i = i + 1 
goto B0001
F0001:

[Olej]

А теперь ещё и циклы for (при любой взаимной вложенности for, while, do)

Ну вот, собственно, всё - в таком варианте, в дополнение, обрабатываются условные операторы ... и написание иллюстрационного интерпретатора языка Z (упрощённый до нуля C) можно считать законченным!

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

[olej@dell reglex]$ ./reglex -v ai1.z
program {    
   int x = 2, y = 3, z;
   if( x > y ) { y = x; };
}
ai1.z - итог трансляции:
int x = 2, y = 3, z
x > y ifn F0001
y = x
F0001:

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

[olej@dell reglex]$ ./reglex -v ai2.z
program {    
   int x = 2, y = 3, z;
   if( x < y ) { 
      z = x; 
   }
   else {
      z = y;
   }
}
ai2.z - итог трансляции:
int x = 2, y = 3, z
x < y ifn B0001
z = x
goto F0001
B0001:
z = y
F0001:

Дальше можно (очень немного и несложно) включить этот транслятор reglex, используя показанный код exec.cc, в код исполняющего транслятора z211.cc, обсуждавшийся ранее ... можно не включать ... и на этом закончить тему, потому что дальше всё элементарно ясно.

Для меня крайне важным и любопытным здесь было то, что лексический анализ и трансляцию в элементарный промежуточный код можно произвести, используя регулярные выражения C++.
Если бы я то же стал делать на C++, даже используя все возможности STL и расширения стандарта C++11, но не используя регулярные выражения, то объём аналогичного кода я оцениваю в 4-5 раз длиннее! (я начинал прописывать прототип именно так ... и только оценив сколько там простой но объёмной рутины - двинулся в регулярные выражения).

[Olej]

Дальше можно (очень немного и несложно) включить этот транслятор reglex, используя показанный код exec.cc, в код исполняющего транслятора z211.cc, обсуждавшийся ранее ... можно не включать ... и на этом закончить тему, потому что дальше всё элементарно ясно.

Для меня крайне важным и любопытным здесь было то, что лексический анализ и трансляцию в элементарный промежуточный код можно произвести, используя регулярные выражения C++.

Из некоторых э-э-э-э .... "политических соображений" я временно приостановил развитие публикации в этой теме, но не приостановил развитие самой темы.
Как говорят в рекламе? : "следите за нашими публикациями" - вскорости (после конца июня) я выложу в полном объёме то, что сделано за прошедшее время.

[Olej]

Из некоторых э-э-э-э .... "политических соображений" я временно приостановил развитие публикации в этой теме, но не приостановил развитие самой темы.

Политические соображения , как несложно догадаться, состояли в том, что в этой теме описывается то, как я помогал (именно помогал, а не делал вместо него) студенту из МГУ им.Ломоносов в его курсовой работе ... и очень не хотелось, чтобы результаты описаний попались на глаза его пЫдагогам , которым пришлось бы потом доказывать и расписывать что, кто и как делал, и кто и откуда списывал...
Теперь возвращаюсь к созданному коду.
Прикреплённый архив - это уже работающий интерпретатор.
В том виде, как он был сдан в МГУ и вполне удовлетворил ... заказчика.
И в том виде как он был приостановлен... (версия 35 ... точнее 0.35 - именно столько достаточно обстоятельных промежуточных версий было сделано в ходе развития).
Циклические, условные выражения обрабатываются препроцессором, вызываемым как дочерний процесс, после чего код интерпретируется линейным интерпретатором.

[Olej]

Прикреплённый архив - это уже работающий интерпретатор.
...
И в том виде как он был приостановлен... (версия 35 ... точнее 0.35 - именно столько достаточно обстоятельных промежуточных версий было сделано в ходе развития).

Теперь самое время ... разобраться и вспомнить что сам там наделал, и описать и привести образцы тестовых прогонов.

Важно: если хоть кому-то, хоть 1-му, из читателей подобные техники, направления интересны, с вариациями развития - влево-вправо - я с интересом продолжил бы развитие и обсуждение этого проекта. Если интересующихся нет, то пусть он остаётся в таком вот, достаточно работоспособном, виде.
Вы можете переопределить сами (расширить, изменить) синтаксис упрощённого языка Z (zero-C), и проект можно элементарно легко перекроить под него. Важно, чтобы язык был императивный (не функциональный как Lisp или Scala, не логический как Prolog, не стековый как Forth и т.д.).

[Olej]

Теперь самое время ... разобраться и вспомнить что сам там наделал, и описать и привести образцы тестовых прогонов.

Вспоминаю

Задача там изрядно сложная, поэтому для её отработки собирается несколько отдельных приложений (для тестирования, проверок и т.д.):

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

[olej@dell z211]$ make
g++ -Wall -O3 -std=c++11    -c -o common.o common.cc
g++ -Wall -O3 -std=c++11 common.o -l pcre reglex.cc -o reglex
g++ -Wall -O3 -std=c++11 common.o -l pcre regs.cc -o regs
g++ -Wall -O3 -std=c++11 common.o -l pcre exec.cc -o exec
g++ -Wall -O3 -std=c++11 -c ppn.cc -o ppn.o
g++ -Wall -O3 -std=c++11    -c -o string.o string.cc
g++ -Wall -O3 -std=c++11 z211r.cc ppn.o string.o common.o -o z211r
g++ -Wall -O3 -std=c++11 pptest.cc ppn.o -o ppntest

Вот из Makefile:

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

TASK = reglex regs exec z211r ppntest
all: $(TASK)