Re[3]: PEG - мысли...
От: palm mute  
Дата: 28.10.09 17:18
Оценка: 52 (2)
Здравствуйте, VladD2, Вы писали:

VD>Может быть. Только основная проблема пролога — дикие тормоза на реальных задачах. Может имеет смысл к прологу мемоизацию прикрутить?

К Mercury прикрутили, мемоизация включается прагмой. А т.к. откаты в логических языках — фича встроенная, реализовать packrat можно элементарно.
Вот граждане пишут, что из этого получилось: DCGs+Memoing=Packrat Parsing but is it worth it?

C>>Заменить прологовскую базу фактов входной строкой, интегрировать в пеги унификацию термов, кое-где подкрасить, надежно склеить скотчем и ... Готов новомодный язык (поди еще и тьюринг-полный) для написания парсеров. Подозреваю нам поставят памятник.

VD> Хорошая идея!

VD>Вопрос только нафига в парсерах унификация? Что унифицировать то будем?


В парсерах на Прологе унификация используется в двух случаях — 1) для возврата результатов парсинга и 2) для добавления контекстных зависимостей.

Например, вот игрушечный парсер XML-элементов на DCG:
chars([C|Cs]) --> [C], chars(Cs).
chars([]) --> [].

tag_open(Tag)  --> "<", chars(Tag), ">".
tag_close(Tag) --> "</", chars(Tag), ">".

elem(node(Tag, Children)) --> tag_open(Tag), elems(Children), tag_close(Tag).   % (1)
elems([Elem|Elems])       --> elem(Elem), elems(Elems).
elems([])                 --> [].


Совпадение открывающих и закрывающих тегов проверяется в строке (1) автоматически за счет унификации.
Re: PEG - мысли...
От: chukichuki  
Дата: 28.10.09 13:36
Оценка: 43 (1) :)
VD>Вот мне и подумалось. А почему бы не развить идею Форда и не сделать логику генерируемого на основе PEG-грамматики парсера точно такой же как у рукописного и не ввести те самые контрольные точки? Правда для этого нужно как-то обозом пометить эти контрольные точки. Скажем это можно сделать введением некого специального символа. Например, '#'.

VD>Грамматика при этом будет выглядеть как-то так:

VD>
VD>Class = CastomAttributs? Modifiers? "partial"? "class" # Identifier # TypeParams? Constrains? '{' # ClassMembers* '}'
VD>


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


Мне механизм пакрат-парсеров все больше напоминает реализацию резолюции в прологе. В этом контексте ваша контрольная точка есть ни что иное, как прологовское отсечение. Может пора уже объединить два механизма ? Заменить прологовскую базу фактов входной строкой, интегрировать в пеги унификацию термов, кое-где подкрасить, надежно склеить скотчем и ... Готов новомодный язык (поди еще и тьюринг-полный) для написания парсеров. Подозреваю нам поставят памятник.
Re: PEG - мысли...
От: z00n  
Дата: 27.10.09 19:16
Оценка: 43 (1)
Здравствуйте, 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'/ ....

Это мило, но легко делается руками, а там, где легко не делается и оптимизатор скорее всего не поможет.

Для мыслей почитать:
http://www.romanredz.se/mouse/Mouse-1.1.manual.pdf

Исходники:
Rats:
http://www.cs.nyu.edu/rgrimm/xtc/rats.html
Mouse:
http://www.romanredz.se/mouse/Mouse-1.1.tar.gz

Интеграция Scala, Erlang и Rats в Netbeans. Сделана на базе Rats — код неплохой. Можно посмотреть как сделан инкрементальный парсинг, восстановление после ошибок etc.
http://hg.netbeans.org/main/contrib
там смотреть:
scala.{...}
erlang.{...}
rats.{...}

К сожалению, все Java.
Re[5]: PEG - мысли...
От: palm mute  
Дата: 28.10.09 21:34
Оценка: 43 (1)
Здравствуйте, VladD2, Вы писали:

PM>>В парсерах на Прологе унификация используется ... 2) для добавления контекстных зависимостей.


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


