| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Синтаксический анализ неполной цепочки |
| Автор: WandG 17.6.2009, 14:28 |
| Доброго времени суток! Есть обширная теория по распознанию цепочки на основе заданной грамматики, методы анализа также отвечают на вопрос выводима ли цепочка в данной граматике. А есть ли какие-нибудь методы, позволяющие решить такой вопрос: есть цепочка, определить может ли она является подцепочкой корректной цепочки. Например, есть язык a^n, b^n (n > 0) - цепочки вида ab, aabb, aaabbb, ... На входе есть цепочка aab - она не принадлежит этому языку, но может быть подцепочкой корректной цепочки, например, aabb (добавили букву b справа). Или, например, есть цепочка aba, очевидно, что она сама не принадлежит языку и никакая цепочка ее содержащая тоже языку не принадлежит. Единственное, что приходит на ум - это модификация анализатора снизу вверх. Буду рад ссылкам и просто идеям. Спасибо! |
| Автор: AVA12 17.6.2009, 17:53 |
| Странный вопрос. Вообще-то, такой анализ является неотъемлемой частью разбора строки. Нужно просто следить за состоянием автомата, анализирующего строку (для грамматики (a*n)(b*n) подойдет автомат с магазинной памятью). Если строка переводит автомат в недопускающее состояние (либо для очередного символа отсутствует правило перехода), то она не принадлежит языку и не является префиксом корректной строки. Если строка переводит автомат в допускающее состояние и стек пуст, то строка принадлежит языку. В остальных случаях строка не принадлежит языку, но является корректным префиксом. |
| Автор: WandG 17.6.2009, 18:39 |
| Спасибо, за ответ, для определения корректных префиксов такой способ действительно подходит. Но я, наверно, не очень хорошо задал вопрос, вообще говоря, интересует проверка любой подстроки, находящейся не обязательно в начале или в конце цепочки. Для наглядности переделаю пример: язык a^n b^n c^n цепочка bbbc - она может содержаться в правильной строке, например aaabbbccc а вот цепочка содержащая подцепочку ac не принадлежит языку Но, вообще говоря, интересует любая информация в т.ч. и по разным частным случаям. |
| Автор: AVA12 17.6.2009, 19:53 |
| Это уже гораздо сложнее. Смутно вырисовывается алгоритм с "обратным" автоматом и описанием всех допустимых состояний... Но это все как-то неубедительно. И годится не для всех случаев. Боюсь, для каждой конкретной грамматики придется придумывать отдельный алгоритм. Если не секрет, откуда взялась такая странная задача? |
| Автор: WandG 17.6.2009, 21:58 |
| Да, общий метод тут особо не придумаешь, надо как минимум выделять классы грамматик и т.п. А исходная задача такая: есть несколько служебных форматов файлов, для которых было бы очень здорово научиться собирать "разбитые" файлы, т.е. есть кусок памяти, надо найти в нем кусочки нашего файла и склеить их. Если формат представить какой-нибудь грамматикой вроде: файл --> заголовок, тело, конец. заголовок --> 0x1234, 0x5678, номер_версии. ну и т.д. то файл, можно воспринимать как цепочку, а задача определения "нашего кусочка" перерастает в то, что озвучено. Реальная задача, конечно, существенно более простая в силу разных особенностей. Но перед тем как решать задачу в лоб, хотелось бы посмотреть, что по этому поводу думает теория, может подчерпнуть идеи. Да и сформулированная в абстрактном виде проблема, мне показалось интересной. |
| Автор: maxdiver 18.6.2009, 14:48 |
| Очень похоже на задачу множественного поиска подстроки в строках. Но в этой задаче подстрока ищется в однозначно определённых строках (из них составляется бор, в нём строятся суффиксные ссылки - алгоритм Ахо-Корасик), а здесь же, похоже, постоянно возникают неопределённости... |
| Автор: WandG 18.6.2009, 15:56 |
| Спасибо, почитаю на досуге что это за алгоритм Ахо-Корасика, может что в голову еще прийдет. |
| Автор: maxdiver 18.6.2009, 16:45 |
| Блин, запутался я немножко. Алгоритм Ахо-Корасик ищет сразу несколько слов в качестве подстроки какой-то одной строки. Т.е. строки словаря в данном тексте. А у нас задача обратная... Так что это не подойдет |