PEG - мысли... - Философия программирования

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

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

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

Мы планировали сделать более наглядные семантические акции в виде методов.

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)

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

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

Здравствуйте, 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? Речь об использовании ДКА при реализации.