Как мы обсуждали вопросы парсинга и кто-то упомянул о том, что существует такая разработка как GLR-парсеры. Мол, что в них решаются проблемы «заглядывания вперед», т.е. проблемы неоднозначностей в грамматиках современных ЯП.
Общая идея там была в разделении процесса разбора на нужное количество ветвей в местах где встречаются неоднозначности.
Я вот подумал, а почему собственно GLR? Почему не GLL? Ведь у LR парсеров кроме трудности с коллизиями еще есть куча других проблем. Это и трудность отладки, и плохие возможности по обработке ошибки. LL(1) и LL(k) парсеры хотя и поддерживают потенциально меньший объем грамматик, но за то намного более эффективнее решают проблемы отладки и диагностики ошибок.
Так вот меня и мучает вопрос. А нельзя ли создать GLL-парсер? Ну, или LL(MAX) что ли? То есть LL-парсер у которого не будет проблем с заглядыванием вперед.
Общая идея такая:
В отличии от большинства LL(k) парсеров правила будут отрабатывать не сразу, а только после процедуры построения верных путей.
При построении верных путей будет производиться банальный рекурсивный спуск, но вместо отработки семантических правил будет строиться некий ациклический направленный граф.
По умолчанию будет вообще строиться дерево, но в местах где возникают коллизии будет строиться альтернативное дерево. Если путей несколько, то и деревьев будет строиться несколько.
За каждый шаг парсера будет простраиваться по одной ветке для каждой альтернативы.
Если в одной из альтернатив появляется ошибка, то все дерево до последнего ветвления отбрасывается.
В результате у нас получается тот самый ациклический направленный граф ветвления в котором являются проявлением двусмысленности грамматик.
Такие двусмысленности будут редки в качественных грамматиках. Да и если они появятся их все же можно будет разрешить с помощью контекстно-зависимыми способами.
Почему-то мне кажется, что такой парсер будет намного проще в реализации. Он позволит так же просто отлаживать грамматики и при этом порождать сообщения об ошибках понятные человеку.
Собственно вопросы:
1. Не пропустил ли я чего существенного?
2. Нет ли у меня логических ошибок в рассуждениях?
3. Почему до этого никто не додумался (или если додумался, то кто и где? И почему бросил?)?
4. На сколько вам кажется реализуема данная идея?
PS
В первую очередь интересует мнение людей лично занимавшихся парсингом сложных языков программирования (обладающих грамматиками вызывающими проблемы при использовании LALR- и LL(1)-парсеров).
... << RSDN@Home 1.1.4 beta 7 rev. 466>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Как мы обсуждали вопросы парсинга и кто-то упомянул о том, что существует такая разработка как GLR-парсеры. Мол, что в них решаются проблемы «заглядывания вперед», т.е. проблемы неоднозначностей в грамматиках современных ЯП.
VD>Общая идея там была в разделении процесса разбора на нужное количество ветвей в местах где встречаются неоднозначности.
VD>Я вот подумал, а почему собственно GLR? Почему не GLL? Ведь у LR парсеров кроме трудности с коллизиями еще есть куча других проблем. Это и трудность отладки, и плохие возможности по обработке ошибки. LL(1) и LL(k) парсеры хотя и поддерживают потенциально меньший объем грамматик, но за то намного более эффективнее решают проблемы отладки и диагностики ошибок.
VD>Так вот меня и мучает вопрос. А нельзя ли создать GLL-парсер? Ну, или LL(MAX) что ли? То есть LL-парсер у которого не будет проблем с заглядыванием вперед.
VD>Я вот подумал, а почему собственно GLR? Почему не GLL? Ведь у LR парсеров кроме трудности с коллизиями еще есть куча других проблем. Это и трудность отладки, и плохие возможности по обработке ошибки. LL(1) и LL(k) парсеры хотя и поддерживают потенциально меньший объем грамматик, но за то намного более эффективнее решают проблемы отладки и диагностики ошибок.
Проблемы LR парсеров проистекают от использования неадекватных генераторов. Коммерческие тулы позволяют генерить LR парсеры с нормальным репортом об ошибках и нормальными возможностями отладки. Вот, рекомендую : Cocktail Toolbox. http://www.cocolab.de . Используется нами для создания парсеров C++, SDL, MSC96, TTCN2,TTCN3, ASN.1, Java и др.
Здравствуйте, VladD2, Вы писали:
VD>Как мы обсуждали вопросы парсинга и кто-то упомянул о том, что существует такая разработка как GLR-парсеры. Мол, что в них решаются проблемы «заглядывания вперед», т.е. проблемы неоднозначностей в грамматиках современных ЯП.
VD>Общая идея там была в разделении процесса разбора на нужное количество ветвей в местах где встречаются неоднозначности.
Да, это будет работать. Проблема при разборе кода с ошибкой — необнозначно место ошибки и соответственно какое правило не сработало.
Идея, вероятно, здравая. Только здесь, видимо, через рекурсивные вызовы сделать не получится, надо будет самому стек вызовов поддерживать. В то смысле, что каждый раз, когда появляется неоднозначность, т.е. для каких-либо двух продукций вида A --> alpha и A --> beta их Follow множества имеют непустое пересечение, копировать стек вызовов и производить разбор параллельно для каждой продукции. Таким образом, вполне можно производить эффективный разбор альтернатив для многих грамматик, но к сожалению, не для всех. Ведь есть еще проблема левой рекурсии. Как ее решать? Нам необходимо, чтобы парсер не зациклился в определенных ситуациях. Т.е. чтобы не было левой рекурсии. В LR-анализаторах производится не разбор правил грамматики, а разбор так называемых "основ", т.е. тех правил, которые могут применимы в данном контексте. Контекст определяется построением LR-автомата. В LL-парсере контекст не определишь, единственный контекст — это множество продукций, разобранных до этого, и множество предосмотров для данной продукции. Что и говорить, контекст не очень-то и богат. Поэтому, таких вот неоднозначностей должно встречаться больше, чем в LR-анализаторе (контекстной информации меньше) и определить неоднозначность можно только одним способом — пересечением First и Follow множеств для альтернативных продукций. В общем, мне видится две главных проблемы:
1. Левая рекурсия. Необходимо, чтобы такой анализатор обрабатывал все правила без исключения. Как эффективно и корректно парсить грамматики с левой рекурсией?
2. Недостаток контекстной информации, из-за чего, возможно, будет больше альтернатив, чем при GLR анализе. Хотя, этот вопрос надо обдумать и здесь я могу ошибаться.
Здравствуйте, _Obelisk_, Вы писали:
_O_>Проблемы LR парсеров проистекают от использования неадекватных генераторов. Коммерческие тулы позволяют генерить LR парсеры с нормальным репортом об ошибках и нормальными возможностями отладки. Вот, рекомендую : Cocktail Toolbox. http://www.cocolab.de . Используется нами для создания парсеров C++, SDL, MSC96, TTCN2,TTCN3, ASN.1, Java и др.
Коммерческие это здорово. Но меня жаба задушит. К тому же на примтивнейшом CocoR я достигаю почти всего что нужно. Вот только сам понимашь LL(1) приводит к геморою с не LL(1) граматиками .
ЗЫ
И все же меня интересует вопрос возможности создания именно GLL-парсера. Почему-то мне кажется, что это окажется самым простым и эффективным решнием.
... << RSDN@Home 1.1.4 beta 7 rev. 466>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, Gramazeka, Вы писали:
G>Да, это будет работать. Проблема при разборе кода с ошибкой — необнозначно место ошибки и соответственно какое правило не сработало.
Дык будет несколько ветвей о которых можно и сообщить. Все же человеку то точно будет проще определить истинную причину ошибки.
... << RSDN@Home 1.1.4 beta 7 rev. 466>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Так вот меня и мучает вопрос. А нельзя ли создать GLL-парсер? Ну, или LL(MAX) что ли? То есть LL-парсер у которого не будет проблем с заглядыванием вперед.
Здравствуйте, VladD2, Вы писали:
А>>см. ANTLR3. А>>В нем как раз реализован GLL-парсер.
VD>А где об этом написано. А то я как-то у них ничего по этому поводу найти не могу.
ANTLR3 (eap) пока доступен только рассылку. На сайте на него ссылок пока нет, т.к. в данный момент он находится в режиме бета-тестирования.
Ближе к вечеру кину ссылки на последний eap, и на статьи об LL(*).
Здравствуйте, Алексей., Вы писали:
А>ANTLR3 (eap) пока доступен только рассылку. На сайте на него ссылок пока нет, т.к. в данный момент он находится в режиме бета-тестирования. А>Ближе к вечеру кину ссылки на последний eap, и на статьи об LL(*).
Буду очень признателен.
... << RSDN@Home 1.2.0 alpha rev. 557>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
.
