Я пишу генератор парсера GLR и как некоторые советы по ресурсам, связанным с этим алгоритмом как в Интернете, так и в разновидности мертвых деревьев (книги для тех, кто не знаком с выродками).
Я знаю, что Bison может генерировать синтаксические анализаторы GLR, и, учитывая его в GPL, я могу проверить его код, однако было бы неплохо иметь полное описание алгоритма.
Итак, знает ли кто-нибудь о каких-либо хороших ресурсах, которые я могу использовать? Спасибо.
Некоторые хорошие вещи, с которыми я столкнулся раньше:
и более подробно:
И я знаю третий анализатор GLR с открытым исходным кодом: DParser.
Адриан Джонстон публикует много работы над расширенными версиями алгоритмов GLR. Его веб-сайт , вероятно, будет интересным ресурсом.
Лучшее описание, которое я когда-либо видел, с картинками, иллюстрирующими каждый шаг алгоритма, содержится в этой книге:
Для псевдокода перейдите к источнику: Обобщенный анализ LR от Tomita, стр. 70 или около того. Бумага Фарши содержит компактное описание.
Это один из тех методов, которые я пробовал для qb.js(qbasic в javascript).
Из того, что я знаю, он работает так же, как парсер LALR, за исключением случаев, когда он сталкивается с двусмысленностью.
Когда он это делает, он по существу делит на отдельные разборки, соответствующие возможным вариантам в этой точке, и продолжает их в тандеме - когда синтаксический разбор не удается (из-за столкновения с незаконным элементом), он просто отбрасывается, потому что он должен были ошибочными предположениями о более ранней двусмысленности.
В конце концов, все, кроме одного синтаксического анализа, должны были погибнуть, а выживающий - это "правильный" анализ этих двусмысленных точек.