Re[6]: PEG - мысли...
От: palm mute  
Дата: 28.10.09 21:37
Оценка:
Здравствуйте, palm mute, Вы писали:

VD>>А второе... я не очень понял о чем идет речь. Можно по подрбнее?

PM>Я как раз попытался проиллюстрировать второй случай примером с закрывающими тегами.
Забыл о классическом примере из букварей по Прологу — в парсерах естественных языков согласование по числу, роду, падежу и т.д. проверяется унификацией.
Re[3]: PEG - мысли...
От: IT Россия linq2db.com
Дата: 28.10.09 23:14
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Меня больше интересует проверка идеи. Не изобрел ли я велосипед?


Ну, если велосипедом называть любую идею, базирующуюся на обыкновенном здравом смысле, то изобрёл.

VD>Почему раньше до такой простой мысли никто не додумался?


Может кто и додумался, но не стал это оформлять в виде научной работы

VD>Ну, и вообще, может кто-то разглядит грабли нежно замаскированные в песке.


Грабли нужно искать в реализации.

VD>А так глядишь народ какую-нить умную мысль подкинет.


Чтобы подкинуть идеи нужно этим позаниматься. А если в общем, то идею тебе уже подкинули авторы Немерле — рулят гибриды. В твоём PEG на самом деле только одна мысль — кеширование, остальное — парсер как парсер, я не понимаю чего ты так на нём зациклился
//rsdn.org/forum/images/bis.gif Если нам не помогут, то мы тоже никого не пощадим.
Re[6]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.10.09 23:41
Оценка:
Здравствуйте, 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>elem(node(Tag, Children)) --> tag_open(Tag), elems(Children), tag_close(Tag).   % (1)
PM>

PM>Пусть входной строкой будет "<foo></foo>". Сначала выполняется tag_open(Tag), при выходе переменная Tag связывается со значением "foo". При вызове tag_close(Tag) значение Tag уже известно, потому tag_close(Tag) выполнится успешно только для правильного закрывающего тега.

Что такое унификация с переменными я в курсе. На них весь вывод типов сделать (в том числе в немерле).
Я идею в прошлый раз не понял. Теперь понял.

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

Надо будет подумать над этим... Спасибо за идею.

PM>Унификация — это самый общий инструмент. Паттерн-матчинг — всего-лишь частный случай, в котором не поддерживаются переменные с левой стороны и повторные вхождения переменных в паттернах.


Наверно ты прав, но унификация занятие весьма не дешевое. А паттерн-матчинг почти эквивалентен аналогичному рукописному коду. Так что где применим ПМ, там унификации делать не чего.

В случае парсера можно обойтись эмуляцией. Скажем ввести правило вводящее переменную. Типа:
var TagName = ['A' .. 'Z'] / ['a' .. 'z'] / '_';

и потом рассматривать это правило как требующее унификации. Тогда можно будет написать:
ComplexTag = "<" TagName Attra? ">" ComplexTag* "<" "\" TagName ">";

и получить эффект аналогичный прологовскому.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.10.09 23:52
Оценка: :)
Здравствуйте, IT, Вы писали:

IT>Ну, если велосипедом называть любую идею, базирующуюся на обыкновенном здравом смысле, то изобрёл.


Вот тут товарищи заметили что мои точки невозрата удивительным образом напоминают точки отсечения в прологе. И ведь, похоже они правы. Так что действительно изобрел велосипед.
Но в данном случаем меня это очень даже радует, так как идея уже проверена временем и пришла во множество голов но в разных аспектах.

VD>>Ну, и вообще, может кто-то разглядит грабли нежно замаскированные в песке.


IT>Грабли нужно искать в реализации.


Э... тут ты не прав. Когда есть много голов, то одна из них может разглядеть грабли еще до реализации. А это ценно, так как экономит время.

IT>Чтобы подкинуть идеи нужно этим позаниматься.


