Темыч, Зенитчик и все остальные Help!!!

[Zenitchik]

Разве это не показывает ещё раз, что монолитный подход хуже, чем мой поэтапный

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

а что этапы ты придумываешь и задаёшь сам

Велосипед, батенька, велосипед.
В чем Ваше ноу-хау-то? Синтаксический анализ за несколько проходов делать?

[tyomitch]

Ну и где мне парсер скобок?

[Хакер]

Я дал себе слово не связываться с этим топиком, пока не напишу рассказ о том, как я попал и лежал в больнице. Потому что в этом топике, после выкладывания в него TreeBuilder-а, начнётся жуткий спор и я смогу удержаться чтобы не отвечать сюда. И тогда непонятно, когда я закончу рассказ .

А парсер-то — он на ноуте, а не на моей основной машине.

[Хакер]

Рассказ написал.

Итак в аттаче две папки:

• test2tyom — исходники библиотеки, работающей с DFA и TKN, как с черным ящиком. Библиотека написана на скорую руку, контроль ошибок отсутствует.
• vb_test_app — VB-проект использующий сишную библиотеку. В VB-проекте есть класс CNode, на базе которого и строится дерево, такое, как ты, tyomitch, заказывал. У класса всего лишь одно свойство: NodeId — то самое число, которыми ты пронумировал ноды своего дерева. Собственно, после разбора выражения VB-проект стопает, и ты там уже можешь как тебе угодно проверять правильность построения дерева, можешь перебирать узлы с помощью For Each, а можешь ставить бряки внутри метода AddSubnode.

[tyomitch]

Заглянул.
У тебя DispID=-4 не на том члене стоит

Как оно всё работает, вообще совершенно не понял.
Но возникает подозрение, что у тебя на втором проходе состояние хранится в стеке
Если это так, то остаётся (для случая с >1 возможной редукцией) прикрутить ещё на второй проход хитрую стейтмашину, и у тебя получится точно такой же МПА, как у всех нормальных людей.
Бонусом, можно будет убрать счётчик уровня вложенности из первого прохода.

[Хакер]

Как оно всё работает, вообще совершенно не понял.

Но возникает подозрение, что у тебя на втором проходе состояние хранится в стеке

Стек используется. Но разве было хоть слово о том, что стек нельзя использовать?

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

Его изначально не было. Но я как рассудил: вот обрабатываем мы строчку, дёргаем NodeConstructor, заставляем создавать новый COM-объекты. А потом в конце обнаруживаем лишнюю скобку. И нам ничего не остаётся, как как уничтожить дерево. А зачем мучиться-создавать, если потом придётся уничтожить?

Так что я ввёл промежуточный этап проверки баланса.

Дык что? Предоставил я пример, и что дальше?

[tyomitch]

Дык что? Предоставил я пример, и что дальше?

Как оно всё работает, вообще совершенно не понял.

Для начала, объяснить, как на самом деле происходит второй проход.

Но возникает подозрение, что у тебя на втором проходе состояние хранится в стеке

Стек используется. Но разве было хоть слово о том, что стек нельзя использовать?

Можно использовать. Просто как бы хотелось неожиданной новизны, вместо перекрашенного МПА.

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

Его изначально не было. Но я как рассудил: вот обрабатываем мы строчку, дёргаем NodeConstructor, заставляем создавать новый COM-объекты. А потом в конце обнаруживаем лишнюю скобку. И нам ничего не остаётся, как как уничтожить дерево. А зачем мучиться-создавать, если потом придётся уничтожить?

Для простоты.
Пример же нарочно выбран для простоты.
А ты зачем-то пошёл усложнять.

[Хакер]

Для начала, объяснить, как на самом деле происходит второй проход.

Поставь брек на входе и выходе MakeSecondPass. Посмотри под отладчиком (под OllyDbg например), что происходит. Будет лучше любого объяснения.

Можно использовать. Просто как бы хотелось неожиданной новизны, вместо перекрашенного МПА.

