Здравствуйте, palm mute, Вы писали:
VD>>А второе... я не очень понял о чем идет речь. Можно по подрбнее? PM>Я как раз попытался проиллюстрировать второй случай примером с закрывающими тегами.
Забыл о классическом примере из букварей по Прологу — в парсерах естественных языков согласование по числу, роду, падежу и т.д. проверяется унификацией.
Здравствуйте, VladD2, Вы писали:
VD>Меня больше интересует проверка идеи. Не изобрел ли я велосипед?
Ну, если велосипедом называть любую идею, базирующуюся на обыкновенном здравом смысле, то изобрёл.
VD>Почему раньше до такой простой мысли никто не додумался?
Может кто и додумался, но не стал это оформлять в виде научной работы
VD>Ну, и вообще, может кто-то разглядит грабли нежно замаскированные в песке.
Грабли нужно искать в реализации.
VD>А так глядишь народ какую-нить умную мысль подкинет.
Чтобы подкинуть идеи нужно этим позаниматься. А если в общем, то идею тебе уже подкинули авторы Немерле — рулят гибриды. В твоём PEG на самом деле только одна мысль — кеширование, остальное — парсер как парсер, я не понимаю чего ты так на нём зациклился
Если нам не помогут, то мы тоже никого не пощадим.
Здравствуйте, palm mute, Вы писали:
PM>Я как раз попытался проиллюстрировать второй случай примером с закрывающими тегами. Конечно, там можно обойтись без унификации. Например, с использованием Parsec парсер бы выглядел так: PM>
PM>element = do tagname1 <- openTag
PM> children <- many element
PM> tagname2 <- closeTag
PM> guard (tagname1 == tagname2)
PM> return (Element tagname1 children)
PM>
PM>Здесь нам нужно заводить 2 отдельные переменные tagname1, tagname2 и проверять их на равенство (guard (tagname1==tagname2)).
А, понял. Согласен. Это было бы прикольно.
PM>Как известно, предикаты Пролога могут работать в двух режимах. Допустим, в базе есть факт microsoft_boss(ballmer). Если запрос содержит свободную переменную, в случае успеха она будет связана с решением — запрос microsoft_boss(Who) нам ответит, что Who=ballmer. Если же передать связанную переменную или терм, предикат будет простой проверкой, на запрос microsoft_boss(gates) мы получим no, на microsoft_boss(ballmer) мы получим yes. Во время унификации 1) проверяется существование решения 2) связываются свободные переменные. PM>Этот факт можно использовать в нашем парсере XML-элементов: PM>
PM>Пусть входной строкой будет "<foo></foo>". Сначала выполняется tag_open(Tag), при выходе переменная Tag связывается со значением "foo". При вызове tag_close(Tag) значение Tag уже известно, потому tag_close(Tag) выполнится успешно только для правильного закрывающего тега.
Что такое унификация с переменными я в курсе. На них весь вывод типов сделать (в том числе в немерле).
Я идею в прошлый раз не понял. Теперь понял.
В принципе, подобные вещи конечно можно (и наверно нужно) решать на стадии семантического анализа. Но на первый взгляд перенос его части в декларативную манеру — это хорошее решение.
Надо будет подумать над этим... Спасибо за идею.
PM>Унификация — это самый общий инструмент. Паттерн-матчинг — всего-лишь частный случай, в котором не поддерживаются переменные с левой стороны и повторные вхождения переменных в паттернах.
Наверно ты прав, но унификация занятие весьма не дешевое. А паттерн-матчинг почти эквивалентен аналогичному рукописному коду. Так что где применим ПМ, там унификации делать не чего.
В случае парсера можно обойтись эмуляцией. Скажем ввести правило вводящее переменную. Типа:
var TagName = ['A' .. 'Z'] / ['a' .. 'z'] / '_';
и потом рассматривать это правило как требующее унификации. Тогда можно будет написать:
Здравствуйте, IT, Вы писали:
IT>Ну, если велосипедом называть любую идею, базирующуюся на обыкновенном здравом смысле, то изобрёл.
Вот тут товарищи заметили что мои точки невозрата удивительным образом напоминают точки отсечения в прологе. И ведь, похоже они правы. Так что действительно изобрел велосипед.
Но в данном случаем меня это очень даже радует, так как идея уже проверена временем и пришла во множество голов но в разных аспектах.
VD>>Ну, и вообще, может кто-то разглядит грабли нежно замаскированные в песке.
IT>Грабли нужно искать в реализации.
Э... тут ты не прав. Когда есть много голов, то одна из них может разглядеть грабли еще до реализации. А это ценно, так как экономит время.
IT>Чтобы подкинуть идеи нужно этим позаниматься.
Опять ты не прав. Люди могли изучать проблему теоретически или на других видах деятельности.
Так и произошло. Прологовские точки отсечения действительно очень похоже на то что я предложил.
Более того идею тоже предложили. В прологе еще есть унификация (это то чем типы в немерле выводятся). Так вот она тут будет тоже очень кстати. Можно будет ряд семантических проверок возложить на парсер. Хотя еще пока не ясно насколько это имеет прикладной смысл. Пока что кроме проверки парности тегов в ХМЛ-е я ничего представить не могу. Но все же...
IT> А если в общем, то идею тебе уже подкинули авторы Немерле — рулят гибриды. В твоём PEG на самом деле только одна мысль — кеширование, остальное — парсер как парсер, я не понимаю чего ты так на нём зациклился
В PEG как раз кэширования нет. Кэширование есть в Пакрате (одном из алгоритмов разбора PEG-а). И похоже, что тупое кэшировние — это скорее зло нежели добро. А точки отсечения могут улучшить картину и сделать процесс построения эффективного парсера проще.
В общем, в голове начинает вырисовываться картина того как можно реализовать PEG весьма эффективным образом и без серьезных ограничений.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, z00n, Вы писали:
Z>Это зависит — если разбирать XML — то конечно не стоит, если язык типа Scala — там это лишнее дерево как слону дробина. Памяти же в случае Pakrat будет потрачена на мемоизацию x100, буквально.
Чистый пакрат — это по всей видимости маразм. А лишнее дерево и для Скалы лишнее. Скажем если использовать парсер в целях интеграции с IDE, то там любой лишний чих может быть в тягость, так как парсер может вызываться на каждый вбитый символ.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, z00n, Вы писали:
Z>>Это зависит — если разбирать XML — то конечно не стоит, если язык типа Scala — там это лишнее дерево как слону дробина. Памяти же в случае Pakrat будет потрачена на мемоизацию x100, буквально.
VD>Чистый пакрат — это по всей видимости маразм. А лишнее дерево и для Скалы лишнее.
Я после разговора погонял тесты — накладные расходы пренебрежимо (по сравнению с разбором) малы — от единиц процентов до, на разогретой JVM до 0. Короче, это не то место, которое нужно оптимизировать.
VD>Скажем если использовать парсер в целях интеграции с IDE, то там любой лишний чих может быть в тягость, так как парсер может вызываться на каждый вбитый символ.
Его уже использовали, интеграция Scala в Netbeans, и причем именно так как я сказал, дерево строится прямо по грамматике, без semantic actions: http://hg.netbeans.org/main/contrib/file/6d4edc376cd9/scala.core/src/org/netbeans/modules/scala/core/rats
Все отлично работает.
И кстати, лексер скалы там занимает 100 строк, парсер < 600 — чистый код без мусора. Продакшн парсер скалы — 4k строк без построителя деревьев.
Здравствуйте, z00n, Вы писали:
Z>Здравствуйте, AndrewVK, Вы писали: AVK>>В итоге реальные файлы грамматик в antlr представляют собой жуткую мешанину, которую, к тому же, не так то просто редактировать, потому что ни интеллисенса, ни тем более более продвинутых фич.
Z>Для ANTLR есть приличная IDE: Z> ...
Здравствуйте, z00n, Вы писали:
Z>Я после разговора погонял тесты — накладные расходы пренебрежимо (по сравнению с разбором) малы — от единиц процентов до, на разогретой JVM до 0. Короче, это не то место, которое нужно оптимизировать.
Значит парсер полное дерьмо. Я сравниваю построение дерева токенов с ручным разбором рекурсивным спуском написанным на более-менее производительном языке.
VD>>Скажем если использовать парсер в целях интеграции с IDE, то там любой лишний чих может быть в тягость, так как парсер может вызываться на каждый вбитый символ. Z>Его уже использовали, интеграция Scala в Netbeans, и причем именно так как я сказал, дерево строится прямо по грамматике, без semantic actions: Z>http://hg.netbeans.org/main/contrib/file/6d4edc376cd9/scala.core/src/org/netbeans/modules/scala/core/rats Z>Все отлично работает.
Где-то можно скачать что-то с инсталлятором чтбы посмотреть на эту отличную работу?
Z>И кстати, лексер скалы там занимает 100 строк, парсер < 600 — чистый код без мусора. Продакшн парсер скалы — 4k строк без построителя деревьев.
Ну, и что же он тогда вручную написан?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, z00n, Вы писали:
Z>>Я после разговора погонял тесты — накладные расходы пренебрежимо (по сравнению с разбором) малы — от единиц процентов до, на разогретой JVM до 0. Короче, это не то место, которое нужно оптимизировать.
VD>Значит парсер полное дерьмо. Я сравниваю построение дерева токенов с ручным разбором рекурсивным спуском написанным на более-менее производительном языке.
Парсер Rats — это аксиома. Мы вообще об одном и том же говорим? Каких токенов?
VD>Где-то можно скачать что-то с инсталлятором чтбы посмотреть на эту отличную работу? http://wiki.netbeans.org/Scala68v1
VD>Ну, и что же он тогда вручную написан?
Не знаю, я не Мартин.
Здравствуйте, VladD2, Вы писали:
IT>>Ну, если велосипедом называть любую идею, базирующуюся на обыкновенном здравом смысле, то изобрёл.
VD>Вот тут товарищи заметили что мои точки невозрата удивительным образом напоминают точки отсечения в прологе. И ведь, похоже они правы. Так что действительно изобрел велосипед. VD>Но в данном случаем меня это очень даже радует, так как идея уже проверена временем и пришла во множество голов но в разных аспектах.
Это называется велосипедофобия.
IT>>Грабли нужно искать в реализации. VD>Э... тут ты не прав. Когда есть много голов, то одна из них может разглядеть грабли еще до реализации. А это ценно, так как экономит время.
Помнится, последний раз мы всё это обсуждали где-то месяц назад, с тех пор можно было уже не одни, а десяток граблей выявить.
IT>>Чтобы подкинуть идеи нужно этим позаниматься.
VD>Опять ты не прав. Люди могли изучать проблему теоретически или на других видах деятельности. VD>Так и произошло. Прологовские точки отсечения действительно очень похоже на то что я предложил.
И что? От того что такая же идея используется в прологе она становится кошернее?
VD>Более того идею тоже предложили. В прологе еще есть унификация (это то чем типы в немерле выводятся). Так вот она тут будет тоже очень кстати. Можно будет ряд семантических проверок возложить на парсер. Хотя еще пока не ясно насколько это имеет прикладной смысл. Пока что кроме проверки парности тегов в ХМЛ-е я ничего представить не могу. Но все же...
Среди идей тоже много всякого разного хлама, можно конечно его весь собрать.
VD>В PEG как раз кэширования нет. Кэширование есть в Пакрате (одном из алгоритмов разбора PEG-а). И похоже, что тупое кэшировние — это скорее зло нежели добро. А точки отсечения могут улучшить картину и сделать процесс построения эффективного парсера проще.
Классно, назови это теперь Гипакрат или как-нибудь Прологопакрат, иначе этим нельзя будет пользоваться.
VD>В общем, в голове начинает вырисовываться картина того как можно реализовать PEG весьма эффективным образом и без серьезных ограничений.
Честно говоря, ничего нового в этом обсуждении, кроме, конечно, кошерности, я не обнаружил.
Если нам не помогут, то мы тоже никого не пощадим.
Здравствуйте, z00n, Вы писали:
VD>>Где-то можно скачать что-то с инсталлятором чтбы посмотреть на эту отличную работу? Z>http://wiki.netbeans.org/Scala68v1
С середины прошлого года Scala plugin использует для этих целей компилятор скалы.
http://wiki.netbeans.org/ScalaImpl
...
At the beginning, I implemented a full-featured syntax parser via Rats! too (org.netbeans.modules.scala.editing.rats.ParserScala.rats), which can naturally express the syntax definition of Scala according to its specification. And also a Scala semantic analyzer under org.netbeans.modules.scala.editing.nodes (deprecated now)
But after while, I replaced these parser and analyzer by Scala's native compiler. The later one is still buggy for editor writing (which throws a lot of unprocessed "AssertError"s),but it has some error recover and full type inference features which needs a lot of man working.
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, dotneter, Вы писали:
D>>Вблизь темы, под .Net есть такой вот язык D>>http://www.chrisseaton.com/katahdin/
Z>С середины прошлого года Scala plugin использует для этих целей компилятор скалы. Z>
Z>http://wiki.netbeans.org/ScalaImpl
Z>...
Z>At the beginning, I implemented a full-featured syntax parser via Rats! too (org.netbeans.modules.scala.editing.rats.ParserScala.rats), which can naturally express the syntax definition of Scala according to its specification. And also a Scala semantic analyzer under org.netbeans.modules.scala.editing.nodes (deprecated now)
Z>But after while, I replaced these parser and analyzer by Scala's native compiler. The later one is still buggy for editor writing (which throws a lot of unprocessed "AssertError"s),but it has some error recover and full type inference features which needs a lot of man working.
Здравствуйте, VladD2, Вы писали:
VD>Для ANTLR IDE появилась года три назад. А вот заработало ли оно полноценно хотя бы сейчас не известно. Год назад это был весьма сырой продукт.
IDE ANTLR и в конце 2007(когда я с ней возился) была полезным продуктом, она позволяла делать несколько полезных преобразований грамматик и, вообще, помогала думать. Отдельные баги с тех пор, наверное, исправили.
Здравствуйте, z00n, Вы писали:
Z>IDE ANTLR и в конце 2007(когда я с ней возился) была полезным продуктом, она позволяла делать несколько полезных преобразований грамматик и, вообще, помогала думать. Отдельные баги с тех пор, наверное, исправили.
Глючила она безбожно. Особенно отладка и все что связано с проверкой грамматик.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
VD>Минусы: VD>1. Совершенно не понятно что делать с выявлением ошибок. Откаты делают выявление ошибок крайне затруднительным.
Так ведь это же прекрасно, что откаты!
Я очень просто делаю — расставляю в грамматике аннотации, и запоминаю несколько крайних обломов. При полном срыве парсера можно показывать эти аннотации. Очень легко их даже генерить автоматически, и показывать, какие токены ожидались в этом месте, если более подробная аннотация отсутствует. Чем подробнее аннотации, тем более полезные и понятные сообщения об ошибках получаются.
VD>2. Скорость то линейная, но очень не высокая. Виной тому огромная таблица мемоизации которую нужно сохранять для всего разбираемого файла.
Не надо таблицу. Списки быстрее и меньше.
VD>4. Реакция парсера должна не иметь побочных эффектов, так как иногда результаты парсинга отбрасываются.
Ну и на кой они, побочные эффекты? Кроме того, парсер может с собой контекст тащить, очень даже удобно.
VD>Улучшение диагностики ошибок будет достигнуто в следствии того, что генератор парсеров будет точно знать контекст в котором неверный вод нужно будет рассматривать именно как ошибку, а не как повод для отката правила.
Хм... А ведь это ровно тот же подход, что я и так использую — с аннотациями к грамматике...
Если нам не помогут, то мы тоже никого не пощадим.