Я как раз попытался проиллюстрировать второй случай примером с закрывающими тегами. Конечно, там можно обойтись без унификации. Например, с использованием Parsec парсер бы выглядел так:
element = do tagname1 <- openTag
             children <- many element
             tagname2 <- closeTag
             guard (tagname1 == tagname2)      
             return (Element tagname1 children)

Здесь нам нужно заводить 2 отдельные переменные tagname1, tagname2 и проверять их на равенство (guard (tagname1==tagname2)).

Как известно, предикаты Пролога могут работать в двух режимах. Допустим, в базе есть факт microsoft_boss(ballmer). Если запрос содержит свободную переменную, в случае успеха она будет связана с решением — запрос microsoft_boss(Who) нам ответит, что Who=ballmer. Если же передать связанную переменную или терм, предикат будет простой проверкой, на запрос microsoft_boss(gates) мы получим no, на microsoft_boss(ballmer) мы получим yes. Во время унификации 1) проверяется существование решения 2) связываются свободные переменные.
Этот факт можно использовать в нашем парсере XML-элементов:
elem(node(Tag, Children)) --> tag_open(Tag), elems(Children), tag_close(Tag).   % (1)

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

VD>Дык для парсера написанного на не логическом языке тут унификация не потребуется. Тут скорее паттерн-матчинг будет нужен.

VD>Так что получается, что в логических унификация используется за не имением других инструментов.
Унификация — это самый общий инструмент. Паттерн-матчинг — всего-лишь частный случай, в котором не поддерживаются переменные с левой стороны и повторные вхождения переменных в паттернах.
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[4]: PEG - мысли...
От: z00n  
Дата: 27.10.09 20:42
Оценка: 2 (1)
Здравствуйте, 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, кажется, сразу строит дерево из своих классов.
Re[4]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.10.09 23:52
Оценка: :)
Здравствуйте, IT, Вы писали:

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


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

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


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


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

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


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

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


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

В общем, в голове начинает вырисовываться картина того как можно реализовать PEG весьма эффективным образом и без серьезных ограничений.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.10.09 15:18
Оценка:
Цель этой темы посоветоваться с народом по поводу мыслей которые пришли в мою голову в процессе анализа PEG/Packrat.

Для начала небольшой анализ.

Плюсы PEG/Packrat:
1. Покрывает почти все нужды парсинга языков программирования.
2. Линейная скорость.
3. Простая реализация.
4. Гибкость. Грамматики можно менять хоть в рантайме. Возможна модульная организация грамматик.
5. Неограниченное заглядывание вперед позволяет упростить многие грамматики.
6. Возможность совместить лексер и парсер в одной грамматике (фактически отдельный лексер не требуется). Именно этим вызвана дружественность к модульности и гибкость.

Минусы:
1. Совершенно не понятно что делать с выявлением ошибок. Откаты делают выявление ошибок крайне затруднительным.
2. Скорость то линейная, но очень не высокая. Виной тому огромная таблица мемоизации которую нужно сохранять для всего разбираемого файла.
3. Большое потребление памяти. Собственно проблема та же что и в п. 2.
4. Реакция парсера должна не иметь побочных эффектов, так как иногда результаты парсинга отбрасываются.

Теперь собственно мысли...

В презентации автора алгоритма Packrat (Форда) говорится, о том, что фактически PEG выражает грамматики разбираемые методом рекурсивного спуска с откатами. При этом он указывает, что реальные парсеры в реальных компиляторах и интерпретаторах в большинстве случае именно так и делаются и что мол Packrat предоставляет все преимущества этого метода.
Но на самом деле он лукавит. Реальные парсеры создаваемые методом рекурсивного спуска работают несколько иначе. Откаты в них встречаются крайне редко. Именно этим, а не мемоизацией (которой в них попросту нет) объясняется их реальная скорость.