МПА — ведь, не более чем математическая абстракция. И ты смотришь через призму МПА на мой способ, видешь в нём перекрашенный МПА. С таким подходом, можно увидеть МПА в абсолютном большинстве алгоритмов и программ, потому что практически все они используют стек. Т.е. сам центральный процессор, выполняющий какой-то код, можно посчитать автоматом с МП, и таким образом признать отсутствие новизны в любом алгоритме коде, выполняющемся на нём.

Новизна-то, вообще говоря не в алгоритме: я придумал не какой-то новый алгоритм, а я сделал способ генерации динамического кода. А зачем мне динамический код? Тут две причины:

• Я вижу целый класс ситуаций, в котором структурный подход программирования, за который (и против goto) так боролся Дейкстра, вреден. (Точно так же, как вижу класс ситуаций, где SEH очень сильно проигрывает VEH-у именно из-за первой букву).
  
  Вообще, термин "структурное программирование" не совсем удачен. Ибо под привычным термином "структурное программирование" понимается такое программирование, когда структура программы носит блочный/фреймовый характер. Если пользоваться термином "структурное программирование", то программа, написанная вопреки этому подходу, будет называться неструктурной? Но ведь у неё всё равно есть своя структура (в общем смысле этого слова)? Как тогда сказать о ней? Неструктурная структура программы? Прямо как "non-paged page". Поэтому я дальше буду применять термин "блочная структура программы", когда буду говорить о программе, написанной по правилам "структурного программирования".
  Так вот, случается, что приходится реализовывать алгоритмы, которые совершенно не дружат со структурностью (т.е., например, если нарисовать их блок-схему, то получится ориентированный граф с кучей узлов, кучей ребёр и кучей циклов).
  Единственным доступным мне языком, который не навязывает структуность/блочность, является ассемблер, но писать на нём долго и сложно (по причине, о которой я скажу дальше).
  Все доступные мне более ВУ-языки навязывают структурность/блочность, и неструктурный/неблочный код в них можно было делать только одним единственным способом: с помощью кучи goto и кучи меток. Но Дейкстра был прав, куча goto и куча меток — ад для программиста, это чертовски неудобно и невыразительно (в смысле: плохо воспринимается структура неблочного кода). И это же самое относится к ассемблеру: куча jmp и куча меток очень круто затрудняют восприятие программы.
  И есть ещё один очень существенный недостаток у goto в ВУ-языках: очевидно, что если на блок-схеме от блока отходит несколько стрелочек, то это значит, что при работе программы выполнение перейдёт только по какой-то одной из них (их стрелочек). По какой — зависит от каких-то условий. Например: если на входе цифра — перейти туда-то, а если буква — в другое место, а если кавычка — в третье, а если пробел — перейти на саму же себя (пример чисто условный). Естественно, что (особенно когда вараинтов того, что может "очутиться" на входе, много), логику переходов лучше всего оформить в виде таблицы переходов. goto ни в VB, ни в С/С++ ни с какими таблицами не дружит, потому единственное, что можно сделать, это либо:
  

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

  processing_of_itself:
If на_входе = 1 then goto processing_of_a
if на_входе = 2 then goto processing_of_a
if на входе = 3 then goto processing_of_b
if на_входе = 4 then goto processing_of_c
if на входе = 5 then goto processing_of_c
if на входе = 5 then goto processing_of_itself

  
  (но это однозначно долгий (т.е. медленный) и кривой вариант)
  либо сделав аналогичное с помощью select-case-подобной конструкции — их компиляторы хотя бы оптимизировать умеют.
  Но как ни крути: логика переходов задаётся на этапе написания, и при компилировании остаётся жестко вшитой в код. Непосредственно в процессе выполнения логику переходов никак не изменишь. Но в С/С++ есть возможность объявить массив указателей на код (на функции, точнее), и в зависимости от того, что на входе, выбирать нужный элемент массива, т.е. нужный указатель, и вызывать функцию. Т.е. никаких if-ов, никаких case-ов, элемент входной последовательности преобразуется непосредственно в индекс элемента массива указателей и происходит вызов. Но и тут облом: это будет структурный/блочный вызов, именно вызов (call), а не переход (goto,jmp), то есть выполнение обязательно вернётся обратно, а нам этого меньше всего надо.
