Ресурсы алгоритма синтаксического анализа GLR - PullRequest
21 голосов
/ 25 января 2010

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

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

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

Ответы [ 4 ]

14 голосов
/ 26 января 2010

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

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

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

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

5 голосов
/ 04 ноября 2010

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

3 голосов
/ 09 марта 2010

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

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 Томиты, стр. 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 ).

2 голосов
/ 25 января 2010

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

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

В конце концов, все парсы, кроме одного, должны были умереть, а выживший является «правильным» разбором этих неоднозначных точек.

...