Я проанализировал то как пишутся парсеры и понял в чем отличие создания парсеров "по науке" и "вручную". Дело в том, что парсер создаваемый вручную пользуется знанием грамматики. Скажем если парсер C# распарсил "class X {", то ему нет никакого смысла думать об откатах. Ведь цель достигнута — парсер распознал корректную конструкцию языка. Далее он может встретить правильную или не правильную конструкцию. Таким образом у рукопашных парсеров есть нечто от парсеров создаваемых на основе конечных автоматов. Я назову этот феномен "контрольной точкой".
Можно сказать, что рукопашные парсеры неявно вводят контрольные точки после которых начинается распознавание некоторой вложенной грамматики. У языка вроде C# такими точками являются: пространства имен, типы, члены типов. Фактически тело метода — это совсем другой язык. Этот язык может использовать общие элементы с другими частями общей (большой) грамматики (например, ссылка на тип может встречаться в описании параметров, в списке базовых типов класса, и внутри кода).

Вот мне и подумалось. А почему бы не развить идею Форда и не сделать логику генерируемого на основе PEG-грамматики парсера точно такой же как у рукописного и не ввести те самые контрольные точки? Правда для этого нужно как-то обозом пометить эти контрольные точки. Скажем это можно сделать введением некого специального символа. Например, '#'.

Грамматика при этом будет выглядеть как-то так:
Class = CastomAttributs? Modifiers? "partial"? "class" # Identifier # TypeParams? Constrains? '{' # ClassMembers* '}'


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

Главной оптимизацией при этом станет возможность использования отдельных хэш-таблиц для всех вложенных частей правил в которых встречается контрольная точка. Это позволит сохранить хэш-таблицу маленькой и уменьшит промахи мимо кэша процессора.

Улучшение диагностики ошибок будет достигнуто в следствии того, что генератор парсеров будет точно знать контекст в котором неверный вод нужно будет рассматривать именно как ошибку, а не как повод для отката правила.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re: PEG - мысли...
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 27.10.09 15:38
Оценка:
Здравствуйте, 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>>
AVK Blog
Re: PEG - мысли...
От: IT Россия linq2db.com
Дата: 27.10.09 15:39
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Вот мне и подумалось. А почему бы не развить идею Форда и не сделать логику генерируемого на основе PEG-грамматики парсера точно такой же как у рукописного и не ввести те самые контрольные точки? Правда для этого нужно как-то обозом пометить эти контрольные точки. Скажем это можно сделать введением некого специального символа. Например, '#'.


Ты спрашиваешь какой символ лучше использовать или разрешения поступиться принципами и пойти ненаучным путём?

Если первое, то можно подумать о более наглядном идентификаторе для точек невозврата, например, '>>' или '=>'. Если второе, то поступись ты этими принципами на годик раньше, то, о чём ты говоришь уже давно было бы сделано
Если нам не помогут, то мы тоже никого не пощадим.
Re[2]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.10.09 15:53
Оценка:
Здравствуйте, IT, Вы писали:

IT>Ты спрашиваешь какой символ лучше использовать


Ага. Точно. Именно этот вопрос мучает меня по ночам .

IT>или разрешения поступиться принципами и пойти ненаучным путём?


Меня больше интересует проверка идеи. Не изобрел ли я велосипед? Почему раньше до такой простой мысли никто не додумался? Ну, и вообще, может кто-то разглядит грабли нежно замаскированные в песке.

IT>Если первое, то можно подумать о более наглядном идентификаторе для точек невозврата, например, '>>' или '=>'. Если второе, то поступись ты этими принципами на годик раньше, то, о чём ты говоришь уже давно было бы сделано


Да у меня все равно работы еще много. А так глядишь народ какую-нить умную мысль подкинет.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.10.09 17:33
Оценка:
Здравствуйте, 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> Ну, вобщем то, да. Только расстановка таких моментов руками весьма нетривиальна. Вот вычислять такие "точки" автоматично — это было бы интересно. Такая задачка, кстати, близка к задаче доказательства по спецификациям.


Построение ДКА и есть (если можно так выразиться) этот автоматический способ. Только при этом теряется гибкость. Кайф пакрата в том, что он прост как три копейки и очень гибок.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG - мысли...
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 27.10.09 18:25
Оценка:
Здравствуйте, 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>>
AVK Blog
Re[3]: PEG - мысли...
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 27.10.09 20:09
Оценка:
Здравствуйте, VladD2, Вы писали:

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