• Второй момент: я "открыл" для себя, что это очень круто: иметь возможность строить такой алгоритм, что он будет содержать только те блоки (узлы) блок-схемы, и только те переходы, которые необходимы для обработки именно тех данных и именно в тех условиях, которые мы сейчас имеем. И делать это не на этапе разработки, а на этапе выполнения.
  Пример (тот, старый):
  Есть множество слов (алфавит: всего четыре буквы (a, b, c, d)), каждому соответствует ненулевой номер. Функция принимает на входе строку; если она соответствует слову, надо вернуть ID слова, если нет — 0. Для простоты рассмотрим случай, что слова у нас все трёхсимвольные.
  Очевидно, что код, который сделает эту задачу за минимальное число шагов (а значит быстрее) выглядит так (вдобавок, он на все слова одинаковой длины потратит одинаковое время, а значит, при оценки эффективности (достаточно ли быстр код) нужно сделать замер только одного случая):
  

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

  int Resolve(char* word)
{
   switch(word[0])
   {
   case 'a':
      switch(word[1])
      {
      case 'a':
         switch(word[2])
         {
         case 'a': return 1;
         case 'b': return 2;
         case 'c': return 3;
         case 'd': return 4;
         default: return 0;
         }
      case 'b':
         switch(word[2])
         {
         case 'a': return 5;
         case 'b': return 6;
         case 'c': return 7;
         case 'd': return 8;
         default: return 0;
         }
      case 'c':
         switch(word[2])
         {
         case 'a': return 9;
         case 'b': return 10;
         case 'c': return 11;
         case 'd': return 12;
         default: return 0;
         }
      case 'd':
         switch(word[2])
         {
         case 'a': return 13;
         case 'b': return 14;
         case 'c': return 15;
         case 'd': return 16;
         default: return 0;
         }
      default: return 0;
      }
   case 'b':
      switch(word[1])
      {
      case 'a':
         switch(word[2])
         {
         case 'a': return 17;
         case 'b': return 18;
         case 'c': return 19;
         case 'd': return 20;
         default: return 0;
         }
      case 'b':
         switch(word[2])
         {
         case 'a': return 21;
         case 'b': return 22;
         case 'c': return 23;
         case 'd': return 24;
         default: return 0;
         }
      case 'c':
         switch(word[2])
         {
         case 'a': return 25;
         case 'b': return 26;
         case 'c': return 27;
         case 'd': return 28;
         default: return 0;
         }
      case 'd':
         switch(word[2])
         {
         case 'a': return 29;
         case 'b': return 30;
         case 'c': return 31;
         case 'd': return 32;
         default: return 0;
         }
      default: return 0;
      }
   case 'c':
      switch(word[1])
      {
      case 'a':
         switch(word[2])
         {
         case 'a': return 33;
         case 'b': return 34;
         case 'c': return 35;
         case 'd': return 36;
         default: return 0;
         }
      case 'b':
         switch(word[2])
         {
         case 'a': return 37;
         case 'b': return 38;
         case 'c': return 39;
         case 'd': return 40;
         default: return 0;
         }
      case 'c':
         switch(word[2])
         {
         case 'a': return 41;
         case 'b': return 42;
         case 'c': return 43;
         case 'd': return 44;
         default: return 0;
         }
      case 'd':
         switch(word[2])
         {
         case 'a': return 45;
         case 'b': return 46;
         case 'c': return 47;
         case 'd': return 48;
         default: return 0;
         }
      default: return 0;
      }
   case 'd':
      switch(word[1])
      {
      case 'a':
         switch(word[2])
         {
         case 'a': return 49;
         case 'b': return 50;
         case 'c': return 51;
         case 'd': return 52;
         default: return 0;
         }
      case 'b':
         switch(word[2])
         {
         case 'a': return 53;
         case 'b': return 54;
         case 'c': return 55;
         case 'd': return 56;
         default: return 0;
         }
      case 'c':
         switch(word[2])
         {
         case 'a': return 57;
         case 'b': return 58;
         case 'c': return 59;
         case 'd': return 60;
         default: return 0;
         }
      case 'd':
         switch(word[2])
         {
         case 'a': return 61;
         case 'b': return 62;
         case 'c': return 63;
         case 'd': return 64;
         default: return 0;
         }
      default: return 0;
      }
   default: return 0;
   }
}

  
  (Извиняюсь перед владельцами IE6)
  Этот код даст вам ID любого из 64 слов за одинакое время и в любом случае ему понадобится сделать всего 3 сравнения и три перехода. Т.е. главное его достоинство — быстрота.
  Минусы:
  1) Словарь получился фиксированным — ни добавить, ни удалить из него слово во время выполнения нельзя. Только на этапе разработки. И то, потребуется вносить кучу правок.
  2) Код однообразен, шаблонен и абсолютно неинтелектуален.
  Если взглянуть на блок-схему функции, то она такая же однообразная и строго иерархичная (т.е. древовидная) — именно поэтому для реализации функции удалось обойтись фишками структурного программирования (select-case-подобной конструкцией):
  
  
  Если бы слова было все 4: bad, bac, dab, dad, функция бы выглядела так:
  

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

  int Resolve(char* word)
{
   switch(word[0])
   {
   case 'b':
      switch(word[1])
      {
      case 'a':
         switch(word[2])
         {
         case 'c': return 1;
         case 'd': return 2;
         default: return 0;
         }
      default: return 0;
      }

   case 'd':
      switch(word[1])
      {
      case 'a':
         switch(word[2])
         {
         case 'b': return 3;
         case 'd': return 4;
         default: return 0;
         }
      default: return 0;
      }
   default: return 0;
   }
}

  
  Для каждого набора слов — свой код функции.

