Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > [C++] switch из ДКА


Автор: rudvil 28.6.2011, 23:13
Всем привет, пытаюсь реализовать на switch'e ДКА, впринципе кое-что получается.
Не могу разобраться с корректным кодом для "развилок" на графе ниже "развилка" из состояния 1 в состояние 2 или 4.
Для примера возьмем ebnf правило
Цитата(ebnf)
test = 'a' 'b' | 'c' 'd';

По нему строим ДКА... получаем:http://radikal.ru/F/s42.radikal.ru/i096/1106/39/9989f334160b.png.html
Я добился автогенерации след. кода для вышеуказанного ДКА
Код
  const std::size_t start_state = 1; // Start state is always 1
  std::size_t state = start_state;
  std::stack<std::size_t> last_state;
  
  std::size_t counter_1 = 0;
  
  bool loop = true;
  while(loop) {
    switch(state) {
    case 1: {
      if(counter_1++ == 0 && MATCH_terminal("a")) {
        last_state.push(1);
        state = 2;
      } else if(counter_1++ == 1 && MATCH_terminal("c")) {
        last_state.push(1);
        state = 4;
      } else {
        if(last_state.empty()) {
          loop = false;
        } else {
          state = last_state.top();
          last_state.pop();
        }
      }
    }
    break;
    case 2: {
      if(MATCH_terminal("b")) {
        state = 6;
      } else {
        if(last_state.empty()) {
          loop = false;
        } else {
          state = last_state.top();
          last_state.pop();
        }
      }
      
    }
    break;
    case 4: {
      if(MATCH_terminal("d")) {
        state = 5;
      } else {
        if(last_state.empty()) {
          loop = false;
        } else {
          state = last_state.top();
          last_state.pop();
        }
      }
      
    }
    break;
    case 5: {
      loop = false;
      
    }
    break;
    case 6: {
      loop = false;
      
    }
    break;
    default: {
      loop = false;
    }
    break;
    }
  }
  // Accepting states:  5 6
  if(state == 5 || state == 6) {
    std::cout << "MATCH SUCCESS\n";
  } else {
    std::cout << "MATCH FAIL\n";
  }

Кратко поясню, что тут творится, а именно о стеке last_state и о переменной counter_1.
Стек нужен для того чтобы возвратиться обратно на "развилку" если один из путей развилки "запоролся",
counter_1 используется чтобы после обратного возврата на "развилку" мы не пошли тем же ложным путем из-за которого мы и вернулись сюда.
Это видно в состоянии 1 если терминал "а" не подошел то после обратного возврата на состояние 1 мы больше не будем пытаться идти путем через терминал  "а", а пойдем путем через терминал "c".

Так о чем собственно речь, этот способ вполне рабочий, но если ДКА будет более "сложным" и из какого-нибудь состояния мы обратно попадем на развилку которую до этого уже прошли и этот counter_... уже не допустит ни в 1 из if/else if, т.к. до этого мы уже прошли все if/else if то мой вариант не прокатывает.

Вот... как корректно должен выглядеть код при развилках и повторениях этих же самих развилок?
Или я совсем не тем путем пошел?

з.ы. надеюсь доступно объяснил ситуацию, если что не понятно спрашивайте

Автор: boostcoder 28.6.2011, 23:33
я нифига не понял... но чем-то напомнило http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0

Автор: rudvil 28.6.2011, 23:48
Цитата(boostcoder @ 28.6.2011,  23:33)
я нифига не понял... но чем-то напомнило http://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0

Проще говоря пытаюсь написать генератор парсера, чтобы на выходе генерировался С++ код самого парсера.
Интересуют варианты реализации парсера из ДКА в виде switch'a.
Насчет ссылки, спасибо конечно почитаю - но не уверен что поможет.

Автор: boostcoder 29.6.2011, 01:11
вообще, для генерации парсеров используют bison, flex, yacc...

Автор: rudvil 29.6.2011, 01:21
Цитата(boostcoder @ 29.6.2011,  01:11)
вообще, для генерации парсеров используют bison, flex, yacc...

конечно я о них знаю, хочется повелосипедить + расширить кругозор, столько всего нового узнал пока все это писал  smile 

Автор: afiskon 29.6.2011, 07:18
Явно делаете что-то не так. Лексический анализатор среднего процедурного языка программирования можно уложить в 100-150 строк кода на си. Синтаксический анализатор - это еще 100-150 строк. Учите мат часть про разработку компиляторов. Начать можно с понимания того, что такое LL(1) грамматика и почему это важно в разработке парсеров/компиляторов.

Автор: boostcoder 29.6.2011, 07:25
Цитата(afiskon @  29.6.2011,  07:18 Найти цитируемый пост)
Лексический анализатор среднего процедурного языка программирования можно уложить в 100-150 строк кода на си. Синтаксический анализатор - это еще 100-150 строк.