Почему не додумался? Додумались. Просто генераторы парсеров большей частью существуют как то сами по себе, а реальные компиляторы большей частью написаны вручную
Основная беда генераторов — рынок очень крошечный. И в реальных генераторах куча очевидных вещей не сделана. К примеру, за редчайшим исключением возможности отодрать семантику от правил грамматики нет, хотя казалось бы — глядя на кашу, которая получается после добавления семантики, догадаться о необходимости такого не сложно.
Ну и, вполне возможно, в существующих реализациях PEG что то подобное есть, либо какая то другая альтернатива есть.
... << RSDN@Home 1.2.0 alpha 4 rev. 1249 on Windows 7 6.1.7600.0>>
AVK Blog
Re[2]: PEG - мысли...
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 27.10.09 20:12
Оценка:
Здравствуйте, z00n, Вы писали:

Z>К сожалению, все Java.


Для дотнета есть FParsec.
... << RSDN@Home 1.2.0 alpha 4 rev. 1249 on Windows 7 6.1.7600.0>>
AVK Blog
Re: PEG - мысли...
От: TimurSPB Интернет  
Дата: 27.10.09 20:48
Оценка:
Зачем нужен транслятор с плохой устойчивостью к ошибкам?
К примеру, в большинстве компиляторов C++ и так пропуск одной точки с запятой карается выводом безумных сообщений. Без опыта ошибки ищутся очень долго.
А тут предлагается методика, снижающая устойчивость к ошибкам.
Make flame.politics Great Again!
Re[5]: PEG - мысли...
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 27.10.09 21:15
Оценка:
Здравствуйте, 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>>
AVK Blog
Re[4]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.10.09 21:58
Оценка:
Здравствуйте, 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% случаев он по ДКА прет. Так вот проблема в том, что наличие единого ДКА грамматики — это тоже огрничение. И очень серьезное.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.10.09 22:01
Оценка:
Здравствуйте, AndrewVK, Вы писали:

AVK>Ну, про RATS я ничего не знаю, сужу по клонам yacc, coco/r и antlr.


Rats — это как раз единственный распространенный PEG/Pacrat генератор парсеров.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[6]: PEG - мысли...
От: z00n  
Дата: 27.10.09 22:16
Оценка:
Здравствуйте, 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) — и потом из-за модульности там все из кусочков можно собирать.
Re[2]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.10.09 22:29
Оценка:
Здравствуйте, 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>
Z>   Statement = 
Z>   / For
Z>   / ... 
   
Z>   For =
Z>   / 'for' Id '=' Expression ',' Expression 'do' Block 'end' # OK
Z>   / 'for' (!StatementFOLLOW .)*   # <- Eat error
        
Z>   StatementFOLLOW = 'for' / 'if' / 'while'/ ....

Z>

Z>Это мило, но легко делается руками, а там, где легко не делается и оптимизатор скорее всего не поможет.

Нет я предлакаю в случае правила:
/ 'for' # Id '=' Expression ',' Expression 'do' Block 'end'

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

Z>Для мыслей почитать:

Z>http://www.romanredz.se/mouse/Mouse-1.1.manual.pdf

Почитаю, спасибо.

Z>Исходники:

Z>Rats:
Z>http://www.cs.nyu.edu/rgrimm/xtc/rats.html
Z>Mouse:
Z>http://www.romanredz.se/mouse/Mouse-1.1.tar.gz

Прочесть исходники и разобраться вот так вот с кондачка вряд ли выйдет. Так что спасибо, но это довольно бесполезно. Для начала хотелось бы идеи понять.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.10.09 22:34
Оценка:
Здравствуйте, z00n, Вы писали:
Z>Для мыслей почитать:
Z>http://www.romanredz.se/mouse/Mouse-1.1.manual.pdf

Z>Исходники:

Z>Mouse:
Z>http://www.romanredz.se/mouse/Mouse-1.1.tar.gz

Этот Мышь — это что за зверь? Когда он появился? И чем отличается от конкурентов?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.10.09 22:35
Оценка:
Здравствуйте, AndrewVK, Вы писали:

AVK>Для дотнета есть FParsec.


Это наверно клон хаскелевского парсека. Он к делу вообще не относится.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.10.09 22:36
Оценка:
Здравствуйте, TimurSPB, Вы писали:

TSP>Зачем нужен транслятор с плохой устойчивостью к ошибкам?

