Всем привет, пытаюсь реализовать на switch'e ДКА, впринципе кое-что получается.
Не могу разобраться с корректным кодом для "развилок" на графе ниже "развилка" из состояния 1 в состояние 2 или 4.
Для примера возьмем ebnf правило
По нему строим ДКА... получаем:
Я добился автогенерации след. кода для вышеуказанного ДКА
Кратко поясню, что тут творится, а именно о стеке last_state и о переменной counter_1.
Стек нужен для того чтобы возвратиться обратно на "развилку" если один из путей развилки "запоролся",
counter_1 используется чтобы после обратного возврата на "развилку" мы не пошли тем же ложным путем из-за которого мы и вернулись сюда.
Это видно в состоянии 1 если терминал "а" не подошел то после обратного возврата на состояние 1 мы больше не будем пытаться идти путем через терминал  "а", а пойдем путем через терминал "c".

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

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

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

Это сообщение отредактировал(а) rudvil - 28.6.2011, 23:17

я нифига не понял... но чем-то напомнило Машину Тьюринга

Это сообщение отредактировал(а) boostcoder - 28.6.2011, 23:33

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

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

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

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

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

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

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

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

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

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

Брал за основу эту статью и переделал код под себя(ebnf).
Имхо там все корректно работает.

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

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

Это сообщение отредактировал(а) rudvil - 29.6.2011, 13:34

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

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

Это сообщение отредактировал(а) rudvil - 29.6.2011, 22:51

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