General LL
От: VladD2 Российская Империя www.nemerle.org
Дата: 11.07.05 22:18
Оценка: 2 (1)
Как мы обсуждали вопросы парсинга и кто-то упомянул о том, что существует такая разработка как 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>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.