TSP>К примеру, в большинстве компиляторов C++ и так пропуск одной точки с запятой карается выводом безумных сообщений. Без опыта ошибки ищутся очень долго.
TSP>А тут предлагается методика, снижающая устойчивость к ошибкам.

Где, если не секрет?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG - мысли...
От: z00n  
Дата: 27.10.09 22:40
Оценка:
Здравствуйте, VladD2, Вы писали:

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

Z>>Для мыслей почитать:
Z>>http://www.romanredz.se/mouse/Mouse-1.1.manual.pdf

Z>>Исходники:

Z>>Mouse:
Z>>http://www.romanredz.se/mouse/Mouse-1.1.tar.gz

VD>Этот Мышь — это что за зверь? Когда он появился? И чем отличается от конкурентов?

Хороший PEG без pakrat, написан грамотным человеком, который пишет статьи о том, что мемоизация не особо нужна
Очень рекомендую его мануал пролистать на предмет принципов обработки ошибок.
http://www.romanredz.se/mouse/Mouse-1.1.manual.pdf
Re[7]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.10.09 22:54
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Нет я имел в виду, что они умеют строить в памяти, грубо говоря, s-expressions, которые потом легко программно преобразовать в AST — и не нужно засорять грамматику custom actions.


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

Мы планировали сделать более наглядные семантические акции в виде методов.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: PEG - мысли...
От: z00n  
Дата: 27.10.09 22:54
Оценка:
Z>>Вы предлагаете автоматически писать что то типа:
Z>>
Z>>   Statement = 
Z>>   / For
Z>>   / ... 
   
Z>>   For =
Z>>   / 'for' Id '=' Expression ',' Expression 'do' Block 'end' # OK
Z>>   / 'for' (!StatementFOLLOW .)*   # <- Eat error
        
Z>>   StatementFOLLOW = 'for' / 'if' / 'while'/ ....

Z>>

Z>>Это мило, но легко делается руками, а там, где легко не делается и оптимизатор скорее всего не поможет.

VD>Нет я предлакаю в случае правила:

VD>
VD>/ 'for' # Id '=' Expression ',' Expression 'do' Block 'end'
VD>

VD>если парсер спарсит 'for', то при наличии несоответствия грамматике не откатываться, а выдавать сообщение об ошибке.
VD>При этом еще и новую хэш-таблицу для мемоизации завадить в каждом таком месте.

Он и не откатится, поскольку вторая продукция сматчится если не сматчится первая! В Rats ее можно пометить другим тегом и получить в дереве Error ноду:
 / 'for' (!StatementFOLLOW .)*   @Error_Node_042 # <- Eat error


Пример из жизни (некорректная программа на луа):
-- lua
x
print(42)


Parse-tree:
(block
  [new-prepos.hlua:2:1: expression in statement position: x
  ,(CallStmt
     (Call
       (Variable
         (Id "print") [])
       [(Args
          (ExpressionList (Number "42") []))]))]
  RNone)
Re[6]: PEG - мысли...
От: z00n  
Дата: 27.10.09 22:56
Оценка:
Здравствуйте, AndrewVK, Вы писали:
AVK>В итоге реальные файлы грамматик в antlr представляют собой жуткую мешанину, которую, к тому же, не так то просто редактировать, потому что ни интеллисенса, ни тем более более продвинутых фич.

Для ANTLR есть приличная IDE:
http://www.antlr.org/works/screenshots/editor.jpg

Re[5]: PEG - мысли...
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 27.10.09 22:57
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Ты не прав. RTFM.


Видать не тот ты FM читал. Я без всяких ФМ щупал генеримый им код в больших количествах. Обычный рекурсивный спуск.

AVK>>Основная разница с PEG — по дефолту там нет никаких откатов,


VD>Вот и подумай, как это возможно без построения ДКА?


Что возможно? LL(k) парсер?

AVK>>Да нет, есть там возможность объединения грамматик, но в доке это довольно мутно описано.


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


Ну да, лексер не расширяем.

AVK>>Опять непонятно. В случае LR(k)/LL(k) откаты просто не нужны


VD>Если есть ДКА.