Опять ты не прав. Люди могли изучать проблему теоретически или на других видах деятельности.
Так и произошло. Прологовские точки отсечения действительно очень похоже на то что я предложил.
Более того идею тоже предложили. В прологе еще есть унификация (это то чем типы в немерле выводятся). Так вот она тут будет тоже очень кстати. Можно будет ряд семантических проверок возложить на парсер. Хотя еще пока не ясно насколько это имеет прикладной смысл. Пока что кроме проверки парности тегов в ХМЛ-е я ничего представить не могу. Но все же...

IT> А если в общем, то идею тебе уже подкинули авторы Немерле — рулят гибриды. В твоём PEG на самом деле только одна мысль — кеширование, остальное — парсер как парсер, я не понимаю чего ты так на нём зациклился


В PEG как раз кэширования нет. Кэширование есть в Пакрате (одном из алгоритмов разбора PEG-а). И похоже, что тупое кэшировние — это скорее зло нежели добро. А точки отсечения могут улучшить картину и сделать процесс построения эффективного парсера проще.

В общем, в голове начинает вырисовываться картина того как можно реализовать PEG весьма эффективным образом и без серьезных ограничений.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 29.10.09 02:07
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Это зависит — если разбирать XML — то конечно не стоит, если язык типа Scala — там это лишнее дерево как слону дробина. Памяти же в случае Pakrat будет потрачена на мемоизацию x100, буквально.


Чистый пакрат — это по всей видимости маразм. А лишнее дерево и для Скалы лишнее. Скажем если использовать парсер в целях интеграции с IDE, то там любой лишний чих может быть в тягость, так как парсер может вызываться на каждый вбитый символ.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[10]: PEG - мысли...
От: z00n  
Дата: 29.10.09 07:11
Оценка:
Здравствуйте, 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 строк без построителя деревьев.
Re[7]: .. и для Rats! скоро будет
От: z00n  
Дата: 29.10.09 07:22
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Здравствуйте, AndrewVK, Вы писали:

AVK>>В итоге реальные файлы грамматик в antlr представляют собой жуткую мешанину, которую, к тому же, не так то просто редактировать, потому что ни интеллисенса, ни тем более более продвинутых фич.

Z>Для ANTLR есть приличная IDE:

Z> ...

... и для XTC Rats! скоро будет
http://blogtrader.net/resources/dcaoyuan/RatsEditor-090630.png
rats xtc peg pakrat netbeans
Re[11]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 29.10.09 07:30
Оценка:
Здравствуйте, 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 строк без построителя деревьев.


Ну, и что же он тогда вручную написан?
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[12]: PEG - мысли...
От: z00n  
Дата: 29.10.09 07:52
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, z00n, Вы писали:


Z>>Я после разговора погонял тесты — накладные расходы пренебрежимо (по сравнению с разбором) малы — от единиц процентов до, на разогретой JVM до 0. Короче, это не то место, которое нужно оптимизировать.


VD>Значит парсер полное дерьмо. Я сравниваю построение дерева токенов с ручным разбором рекурсивным спуском написанным на более-менее производительном языке.


Парсер Rats — это аксиома. Мы вообще об одном и том же говорим? Каких токенов?

VD>Где-то можно скачать что-то с инсталлятором чтбы посмотреть на эту отличную работу?

http://wiki.netbeans.org/Scala68v1

VD>Ну, и что же он тогда вручную написан?

Не знаю, я не Мартин.
Re[5]: PEG - мысли...
От: IT Россия linq2db.com
Дата: 29.10.09 13:04
Оценка:
Здравствуйте, VladD2, Вы писали:

IT>>Ну, если велосипедом называть любую идею, базирующуюся на обыкновенном здравом смысле, то изобрёл.


VD>Вот тут товарищи заметили что мои точки невозрата удивительным образом напоминают точки отсечения в прологе. И ведь, похоже они правы. Так что действительно изобрел велосипед.

VD>Но в данном случаем меня это очень даже радует, так как идея уже проверена временем и пришла во множество голов но в разных аспектах.

Это называется велосипедофобия.

IT>>Грабли нужно искать в реализации.