Так вот, сначала я сделал код-резолвер, таблица перехода которого задовались на этапе компилирования и занимали площадь в 8 экранов. И добавить/удалить слово было нетривиальной задачей. Потом я решил использовать дин.код и генерировать код-резолвер и таблицы переходов в рантайме. Это значит что в рантайме можно добавлять/удалять слова в словарь, при этом код-резолвер будет должным образом перестраиваться.
Это как раз та библиотека, которая лежит в топике Abandonware. Она умела генерировать динамический код исключительно для транслирования слова в номер. Ничего кроме. При том, динкод (сразу представляй себе блок-схему) должен был быть обязательно древовидным.
В последствии я обнаружил задачи (токенизация — одна из них), где совсем не должно пахнуть структурностью. Тогда я создал новую библиотеку: позволяющую во время выполнения строить граф (идентичный блок-схеме), в узлах которого — любой код + таблица переходов (на другие узлы). Библиотека сама отвечала за размещение кода, за связывание узлов между собой, за размещение таблиц переходов — вобщем, предоставляла возможность сконцентрироваться на главном. Можно строить граф самому, вызывая функции Dfa* (как сделано в примере тебе), можно было бы написать программу, в которой рисуешь граф и которая генерирует код, для его построения. Можно было написать поверх DFA-библиотеки обертку, которая загружает граф из файла и по этой информации строит код.

На базе Dfa (читать: на базе готового хорошо отлаженного механизма построения и управления динамическим кодом) был сделан Krm (тот самый транслятор слов в ID-ы), Tkn (токенайзер), Ncd (декомпилятор x86-кода) и т.п.
Первые две — тоненькие обёрточки над Dfa-функциями:

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