Пофиг, есть или нет. Даже если LL парсер реализован чистым рекурсивным спуском.

VD> Иначе заглядывание вперед выльется в те самые откаты.


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

VD>К тому же LR(k)/LL(k) даже C# отпарсить не могут. Весьма немощные они.


Недостатки являются продолжением достоинств.

VD>Подумай что сказал. Что значит "анализа"? Это заглядывание вперед. А оно не бесплатно.


Для фиксированного k — очень дешево.

VD> Это тот же парсинг + откат.


Не думаю, что простое сравнение фиксированного количества типов токенов стоит называть парсингом с откатом. Ну и главное — ДКА реализация ничем не отличается от рекурсивного спуска в этом плане. И там и там происходит ровно одно и то же, просто вместо свитчей и ифов используют большой лукап.

VD>Бесплатное заглядывание вперед получается только мемоизацией.


В LL/LR никакая мемоизация не нужна, там для каждого конкретного токена несколько вызовов одного правила невозможны.

VD> Антлр 3 использует мемоизацию (задается опцией)


Только там, где реально в правилах фиксированный k невозможен.

VD>. В остальных случаях работает или на чистых откахат или строго по ДКА (без заглядывания вперед).


LL(k) парсер, даже если он реализован при помощи ДКА (и вообще при помощи чего угодно), все равно будет местами заглядывать на k лексем вперед. Собственно, значение k именно это и определяет.

VD>Короче, разберись в вопросе сначала.



Влад, вот ты сколько на базе antlr нетривиальных парсеров сделал?

AVK>>По крайней мере в antlr структура дерева правил проверяется до генерации реализации парсера, я исходники antlr2 в свое время подробно изучал. Т.е. построение ДКА это совсем другой процесс.


VD>Все правильно. Потому он и не PEG, а LL(*).


antlr2 — LL(k), а не LL(*). Если, конечно, синтаксические предикаты не использовать. И при чем тут PEG? Речь об использовании ДКА при реализации.
... << RSDN@Home 1.2.0 alpha 4 rev. 1249 on Windows 7 6.1.7600.0>>
AVK Blog
Re[7]: PEG - мысли...
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 27.10.09 22:57
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Нет я имел в виду, что они умеют строить в памяти, грубо говоря, s-expressions, которые потом легко программно преобразовать в AST


Лишнее промежуточное дерево? Не уверен что это хорошее решение.

Z> — и не нужно засорять грамматику custom actions.


Вот тебе не кажется, что то, что ради хорошего вида исходников мы делаем кучу лишних действий в рантайме, как то оно для production кода не очень, нет?
Опять же, от эвристик и кастомных ошибок это не спасает.
... << RSDN@Home 1.2.0 alpha 4 rev. 1249 on Windows 7 6.1.7600.0>>
AVK Blog
Re[4]: PEG - мысли...
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 27.10.09 22:57
Оценка:
Здравствуйте, VladD2, Вы писали:

VD>Это наверно клон хаскелевского парсека.


Вроде того.

VD> Он к делу вообще не относится.


Почему это? PEG в чистом виде.
... << RSDN@Home 1.2.0 alpha 4 rev. 1249 on Windows 7 6.1.7600.0>>
AVK Blog
Re[8]: PEG - мысли...
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 27.10.09 23:01
Оценка:
Здравствуйте, VladD2, Вы писали:

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


Вот вот. То один косяк, то другой. В итоге большая часть генераторов, имхо, не mature.
... << RSDN@Home 1.2.0 alpha 4 rev. 1249 on Windows 7 6.1.7600.0>>
AVK Blog
Re[7]: PEG - мысли...
От: AndrewVK Россия http://blogs.rsdn.org/avk
Дата: 27.10.09 23:01
Оценка:
Здравствуйте, z00n, Вы писали:

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


Видел. На тот момент, когда смотрел (конец 2007), не очень оно приличным было.
... << RSDN@Home 1.2.0 alpha 4 rev. 1249 on Windows 7 6.1.7600.0>>
AVK Blog
Re[8]: PEG - мысли...
От: z00n  
Дата: 27.10.09 23:12
Оценка:
Здравствуйте, AndrewVK, Вы писали:


AVK>Лишнее промежуточное дерево? Не уверен что это хорошее решение.


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