VD>Э... тут ты не прав. Когда есть много голов, то одна из них может разглядеть грабли еще до реализации. А это ценно, так как экономит время.

Помнится, последний раз мы всё это обсуждали где-то месяц назад, с тех пор можно было уже не одни, а десяток граблей выявить.

IT>>Чтобы подкинуть идеи нужно этим позаниматься.


VD>Опять ты не прав. Люди могли изучать проблему теоретически или на других видах деятельности.

VD>Так и произошло. Прологовские точки отсечения действительно очень похоже на то что я предложил.

И что? От того что такая же идея используется в прологе она становится кошернее?

VD>Более того идею тоже предложили. В прологе еще есть унификация (это то чем типы в немерле выводятся). Так вот она тут будет тоже очень кстати. Можно будет ряд семантических проверок возложить на парсер. Хотя еще пока не ясно насколько это имеет прикладной смысл. Пока что кроме проверки парности тегов в ХМЛ-е я ничего представить не могу. Но все же...


Среди идей тоже много всякого разного хлама, можно конечно его весь собрать.

VD>В PEG как раз кэширования нет. Кэширование есть в Пакрате (одном из алгоритмов разбора PEG-а). И похоже, что тупое кэшировние — это скорее зло нежели добро. А точки отсечения могут улучшить картину и сделать процесс построения эффективного парсера проще.


Классно, назови это теперь Гипакрат или как-нибудь Прологопакрат, иначе этим нельзя будет пользоваться.

VD>В общем, в голове начинает вырисовываться картина того как можно реализовать PEG весьма эффективным образом и без серьезных ограничений.


Честно говоря, ничего нового в этом обсуждении, кроме, конечно, кошерности, я не обнаружил.
//rsdn.org/forum/images/bis.gif Если нам не помогут, то мы тоже никого не пощадим.
Re[13]: Correction
От: z00n  
Дата: 29.10.09 17:39
Оценка:
Здравствуйте, 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.


Поэтому "отличную работу" нужно смотреть на Erlang plugin:
http://blogtrader.net/dcaoyuan/entry/erlang_plugin_version_1_for

Подробная инструкция по его написанию в 11 частях:
http://blogtrader.net/dcaoyuan/entry/erlang_plugin_for_netbeans_in
http://blogtrader.net/dcaoyuan/entry/erlang_plugin_for_netbeans_in1
...
про интеграцию Rats:
http://blogtrader.net/dcaoyuan/entry/erlang_plugin_for_netbeans_in3
...
http://blogtrader.net/dcaoyuan/entry/erlang_plugin_for_netbeans_in10
Re: PEG - мысли...
От: dotneter  
Дата: 29.10.09 18:49
Оценка: 43 (1)
Вблизь темы, под .Net есть такой вот язык
http://www.chrisseaton.com/katahdin/
... << RSDN@Home 1.2.0 alpha 4 rev. 1111>>
Talk is cheap. Show me the code.
Re[2]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 30.10.09 08:58
Оценка:
Здравствуйте, dotneter, Вы писали:

D>Вблизь темы, под .Net есть такой вот язык

D>http://www.chrisseaton.com/katahdin/

Интересная работа. В первую очередь тем, что это адаптация PEG для использования в рамках языка с расширяемым синтаксисом.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG - мысли...
От: z00n  
Дата: 30.10.09 09:35
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, dotneter, Вы писали:


D>>Вблизь темы, под .Net есть такой вот язык

D>>http://www.chrisseaton.com/katahdin/

Из интересных практических применений PEG есть еще OMeta
http://tinlizzie.org/ometa/

В том числе для шарпа
http://www.codeplex.com/ometasharp
Building Object Oriented Parasitic Metalanguage
Re[4]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 30.10.09 09:39
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Из интересных практических применений PEG есть еще OMeta

Z>http://tinlizzie.org/ometa/

Это я как раз смотрел. Там ничего интересного нет.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[14]: Correction
От: VladD2 Российская Империя www.nemerle.org
Дата: 30.10.09 13:00
Оценка:
Здравствуйте, z00n, Вы писали:


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.


