Здравствуйте, 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. Алгоритм Эрли на самом деле состоит в последовательном потсроении всех таких деревьев-ситуаций начиная с первого символа входной тсроки. Какие-то деревья дальше не продолжаются, какие-то продолжаются, растут и, в конце-концов, выростают в деревья с вершинами в начальном нетерминале грамматики, покарывающие всю входную строку.
Теперь надо выяснить каким образом эти списки узлов деревьев (ситуаций) строятся и как вообще из одних ситуаций следуют другие. Но, прежде чем перейти к этому вопросу, хотелось бы выяснить, все-ли понятно с понятием ситуации?
О том что такое ситуация, лично мне, было примерно понятно еще из статьи. Но все равно спасибо за более доступное изложение.
Единственное замечание которое хочется сделать — это то что не все хорошо воспринимают обстрактные примеры. Книги и статьи по теории парсинга постоянно оперируют этими абстрактными примерами, и это неизменно вызвает непонимание у многих читателей. По этому предлагаю взять в качестве примеров нечто знакомое всем окружающим. Например в статье использовалось сложение. Если нужно что-то более сложное, то можно взять граматику оператора "?:" из С и т.п. В общем, чтобы примеры были более реальны. Так проще их уложить в голове.
Ну, а что до алгоритма, то лично у меня вызвают вопросы именно реализация функций Scanner, Completer и Predictor. Собственно интересна не только реализация, но и их смысл.
Как я понимаю ситуацию можно описать так (C#):
class Situation
{
public int RuleIndex; // индекс в некотором массиве правилpublic int PosInRule; // позиция в правиле (та самая звездочка/точка)public int TokenIndex; // Номер символа разбираемой строки
}
Хранить их наверно лучше в динамическом массиве для которого заранее занимать по больше памяти (чтобы небыло перезаемов). Если нужен их поиск, то вместо массива наверно стоит хранить их в хэш-таблице (точнее даже хэш-сете).
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, mefrill, Вы писали:
VD>О том что такое ситуация, лично мне, было примерно понятно еще из статьи. Но все равно спасибо за более доступное изложение.
VD>Единственное замечание которое хочется сделать — это то что не все хорошо воспринимают обстрактные примеры. Книги и статьи по теории парсинга постоянно оперируют этими абстрактными примерами, и это неизменно вызвает непонимание у многих читателей. По этому предлагаю взять в качестве примеров нечто знакомое всем окружающим. Например в статье использовалось сложение. Если нужно что-то более сложное, то можно взять граматику оператора "?:" из С и т.п. В общем, чтобы примеры были более реальны. Так проще их уложить в голове.
Хорошо, как раз дошла очередь и до примеров.
VD>Ну, а что до алгоритма, то лично у меня вызвают вопросы именно реализация функций Scanner, Completer и Predictor. Собственно интересна не только реализация, но и их смысл.
В соседней ветке это оптсараююсь описать.
VD>Как я понимаю ситуацию можно описать так (C#): VD>
VD>class Situation
VD>{
VD> public int RuleIndex; // индекс в некотором массиве правил
VD> public int PosInRule; // позиция в правиле (та самая звездочка/точка)
VD> public int TokenIndex; // Номер символа разбираемой строки
VD>}
VD>
VD>Хранить их наверно лучше в динамическом массиве для которого заранее занимать по больше памяти (чтобы небыло перезаемов). Если нужен их поиск, то вместо массива наверно стоит хранить их в хэш-таблице (точнее даже хэш-сете).
Я храню (и убежден, что это самое лучшее решение) списки ситуаций в состоянии как множество отдельных списков, каждый из которых соответствует определенному символу грамматики. Дело в том, что операции Completer и Scanner осуществляют поиск по спискам ситуаций с целью найти ситуации, где определенный символ стоит после точки в правой части правила. Чтобы такого поиска не осуществлялось, я просто храню для каждого символа все ситуации, где этот символ стоит после точки. Тогда и поиска, фактически, производить не нужно будет.
Каким образом заполняются списки ситуаций для каждого символа входной строки? (их еще называют состояниями Эрли)
Вообще говоря, с помощью сдвига точки на один символ вправо, т.е. ситуация вида [A --> X1...Xk * Xk+1...Xp, i], принадлежащая списку под номером j, может попасть в какой-то список с большим номером только передвинув точку вправо т.е. трансформируясь в ситуацию вида [A --> X1...Xk+1 * Xk+2...Xp, i]. Одни ситуации попадают в списки правее, другие нет. Каким образом и почему это происходит?
С помощью трех операций:
Scanner — работает только с терминальными символами. Scanner работает на некотором списке Si когда тот уже заполнен плностью, т.е. туда больше ничего добавить нельзя. Поэтому настает время перейти к заполнению следующего списка Si+1. Т.е. Scanner вызывается для инициализации каждого списка S1...Sn, а список S0 инициализируется особым образом. Что делает Scanner? Он сравнивает символ ai+1 во входной терминальной строке с символом после точки в каждой ситуации из списка Si и, если символ после точки совпадает с символом ai+1, то Scanner добавляет эту ситуацию в список Si+1, преварительно передвинув точку в правой части правила ситуации на символ правее. Например, у нас в списке Si были такие ситуации:
[A --> Bc*gA, 0]
[A --> c*B, 3]
[S --> *gf,1]
и текущий символ во входной строке есть g. Тогда Scanner пройдет по списку ситуаций, найдет две из них [A --> Bc*gA, 0] и [S --> *gf,1], где символо после точки равен g, и добавит в следующщий список Si+1 ситуации
[A --> Bcg*A, 0]
[S --> g*f,1]
Каким деревьям соответсвуют ситуации из списка Si? Вот каким:
A
/ \
Bc gA
/ \
/ \
a1....ak+1.......ai ai+1.......an
A
/ \
c B
/ \
/ \
a1....al+1.......ai ai+1.......an
S
/ \
g f
a1....ai+1.......an
Обратим внимане, что в последнем дереве фактически из символа S пока ничего не выводится, так как точка в правой части правила стоит крайней слева, т.е. пока ни один символ з правой части правила не выводился.
Теперь надо пройти дальше, т.е. продолжить вывод деревьев. Из трех деревьев только два могут быть продолжены, ведь ai+1 равен символу g. Итак, продолжаем вывод этих деревьев, получаем деревья.
A
/ \
Bcg A
/ \
/ \
a1....ak+1.......ai+1.......an
S
/ \
g f
|
a1...ai+1.......an
Процедура Completer осуществляет такой же сдвиг точки, как и процедура Scanner, но работает на нетерминальных символах. Как она работает? Предположим, что в каком-то списке Si у нас ситуация, в которой точка стоит в самом конца правой части правила. т.е. ситуация вида [A --> X1...Xk *, j]. Что это значит на дереве вывода? Это значит, что у нас есть такое дерево вывода:
A
/ \
X1...Xk
/ \
/ \
a1....aj+1...........ai.......an
Т.е. символ A полностью вывелся в строку aj+1...ai. Почему именно aj+1...ai? Обратим внимание на вторую компоненту ситуации [A --> X1...Xk *, j] — это число j. Что такое j? Это номер списка, в котором эта ситуация "родилась", т.е. в который была добавлена ситуация вида [A --> * X1...Xk, j] с точкой в самом начале правой части правила. А номер i — это номер списка Si, которому принадлежит ситуация [A --> X1...Xk *, j].
Теперь. предположим, что в списке Sj у нас есть ситуация вида [B --> alpha * A beta, l]. Это значит, что есть дерево
B
/ \
alpha A beta
/ \
/ \
a1....al+1........aj.......an
Сравнивая деревья для обеих ситуаций, имеем дерево
B
/ \
/ \
alpha A beta
/ \ / \
al+1.....aj X1....Xk
/ \
a1... aj+1........ai.....an
Иначе говоря, в списке Si мы должны иметь ситуацию вида [B --> alpha A * beta, l], соответсвующую дереву
B
/ \
/ \
alpha A beta
/ \
a1...al+1........ai.....an
Где символ A вывелся через строку X1...Xk ==> aj+1...ai.
Как добавить такую ситуацию в список Si? Простым вычислимым процессом. Мы идем в список Sj, ищем там все ситуации, где символ после точки есть символ A. и добаляем их в список Si, предварительно сдвинув точку на символ правее. Т.е. для ситуации [B --> alpha * A beta, l] мы действительно добавим в список Si ситуацию [B --> alpha A * beta, l].
Итак, операция Completer, примененная к ситуации [A --> X1...Xk *, j], принадлежащей списку Si, делает следующее:
1. Проходит по всем ситуациям списка Sj.
2. Если в ситуации символ после точки есть символ A, то добавляет эту ситуацию в список Si, сдвинув предварительно точку в правой части на символ правее.
И последняя операция — это Predictor. Название для нее предсказатель и функция как раз в предсказании и состоит. Что она делает? Она добавляет в текущий список ситуации, в которых точка стоит в самом начале правой части правила. Ведь ни Scanner ни Completer такого не делают, кто-то должен такие ситуации-заготовки добавлять? Ситуация, в которой точка стоит в начале правой части помеченного правила, на самом деле означает, что из правой части правила пока ничего не вывелось, но потенциально может быть выведено. Вот эту потенциальную возможность выводимости и предсказывает Predictor. Как он это делает? Предположим, что в некотором списке Si есть ситуация вида [B --> alpha * A beta, j]. Это значит есть дерево
B
/ \
/ \
alpha A beta
/ \
a1...aj+1......ai.....an
Как может быть выведен символ A? Конечно, через правила грамматики вида A --> delta, где символ в левой части есть нетерминал A. Во операция Predictor и добавляет ситуации для всех таких правил, т.е. добавляет ситуации вида [A --> * delta, i] для каждого правила вида A --> delta из нашей грамматики. Обратим внимание, что вторая компонента ситуации есть номер текущего списка Si, т.е. число i. Но это и естественно, ведь вывод правила A --> delta в текущем контексте начнется (если начнется) с символа ai+1, т.е. мы как раз перед ним и находимся и еще пока ни одного символа из строки delta не выведено.
Итак, операция Predictor, примененная к ситуации [B --> alpha * A beta, j], принадлежащей списку Si, делает следующее:
1. Проходит по правилам грамматики.
2. Для каждого правила вида A --> delta, где символ в левой части совпадает с символом после точки, добаляет в список Si ситуацию [A --> * delta, i].
Для заоплнения списков мы сначала инициализируем список операцией Scanner, примененной к предыдущему списку, а затем, к каждой ситуации из списка применяем процедуры Completer и Predictor. Эти процедуры добавляют новые, и к ним тоже применяем процедуры Completer и Predictor, и т.д. пока в списко не перестанут добавляться новые ситуации. Этот процесс обязательно закончится, это доказано.
Единственное исключение — это инициализация нулевого списка, ведь Scanner здесь не применишь, не к чему. Нулевой список инициализируется операцией Predictor, примененной к начальному символу грамматики. Т.е. для каждого правила грамматики вида S --> alpha, где символ слева — это начальный нетерминал грамматики S, добавляем в нулевой список ситуацию вида [S --> * alpha, 0]. И дальше точно также начинаем применять операции Completer и Predictor.
Пока все, будут вопросы — с удовольствием отвечу. Когда то, что я написал, достточно переварится, можно посмотреть работу алгоритма на конкретном примере, а также кое-какой код написать, ведь алгоритм очень простой для реализации.
Здравствуйте, mefrill, Вы писали:
M>Я храню (и убежден, что это самое лучшее решение) списки ситуаций в состоянии как множество отдельных списков, каждый из которых соответствует определенному символу грамматики. Дело в том, что операции Completer и Scanner осуществляют поиск по спискам ситуаций с целью найти ситуации, где определенный символ стоит после точки в правой части правила. Чтобы такого поиска не осуществлялось, я просто храню для каждого символа все ситуации, где этот символ стоит после точки. Тогда и поиска, фактически, производить не нужно будет.
Я пока что не очень понимаю алгритм, но храниние списков в 99% случаев == тормоза. Так как сапски это:
1. Вечные поиски перебором.
2. Расход лишней памяти.
3. Плохая локализация связанных элементов.
Как показывает мой опыт связка массивов и хэш-таблиц обычно бывает быстрее любых других решений.
Ну, да когда я пойму алгоритм целиком можно будет подумать и провести ряд эксперементов. Оптимальную структуру для неизвесного алгоритма подобрать невозможно.
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Я пока что не очень понимаю алгритм, но храниние списков в 99% случаев == тормоза. Так как сапски это: VD>1. Вечные поиски перебором. VD>2. Расход лишней памяти. VD>3. Плохая локализация связанных элементов.
VD>Как показывает мой опыт связка массивов и хэш-таблиц обычно бывает быстрее любых других решений.
В том-то и дело, что чпецифика алгоритма такова, что поиска в этом случае вообще не будет. Ведь поиск идет по каждой из операций Scanner, Completer и Predictor. Scanner ищет все ситуации, где символ после точки — это терминал, совпадающий со следующим входным символом. Если мы держим в отдельном списке все ситуации, у которых после точки этот символ стоит, тогда мы ничего не ищем, просто берем и обрабатываем каждый из них. Для операции Completer точно такая же картина. А вот Predictor работает уже с исходной грамматикой. Эта операция ищет в грамматике все правила, у которых символ слева — это нужный нетерминал. Точно так-же можно разбить грамматику на такие списки для каждого нетерминала и поиска тогда вообще не будет. Т.е. на самом деле, это и есть хэш-таблица, где роль хэш-функции играет простое вычисление номера символа грамматики. Почему так важно хорошо пронумеровать символы грамматики перед запуском алгоритма.
Теперь приведу пример. Пусть грамматика имеет следующий вид:
S --> S + n
S --> n
где, S — нетерминальный и начальный символ грамматики, а n и + — терминалы.
Пусть на вход подается строка n+n. Посмотрим как алгоритм Эрли проведет разбор данной строки на основе грамматики выше.
Первым шагом алгоритма является добавление в нулевой список S0 ситуаций для правил с начальным нетерминалом S в левой части. В нашей грамматике оба правила имеют нетерминал S в левой части, поэтому добавляем в список S0 две ситуации [S --> * S + n, 0] и [S --> * n, 0]. Запускаем на этом списке Predictor и Completer. Completer работать не будет, т.к. он работает только на ситуациях, у которых точка стоит в самом конце правой части правила, а у нас сейчас в списке таких нет. Predictor сканирует каждую ситуацию в списке чтбы найти нетерминал после точки. В нашем случае, мы имеем в первой ситуации [S --> * S + n, 0] нетерминал S после точки и надо добавить в список S0 ситуации для всех правил грамматики, у которых нетерминал S (после точки) стоит в левой части. Но, так как неетрминал S — начальный нетерминал грамматики, мы уже добавили все правила с ним в левой части в наш список S0, так что ничего больше не добавляем. Следующая ситуация — это [S --> * n, 0]. В ней после точки стоит терминальный символ n, так что ничего не добавляем. Т.о. обработка списка S0 операциями Predictor и Completer ничего нового в этот список не добавили, поэтому переходим к заполнению списка S1. Для этого запускаем процедуру Scanner на списке S0 и читаем первый входной символ строки n+n, это терминал n. Проходим по списку S0:
в ситуации [S --> * S + n, 0] после точки стоит символ S, он не равен текущему символу n входной строки, поэтому пропускаем эту ситуацию. Следующая ситуация — это [S --> * n, 0]. Вот у нее символ после точки равен n. Поэтому, добавляем эту ситуацию в список S1, сдвинув точку на символ правее, имеем ситуацию [S --> n *, 0] в списке S1. Применяем теперь операции Predictor и Completer. Применение Predictor ничего не дает, ведь после точки нет никакого символа. А вот Completer здесь применить можно, т.к. точка в ситуации [S --> n *, 0] стоит в конце правой части. Итак, смотрим на второй элемент ситуации — это число 0. Идем в список S0 и ищем там ситуации, у которых символ S стоит после точки. Такая ситуация есть, это [S --> * S + n, 0]. Добавляем ее в наш список S1, сдвинув точку на символ правее. Имеем в списке S1 две ситуации:
уже обработанную процедурами Predictor и Completer ситуацию [S --> n *, 0] и еще не обработанную ситуацию [S --> S * + n, 0].
обрабатываем последнюю ситуацию. Predictor на ней не работает, т.к. символ после точки — нетерминальный, а Completer работаь также не может, ведь точка стоит не в конце правой части. Поэтому список остается тем же.
Запускаем операцию Scanner для инициализации списка S2. Второй символ входной строки n+n — это символ +. Проходим по списку S1 и сравниваем символ после точки в ситуации [S --> n *, 0] с символом +. Там вообще никакого символа нет, поэтому переходим к ситуации [S --> S * + n, 0]. У нее символ после точки равен символу +, поэтому добавляем эту ситуацию в список S2, передвинув точку вправо. Имеем в списке S2 одну ситуацию [S --> S + * n, 0]. Очевидно, что ни Predictor ни Completer на этой ситуации не работают, в первом случае символ после точки — терминальный, во втором — точка не в конце правой части.
переходим к заполнению списка S3. Третий список входной строки n+n — это n. Сканируем список S2, он сотоит из одной ситуации [S --> S + * n, 0]. Символ после точки равен символу n, поэтому добавляем эту ситуацию в список S3, предварительно сдвинув точку на символ правее. Имеем в списке S3 ситуацию [S --> S + n *, 0]. Операция Predictor, очевидно, к этой ситуации не применима, а вот Completer работает. Смотрим второй элемент ситуации — это число 0, идем в список S0 и ищем в нем ситуации, в которых символ S (который в помеченном правиле S --> S + n * стоит в левой части) стоит после точки. Такая ситуация есть, это [S --> * S + n, 0]. Добавляем ее в список S3, передвинув точку на символ вправо. Имеем ситуацию [S --> S * + n, 0]. Обрабатываем ее операциями Predictor и Completer, ни одна из них не добавляет новой ситуации в список S3, входная строка закончена, поэтому завершаем работу алгоритма. Итак, имеем списки:
S0
[S --> * S + n, 0]
[S --> * n, 0]
S1
[S --> * n, 0]
[S --> S * + n, 0]
S2
[S --> S + * n, 0]
S3
[S --> S + n *, 0]
[S --> S * + n, 0]
Выводится ли строка n+n в нашей граматике? Да, ведь список S3 содержит ситуацию [S --> S + n *, 0], в котрой точка стоит в конце правой части правила, символ в левой части есть начальный нетерминал грамматики и второй компонент правила есть 0.
Следующим шагом может быть попытка написать работающий алгоритм Эрли.
Здравствуйте, mefrill, Вы писали:
M>В том-то и дело, что чпецифика алгоритма такова, что поиска в этом случае вообще не будет. Ведь поиск идет по каждой из операций Scanner, Completer и Predictor. Scanner ищет все ситуации, где символ после точки — это терминал, совпадающий со следующим входным символом. Если мы держим в отдельном списке все ситуации, у которых после точки этот символ стоит, тогда мы ничего не ищем, просто берем и обрабатываем каждый из них. Для операции Completer точно такая же картина. А вот Predictor работает уже с исходной грамматикой. Эта операция ищет в грамматике все правила, у которых символ слева — это нужный нетерминал. Точно так-же можно разбить грамматику на такие списки для каждого нетерминала и поиска тогда вообще не будет. Т.е. на самом деле, это и есть хэш-таблица, где роль хэш-функции играет простое вычисление номера символа грамматики. Почему так важно хорошо пронумеровать символы грамматики перед запуском алгоритма.
Но ведь есть списки по которым нужно каждый раз пробегаться. Это и вызовет замедление алгоритма. Единственная возможность сделать алгоритм O(n) — это сделать так, чтобы в списках в 99% случаев было по одному элементу. Но боюсь это не реально.
Пока думал над алгоритмом в голову пришла мысль...
А что если спарить этот алгоритм с LL(1)-автоматом? Ну, пока граматика однозначна для LL(1)-парсера, парсим супер эффективным ДКА. А как толко появляется неоднозначность переходим на Эрли. Проблема тольк в том, как возвращаться обратно когда найдено две подветки или устрнена LL(1)-неоднозначность?
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Но ведь есть списки по которым нужно каждый раз пробегаться. Это и вызовет замедление алгоритма. Единственная возможность сделать алгоритм O(n) — это сделать так, чтобы в списках в 99% случаев было по одному элементу. Но боюсь это не реально.
Почему каждый раз? Предиктор только один раз работает, также каждая ситуация тоже обрабатывается не более одного раза. Если нет альтернатив, то вообще только один раз все будет работать. Вот в примере, который я привел в соседней ветке, там ведь по одному разу обходится. Scanner работает тоже один раз. Весь вопрос только в операции Completer, это самая дорогостоящая операция. Но и там, если грамматика позволяет парсить без ворзвратов, то все будет нормально, тоже только раз такой список будет пройден.
VD>Пока думал над алгоритмом в голову пришла мысль... VD>А что если спарить этот алгоритм с LL(1)-автоматом? Ну, пока граматика однозначна для LL(1)-парсера, парсим супер эффективным ДКА. А как толко появляется неоднозначность переходим на Эрли. Проблема тольк в том, как возвращаться обратно когда найдено две подветки или устрнена LL(1)-неоднозначность?
Немного непонятно, что подразумевается под LL(1)-автоматом? Если имеется ввиду те First и Follow множетсва, то конечно, можно. Этот вопрос еще в 1974 году (если правильно помню) исследовался и было показано, что использование таких множеств может уменьшить количество ситуаций с списках и улучшить производительность операции Predictor (которая и так достаточно быстрая), но не намного. У меня этот метод реализован в первом варианте парсера, который я для диссертации писал. Но особых преимуществ я не получил, только в специальных случаях. В общем, особого смысла я в этом не вижу. На неоднозначность это не влияет никаки образом, а если надо быстрый парсер для простой грамматики, то гораздо легче и эффективнее построить LR-анализатор.
Здравствуйте, mefrill, Вы писали:
M>Немного непонятно, что подразумевается под LL(1)-автоматом? Если имеется ввиду те First и Follow множетсва, то конечно, можно.
Почти. Я имею введу ДКА построеный на основе тех самых множеств. Удобно создать таблицу и проверять возможность выполения операции по ней, а не делать кучу ифов/свитчей.
M> Этот вопрос еще в 1974 году (если правильно помню) исследовался и было показано, что использование таких множеств может уменьшить количество ситуаций с списках и улучшить производительность операции Predictor (которая и так достаточно быстрая), но не намного. У меня этот метод реализован в первом варианте парсера, который я для диссертации писал. Но особых преимуществ я не получил, только в специальных случаях. В общем, особого смысла я в этом не вижу. На неоднозначность это не влияет никаки образом, а если надо быстрый парсер для простой грамматики, то гораздо легче и эффективнее построить LR-анализатор.
Я уже устал повторять, что LR годятся только для помойки. Таких грамматик которые они могут парсить (без костылей) и которые не могут парсить куда более простые LL(1)-парсеры я просто не видел. А учитывая геморрой с их отладкой и качество сообщений об ошибках которые они порождают, то я бы вообще их век не видел.
Нужен парсер который съедает граматику современных ЯП. Это не простой или очень сложный случай. Это просто конкреный случай. В нем почти всегда есть места проблемыне как для LR-парсеров, так и для LL. С другой стороны процентов 90 грамматики таки подпадает под LL(1)-правила.
Вот я и думаю. Нельзя ли сделать LL(1)-парсер переходящий на более изощьренные алгоритмы только в 10% случаев где действительно LL-парсер уже бессилен?
... << RSDN@Home 1.2.0 alpha rev. 631>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, mefrill, Вы писали:
M>в ситуации [S --> * S + n, 0] после точки стоит символ S, он не равен текущему символу n входной строки
Почему? Требуется чтобы после точки был терминал и он совпадал с текущим терминалом?
M>уже обработанную процедурами Predictor и Completer ситуацию [S --> n *, 0] и еще не обработанную ситуацию [S --> S * + n, 0]. M>обрабатываем последнюю ситуацию. Predictor на ней не работает, т.к. символ после точки — нетерминальный
То есть как это?
... << RSDN@Home 1.2.0 alpha rev. 629 on Windows XP 5.1.2600.131072>>
Здравствуйте, AndrewVK, Вы писали:
M>>в ситуации [S --> * S + n, 0] после точки стоит символ S, он не равен текущему символу n входной строки AVK>Почему? Требуется чтобы после точки был терминал и он совпадал с текущим терминалом?
Да точно.
M>>уже обработанную процедурами Predictor и Completer ситуацию [S --> n *, 0] и еще не обработанную ситуацию [S --> S * + n, 0]. M>>обрабатываем последнюю ситуацию. Predictor на ней не работает, т.к. символ после точки — нетерминальный AVK>То есть как это?
Пардон, терминальный, именно поэтому Предиктор не работает.
Здравствуйте, AndrewVK, Вы писали:
AVK>Понятно. Но пример не очень удачный — слишком редуцированная ситуация.
Да, предиктор фактически не работает. Но, я хотел проще простого пример сделать. В принципе, следующим шагом можно написать прямо в комментариях код работающего алгоритма. Ведь там совсем все просто, если без оптимизаций. Тогда понятно должно совсем стать. как насчет этого?
Здравствуйте, mefrill, Вы писали:
M>Да, предиктор фактически не работает. Но, я хотел проще простого пример сделать. В принципе, следующим шагом можно написать прямо в комментариях код работающего алгоритма. Ведь там совсем все просто, если без оптимизаций. Тогда понятно должно совсем стать. как насчет этого?
Давай. Только при абсолютном минимуме всяких оптимизаций и наворотов. Лишь бы работал.
... << RSDN@Home 1.2.0 alpha rev. 629 on Windows XP 5.1.2600.131072>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Давай. Только при абсолютном минимуме всяких оптимизаций и наворотов. Лишь бы работал.
Ага, на си++. Влад может тоже самое на си шарп реализовать. Надо сначала реализовать грамматику, так чтобы по символам поиск предиктором делать. А затем уже совсем несложно сам алгоритм реализовать.
символы грамматики мы будем держать в векторе, чтобы дать каждому символу индекс. И еще необходимы два ассоциативных массива, чтобы держать соответсвие между именами символов и их индексами.
typedef std::vector< symbol > symbols_t;
typedef std::map< std::string, unsigned int > name2index_t;
typedef std::map< unsigned int, std::string > index2name_t;
нужны еще правила. Каждое правило содержит нетерминал в левой части и вектор символов в правой части.
теперь грамматика. Содержит коллекцию символов и несколько методов чтобы добавлять новые символы и производить поиск по ним. Также содержит коллекцию правил и методы для добавления в правила символов.
А что, на C# никак? Тогда желательно с минимальным использованием STL и без всяких boost и loki.
M> Влад может тоже самое на си шарп реализовать. Надо сначала реализовать грамматику, так чтобы по символам поиск предиктором делать.
Достаточно пока реализовать AST грамматики и для тестов заполнять ее программно. А потом уже сделать ее парсер на себе самом.
M>символ грамматики можно закодировать так:
M>
А зачем конструктор без параметров? При его наличии придется делать доступ к полям по записи, а это снижает защиту.
M>нужны еще правила. Каждое правило содержит нетерминал в левой части и вектор символов в правой части. M>
А почему хранятся индексы, а не указатели?
M>теперь грамматика. Содержит коллекцию символов и несколько методов чтобы добавлять новые символы и производить поиск по ним. Также содержит коллекцию правил и методы для добавления в правила символов.
M>
Совсем не понял? Зачем нам глобальный список Symbol? Почему нельзя локально хранить их список внутри каждого правила? Просто чтобы обеспечить быстрое сравнение по указателям одних и тех же символов в разных правилах? Тогда куда лучше сделать NameTable, который при добавлении будет имя ресолвить в приделах грамматики (тем более что ты один фиг их ресолвишь по имени конструировании правила). В итоге получим и сравнение по указателям и чистый несвязный код.
M>ну как это можно использовать? Типа такого:
M>
M>grammar gr;
M>gr.add_symbol( "S", false, true );
M>gr.add_symbol( "n", true );
M>gr.add_symbol( "+", true );
Вот это лишнее ИМХО.
M>unsigned int S_S_plus_n = gr.add_rule( "S --> S + n" );
M>gr.add_left_nonterminal_to_rule( S_S_plus_n, "S" );
M>gr.add_symbol_to_right_part_of_rule( S_S_plus_n, "S" );
M>gr.add_symbol_to_right_part_of_rule( S_S_plus_n, "+" );
M>gr.add_symbol_to_right_part_of_rule( S_S_plus_n, "n" );
M>unsigned int S_n = gr.add_rule( "S --> n" );
M>gr.add_left_nonterminal_to_rule( S_n, "S" );
M>gr.add_symbol_to_right_part_of_rule( S_n, "n" );
M>
... << RSDN@Home 1.2.0 alpha rev. 629 on Windows XP 5.1.2600.131072>>
Вот мой вариант. На C#, но там все очень просто, думаю разберешься.
Использование:
Grammar g = new Grammar();
g.AddRule("S --> S + n", "S", "S", "+", "n");
g.AddRule("S --> n", "S", "n");
g.PrintRules(Console.Out);
Вывод:
S --> S + n: S --> S(n) +(t) n(t)
S --> n: S --> n(t)
Единственный момент — нетерминальный символ Х может использоваться в правой части только после (или в момент) добавления правила с этим символом в левой части. Т.е. нельзя добавить сначала правило B --> A + t, а потом A --> t2.
... << RSDN@Home 1.2.0 alpha rev. 629 on Windows XP 5.1.2600.131072>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, mefrill, Вы писали:
M>>Ага, на си++.
AVK>А что, на C# никак? Тогда желательно с минимальным использованием STL и без всяких boost и loki.
ну мне удобнее на си++. Можно потом легко переписать.
M>>символ грамматики можно закодировать так:
M>>
AVK>А зачем конструктор без параметров? При его наличии придется делать доступ к полям по записи, а это снижает защиту.
Дело в том, что я символы в векторе размещаю, а там конструктор по умолчанию необходим. На самом деле делать так нехорошо и в рабочей версии такого быть не должно. Но здесь, ради простоты, можно так реализовать. Качество кода в данном случае мне кажется неважным, главное чтобы идея аллгоритма была понятна.
M>>нужны еще правила. Каждое правило содержит нетерминал в левой части и вектор символов в правой части. M>>
Я считаю, что это самый быстрый способ для хранения. Вообще, лучший способ хранить грамматику — это использовать три вектора: вектор терминалов, вектор нетерминалов и вектор правил, где каждый элемент правила — это просто индекс в первых двух векторах. В алгоритм Эрли это все легко укладывается и работает хорошо. Хотя, все несомненно, обсуждается.
M>>теперь грамматика. Содержит коллекцию символов и несколько методов чтобы добавлять новые символы и производить поиск по ним. Также содержит коллекцию правил и методы для добавления в правила символов.
M>>
AVK>Совсем не понял? Зачем нам глобальный список Symbol? Почему нельзя локально хранить их список внутри каждого правила? Просто чтобы обеспечить быстрое сравнение по указателям одних и тех же символов в разных правилах? Тогда куда лучше сделать NameTable, который при добавлении будет имя ресолвить в приделах грамматики (тем более что ты один фиг их ресолвишь по имени конструировании правила). В итоге получим и сравнение по указателям и чистый несвязный код.
Ну да, в реальности ничего не сравнивается по строкам. Каждому символу грамматики дается индекс в векторах, о которых я говорил выше. И все сравнения идут на индексах. Получается очень быстро и удобно.
В общем, код я щас написал рабочий и без оптимизации. Даю ниже, мне кажется там несложно. С удовольствием отвечу на все вопросы. И еще, код этот только для иллюстрации работаы алгоритма, так об эффективности и красоте я совсем не думал.
Я использовал три класса:
класс грамматики, описанный выше.
класс лексера, примитивный, в несколько строк, легко понятен.
класс алгоритма Эрли, называется earley. Оперирует состояниями Эрли (класс state) и ситуациями Эрли (класс item). Вроде ничего там сложного не должно быть. Ниже включаю код по файлам. Код постарался подробно прокомментировать.
lexer.h
#ifndef LEXER_H__
#define LEXER_H__
#include <string>
#include <vector>
typedef std::vector< std::string > input_t;
class lexer{
input_t input_;
int pos_;
public:
lexer():pos_(0){}
void add_to_input( const std::string& _str ) { input_.push_back( _str ); }
std::string get_next()
{
if( pos_ < input_.size() )
{
return input_[ pos_ ++ ];
}
return"EOF";
}
};
#endif// LEXER_H__
grammar.h
#ifndef GRAMMAR_H__
#define GRAMMAR_H__
#include <vector>
#include <map>
#include <string>
struct symbol{
std::string name_;
bool is_terminal_;
symbol(){}
symbol( const std::string& _name, bool _is_terminal )
:
name_(_name),
is_terminal_(_is_terminal)
{}
};
typedef std::vector< symbol > symbols_t;
typedef std::map< std::string, unsigned int > name2index_t;
typedef std::map< unsigned int, std::string > index2name_t;
typedef std::vector< unsigned int > indexes_t;
struct rule{
std::string rule_name_;
unsigned int left_nonterminal_;
indexes_t right_part_;
rule(){}
rule( const std::string& _rule_name )
:
rule_name_(_rule_name)
{}
};
typedef std::vector< rule > rules_t;
class grammar{
unsigned int start_nonterminal_index_;
symbols_t symbols_;
name2index_t name2index_;
index2name_t index2name_;
rules_t rules_;
public:
unsigned int add_symbol( const std::string& _name, bool _is_terminal, bool _is_start = false )
{
unsigned int _cur_index = symbols_.size();
symbols_.push_back( symbol( _name, _is_terminal ) );
if( _is_start ) start_nonterminal_index_ = _cur_index;
name2index_[ _name ] = _cur_index;
index2name_[ _cur_index ] = _name;
return _cur_index;
}
unsigned int add_rule( const std::string& _name )
{
unsigned int _cur_index = rules_.size();
rules_.push_back( rule( _name ) );
return _cur_index;
}
void add_left_nonterminal_to_rule( unsigned int _rule_index, const std::string& _nonterminal_name )
{
rules_[ _rule_index ].left_nonterminal_ = name2index_[ _nonterminal_name ];
}
void add_symbol_to_right_part_of_rule( unsigned int _rule_index, const std::string& _symbol_name )
{
rules_[ _rule_index ].right_part_.push_back( name2index_[ _symbol_name ] );
}
friend class earley;
};
#endif// GRAMMAR_H__
earley.h
#ifndef EARLEY_H__
#define EARLEY_H__
#include"grammar.h"#include"lexer.h"struct item{
unsigned int rule_index_;
unsigned int dot_pos_;
unsigned int origin_;
item(){}
item( unsigned int _rule_index, unsigned int _dot_pos, unsigned int _origin )
:
rule_index_(_rule_index),
dot_pos_(_dot_pos),
origin_(_origin)
{}
};
typedef std::vector< item > items_t;
struct state{
items_t items_;
};
typedef std::vector< state > states_t;
class earley{
grammar& gr_;
lexer& lex_;
states_t states_;
public:
earley( grammar& _gr, lexer& _lex )
:
gr_(_gr),
lex_(_lex)
{}
bool parse();
void print();
private:
bool scanner( unsigned int _state_num );
void predictor( unsigned int _state_num, unsigned int _symbol );
void completer( unsigned int _state_num, unsigned int _item_index );
};
#endif// EARLEY_H__
earley.cpp
#include <iostream>
#include"earley.h"bool earley::parse()
{
// сначала добавляем в нулевое состояние все ситуации, где в правиле тоит начальный
// нетерминал грамматики
states_.push_back( state() );
// проходим по правилам грамматикиfor( unsigned int _rule_index = 0; _rule_index < gr_.rules_.size(); ++ _rule_index )
{
// и добавляем в нулевое состояние ситуации с правилами,
// в которых нетерминал слева - это начальный нетерминал грамматикиif( gr_.start_nonterminal_index_ == gr_.rules_[ _rule_index ].left_nonterminal_ )
{
states_[ 0 ].items_.push_back( item( _rule_index, 0, 0 ) );
}
}
// запускаем последовательно Predictor и Completer на нулевом состоянииfor( unsigned int _item_index = 0; _item_index < states_[ 0 ].items_.size(); ++ _item_index )
{
// если в текущей ситуации точка в конце правой части, то вызываем Completerif( states_[ 0 ].items_[ _item_index ].dot_pos_ == gr_.rules_[ states_[ 0 ].items_[ _item_index ].rule_index_ ].right_part_.size() )
{
completer( 0, _item_index );
}
// если символ после точки - это нетерминал, то вызываем Predictorelse if( ! gr_.symbols_[ gr_.rules_[ states_[ 0 ].items_[ _item_index ].rule_index_ ].right_part_[ states_[ 0 ].items_[ _item_index ].dot_pos_ ] ].is_terminal_ )
{
predictor( 0, gr_.rules_[ states_[ 0 ].items_[ _item_index ].rule_index_ ].right_part_[ states_[ 0 ].items_[ _item_index ].dot_pos_ ] );
}
}
// теперь для каждого состояния сначала инициализируем его вызовом scanner
// а затем дополняем вызовами predictor и completerunsigned int _state_index = 1;
do
{
if( scanner( _state_index - 1 ) )
{
// запускаем последовательно Predictor и Completer на нулевом состоянииunsigned int _item_index = 0;
for( ; _item_index < states_[ _state_index ].items_.size(); ++ _item_index )
{
// если в текущей ситуации точка в конце правой части, то вызываем Completerif( states_[ _state_index ].items_[ _item_index ].dot_pos_ == gr_.rules_[ states_[ _state_index ].items_[ _item_index ].rule_index_ ].right_part_.size() )
{
completer( _state_index, _item_index );
}
// если символ после точки - это нетерминал, то вызываем Predictorelse if( ! gr_.symbols_[ gr_.rules_[ states_[ _state_index ].items_[ _item_index ].rule_index_ ].right_part_[ states_[ _state_index ].items_[ _item_index ].dot_pos_ ] ].is_terminal_ )
{
predictor( _state_index, gr_.rules_[ states_[ _state_index ].items_[ _item_index ].rule_index_ ].right_part_[ states_[ _state_index ].items_[ _item_index ].dot_pos_ ] );
}
}
// если scanner не добавил ни одной ситуации в текущее состояниеif( _item_index == 0 ) return false;
}
else break;
} while( _state_index ++ < states_.size() );
// проверяем вывелась ли текущая строка в данной грамматике или нетfor( unsigned int _item_index = 0; _item_index < states_[ _state_index - 1 ].items_.size(); ++ _item_index )
{
item& _cur_item = states_[ _state_index - 1 ].items_[ _item_index ];
// если в текущей ситуации точка в конце правой части и origin равен нулюif( _cur_item.dot_pos_ == gr_.rules_[ _cur_item.rule_index_ ].right_part_.size() && _cur_item.origin_ == 0 )
{
// если символ в левой части правила - это начальные нетерминал грамматикиif( gr_.rules_[ _cur_item.rule_index_ ].left_nonterminal_ == gr_.start_nonterminal_index_ )
{
return true;
}
}
}
return false;
}
// параметр _state_num - номер состояния, которое необходимо обработать, чтобы добавить
// ситуации в следующее состояние _state_num + 1bool earley::scanner( unsigned int _state_num )
{
// читаем следующий символ во входной строке
// если это конец строки, то не добавляем ни одной ситуации в следующее состояние
std::string _next_symbol = lex_.get_next();
if( "EOF" == _next_symbol ) return false;
// индекс следующего символаunsigned int _next_symbol_index = gr_.name2index_[ _next_symbol ];
// новое состояние
states_.push_back( state() );
// проходим по ситуациям в состоянии под номером _state_num
items_t::iterator it = states_[ _state_num ].items_.begin(), end = states_[ _state_num ].items_.end();
for( ; it != end; ++ it )
{
// если точка не последняя в правой части правилаif( gr_.rules_[ (*it).rule_index_ ].right_part_.size() > (*it).dot_pos_ )
{
// если символ после точки совпадает с текущим символом входной строкиif( gr_.rules_[ (*it).rule_index_ ].right_part_[ (*it).dot_pos_ ] == _next_symbol_index )
{
// добавляем эту ситуацию в следующее состояние, предварительно передвинув
// точку в правой части правила на символ правее
states_[ _state_num + 1 ].items_.push_back( item( (*it).rule_index_, (*it).dot_pos_ + 1, (*it).origin_ ) );
}
}
}
return true;
}
// параметр _state_num - номер теущего состояния
// параметр _symbol - нетерминал, для которого мы будем добавлять ситуации в текущее состояние.
// если _symbol - индекс нетерминала A, то добавим в текущее состояние все ситуации вида [A --> * alpha, _state_num]
// для каждого правила A --> alpha грамматикиvoid earley::predictor( unsigned int _state_num, unsigned int _symbol )
{
// проходим по правилам грамматикиfor( unsigned int _rule_index = 0; _rule_index < gr_.rules_.size(); ++ _rule_index )
{
// если символ в левой части правила равен переданному как параметр, то добавляем ситуацию в текущее состояниеif( gr_.rules_[ _rule_index ].left_nonterminal_ == _symbol )
{
// сначала проверим, что такой ситуации еще нет в данном состоянииbool _rule_is_in_state = false;
items_t::iterator it = states_[ _state_num ].items_.begin(), end = states_[ _state_num ].items_.end();
for( ; it != end; ++ it )
{
if( (*it).rule_index_ == _rule_index && (*it).dot_pos_ == 0 && (*it).origin_ == _state_num )
{
_rule_is_in_state = true;
break;
}
}
// если такой ситуации нет в данном состоянии, то добавляем ееif( ! _rule_is_in_state ) states_[ _state_num ].items_.push_back( item( _rule_index, 0, _state_num ) );
}
}
}
// параметр _state_num - номер текущего состояния
// параметр _item_index - номер ситуации вида [A --> alpha *, i]. Мы должны пойти в состояние номер i
// и нацти там все ситуации, где символ после точки равен символу A и добавить их в текущее состояние
// предварительно сдвинув точку в правой части правила на символ правееvoid earley::completer( unsigned int _state_num, unsigned int _item_index )
{
// мы имеем ситуацию вида [A --> alpha *, i]
// проходим по все ситуациям в состоянии под номером i
items_t::iterator it = states_[ states_[ _state_num ].items_[ _item_index ].origin_ ].items_.begin(),
end = states_[ states_[ _state_num ].items_[ _item_index ].origin_ ].items_.end();
for( ; it != end; ++ it )
{
// если точка не последняя в правой части правилаif( gr_.rules_[ (*it).rule_index_ ].right_part_.size() > (*it).dot_pos_ )
{
// если символ после точки равен символу в евой части правила нашей ситуации
// то добавляем эту ситуацию в текущее состоянии, сдвинув точку на символ правееif( gr_.rules_[ (*it).rule_index_ ].right_part_[ (*it).dot_pos_ ] == gr_.rules_[ states_[ _state_num ].items_[ _item_index ].rule_index_ ].left_nonterminal_ )
{
// сначала проверим, что такой ситуации еще нет в текущем состоянииbool _rule_is_in_state = false;
items_t::iterator it_cur = states_[ _state_num ].items_.begin(), end_cur = states_[ _state_num ].items_.end();
for( ; it_cur != end_cur; ++ it_cur )
{
if( (*it_cur).rule_index_ == (*it).rule_index_
&& (*it_cur).dot_pos_ == (*it).dot_pos_
&& (*it_cur).origin_ == (*it).origin_ )
{
_rule_is_in_state = true;
break;
}
}
// если такой ситуации нет в данном состоянии, то добавляем ееif( ! _rule_is_in_state ) states_[ _state_num ].items_.push_back( item( (*it).rule_index_, (*it).dot_pos_ + 1, (*it).origin_ ) );
}
}
}
}
void earley::print()
{
states_t::iterator it = states_.begin(), end = states_.end();
for( ; it != end; ++ it )
{
std::cout << "********************************************************\n";
items_t::iterator it_item = (*it).items_.begin(), end_item = (*it).items_.end();
for( ; it_item != end_item; ++ it_item )
{
std::cout << "[" << gr_.symbols_[ gr_.rules_[ (*it_item).rule_index_ ].left_nonterminal_ ].name_ << "-->";
unsigned int _rp_index = 0;
for( ; _rp_index < gr_.rules_[ (*it_item).rule_index_ ].right_part_.size(); ++ _rp_index )
{
if( _rp_index == (*it_item).dot_pos_ ) std::cout << "*";
std::cout << gr_.symbols_[ gr_.rules_[ (*it_item).rule_index_ ].right_part_[ _rp_index ] ].name_;
}
if( _rp_index == (*it_item).dot_pos_ ) std::cout << "*";
std::cout << ", " << (*it_item).origin_ << "]\n";
}
std::cout << "--------------------------------------------------------\n";
}
}
main.cpp
#include <iostream>
#include"earley.h"int main()
{
grammar gr;
gr.add_symbol( "S", false, true );
gr.add_symbol( "n", true );
gr.add_symbol( "+", true );
unsigned int S_S_plus_n = gr.add_rule( "S --> S + n" );
gr.add_left_nonterminal_to_rule( S_S_plus_n, "S" );
gr.add_symbol_to_right_part_of_rule( S_S_plus_n, "S" );
gr.add_symbol_to_right_part_of_rule( S_S_plus_n, "+" );
gr.add_symbol_to_right_part_of_rule( S_S_plus_n, "n" );
unsigned int S_n = gr.add_rule( "S --> n" );
gr.add_left_nonterminal_to_rule( S_n, "S" );
gr.add_symbol_to_right_part_of_rule( S_n, "n" );
lexer lex;
lex.add_to_input( "n" );
lex.add_to_input( "+" );
lex.add_to_input( "n" );
earley parser( gr, lex );
if( parser.parse() ) std::cout << "parsing well done\n";
else std::cout << "parsing is failed\n";
parser.print();
return 0;
}
