Ресурсы алгоритмов синтаксического анализа

Я пишу генератор парсера GLR и как некоторые советы по ресурсам, связанным с этим алгоритмом как в Интернете, так и в разновидности мертвых деревьев (книги для тех, кто не знаком с выродками).

Я знаю, что Bison может генерировать синтаксические анализаторы GLR, и, учитывая его в GPL, я могу проверить его код, однако было бы неплохо иметь полное описание алгоритма.

Итак, знает ли кто-нибудь о каких-либо хороших ресурсах, которые я могу использовать? Спасибо.

Ответы

Ответ 1

Некоторые хорошие вещи, с которыми я столкнулся раньше:

документ о Elkhound, еще один открытый анализатор GLR: Скотт МакПак, Джордж С. Некула. Elkhound: быстрый, практичный генератор Parser GLR. В трудах конференции по строителю компилятора (CC04), апрель 2004 г.

и более подробно:

технический отчет UCB/CSSD-2-1214, который является расширенной версией вышеупомянутой статьи;
документ, упомянутый в Документация Bison: Элизабет Скотт, Адриан Джонстон и Шамса Садаф Хуссейн. Обобщенные интерпретаторы LR в стиле Томита. TR-00-12, Royal Holloway, Лондонский университет, факультет компьютерных наук, декабрь 2000 года.

И я знаю третий анализатор GLR с открытым исходным кодом: DParser.

Ответ 2

Адриан Джонстон публикует много работы над расширенными версиями алгоритмов GLR. Его веб-сайт , вероятно, будет интересным ресурсом.

Ответ 3

Лучшее описание, которое я когда-либо видел, с картинками, иллюстрирующими каждый шаг алгоритма, содержится в этой книге:

http://books.google.ca/books?id=05xA_d5dSwAC&lpg=PA381&dq=generalized%20deterministic%20parsers&pg=PA381#v=onepage&q=generalized%20deterministic%20parsers&f=false

Для псевдокода перейдите к источнику: Обобщенный анализ LR от Tomita, стр. 70 или около того. Бумага Фарши содержит компактное описание.

http://books.google.ca/books?id=PvZiZiVqwHcC&lpg=PP1&dq=generalized%20lr%20parsing&pg=PA70#v=onepage&q=&f=false

Это один из тех методов, которые я пробовал для qb.js(qbasic в javascript).

Ответ 4

Из того, что я знаю, он работает так же, как парсер LALR, за исключением случаев, когда он сталкивается с двусмысленностью.

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

В конце концов, все, кроме одного синтаксического анализа, должны были погибнуть, а выживающий - это "правильный" анализ этих двусмысленных точек.