Уже само по себе это говорит о многом.

Z>Поэтому "отличную работу" нужно смотреть на Erlang plugin:

Z>http://blogtrader.net/dcaoyuan/entry/erlang_plugin_version_1_for

Z>Подробная инструкция по его написанию в 11 частях:

Z>http://blogtrader.net/dcaoyuan/entry/erlang_plugin_for_netbeans_in
Z>http://blogtrader.net/dcaoyuan/entry/erlang_plugin_for_netbeans_in1

ОК, посмотрю. Но Эрланг динамически типизированный язык. Для него вообще мало смысла заниматься парсингом и постороением АСТ, так как с них мало толку. Все равно типы будут только в рантайме.

Z>...

Z>про интеграцию Rats:
Z>http://blogtrader.net/dcaoyuan/entry/erlang_plugin_for_netbeans_in3
Z>...
Z>http://blogtrader.net/dcaoyuan/entry/erlang_plugin_for_netbeans_in10

Спасибо, почитаю.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: .. и для Rats! скоро будет
От: VladD2 Российская Империя www.nemerle.org
Дата: 30.10.09 15:02
Оценка:
Здравствуйте, z00n, Вы писали:

Z>>Для ANTLR есть приличная IDE:

Z>> ...

Z>... и для XTC Rats! скоро будет


Для ANTLR IDE появилась года три назад. А вот заработало ли оно полноценно хотя бы сейчас не известно. Год назад это был весьма сырой продукт.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[9]: .. и для Rats! скоро будет
От: z00n  
Дата: 30.10.09 15:50
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Для ANTLR IDE появилась года три назад. А вот заработало ли оно полноценно хотя бы сейчас не известно. Год назад это был весьма сырой продукт.


IDE ANTLR и в конце 2007(когда я с ней возился) была полезным продуктом, она позволяла делать несколько полезных преобразований грамматик и, вообще, помогала думать. Отдельные баги с тех пор, наверное, исправили.
Re[10]: .. и для Rats! скоро будет
От: VladD2 Российская Империя www.nemerle.org
Дата: 30.10.09 16:32
Оценка:
Здравствуйте, z00n, Вы писали:

Z>IDE ANTLR и в конце 2007(когда я с ней возился) была полезным продуктом, она позволяла делать несколько полезных преобразований грамматик и, вообще, помогала думать. Отдельные баги с тех пор, наверное, исправили.


Глючила она безбожно. Особенно отладка и все что связано с проверкой грамматик.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: PEG - мысли...
От: metaprogrammer  
Дата: 03.11.09 08:20
Оценка:
Здравствуйте, VladD2, Вы писали:


VD>Минусы:

VD>1. Совершенно не понятно что делать с выявлением ошибок. Откаты делают выявление ошибок крайне затруднительным.

Так ведь это же прекрасно, что откаты!

Я очень просто делаю — расставляю в грамматике аннотации, и запоминаю несколько крайних обломов. При полном срыве парсера можно показывать эти аннотации. Очень легко их даже генерить автоматически, и показывать, какие токены ожидались в этом месте, если более подробная аннотация отсутствует. Чем подробнее аннотации, тем более полезные и понятные сообщения об ошибках получаются.

VD>2. Скорость то линейная, но очень не высокая. Виной тому огромная таблица мемоизации которую нужно сохранять для всего разбираемого файла.


Не надо таблицу. Списки быстрее и меньше.

VD>4. Реакция парсера должна не иметь побочных эффектов, так как иногда результаты парсинга отбрасываются.


Ну и на кой они, побочные эффекты? Кроме того, парсер может с собой контекст тащить, очень даже удобно.

VD>Улучшение диагностики ошибок будет достигнуто в следствии того, что генератор парсеров будет точно знать контекст в котором неверный вод нужно будет рассматривать именно как ошибку, а не как повод для отката правила.


Хм... А ведь это ровно тот же подход, что я и так использую — с аннотациями к грамматике...
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.