Это зависит — если разбирать XML — то конечно не стоит, если язык типа Scala — там это лишнее дерево как слону дробина. Памяти же в случае Pakrat будет потрачена на мемоизацию x100, буквально.
Re[3]: PEG - мысли...
От: TimurSPB Интернет  
Дата: 27.10.09 23:12
Оценка:
Здравствуйте, VladD2, Вы писали:

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


TSP>>Зачем нужен транслятор с плохой устойчивостью к ошибкам?

TSP>>К примеру, в большинстве компиляторов C++ и так пропуск одной точки с запятой карается выводом безумных сообщений. Без опыта ошибки ищутся очень долго.
TSP>>А тут предлагается методика, снижающая устойчивость к ошибкам.

VD>Где, если не секрет?



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


Попробую уточнить.
Я правильно понял, что это свойство в конечной реализации может привести к снижению качества обработки ошибок?
Make flame.politics Great Again!
Re[4]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.10.09 23:49
Оценка:
Здравствуйте, TimurSPB, Вы писали:

TSP>

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


TSP>Попробую уточнить.

TSP>Я правильно понял, что это свойство в конечной реализации может привести к снижению качества обработки ошибок?

Все что я написал в исходном сообщении темы как раз и направлено на избавление от этого недостатка.

К тому же, как верно заметили тут товарищи в природе существуют реально работающие генераторы парсеров которые тоже каким-то образом решили эту проблему.
Конечно же никто не говорит о том, что можно использовать парсеры работающие в режиме плохо реализованных регулярных выражения — смачилось/не сматчилось.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.10.09 16:19
Оценка:
Здравствуйте, AndrewVK, Вы писали:

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


AVK>Видел. На тот момент, когда смотрел (конец 2007), не очень оно приличным было.


Интелисенс и рефакторинг прилично работали еще в 2008. Сейчас наверно и отладка с проверкой заработали.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.10.09 16:27
Оценка:
Здравствуйте, z00n, Вы писали:

Z>Он и не откатится, поскольку вторая продукция сматчится если не сматчится первая! В Rats ее можно пометить другим тегом и получить в дереве Error ноду:

Z>
Z> / 'for' (!StatementFOLLOW .)*   @Error_Node_042 # <- Eat error
Z>


Согласен. Но зачем какие-то лишние действия когда можно просто ничего не делать?

Такой ход хорош только для востановления. Скажем внутри стэйтмента С-подобного языка хорошей стратегией востановления будет жрать все до следующей ";" или наоборот начать парсинг нового стэйтмента с токена на котором произошла ошибка.

Z>Пример из жизни (некорректная программа на луа):

Z>
Z>-- lua
Z>x
Z>print(42)
Z>


Z>Parse-tree:

Z>
Z>(block
Z>  [new-prepos.hlua:2:1: expression in statement position: x
Z>  ,(CallStmt
Z>     (Call
Z>       (Variable
Z>         (Id "print") [])
Z>       [(Args
Z>          (ExpressionList (Number "42") []))]))]
Z>  RNone)
Z>



Для Луа АСТ строится?


Что касается стратегии обнаружения ошибок в Маус, я почитал ту статью...
Они просто сообщают о том что несматчилось в самой дальней из разбираемых позиций в тексте.
Согласен, что в общем случае это хорошая стратегия. Но бенефиты от моего предложения не только в упрощении идентификации ошибок, но и в значительном сокращении потребляемых ресурсов.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.10.09 16:30
Оценка:
Здравствуйте, z00n, Вы писали:
Z>Хороший PEG без pakrat, написан грамотным человеком, который пишет статьи о том, что мемоизация не особо нужна
Z>Очень рекомендую его мануал пролистать на предмет принципов обработки ошибок.
Z>http://www.romanredz.se/mouse/Mouse-1.1.manual.pdf

Как оказалось и Пакратом тоже. Только его отдельной опцией включать нужно (-m, если не ошибаюсь). Плюс у них есть режим профилирования в котором выводится статистика (в том числе об откатах), что позволяет понять нужна ли мемоизация и или включить ее, или изменить грамматику. Кстати, хорошая идея.

