Адаптированный алгоритм Эрли - описание
От: mefrill Россия  
Дата: 17.01.06 17:46
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Только одно но. Быстро восоздать алгоритм по твоей статье и коду на С++ мне явно не удастся. Нужно более простое объяснение. Можно попробывать сделать что-то в интерактивном режиме.

VD>Если есть желание можно попробовать.

Нет проблем. За базу можно взять какой-нибудь простой пример. Сначала разобраться что такое ситуация, затем что такое эти самые три процедуры: Scanner, Completer и Predictor. Параллельно можно смотреть мой код, там на самом деле несложно, просто пришлось от STL отказаться, поиск по спискам очень сильно тормозил, на создание итератора до фига времени шло. А сама реализация занимает всего несколько функций. Вообще, алгоритм очень простой, но вот объяснить его сложно, к сожалению. Давай начнем с примера? Предлагаю заинтересованным лицам присоедениться.

Итак, что такое ситуация? Это, на самом деле, просто пара из помеченного правила (т.е. правила с точкой в правой части) и некоторого числа в диапазоне от нуля до длины входной строки. Например, имеем правила


S --> A B
A --> a
B --> b


можно построить следующие помеченные правила (точку для удобства обозначим звездочкой):


S --> * A B, S --> A * B, S --> A B *
A --> * a, A --> a *
B --> * b, B --> b *



Вот ситуация, это например, такая пара [S --> A * B, 0] или такая [B --> b *, 5].

полагаем, что входная строка это omega = a1...an состоит из n символов.

Алгоритм Эрли строит списки таких ситуаций, один список для каждого символа входной строки. Есть еще список для нулевой позиции при чтении строки. Т.е. если входная строка имеет длины n, то списков у нас будет построено n+1, и пронумерованы они будут от 0 до n.

Считается, что входная строка распознана успешно в данной грамматике, если в последнем списке, т.е. в списке, соответствующем последнему символу входной строки, есть ситуация вида [S --> X1...Xk *, 0]. Т.е. помеченное правило должно иметь точку в самом конца правой части и символ в левой части правила должен быть начальным нетерминалом грамматики, а второй элемент ситуации — число, должно быть равно нулю.

В чем состоит таинственный смысл понятия ситуации? Он не так уж и сложен. Если мы имеем ситуацию вида [A --> alpha * beta, i], принадлежащую списку номер p, то это значит, что из строки alpha в правой части правила A --> alpha beta выводится часть ai...ap нашей входной сnроки omega. Т.е. мы имеем дерево


                  alpha
                 /      \
        a1......ai.......ap.....an



Но дерево это не произвольно, а в контексте всей грамматики, т.е. нетерминал A для правила A --> alpha beta реально задействован в каком-то дереве для вывода всеей подстроки a1...ap. Поэтому, если мы имеем ситуацию вида [S --> X1...Xk *, 0], это значит мы реально имеем дерево


                     S
                    /  \
                   X1...Xk
                  /        \
                 a1.........an



что нам и нужно.

Итак, каждая ситуация Эрли на самом деле означает некотрое конкретное дерево, а точнее — узел некоторого дерева вывода какой-то подстроки нашей входной строки omega. Алгоритм Эрли на самом деле состоит в последовательном потсроении всех таких деревьев-ситуаций начиная с первого символа входной тсроки. Какие-то деревья дальше не продолжаются, какие-то продолжаются, растут и, в конце-концов, выростают в деревья с вершинами в начальном нетерминале грамматики, покарывающие всю входную строку.

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


18.01.06 00:30: Ветка выделена из темы Идеальный парсер: Адаптированный алгоритм Эрли: Адапт
Автор: mefrill
Дата: 12.01.06
— VladD2
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.