Re[7]: PEG - мысли...
От: VladD2 Российская Империя www.nemerle.org
Дата: 27.10.09 22:54
Оценка:
Здравствуйте, z00n, Вы писали:

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


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

Мы планировали сделать более наглядные семантические акции в виде методов.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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

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>Я правильно понял, что это свойство в конечной реализации может привести к снижению качества обработки ошибок?

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

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

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


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


Интелисенс и рефакторинг прилично работали еще в 2008. Сейчас наверно и отладка с проверкой заработали.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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>



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


Что касается стратегии обнаружения ошибок в Маус, я почитал ту статью...
Они просто сообщают о том что несматчилось в самой дальней из разбираемых позиций в тексте.
Согласен, что в общем случае это хорошая стратегия. Но бенефиты от моего предложения не только в упрощении идентификации ошибок, но и в значительном сокращении потребляемых ресурсов.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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, если не ошибаюсь). Плюс у них есть режим профилирования в котором выводится статистика (в том числе об откатах), что позволяет понять нужна ли мемоизация и или включить ее, или изменить грамматику. Кстати, хорошая идея.

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

TSP>

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


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

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

В догонку...

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

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


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

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


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

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


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

Вопрос только нафига в парсерах унификация? Что унифицировать то будем?
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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[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) автоматически за счет унификации.


Дык для парсера написанного на не логическом языке тут унификация не потребуется. Тут скорее паттерн-матчинг будет нужен.
Так что получается, что в логических унификация используется за не имением других инструментов.
http://nemerle.org/Banners/?g=dark
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
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>Так что получается, что в логических унификация используется за не имением других инструментов.
Унификация — это самый общий инструмент. Паттерн-матчинг — всего-лишь частный случай, в котором не поддерживаются переменные с левой стороны и повторные вхождения переменных в паттернах.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.