Кстати... А насколько можно делать мемоизацию для отдельных правил?
Ведь можно делать ее динамически. Если профилирование показало, что для каких-то правил идет много откатов, то именно для них можно врубить мемоизацию.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.10.09 16:32
Оценка:
Здравствуйте, TimurSPB, Вы писали:

TSP>

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


TSP>Попробую уточнить.

TSP>Я правильно понял, что это свойство в конечной реализации может привести к снижению качества обработки ошибок?

В догонку...

Посмотрел на то как сделаны сообщения об ошибках в Маусе (ссылка есть рядом).
Там используется стратегия — сообщать о неудачах правил которые были применены к наиболее дальнему символу разбираемой строки. Судя по всему это так же решает проблему.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[2]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.10.09 16:35
Оценка:
Здравствуйте, chukichuki, Вы писали:

C>Мне механизм пакрат-парсеров все больше напоминает реализацию резолюции в прологе. В этом контексте ваша контрольная точка есть ни что иное, как прологовское отсечение.


Есть немного.

C>Может пора уже объединить два механизма ?


Может быть. Только основная проблема пролога — дикие тормоза на реальных задачах. Может имеет смысл к прологу мемоизацию прикрутить?

C>Заменить прологовскую базу фактов входной строкой, интегрировать в пеги унификацию термов, кое-где подкрасить, надежно склеить скотчем и ... Готов новомодный язык (поди еще и тьюринг-полный) для написания парсеров. Подозреваю нам поставят памятник.


Хорошая идея!

Вопрос только нафига в парсерах унификация? Что унифицировать то будем?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[4]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 28.10.09 18:14
Оценка:
Здравствуйте, palm mute, Вы писали:

PM>Вот граждане пишут, что из этого получилось: DCGs+Memoing=Packrat Parsing but is it worth it?


Спасибо. Очень интересная ссылка! Причем она интересна именно относительно Пакрата, а не прикручивания Меркури как такового.

PM>В парсерах на Прологе унификация используется в двух случаях — 1) для возврата результатов парсинга и 2) для добавления контекстных зависимостей.


Первое не нужно для обычных (не логических) языков. А второе... я не очень понял о чем идет речь. Можно по подрбнее?

PM>
PM>elem(node(Tag, Children)) --> tag_open(Tag), elems(Children), tag_close(Tag).   % (1)
PM>


PM>Совпадение открывающих и закрывающих тегов проверяется в строке (1) автоматически за счет унификации.


Дык для парсера написанного на не логическом языке тут унификация не потребуется. Тут скорее паттерн-матчинг будет нужен.
Так что получается, что в логических унификация используется за не имением других инструментов.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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 на самом деле только одна мысль — кеширование, остальное — парсер как парсер, я не понимаю чего ты так на нём зациклился
Если нам не помогут, то мы тоже никого не пощадим.
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 ">";

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

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


Чистый пакрат — это по всей видимости маразм. А лишнее дерево и для Скалы лишнее. Скажем если использовать парсер в целях интеграции с IDE, то там любой лишний чих может быть в тягость, так как парсер может вызываться на каждый вбитый символ.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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! скоро будет
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 строк без построителя деревьев.


Ну, и что же он тогда вручную написан?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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 весьма эффективным образом и без серьезных ограничений.


Честно говоря, ничего нового в этом обсуждении, кроме, конечно, кошерности, я не обнаружил.
Если нам не помогут, то мы тоже никого не пощадим.
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[2]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 30.10.09 08:58
Оценка:
Здравствуйте, dotneter, Вы писали:

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

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

Интересная работа. В первую очередь тем, что это адаптация PEG для использования в рамках языка с расширяемым синтаксисом.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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/

Это я как раз смотрел. Там ничего интересного нет.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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

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

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

Z>> ...

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


Для ANTLR IDE появилась года три назад. А вот заработало ли оно полноценно хотя бы сейчас не известно. Год назад это был весьма сырой продукт.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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(когда я с ней возился) была полезным продуктом, она позволяла делать несколько полезных преобразований грамматик и, вообще, помогала думать. Отдельные баги с тех пор, наверное, исправили.


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


VD>Минусы:

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

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

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

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


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

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


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

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


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