Rating@Mail.ru

Форум по операционной системе GNU/Linux и свободному программному обеспечению


Текущее время: 25 июл 2017, 05:55

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу Пред.  1, 2, 3  След.
Автор Сообщение
Непрочитанное сообщениеДобавлено: 13 май 2017, 01:39 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 9820
Откуда: Харьков
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 ... который никому всерьёз и на фиг не нужен ("неуловимый Джо" :lol: ) + и большинство расширенных там конструкций неприменимо в вашем используемом языке ... но уж очень обширный там обзор... ;-)
Цитата:
Рекурсивные выражения
...


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 13 май 2017, 10:15 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 9820
Откуда: Харьков
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++ кода транслирующей функции
ХитрО :lol:

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


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 13 май 2017, 23:14 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 9820
Откуда: Харьков
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 и использовать в неизменном виде как дочерний процесс ... который просто прокинет транслированный исходный код в тот исполняющий интерпретатор, который приводился выше:
Olej писал(а):
z211.cc - это и есть сам интерпретатор.

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


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 13 май 2017, 23:18 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 9820
Откуда: Харьков
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 )


Вложения:
exec.cc [1.24 КБ]
Скачиваний: 12
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 14 май 2017, 16:48 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 9820
Откуда: Харьков
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:


Вложения:
reglex.v2.tgz [6.81 КБ]
Скачиваний: 12
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 15 май 2017, 15:56 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 9820
Откуда: Харьков
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, обсуждавшийся ранее ... можно не включать :lol: ... и на этом закончить тему, потому что дальше всё элементарно ясно.

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


Вложения:
reglex.v3.tgz [12.15 КБ]
Скачиваний: 11
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 17 июн 2017, 14:24 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 9820
Откуда: Харьков
Olej писал(а):
Дальше можно (очень немного и несложно) включить этот транслятор reglex, используя показанный код exec.cc, в код исполняющего транслятора z211.cc, обсуждавшийся ранее ... можно не включать :lol: ... и на этом закончить тему, потому что дальше всё элементарно ясно.

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

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


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 24 июн 2017, 13:55 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 9820
Откуда: Харьков
Olej писал(а):
Из некоторых э-э-э-э ;-) .... "политических соображений" я временно приостановил развитие публикации в этой теме, но не приостановил развитие самой темы.

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


Вложения:
z211.35.tgz [44.66 КБ]
Скачиваний: 1
Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 24 июн 2017, 14:01 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 9820
Откуда: Харьков
Olej писал(а):
Прикреплённый архив - это уже работающий интерпретатор.
...
И в том виде как он был приостановлен... (версия 35 ... точнее 0.35 - именно столько достаточно обстоятельных промежуточных версий было сделано в ходе развития).

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

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


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Непрочитанное сообщениеДобавлено: 24 июн 2017, 14:18 
Не в сети
Писатель
Аватара пользователя

Зарегистрирован: 24 сен 2011, 14:22
Сообщения: 9820
Откуда: Харьков
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)


Вернуться к началу
 Профиль Отправить личное сообщение  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу Пред.  1, 2, 3  След.

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 2


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB
[ Time : 0.146s | 17 Queries | GZIP : On ]