...
...
ULONG KrmAddKwd(LPSTR sKeyword, DWORD id)
{
   if(KrmInitialized)
   {
      unsigned int l = GenStrLen(sKeyword);
      unsigned int i = 0;

      if(l == 0)
      {
         return STATUS_SUCCESS;
      }
      else
      {
         T_ROUTER_ENTRY *r;
         ULONG PathIndex;
         ULONG JatWidth = KrmActiveRangeEnd - KrmActiveRangeBegin + 1;


         r = Krm->BaseRouter;
         PathIndex = l;

         while(i < l)
         {
            if((*r->JAT)[PathIndex].RouterEntry->JatSize == 0)
            {
               r = DfaAddChildRouter(r, PathIndex, (LPVOID)FavKrmRouter, DFARTL_USE_FAV_CODE, 0, JatWidth);
               for(unsigned int j = 0; j < JatWidth; j++)
               {
                  DfaAddChildRouter(r, j, FavKrmTerminator, DFARTL_USE_FAV_CODE, 0, 0);
               }
            }
            else
            {
               r = (*r->JAT)[PathIndex].RouterEntry;
            }
            
            PathIndex = SYMBOL2PATHID(sKeyword[i++]);
         }
         

         //
         // Создаём конечный роутер (терминатор дерева) и устанавливаем в качестве
         // терминационного кода идентификатор ключевого слова
         //

         T_ROUTER_ENTRY *Finalizer;

         Finalizer = DfaAddChildRouter(r, PathIndex, (LPVOID)FavKrmTerminator, DFARTL_USE_FAV_CODE, 0, 0);
         DfaSetTerminatorData(Finalizer, id);

         return STATUS_SUCCESS;
      }
      
   }
   else
   {
      return STATUS_ERROR_NOT_INITIALIZED;
   }
}

ULONG KrmDeleteKwd(LPSTR Keyword)
{
   ULONG l = GenStrLen(Keyword);

   if(KrmResolve((DWORD)Keyword, 0, l) != 0)
   {
      T_ROUTER_ENTRY *r = (*Krm->BaseRouter->JAT)[l].RouterEntry;

      for(ULONG i = 0; i < l; i++)
      {
         r = (*r->JAT)[SYMBOL2PATHID(Keyword[i])].RouterEntry; 
      }

      KrmDeleteKwdByTerminator(r);
   }
   return STATUS_SUCCESS;
}

ULONG KrmDeleteKwdByTerminator(T_ROUTER_ENTRY *Terminator)
{
   T_ROUTER_ENTRY *BaseRouter;
   T_ROUTER_ENTRY *ThisRouter;

   BaseRouter = Terminator->Automat->BaseRouter;

   //
   // Сейчас мы циклически спустимся по ветке в сторону корня и найдём первый
   // по ходу обхода узел бифуркации. Во всей ветке от узла бифуркации до
   // терминатора отсутствуют бифуркации, поэтому вся эта ветка будет
   // удалена одним вызовом DfaRemoveRouter для первого (после бифуркационного)
   // роутера ветки
   //
   
   for(ThisRouter = Terminator; ThisRouter != BaseRouter; /* Здесь итератор писать нельзя */ )
   {
      if(DfaGetRouterBifurcation(ThisRouter->ParentRouter) > 1)
      {
         //
         // Родительской роутер этого роутера имеет бифуркации, а значит, не может быть удален
         // Поэтому удаляем этот роутер, но прежде, терминируем соотв. ячейку родительской JAT
         //

         DfaAddChildRouter(ThisRouter->ParentRouter, DfaGetRouterJATIndex(ThisRouter), (LPVOID)FavKrmTerminator, DFARTL_USE_FAV_CODE, 0, 0);     
         DfaRemoveRouter(ThisRouter);
         break;
      }
   }

   return STATUS_SUCCESS;
}

...
...

Последняя — толстенькая

(А вообще, сколько я могу разбазаривать исходники закрытых проектов? )

Но!