сколько вам нужно заплатить, чтоб увидеть решение в 100-150 строк? smile 
просто любопытно что у вас получится.

Автор: Earnest 29.6.2011, 10:31
boostcoder, вообще-то для лексического анализатора это даже много: чего там писать-то в этих строках, разве что на ассемблере...
Синтаксический - ну как повезет с грамматикой... И как считать строки (скажем, если определения классов не учитывать, а только процедурный код, то можно и уложиться, наверное)

Автор: rudvil 29.6.2011, 10:42
Цитата(afiskon @ 29.6.2011,  07:18)
Явно делаете что-то не так. Лексический анализатор среднего процедурного языка программирования можно уложить в 100-150 строк кода на си. Синтаксический анализатор - это еще 100-150 строк. Учите мат часть про разработку компиляторов. Начать можно с понимания того, что такое LL(1) грамматика и почему это важно в разработке парсеров/компиляторов.

Это не лексический анализатор, это часть кода парсера сгенерированного моей программой из вышеупомянутого ДКА(а ДКА в свою очередь из ebnf правила...), т.е. код не рукописный.
Про компиляторы я читал, и про LL(1) тоже, только я не пишу парсер к "чему-то", а пишу генератор, который будет генерировать из заданной грамматики готовый парсер.
Тут интересует конкретная деталь: разветвление и их возможные повторения, подробно я описал выше.

Автор: xvr 29.6.2011, 13:02
Цитата(rudvil @  28.6.2011,  23:13 Найти цитируемый пост)
Стек нужен для того чтобы возвратиться обратно на "развилку" если один из путей развилки "запоролся",

Для ДКА такого не бывает. Граф переходов автомата строится с учетом всех возможных переходов, в том числе и возвратов из развилок.
Так что никакой counter и стек там не нужен, а нужен правильный генератор ДКА.

Из ebnf напрямую генерируется НКА, а уже из него - ДКА. Сгенерировать ДКА напрямую из ebnf практически невозможно  smile 

Автор: rudvil 29.6.2011, 13:33
Цитата

Из ebnf напрямую генерируется НКА, а уже из него - ДКА. Сгенерировать ДКА напрямую из ebnf практически невозможно  

У меня также, просто не упомянул, извиняюсь.
Цитата

Так что никакой counter и стек там не нужен, а нужен правильный генератор ДКА.

Брал за основу http://www.codeproject.com/KB/recipes/OwnRegExpressionsParser.aspx статью и переделал код под себя(ebnf).
Имхо там все корректно работает.
Цитата

Для ДКА такого не бывает. Граф переходов автомата строится с учетом всех возможных переходов, в том числе и возвратов из развилок.

Но ведь после неудачного пути в развилке, нужно как-то запоминать где мы уже были, а где нет? иначе будет бесконечный цикл.
Для этого я и химичил со стеком и counter'ом.

Если я в корне не правильно генерирую код, поправьте.
И если не трудно  smile , спасибо.

Автор: xvr 29.6.2011, 22:33
Цитата(rudvil @  29.6.2011,  13:33 Найти цитируемый пост)
Но ведь после неудачного пути в развилке,

В DFA не бывает 'неудачного пути'. Там все пути детерминированны и однозначны. Любой переход между узлами делается по какому то конкретному символу. И если мы пошли по какой то ветке из узла, то мы никоим образом не можем пойти из этого же узла по другой ветке.
Если автомат зашел в тупик, то это значит, что входная последовательность не матчится с образцом. Ничего перебирать не нужно.

Цитата(rudvil @  29.6.2011,  13:33 Найти цитируемый пост)
И если не трудно  smile , спасибо

Код

int match(char* src)
{
 int state=1;
 for(;;)
  {
   char* cur_sym = *src++;
   switch(state)
     {
      case 1:
        switch(cur_sym)
          {
            case 'a': state=2; break;
            case 'c': state=4; break;
            default: return -1;
          }
        break;
      case 2:
        switch(cur_sym)
          {
            case 'b': state=6; break;
            default: return -1;
          }
        break;
      case 4:
        switch(cur_sym)
          {
            case 'd': state=5; break;
            default: return -1;
          }
        break;
      case 5: return 5;
      case 6: return 6;
     }
  }
}

Автор: rudvil 29.6.2011, 22:50
xvr, большое вам спасибо, очень доступно  smile  
Все оказалось как всегда проще  smile 
с меня "+", завтра поставлю.

Автор: afiskon 30.6.2011, 07:05
Цитата(boostcoder @ 29.6.2011,  07:25)
Цитата(afiskon @  29.6.2011,  07:18 Найти цитируемый пост)
Лексический анализатор среднего процедурного языка программирования можно уложить в 100-150 строк кода на си. Синтаксический анализатор - это еще 100-150 строк.

сколько вам нужно заплатить, чтоб увидеть решение в 100-150 строк? smile 
просто любопытно что у вас получится.

Поищу сегодня вечером на диске, если не забуду.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)