GLR парсинг ресурсов алгоритма
Я пишу генератор анализатора GLR и хотел бы некоторый совет относительно ресурсов, касающихся этого алгоритма и в Интернете и вида мертвого дерева (книги для незнакомых с гиком - говорят).
Я знаю, что Бизон может произвести анализаторы GLR, и, учитывая он находится под GPL, я могу исследовать его кодекс, однако было бы хорошо иметь полное описание алгоритма.
Так, кто-либо знает о каких-либо хороших ресурсах там, которые я могу использовать?Спасибо.
3 ответа
Некоторые хорошие вещи, которые я столкнулся с онлайн:
- статью о Elkhound , еще один анализатор открытого источника GLR: Scott McPeak, Джордж С. Necula. Элхунд: быстрый, практичный, практичный генератор Parser . В процессе конференции на Compiler Constructor (CC04), апрель 2004 года.
и для получения более подробной информации:
- Технический отчет UCB / CSSD-2-1214 , который является расширенной версией вышеуказанного Бумага;
- Бумага, на которую ссылаются в документацию . Документация : Элизабет Скотт, Адриан Джонстон и Шамса Садаф Хуссейн. Генерализованные анализаторы LR . TR-00-12, Royal Holloway, Лондонский университет, Департамент информатики, декабрь 2000 года.
И я знаю из третьего анализатора открытого источника ГЛР: DPARSER .
Из того, что я знаю, он функционирует так же, как анализатор LALR - за исключением случаев, когда он сталкивается с двусмысленностью.
Когда он делает, это, по сути, это по существу делит на отдельные анализаторы, соответствующие возможным вариантам в этой точке, и продолжается с ними в тандеме - когда анализ не удается (из-за встречи незаконного элемента), он просто упал, потому что он должен были неправильно догадаться на более ранней двусмысленности.
В конце все, кроме одного анализа должно быть умер - и выжившие - это «правильный» анализ этих неоднозначных точек.
Лучшее описание, которое я когда-либо видел, с изображениями, иллюстрирующими каждый шаг алгоритма, содержится в этой книге:
Для псевдокода перейдите к источнику: Generalized LR Parsing by Tomita, page 70 или около того. Статья Фарши содержит краткое описание.
Это одна из техник, которые я пробовал для qb.js ( qbasic в javascript ).