Когда я сказал "мой способ задания правил лучше", я вообще сказал это в шутку (о чём свидетельствует смайлик после фразы), и смысл существования поста был больше в его P.S., чем в нём самом.
Так вот, я имел в виду не конкретно Dfa или Tkn, а имел в виду подход.
SLIM-у надо будет:
1) Сам разбирающий механизм.
2) Сделать анализатор описания грамматики, котрый будет управлять разбирающим механизмом.
3) Сделать описание грамматики.
Мне надо будет:
1) <аналогично>
2) С помощью функций пункта-1 построить граф нужный для конкретной грамматики конкретного формата входных данных

[SLIM]

Супер!!!

Сама идея просто конфетка. Т.е. у меня возникала такая идея, но не хватало, видимо, знаний...ИМХО это достаточно тяжело.
Тогда я подумал - если я не могу написать код, создающий динамический код, то я для разбора буду использовать одну единственную библиотеку, т.е. все функции разбора будут в одной библиотеке независимо от грамматики и того, что я буду разбирать. После создания такой библиотеки пользователь(программист например) загружает программу с моей библиотечкой, заносит таблицу символов например (тут должен быть полный курс разработки грамматики начиная от таблицы символов до приоритетов выводов из нетерменалов слов). После того как человек ввел все что нужно, на основе этого создается некая структура (я назвал его ресурсом для библиотеки). Этот ресурс будет использоваться той самой монолитной библиотекой (код то там один для любого ресурса). Итак получается что для того чтобы разобрать грамматику, в которой имеется 3 символа и пять слов из них я (конечно уже с готовой библиотекой):
1. Задаю символы, правила вывода, расставляю приоритеты (программа (библиотека) составляет априорные критерии и т.д.)
2. Создаю ресурс на заданный вид грамматики
3. Подключаю к проекту библиотеку и ресурс (собственно где лежит вся грамматика)
4. Юзаю юзаю юзаю

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

Поэтому я наконец-то понял как все устроено у тебя, чему очень рад - ибо убедился что такое возможно. И радует то, что (если я все таки все верно понял) моя идея была такой же, но умений и навыков для этого нет..

Когда я сказал "мой способ задания правил лучше", я вообще сказал это в шутку (о чём свидетельствует смайлик после фразы), и смысл существования поста был больше в его P.S., чем в нём самом.

Ну об этом мы уже поговорили правда? И я таки осознал свою неправоту

[Zenitchik]

Ну Вы, блин, открыли америку!
Описание грамматики - это метод проектирования. К конечному продукту он никакого отношения не имеет.

Для простых языков я сам сразу строю граф переходов, минуя описание продукций грамматики - так проще. Потребность в явном описании продукций я испытал только на RL(0)-грамматике.

Для чего нужен универсальный автомат - в упор не понимаю. Проще написать автомат, пишуший автоматы.

[Хакер]

Для чего нужен универсальный автомат - в упор не понимаю.

Какой ещё универсальный автомат?

[Zenitchik]

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

[Хакер]

И к кому это относится? Кто разрабатывает универсальный распознователь языков?

[SLIM]

И к кому это относится? Кто разрабатывает универсальный распознователь языков?

Ну это относится ко мне по видимому

Отвечу - зачем программисту каждый раз писать что-то по новой то?

[Хакер]

Вряд ли. В этой теме два лагеря, между которыми шло противостояние. Ты и зенитчик — из одного лагеря.

[Zenitchik]

Ты и зенитчик — из одного лагеря.

Я в этом уже сомневаюсь. Я только за то, что программирование это наука, а не ремесло. И теория грамматик здорово облегчает жизнь. Но вот заставлять прогармму при каждом запуске допроектировать саму себя, причем с одним и тем же результатом - пребор.

Отвечу - зачем программисту каждый раз писать что-то по новой то?

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

[Хакер]

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

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

Лагерь "Тёмыча-Зенитчика-Слима", как мне казалось, был за лозунг: "Видешь теорию! Умные дядьки построили, ууу... бери и используй, нефиг выпендриваться, изобретая свои подходы".
Я ошибался?

[Zenitchik]

Именно так. Вооружившись теорией легче составить свой подход. Теорию действительно разработали не дураки.