Цель этой темы посоветоваться с народом по поводу мыслей которые пришли в мою голову в процессе анализа PEG/Packrat.
Для начала небольшой анализ.
Плюсы PEG/Packrat:
1. Покрывает почти все нужды парсинга языков программирования.
2. Линейная скорость.
3. Простая реализация.
4. Гибкость. Грамматики можно менять хоть в рантайме. Возможна модульная организация грамматик.
5. Неограниченное заглядывание вперед позволяет упростить многие грамматики.
6. Возможность совместить лексер и парсер в одной грамматике (фактически отдельный лексер не требуется). Именно этим вызвана дружественность к модульности и гибкость.
Минусы:
1. Совершенно не понятно что делать с выявлением ошибок. Откаты делают выявление ошибок крайне затруднительным.
2. Скорость то линейная, но очень не высокая. Виной тому огромная таблица мемоизации которую нужно сохранять для всего разбираемого файла.
3. Большое потребление памяти. Собственно проблема та же что и в п. 2.
4. Реакция парсера должна не иметь побочных эффектов, так как иногда результаты парсинга отбрасываются.
Теперь собственно мысли...
В презентации автора алгоритма Packrat (Форда) говорится, о том, что фактически PEG выражает грамматики разбираемые методом рекурсивного спуска с откатами. При этом он указывает, что реальные парсеры в реальных компиляторах и интерпретаторах в большинстве случае именно так и делаются и что мол Packrat предоставляет все преимущества этого метода.
Но на самом деле он лукавит. Реальные парсеры создаваемые методом рекурсивного спуска работают несколько иначе. Откаты в них встречаются крайне редко. Именно этим, а не мемоизацией (которой в них попросту нет) объясняется их реальная скорость.
Я проанализировал то как пишутся парсеры и понял в чем отличие создания парсеров "по науке" и "вручную". Дело в том, что парсер создаваемый вручную пользуется знанием грамматики. Скажем если парсер C# распарсил "class X {", то ему нет никакого смысла думать об откатах. Ведь цель достигнута — парсер распознал корректную конструкцию языка. Далее он может встретить правильную или не правильную конструкцию. Таким образом у рукопашных парсеров есть нечто от парсеров создаваемых на основе конечных автоматов. Я назову этот феномен "контрольной точкой".
Можно сказать, что рукопашные парсеры неявно вводят контрольные точки после которых начинается распознавание некоторой вложенной грамматики. У языка вроде C# такими точками являются: пространства имен, типы, члены типов. Фактически тело метода — это совсем другой язык. Этот язык может использовать общие элементы с другими частями общей (большой) грамматики (например, ссылка на тип может встречаться в описании параметров, в списке базовых типов класса, и внутри кода).
Вот мне и подумалось. А почему бы не развить идею Форда и не сделать логику генерируемого на основе PEG-грамматики парсера точно такой же как у рукописного и не ввести те самые контрольные точки? Правда для этого нужно как-то обозом пометить эти контрольные точки. Скажем это можно сделать введением некого специального символа. Например, '#'.
Это позволит с одной стороны делать серьезные оптимизации, а с другой улучшить выявление ошибок в разбираемом коде.
Главной оптимизацией при этом станет возможность использования отдельных хэш-таблиц для всех вложенных частей правил в которых встречается контрольная точка. Это позволит сохранить хэш-таблицу маленькой и уменьшит промахи мимо кэша процессора.
Улучшение диагностики ошибок будет достигнуто в следствии того, что генератор парсеров будет точно знать контекст в котором неверный вод нужно будет рассматривать именно как ошибку, а не как повод для отката правила.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>1. Совершенно не понятно что делать с выявлением ошибок. Откаты делают выявление ошибок крайне затруднительным.
Я так понимаю, тебя смущает формирование ошибок на альтернативах? Нужно просто собирать ошибки по каждой альтернативе и выдавать их все. + возможность явного указания либо главной альтернативы, либо возможности написания рукопашного кода по формированию ошибки, по типу как в antlr.
VD>2. Скорость то линейная, но очень не высокая. Виной тому огромная таблица мемоизации которую нужно сохранять для всего разбираемого файла. VD>3. Большое потребление памяти. Собственно проблема та же что и в п. 2.
Зависит от грамматики. Чем больше альтернатив, тем хуже.
VD>4. Реакция парсера должна не иметь побочных эффектов, так как иногда результаты парсинга отбрасываются.
Ну, это скорее преимущество .
VD>Но на самом деле он лукавит. Реальные парсеры создаваемые методом рекурсивного спуска работают несколько иначе. Откаты в них встречаются крайне редко. Именно этим, а не мемоизацией (которой в них попросту нет) объясняется их реальная скорость.
Именно так.
VD>Я проанализировал то как пишутся парсеры и понял в чем отличие создания парсеров "по науке" и "вручную". Дело в том, что парсер создаваемый вручную пользуется знанием грамматики. Скажем если парсер C# распарсил "class X {", то ему нет никакого смысла думать об откатах. Ведь цель достигнута — парсер распознал корректную конструкцию языка. Далее он может встретить правильную или не правильную конструкцию.
Ну, LL(*) генераторы обычно точно так же умеют. В antlr(2) так же были синтаксические предикаты, которые, по сути, выражали ровно то, что ты сейчас сказал прямо в грамматике. А в данном конкретном приведенном тобой примере вообще количество токенов фиксировано, т.е. достаточно LL(k).
VD> Таким образом у рукопашных парсеров есть нечто от парсеров создаваемых на основе конечных автоматов. Я назову этот феномен "контрольной точкой".
Честно говоря, мысль не понял. При чем тут КА?
VD>Вот мне и подумалось. А почему бы не развить идею Форда и не сделать логику генерируемого на основе PEG-грамматики парсера точно такой же как у рукописного и не ввести те самые контрольные точки? Правда для этого нужно как-то обозом пометить эти контрольные точки.
Ты имеешь в виду, что можно в какой то момент вычисления альтернативы А понять, что все остальные альтернативы уже точно не подходят? Ну, вобщем то, да. Только расстановка таких моментов руками весьма нетривиальна. Вот вычислять такие "точки" автоматично — это было бы интересно. Такая задачка, кстати, близка к задаче доказательства по спецификациям.
... << RSDN@Home 1.2.0 alpha 4 rev. 1249 on Windows 7 6.1.7600.0>>
Здравствуйте, VladD2, Вы писали:
VD>Вот мне и подумалось. А почему бы не развить идею Форда и не сделать логику генерируемого на основе PEG-грамматики парсера точно такой же как у рукописного и не ввести те самые контрольные точки? Правда для этого нужно как-то обозом пометить эти контрольные точки. Скажем это можно сделать введением некого специального символа. Например, '#'.
Ты спрашиваешь какой символ лучше использовать или разрешения поступиться принципами и пойти ненаучным путём?
Если первое, то можно подумать о более наглядном идентификаторе для точек невозврата, например, '>>' или '=>'. Если второе, то поступись ты этими принципами на годик раньше, то, о чём ты говоришь уже давно было бы сделано
Если нам не помогут, то мы тоже никого не пощадим.
Здравствуйте, IT, Вы писали:
IT>Ты спрашиваешь какой символ лучше использовать
Ага. Точно. Именно этот вопрос мучает меня по ночам .
IT>или разрешения поступиться принципами и пойти ненаучным путём?
Меня больше интересует проверка идеи. Не изобрел ли я велосипед? Почему раньше до такой простой мысли никто не додумался? Ну, и вообще, может кто-то разглядит грабли нежно замаскированные в песке.
IT>Если первое, то можно подумать о более наглядном идентификаторе для точек невозврата, например, '>>' или '=>'. Если второе, то поступись ты этими принципами на годик раньше, то, о чём ты говоришь уже давно было бы сделано
Да у меня все равно работы еще много. А так глядишь народ какую-нить умную мысль подкинет.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, AndrewVK, Вы писали:
AVK>Я так понимаю, тебя смущает формирование ошибок на альтернативах? Нужно просто собирать ошибки по каждой альтернативе и выдавать их все.
Все — это нереально. На каждую альтернативу "/" будет выдано по ошибке. Даже идея выявлять самые вложенные пути и та не очень хороша.
AVK> + возможность явного указания либо главной альтернативы, либо возможности написания рукопашного кода по формированию ошибки, по типу как в antlr.
antlr использует ДКА. У него таких проблем нет. Но у него есть почти все проблемы ДКА .
VD>>2. Скорость то линейная, но очень не высокая. Виной тому огромная таблица мемоизации которую нужно сохранять для всего разбираемого файла. VD>>3. Большое потребление памяти. Собственно проблема та же что и в п. 2.
AVK>Зависит от грамматики. Чем больше альтернатив, тем хуже.
Зависит только от количества правил. Сама грамматика монопенисуальна. Чистый пакрат дает проекцию количества правил * количество символов во входном потоке.
VD>>4. Реакция парсера должна не иметь побочных эффектов, так как иногда результаты парсинга отбрасываются.
AVK>Ну, это скорее преимущество .
Офигительное такое преимущество. Например, семантику языка отслеживать нельзя. Значит С++ таким парсером не распарсить.
VD>>Я проанализировал то как пишутся парсеры и понял в чем отличие создания парсеров "по науке" и "вручную". Дело в том, что парсер создаваемый вручную пользуется знанием грамматики. Скажем если парсер C# распарсил "class X {", то ему нет никакого смысла думать об откатах. Ведь цель достигнута — парсер распознал корректную конструкцию языка. Далее он может встретить правильную или не правильную конструкцию.
AVK>Ну, LL(*) генераторы обычно точно так же умеют. В antlr(2) так же были синтаксические предикаты, которые, по сути, выражали ровно то, что ты сейчас сказал прямо в грамматике. А в данном конкретном приведенном тобой примере вообще количество токенов фиксировано, т.е. достаточно LL(k).
Как я уже сказал в Antlr-ах используется ДКА. Antlr 3 — это, кстати, смесь LL(k) и PEG-а. Потому он так и крут. Но как я уже сказал у Antlr-а есть огромные недостатки. Он не модулен и не позволяет расширять парсер динамически.
Посему у Antlr-а 3 нет проблем с откатами, так как есть предсказатель который в большинстве случаев позволяет обойтись без откатов. Но полный ДКА — это приговор гибкости. Так что его опыт не очень интересен.
VD>> Таким образом у рукопашных парсеров есть нечто от парсеров создаваемых на основе конечных автоматов. Я назову этот феномен "контрольной точкой".
AVK>Честно говоря, мысль не понял. При чем тут КА?
При том, что ДКА как и ручной парсер "знакт", что после распознавания некой последовательности откаты не нужны. Можно это рассматривать как наличие автоматический контрольных точек (точек не возврата).
Ты вообще, с алгоритмом Пакртат ознакомился?
VD>>Вот мне и подумалось. А почему бы не развить идею Форда и не сделать логику генерируемого на основе PEG-грамматики парсера точно такой же как у рукописного и не ввести те самые контрольные точки? Правда для этого нужно как-то обозом пометить эти контрольные точки.
AVK>Ты имеешь в виду, что можно в какой то момент вычисления альтернативы А понять, что все остальные альтернативы уже точно не подходят?
Дать понять построителю парсера, что распознанное правило правильное даже не смотря на то, что в дальнейшем в коде могут встретиться ошибки.
AVK> Ну, вобщем то, да. Только расстановка таких моментов руками весьма нетривиальна. Вот вычислять такие "точки" автоматично — это было бы интересно. Такая задачка, кстати, близка к задаче доказательства по спецификациям.
Построение ДКА и есть (если можно так выразиться) этот автоматический способ. Только при этом теряется гибкость. Кайф пакрата в том, что он прост как три копейки и очень гибок.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Все — это нереально. На каждую альтернативу "/" будет выдано по ошибке.
Все верно. Но если вверх по иерархии будет еще альтернатива с ошибкой, то она более нижнюю перекроет. Ну либо какие то приоритеты ошибок вводить.
VD>antlr использует ДКА.
Только для лексера, и то не полностью. Парсер там — чистый рекурсивный спуск (по крайней мере в antlr 2, третий я подробно не изучал). Для откатов используется специальный флажок, переключающий режимы. В режиме проверки семантика не выполняется.
AVK>>Ну, это скорее преимущество .
VD>Офигительное такое преимущество. Например, семантику языка отслеживать нельзя.
Можно, только осторожно. Семантику можно сделать ленивой и вычислять только после фиксации правильной ветки от самого корня. Оверхед будет только на конструкторах замыканий.
VD>Как я уже сказал в Antlr-ах используется ДКА.
См. выше. Основная разница с PEG — по дефолту там нет никаких откатов, и только при явном указании синтаксического предиката откаты могут быть, причем только по правилу этого предиката вниз и только целиком все правило. Соотв. описанной тобой проблемы там нет.
VD> Antlr 3 — это, кстати, смесь LL(k) и PEG-а. Потому он так и крут. Но как я уже сказал у Antlr-а есть огромные недостатки. Он не модулен и не позволяет расширять парсер динамически.
Да нет, есть там возможность объединения грамматик, но в доке это довольно мутно описано.
VD>При том, что ДКА как и ручной парсер "знакт", что после распознавания некой последовательности откаты не нужны.
Опять непонятно. В случае LR(k)/LL(k) откаты просто не нужны, потому что на основе анализа фиксированного k токенов сразу известно, куда идти. Вне зависимости, как парсер внутри будет реализован — при помощи ДКА, рекурсивного спуска или как то еще. Главное — k токенов однозначно определяют 0 или 1 правило.
VD>Ты вообще, с алгоритмом Пакртат ознакомился?
Да. Вопрос не про него, а про то, каким боком тут ДКА.
VD>Дать понять построителю парсера, что распознанное правило правильное даже не смотря на то, что в дальнейшем в коде могут встретиться ошибки.
Понятно.
VD>Построение ДКА и есть (если можно так выразиться) этот автоматический способ.
По крайней мере в antlr структура дерева правил проверяется до генерации реализации парсера, я исходники antlr2 в свое время подробно изучал. Т.е. построение ДКА это совсем другой процесс.
... << RSDN@Home 1.2.0 alpha 4 rev. 1249 on Windows 7 6.1.7600.0>>
Здравствуйте, VladD2, Вы писали:
VD>Для начала небольшой анализ.
VD>Плюсы PEG/Packrat: VD>...
VD>Минусы: VD>1. Совершенно не понятно что делать с выявлением ошибок. Откаты делают выявление ошибок крайне затруднительным.
Xts Rats в большинстве случаев совершенно нормально диагностирует ошибки (есть статья, есть исходники). С восстановлением все тоже более менее ясно — проще всего синхронизироваться по каким-то токенам + завести отдельные продукции для часто встречающихся ошибок.
VD>2. Скорость то линейная, но очень не высокая. Виной тому огромная таблица мемоизации которую нужно сохранять для всего разбираемого файла.
Некоторые граматики, в которых мало бэктрекинга лучше вообще не мемоизировать. VD>3. Большое потребление памяти. Собственно проблема та же что и в п. 2.
ditto
VD>4. Реакция парсера должна не иметь побочных эффектов, так как иногда результаты парсинга отбрасываются. VD>Теперь собственно мысли...
VD>В презентации автора алгоритма Packrat (Форда) говорится, о том, что фактически PEG выражает грамматики разбираемые методом рекурсивного спуска с откатами. При этом он указывает, что реальные парсеры в реальных компиляторах и интерпретаторах в большинстве случае именно так и делаются и что мол Packrat предоставляет все преимущества этого метода. VD>Но на самом деле он лукавит. Реальные парсеры создаваемые методом рекурсивного спуска работают несколько иначе. Откаты в них встречаются крайне редко. Именно этим, а не мемоизацией (которой в них попросту нет) объясняется их реальная скорость.
Количество откатов зависит все-таки больше от разбираемой грамматики а не от генератора парсеров.
VD>Я проанализировал то как пишутся парсеры и понял в чем отличие создания парсеров "по науке" и "вручную". Дело в том, что парсер создаваемый вручную пользуется знанием грамматики. Скажем если парсер C# распарсил "class X {", то ему нет никакого смысла думать об откатах. Ведь цель достигнута — парсер распознал корректную конструкцию языка. Далее он может встретить правильную или не правильную конструкцию. Таким образом у рукопашных парсеров есть нечто от парсеров создаваемых на основе конечных автоматов. Я назову этот феномен "контрольной точкой".
в Xtc Rats вы просто пишите перед такой продукцией transient — и она не мемоизируется.
VD>Можно сказать, что рукопашные парсеры неявно вводят контрольные точки после которых начинается распознавание некоторой вложенной грамматики. У языка вроде C# такими точками являются: пространства имен, типы, члены типов. Фактически тело метода — это совсем другой язык. Этот язык может использовать общие элементы с другими частями общей (большой) грамматики (например, ссылка на тип может встречаться в описании параметров, в списке базовых типов класса, и внутри кода).
Рукописные парсеры не вводят котрольные точки, а пользуются тем, что грамматику можно(иногда) разбить, грубо говоря, на несколько LL(1) кусков.
Вы все это можете делать и с PEG, но можете сначала набросать работающий парсер, а потом оптимизировать если нужно.
VD>Вот мне и подумалось. А почему бы не развить идею Форда и не сделать логику генерируемого на основе PEG-грамматики парсера точно такой же как у рукописного и не ввести те самые контрольные точки? Правда для этого нужно как-то обозом пометить эти контрольные точки. Скажем это можно сделать введением некого специального символа. Например, '#'.
Вы можете такой контрольной точкой считать любую LL(1) продукцию, типа for ... end. Ее никак не нужно помечать — генератору просто вычислить все First и Follow и использовать это для оптимизации — многие так и делают. Вообще, хороший генератор должен еше отсекать (и исправлять) места типа:
...
| id
| id '.' id // <- никогда не сматчится
... и разворачивать левую рекурсию.
VD>Улучшение диагностики ошибок будет достигнуто в следствии того, что генератор парсеров будет точно знать контекст в котором неверный вод нужно будет рассматривать именно как ошибку, а не как повод для отката правила.
Вы предлагаете автоматически писать что то типа:
Statement =
/ For
/ ...
For =
/ 'for' Id '=' Expression ',' Expression 'do' Block 'end' # OK
/ 'for' (!StatementFOLLOW .)* # <- Eat error
StatementFOLLOW = 'for' / 'if' / 'while'/ ....
Это мило, но легко делается руками, а там, где легко не делается и оптимизатор скорее всего не поможет.
Интеграция Scala, Erlang и Rats в Netbeans. Сделана на базе Rats — код неплохой. Можно посмотреть как сделан инкрементальный парсинг, восстановление после ошибок etc. http://hg.netbeans.org/main/contrib
там смотреть:
scala.{...}
erlang.{...}
rats.{...}
Здравствуйте, VladD2, Вы писали:
VD>Меня больше интересует проверка идеи. Не изобрел ли я велосипед? Почему раньше до такой простой мысли никто не додумался?
Почему не додумался? Додумались. Просто генераторы парсеров большей частью существуют как то сами по себе, а реальные компиляторы большей частью написаны вручную
Основная беда генераторов — рынок очень крошечный. И в реальных генераторах куча очевидных вещей не сделана. К примеру, за редчайшим исключением возможности отодрать семантику от правил грамматики нет, хотя казалось бы — глядя на кашу, которая получается после добавления семантики, догадаться о необходимости такого не сложно.
Ну и, вполне возможно, в существующих реализациях PEG что то подобное есть, либо какая то другая альтернатива есть.
... << RSDN@Home 1.2.0 alpha 4 rev. 1249 on Windows 7 6.1.7600.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, VladD2, Вы писали:
VD>>Меня больше интересует проверка идеи. Не изобрел ли я велосипед? Почему раньше до такой простой мысли никто не додумался?
AVK>Почему не додумался? Додумались. Просто генераторы парсеров большей частью существуют как то сами по себе, а реальные компиляторы большей частью написаны вручную
Это исторически, например JavaFX написан на ANTLR. Ну или например в Plan9/Inferno все компиляторы: C/Tcl/AWK/Limbo etc, все написаны на Yacc/Lex (они и Страуструпа пытались заставить — но он, гад, не поддался и придумал неразбираемый язык). Ocaml/Smlnj/Mlton/Ghc/F# — все на генераторах.
AVK>Основная беда генераторов — рынок очень крошечный. И в реальных генераторах куча очевидных вещей не сделана. К примеру, за редчайшим исключением возможности отодрать семантику от правил грамматики нет, хотя казалось бы — глядя на кашу, которая получается после добавления семантики, догадаться о необходимости такого не сложно.
В ANTLR и RATS можно сразу получить дерево прямо из правил. Я смотрел несколько парсеров на RATS — все так и делают, только Fortress, кажется, сразу строит дерево из своих классов.
Зачем нужен транслятор с плохой устойчивостью к ошибкам?
К примеру, в большинстве компиляторов C++ и так пропуск одной точки с запятой карается выводом безумных сообщений. Без опыта ошибки ищутся очень долго.
А тут предлагается методика, снижающая устойчивость к ошибкам.
Здравствуйте, z00n, Вы писали:
Z>В ANTLR и RATS можно сразу получить дерево прямо из правил.
Это в основном для сравнительно простых языков работает, которые полностью в LL(k) укладываются. Всякие штуки вроде вызова методов через точку уже заставляют кастомную семантику писать. Я уж не говорю про всякие эвристики парсинга и генерации ошибок. В итоге реальные файлы грамматик в antlr представляют собой жуткую мешанину, которую, к тому же, не так то просто редактировать, потому что ни интеллисенса, ни тем более более продвинутых фич.
Z> Я смотрел несколько парсеров на RATS — все так и делают, только Fortress, кажется, сразу строит дерево из своих классов.
Ну, про RATS я ничего не знаю, сужу по клонам yacc, coco/r и antlr.
... << RSDN@Home 1.2.0 alpha 4 rev. 1249 on Windows 7 6.1.7600.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Все верно. Но если вверх по иерархии будет еще альтернатива с ошибкой, то она более нижнюю перекроет. Ну либо какие то приоритеты ошибок вводить.
Ну, и на фиг этот гимор?
VD>>antlr использует ДКА.
AVK>Только для лексера, и то не полностью. Парсер там — чистый рекурсивный спуск (по крайней мере в antlr 2, третий я подробно не изучал). Для откатов используется специальный флажок, переключающий режимы. В режиме проверки семантика не выполняется.
Ты не прав. RTFM.
AVK>Можно, только осторожно. Семантику можно сделать ленивой и вычислять только после фиксации правильной ветки от самого корня. Оверхед будет только на конструкторах замыканий.
В том то и дело, что в С++ значение конструкции зависит от семантики.
VD>>Как я уже сказал в Antlr-ах используется ДКА.
AVK>См. выше.
RTFM.
AVK>Основная разница с PEG — по дефолту там нет никаких откатов,
Вот и подумай, как это возможно без построения ДКА?
VD>> Antlr 3 — это, кстати, смесь LL(k) и PEG-а. Потому он так и крут. Но как я уже сказал у Antlr-а есть огромные недостатки. Он не модулен и не позволяет расширять парсер динамически.
AVK>Да нет, есть там возможность объединения грамматик, но в доке это довольно мутно описано.
В парсере с выделенным лексером вообще модульность сделать невозможно. Точнее получится нечто не полноценное.
К тому же я говорю о динамическом изменении парсера.
VD>>При том, что ДКА как и ручной парсер "знакт", что после распознавания некой последовательности откаты не нужны.
AVK>Опять непонятно. В случае LR(k)/LL(k) откаты просто не нужны
Если есть ДКА. Иначе заглядывание вперед выльется в те самые откаты.
К тому же LR(k)/LL(k) даже C# отпарсить не могут. Весьма немощные они.
AVK>, потому что на основе анализа фиксированного k токенов сразу известно, куда идти.
Подумай что сказал. Что значит "анализа"? Это заглядывание вперед. А оно не бесплатно. Это тот же парсинг + откат.
AVK>Вне зависимости, как парсер внутри будет реализован — при помощи ДКА, рекурсивного спуска или как то еще. Главное — k токенов однозначно определяют 0 или 1 правило.
Бесплатное заглядывание вперед получается только мемоизацией. В пакрате так и делается. В любом другом случае — это тормоза. Антлр 3 использует мемоизацию (задается опцией). В остальных случаях работает или на чистых откахат или строго по ДКА (без заглядывания вперед).
VD>>Ты вообще, с алгоритмом Пакртат ознакомился?
AVK>Да. Вопрос не про него, а про то, каким боком тут ДКА.
Не. Вопрос именно про него. ДКА к нему никаким боком. Но на ДКА основан Антлр котоырй ты тут упоминал.
Короче, разберись в вопросе сначала.
VD>>Построение ДКА и есть (если можно так выразиться) этот автоматический способ.
AVK>По крайней мере в antlr структура дерева правил проверяется до генерации реализации парсера, я исходники antlr2 в свое время подробно изучал. Т.е. построение ДКА это совсем другой процесс.
Все правильно. Потому он и не PEG, а LL(*). У него только "*" достигается откатами с мемоизацией. А в 90% случаев он по ДКА прет. Так вот проблема в том, что наличие единого ДКА грамматики — это тоже огрничение. И очень серьезное.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, AndrewVK, Вы писали:
AVK>Здравствуйте, z00n, Вы писали:
Z>>В ANTLR и RATS можно сразу получить дерево прямо из правил.
AVK>Это в основном для сравнительно простых языков работает, которые полностью в LL(k) укладываются. Всякие штуки вроде вызова методов через точку уже заставляют кастомную семантику писать.
Нет я имел в виду, что они умеют строить в памяти, грубо говоря, s-expressions, которые потом легко программно преобразовать в AST — и не нужно засорять грамматику custom actions.
AVK>Я уж не говорю про всякие эвристики парсинга и генерации ошибок. В итоге реальные файлы грамматик в antlr представляют собой жуткую мешанину, которую, к тому же, не так то просто редактировать, потому что ни интеллисенса, ни тем более более продвинутых фич.
Z>> Я смотрел несколько парсеров на RATS — все так и делают, только Fortress, кажется, сразу строит дерево из своих классов.
AVK>Ну, про RATS я ничего не знаю, сужу по клонам yacc, coco/r и antlr.
На RATS все выглядит пристойнее (http://cs.nyu.edu/rgrimm/xtc/xtc-core.zip) — и потом из-за модульности там все из кусочков можно собирать.
Здравствуйте, z00n, Вы писали:
Z>Xts Rats в большинстве случаев совершенно нормально диагностирует ошибки (есть статья, есть исходники). С восстановлением все тоже более менее ясно — проще всего синхронизироваться по каким-то токенам
Исходники то есть, но изучить их с хоту так вот не просто. Ты сам то смотрел как там диагностика ошибок сделана?
Z>+ завести отдельные продукции для часто встречающихся ошибок.
Для некоторых случаев это сделать можно. Но на все случаи жизни оппупеешь это делать.
VD>>2. Скорость то линейная, но очень не высокая. Виной тому огромная таблица мемоизации которую нужно сохранять для всего разбираемого файла. Z>Некоторые граматики, в которых мало бэктрекинга лучше вообще не мемоизировать.
О том и речь. Более того таких грамматик в реальности 90% .
VD>>3. Большое потребление памяти. Собственно проблема та же что и в п. 2. Z>ditto
Чё?
Z>Количество откатов зависит все-таки больше от разбираемой грамматики а не от генератора парсеров.
Конечно. Но я не о том говорил. Я говорил, о том, что в его рассуждении как раз нет этих самых чекпоинтов. А с ними откаты уже не так страшны. Да и не так их много в реальных грамматиках то.
Z>в Xtc Rats вы просто пишите перед такой продукцией transient — и она не мемоизируется.
Не. Это не одно и то же. Не "мемоизируется" не значит "не откатывается".
Z>Рукописные парсеры не вводят котрольные точки, а пользуются тем, что грамматику можно(иногда) разбить, грубо говоря, на несколько LL(1) кусков. Z>Вы все это можете делать и с PEG, но можете сначала набросать работающий парсер, а потом оптимизировать если нужно.
Можно конечно и так представить. Но факт остается фактом, что в реальных рукописных парсерах есть контрольные точки дальше которых откат не идет ни при каких условиях.
Проблемы же которые решаются мемоизацией действительно решаются именно общих под-грамматик.
Собственно именно в анализе мышления человека при составлении парсера вручную и кроется, на мой взгляд, клуюч к простоте и эффективности.
VD>>Вот мне и подумалось. А почему бы не развить идею Форда и не сделать логику генерируемого на основе PEG-грамматики парсера точно такой же как у рукописного и не ввести те самые контрольные точки? Правда для этого нужно как-то обозом пометить эти контрольные точки. Скажем это можно сделать введением некого специального символа. Например, '#'.
Z>Вы можете такой контрольной точкой считать любую LL(1) продукцию, типа for ... end. Ее никак не нужно помечать — генератору просто вычислить все First и Follow и использовать это для оптимизации — многие так и делают.
Кто же? Ну, кроме Антлр 3 который прибит гвоздями к своему ДКА и даже не позволяет избавиться от лексера.
Z> Вообще, хороший генератор должен еше отсекать (и исправлять) места типа: Z>
Z>...
Z> | id
Z> | id '.' id // <- никогда не сматчится
Z>
Z>... и разворачивать левую рекурсию.
Согласен.
Но, да ежу понятно, что что прикручивание ДКА может решить проблему автоматического выявления таких точек.
Но ДКА — это приговор гибкости!
К тому же все будет не очень то тривиально. Ведь придется как-то автоматически выделить эти самые LL(1) под-грамматики. Вы уверены, что это так уж просо?
VD>>Улучшение диагностики ошибок будет достигнуто в следствии того, что генератор парсеров будет точно знать контекст в котором неверный вод нужно будет рассматривать именно как ошибку, а не как повод для отката правила.
Z>Вы предлагаете автоматически писать что то типа: Z>
если парсер спарсит 'for', то при наличии несоответствия грамматике не откатываться, а выдавать сообщение об ошибке.
При этом еще и новую хэш-таблицу для мемоизации завадить в каждом таком месте.
Z>Для мыслей почитать: Z>http://www.romanredz.se/mouse/Mouse-1.1.manual.pdf
Прочесть исходники и разобраться вот так вот с кондачка вряд ли выйдет. Так что спасибо, но это довольно бесполезно. Для начала хотелось бы идеи понять.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, TimurSPB, Вы писали:
TSP>Зачем нужен транслятор с плохой устойчивостью к ошибкам? TSP>К примеру, в большинстве компиляторов C++ и так пропуск одной точки с запятой карается выводом безумных сообщений. Без опыта ошибки ищутся очень долго. TSP>А тут предлагается методика, снижающая устойчивость к ошибкам.
Где, если не секрет?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
.
Если нам не помогут, то мы тоже никого не пощадим.
.
