Re[5]: патологические случаи в PEG - Философия программирования

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

L>А какие есть вообще варианты, когда у PEG получается сложность хуже чем линейная? Удалось придумать только такой изврат:
L>

L>xxxxxxxx
L>A = . A / . A / "y";
L>

L>(экспонента, негативный результат)

И что ты тут придумал?

Если '.' — это любой символ, то смысл в ' / . A / "y"' отсутствует на прочь, а разбираться эта байда будет за линейное время.

В PEG '/' — это приоритетный выбор. Если он сматчился, то другие альтернативы рассматриваться не будут. По сему в PEG любая грамматика однозначана.

Что до "когда у PEG получается сложность хуже чем линейная" то все зависит от алгоритма. Для PEG есть алгоритм Пакрат. У него линейная сложность для любой грамматики. Вот только тормоз он.
Ну, а без Пакрата (читай тотальной мемоизации). Любая грамматика требующая сильных откатов будет не ленейная. Но опять же все зависит от оптимизаций.

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

VD>И что ты тут придумал?
Вообще говоря экспоненту. Посмотри сам внимательно.
Это правило обламывается на данной строке. Но если не мемоизировать то обноружение облома потребует 2^n времени.
Правда моя реализация отработает за линейное время.
Ибо тут достаточно запоминать последнее применение правила.
Что я и делаю.

VD>Что до "когда у PEG получается сложность хуже чем линейная" то все зависит от алгоритма. Для PEG есть алгоритм Пакрат. У него линейная сложность для любой грамматики. Вот только тормоз он.
Это да. Но тут видимо имелось в виду реализация без мемоизации.

VD>Ну, а без Пакрата (читай тотальной мемоизации). Любая грамматика требующая сильных откатов будет не ленейная. Но опять же все зависит от оптимизаций.
Без мемоизации могут помочь только ДКА. И только в очень редких случаях.
Но в случае с пегом строить их занятие очень не простое. Лобовое решение не работает.
Собственно проблем целых 3 (не считая рекурсии):
1)Предикаты. Полный песец. Как их засунуть в автомат вообще не ясно.
2)Приоритетный выбор. Тут проблема в том что данное правило "x" / "xx" по правилам ПЕГа никогда не смтатчит "xx". Но если его тупо засунуть в ДКА то оно будет матчить "xx".

    printFsm(
      Choice
        ([String("x"),
          String("xx")
        ])
    );

0  start
-> 1 ['x']

1  ok
-> 2 ['x']

2  ok

3)Различие в поведении *, + и ?.
В ПЕГе операторы жадные и не уступчивые.
А при тупом запихивании в ДКА становятся жадными и уступчивыми.
По правилам ПЕГ данное правило ".*." никогда не сматчит. Ибо * сожрет всю строку и . будет всегда обламываться.
Но если загнать это в ДКА то получим

    printFsm(
      Seq
        ([RepeatMin(0, any),
          any
        ])
    );

0  start
-> 1 ['\0'.. char.MaxValue]

1  ok
-> 1 ['\0'.. char.MaxValue]

Данный ДКА будет разбирать любую строку из как минимум одного символа.

... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>

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

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

L>А насчет левой рекурсии вы не размышляли, можно ли ее все-таки разрулить?

Имхо, это не принципиально. Её всегда можно в итерацию переписать.

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

H>Имхо, это не принципиально. Её всегда можно в итерацию переписать.

По моему это очень геморно. Как переписать грамматику вот для такого примера, и сохранить при этом правильную ассоциативность?
2 + 3 * 5 * 6 * (1 + 2) * 3 + 4 ^ 6 ^ 7
?

WH>1)Предикаты. Полный песец. Как их засунуть в автомат вообще не ясно.

допустим для состояния n есть правило (!predicat first-variant) / second-variant
тогда для состояния n можно добавить три цвета: красный(предикат), зеленый(first-variant) и синий(second-variant)
автомат начинает работу с состояния n-красный,
если при разборе предиката происходит сбой (не матчится), то происходит переход в состояние n-зеленый и восстановление позиции,
если предикат заканчивается, то происходит переход в состояние n-синий и восстановление позиции

WH>2)Приоритетный выбор. Тут проблема в том что данное правило "x" / "xx" по правилам ПЕГа никогда не смтатчит "xx". Но если его тупо засунуть в ДКА то оно будет матчить "xx".

здесь необходимо модифицировать правила построения автомата
правила перехода для first-variant должны всегда перекрывать такие же правила для second-variant

WH>3)Различие в поведении *, + и ?.
WH>В ПЕГе операторы жадные и не уступчивые.
WH>А при тупом запихивании в ДКА становятся жадными и уступчивыми.
WH>По правилам ПЕГ данное правило ".*." никогда не сматчит. Ибо * сожрет всю строку и . будет всегда обламываться.

в состояния автомата необходимо добавить информацию к какой именно части какого конкретного правила эти состояния относятся

WH>Другими словами ненадо ничего делать. Ибо ровно тоже самое получается при генерации кода методом "в лоб".

да, есть такое

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

DG>>здесь необходимо модифицировать правила построения автомата
DG>>правила перехода для first-variant должны всегда перекрывать такие же правила для second-variant
WH>Спасибо тебе КО. Вот только засада в том что лесом пойдет вся теория автоматов и все алгоритмы придется выдумывать с нуля.

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

DG>>в состояния автомата необходимо добавить информацию к какой именно части какого конкретного правила эти состояния относятся
WH>И что это даст?

для правила .*. — это даст автомат:

(0,.)->0
(0,else)->1
(1,.)->end
(1,else)->error

А какие есть вообще варианты, когда у PEG получается сложность хуже чем линейная? Удалось придумать только такой изврат:

xxxxxxxx
A = . A / . A / "y";

(экспонента, негативный результат)

Какие есть еще варианты?

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

VD>>Что до "когда у PEG получается сложность хуже чем линейная" то все зависит от алгоритма. Для PEG есть алгоритм Пакрат. У него линейная сложность для любой грамматики. Вот только тормоз он.
WH>Это да. Но тут видимо имелось в виду реализация без мемоизации.

Да, я имел в виду без мемоизации. Просто я делаю свой велосипедик, для саморазвития. Поэтому интересуюсь.
Но мемоизация — это полный ппц. Лучшей реализацией вроде бы считается Rats!, но он у меня сожрал 400мб оперативки на несложной тестовой грамматике и инпуте в 1мб

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

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

но такую задачу я решил рукопашной расстановкой приоритетов (алгоритм на десяток строк) — это существенно ускорило парсер C#.

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

WH>Вообще говоря экспоненту. Посмотри сам внимательно.
WH>Это правило обламывается на данной строке. Но если не мемоизировать то обноружение облома потребует 2^n времени.

Да, я как-то упустил из виду, что речь идет о случае облома. Ну, так надо или алгоритмы сложнее плинтуса использовать или не писать абсолютно бредовые грамматики. А лучше и то, и другое. На что циклы то?

WH>Правда моя реализация отработает за линейное время.
WH>Ибо тут достаточно запоминать последнее применение правила.

Ну, да. Частичная мемоизация и куда более жизненные случаи оптимизирует.

VD>>Что до "когда у PEG получается сложность хуже чем линейная" то все зависит от алгоритма. Для PEG есть алгоритм Пакрат. У него линейная сложность для любой грамматики. Вот только тормоз он.
WH>Это да. Но тут видимо имелось в виду реализация без мемоизации.

Ну, раз имелось, то надо было об этом и говорить. Без этого его слова являются чушью.

VD>>Ну, а без Пакрата (читай тотальной мемоизации). Любая грамматика требующая сильных откатов будет не ленейная. Но опять же все зависит от оптимизаций.
WH>Без мемоизации могут помочь только ДКА. И только в очень редких случаях.

Ну, дык мемоизация тоже является оптимизацией. Зачем от нее отказываться? Можно поступить как ты — мемоизировать только значение разбора правила для одной позиции. Можно делать тоже самое для двух позиций (где-то читал, что это дает лучший результат и покрывает 99% случаев). Можно придумать и другие подходы.

WH>Но в случае с пегом строить их занятие очень не простое. Лобовое решение не работает.

Ну не лобовой же работает же? Хотя ты по началу мне сказал что ничего не выйдет. Я тебе сразу сказал, что для разбора листовых правил (аналогов токенов) лучше ДКА ничего не придумаешь.

WH>Собственно проблем целых 3 (не считая рекурсии):
WH>1)Предикаты. Полный песец. Как их засунуть в автомат вообще не ясно.

И с предикатами можно автоматы делать. Не для всех случаев конечно, но все же.

Потом я тебе уже приводил ссылку на Metafront. У них другой подход. Но его очень даже можно приспособить для разбора PEG-а. Как грится — сложно, но можно.

WH>2)Приоритетный выбор. Тут проблема в том что данное правило "x" / "xx" по правилам ПЕГа никогда не смтатчит "xx". Но если его тупо засунуть в ДКА то оно будет матчить "xx".

Дык, а зачем тупо? Случаи вроде "x" / "xx" можно выявлять и устранять (или сообщать об ошибках). Это тупой случай общего префикса. Его выявление не составляет труда.

WH>3)Различие в поведении *, + и ?.
WH>В ПЕГе операторы жадные и не уступчивые.
WH>А при тупом запихивании в ДКА становятся жадными и уступчивыми.

Что значит уступчивые?

WH>По правилам ПЕГ данное правило ".*." никогда не сматчит. Ибо * сожрет всю строку и . будет всегда обламываться.
WH>Но если загнать это в ДКА то получим
WH>

WH>    printFsm(
WH>      Seq
WH>        ([RepeatMin(0, any),
WH>          any
WH>        ])
WH>    );
WH>

WH>[code]
WH>0 start
->> 1 ['\0'.. char.MaxValue]

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

Только это опять же пример бессмысленной грамматики. Такие надо выявлять и предупреждать, что грамматика не корректна (всегда файлит).

WH>Данный ДКА будет разбирать любую строку из как минимум одного символа.

Ежу понятно, что если ДКА не соответствует грамматике, то он будет вести себя иначе.

В общем, не надо свои недоработки на особенности технологии списывать.

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

L>Да, я имел в виду без мемоизации.

Ну, так и сказал бы об этом.

L>Но мемоизация — это полный ппц. Лучшей реализацией вроде бы считается Rats!, но он у меня сожрал 400мб оперативки на несложной тестовой грамматике и инпуте в 1мб

Лучший результат пока что у нас в PegGrammar. Вольфхаунд его основной автор. Линейной сложности мы не обеспечиваем, но на реальных грамматиках скорость получается весьма приличная. Специальных исследований мы не производили, но по косвенным данным она сильно выше чем у Rats! и разных ANTLR. С последними оптимизациями Вольфхаунда скорость составляет где-то 4 метра в секунду на процессоре ~3 Ггц класса Core. А уж что-то вроде регулярных выражений++ вообще разбирается со скоростью близкой к рукописной. Например, реализация парсера JSON-а сделала рукописный парсер из Json.NET где-то в полтора раза.

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

VD>Ну не лобовой же работает же? Хотя ты по началу мне сказал что ничего не выйдет. Я тебе сразу сказал, что для разбора листовых правил (аналогов токенов) лучше ДКА ничего не придумаешь.
Это было в твоем воображении.

VD>И с предикатами можно автоматы делать. Не для всех случаев конечно, но все же.
Вот тебе правило
!"*/" any
загони его в ДКА.

VD>Дык, а зачем тупо? Случаи вроде "x" / "xx" можно выявлять и устранять (или сообщать об ошибках). Это тупой случай общего префикса. Его выявление не составляет труда.
В частном случае.
В общем же случае там не все так просто.

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

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

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

... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>

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

L>По моему это очень геморно. Как переписать грамматику вот для такого примера, и сохранить при этом правильную ассоциативность?
L>2 + 3 * 5 * 6 * (1 + 2) * 3 + 4 ^ 6 ^ 7
L>?

Это, извини, детский лепет. Вот повторить грамматику шарпа сложнее. Ассоциативность вообще не признак грамматики, а семантика. Скажем 1 + 3 + 5 можно рассматривать как (1 + 3) + 5 или как 1 + (3 + 5). Причем с точки зрения сложения разницы не будет вовсе. В PEG такие правила обычно описываются циклами: "Expr ('+' Expr)*", что приводит к тому, что при построении АСТ (или другой обработке) вместо "('+' Expr)*" получается список. А там уже все зависит от алгоритма обработки этого списка.

Когда Хардкейс на PegGrammar делал парсер C#, то с толкнулся с тем, то описать приоритеты и ассоциативность в виде правил само по себе не просто. В итоге он просто запутался в нахрамождении правил. Тогда я ему предложил воспользоваться старым как мир подходом Pratt-парсер. При этом грамматика упростилась до примитивной и при этом еще и скорость выросла (правда тогда PegGrammar еще не поддерживал частичной мемоизации). Сейчас, возможно скорость бы осталась та же. Но по любому Pratt резко упрощает работу с операторами. Ассоциативность и приоритеты становятся декларируемыми.

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

VD>>Ну не лобовой же работает же? Хотя ты по началу мне сказал что ничего не выйдет. Я тебе сразу сказал, что для разбора листовых правил (аналогов токенов) лучше ДКА ничего не придумаешь.
WH>Это было в твоем воображении.

Гы. Любишь ты забывать то что не хочешь помнить.
Я как сейчас помню, что ты мне говрил как сложно прикрутить ДКА и что они мало что дадут в следствии того, что откаты и так идут в массе свой по первому символу.
Вот только прикрутил в итоге и это дало не малый прирост.

VD>>И с предикатами можно автоматы делать. Не для всех случаев конечно, но все же.
WH>Вот тебе правило
WH>!"*/" any
WH>загони его в ДКА.

В чем проблема то?

VD>>Дык, а зачем тупо? Случаи вроде "x" / "xx" можно выявлять и устранять (или сообщать об ошибках). Это тупой случай общего префикса. Его выявление не составляет труда.
WH>В частном случае.
WH>В общем же случае там не все так просто.

Жизнь она и состоит и массы частный случаев. Общий префикс один из них. Обработай его и будет тебе счастье.

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

ДКА то? Ты что-то путаешь.

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

Гы-гы. У него баги в алгоритме, а он вместо их исправления говорит окружающим "сам дурак".
Тут разбираться не в чем. Если у тебя есть грамматика any* any, то она она а) никогда успешно не спарсится, б) ДКА для нее таки построить можно, вот только они никогда ничего не сматчит.

VD>>Только это опять же пример бессмысленной грамматики. Такие надо выявлять и предупреждать, что грамматика не корректна (всегда файлит).
WH>Ну давай попробуй.

А что пробовать то? Вычислить, что один из может потребить любой ввод не проблема. Все что идет за таким правилом уже никогда не спарсится.

WH>Только не напиши экспоненциальный алгоритм как в случае с поиском левой рекурсии.

Там где-то баг. Просто надо поправить.

WH>Ты кстати обещал это исправить но воз и ныне там.

У меня другие проблемы есть. Доберусь до него — поправлю.
Я обещал это исправление на той неделе. Ты же обещал поддержку динамической расширяемости уже пол года назад. Но воз и ныне там. Причем это не просто баг, а критически важная фича для Nemerle 2.0. Причем нужна она уже сейчас. Хардкейс во всю работает над новой макросистемой.

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

VD>Вот только прикрутил в итоге и это дало не малый прирост.
Оно дало прирост в одном патологичском случае.

      keyword = ("abstract"     / "as"          / "base"        / "bool"        / "break"
                / "byte"        / "case"        / "catch"       / "char"        / "checked"
                / "class"       / "const"       / "continue"    / "decimal"     / "default"
                / "delegate"    / "do"          / "double"      / "else"        / "enum"
                / "event"       / "explicit"    / "extern"      / "false"       / "finally"
                / "fixed"       / "float"       / "for"         / "foreach"     / "goto"
                / "if"          / "implicit"    / "in"          / "int"         / "interface"
                / "internal"    / "is"          / "lock"        / "long"        / "namespace"
                / "new"         / "null"        / "object"      / "operator"    / "out"
                / "override"    / "params"      / "private"     / "protected"   / "public"
                / "readonly"    / "ref"         / "return"      / "sbyte"       / "sealed"
                / "short"       / "sizeof"      / "stackalloc"  / "static"      / "string"
                / "struct"      / "switch"      / "this"        / "throw"       / "true"
                / "try"         / "typeof"      / "uint"        / "ulong"       / "unchecked"
                / "unsafe"      / "ushort"      / "using"       / "virtual"     / "void"
                / "volatile"    / "while"       ) !identifierPartCharacters;

На всех остальных правилах там слезы, а не прирост.

VD>В чем проблема то?
В том что нужно пройти два символа, а распарсится только один.
Короче разберись в вопросе или не лезь.

WH>>Могут уступить часть строки куторую сожрали другому оператору чтобы строка сматчилась.
VD>ДКА то? Ты что-то путаешь.
Это ты не понимашь как композиция ДКА работает.

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

Вон в соседней ветке mefrill тоже из себя компилятор строить пытался... и что у него из этого вышло...

VD>Тут разбираться не в чем. Если у тебя есть грамматика any* any, то она она а) никогда успешно не спарсится, б) ДКА для нее таки построить можно, вот только они никогда ничего не сматчит.
Ну давай. Покажи как провести композицию двух автоматов:
Это any*

0  start ok
-> 0 ['\0'.. char.MaxValue]

Это any

0  start
-> 1 ['\0'.. char.MaxValue]

1  ok

Вперед.

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

WH>>Только не напиши экспоненциальный алгоритм как в случае с поиском левой рекурсии.
VD>Там где-то баг. Просто надо поправить.
Вот и поправь. Или просто выкинь.

VD>У меня другие проблемы есть. Доберусь до него — поправлю.
Закоментировать одну строку много времени не нужно.
У меня просто весь проект разобран, а вытягивать еще одну копию исходников я не хочу.

... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>

L>По моему это очень геморно. Как переписать грамматику вот для такого примера, и сохранить при этом правильную ассоциативность?
L>2 + 3 * 5 * 6 * (1 + 2) * 3 + 4 ^ 6 ^ 7
L>?

с этим все примитивно, правило с меньшим приоритетом должно "вызывать" правило с большим приоритетом

expression := sum-expression;
sum-expression := mul-expression ( sum-op mul-expression)*;
mul-expression := pow-expression( mul-op pow-expression)*;
pow-expression := other-expression ('^' other-expression)*;
other-expression := '(' expression ')') / number;

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

WH>Оно дало прирост в одном патологичском случае.

Ты рассуждаешь как теоретик. На практике же паталогические случаи являются самыми распространенными. По сему слезы превращаются в море.

WH>На всех остальных правилах там слезы, а не прирост.

У тебя от любой оптимизации "слезы, а не прирост" в некоторых случаях. Но на практике каждая дает прирост производительности, а в сумме получается приличная производительность генерированного кода.

VD>>В чем проблема то?
WH>В том что нужно пройти два символа, а распарсится только один.

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

Предикат вида "P any" где P литерал можно смело переписать в ~P, например.

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

Ты уже достал немного этим.

WH>>>Могут уступить часть строки куторую сожрали другому оператору чтобы строка сматчилась.
VD>>ДКА то? Ты что-то путаешь.
WH>Это ты не понимашь как композиция ДКА работает.

Нарисованный тобой автомат не верный. Ты сливаешь то что не должно сливаться.

VD>>Гы-гы. У него баги в алгоритме, а он вместо их исправления говорит окружающим "сам дурак".
WH>Все что тут можно сделать это не проводить композицию двух автоматов.

А что мешает просто добавить еще одно состояние? Не, я понимаю, что грамматика абсурдна. Но все же.
В прочем, вложенные автоматы тоже решение.

VD>>Тут разбираться не в чем. Если у тебя есть грамматика any* any, то она она а) никогда успешно не спарсится, б) ДКА для нее таки построить можно, вот только они никогда ничего не сматчит.
WH>Ну давай. Покажи как провести композицию двух автоматов:
WH>Это any*
WH>

WH>0  start ok
->> 0 ['\0'.. char.MaxValue]
WH>

WH>Это any
WH>

WH>0  start
->> 1 ['\0'.. char.MaxValue]
WH>1  ok
WH>

WH>Вперед.

Я тебе могу такой автомат нарисовать он совсем примитивный.

def trans(state : int, pos : int, str : string) : int
{
  def fail = -1;
  match (state)
  {
    | 0 => if (pos >= str.Length) trans(-1, pos, str) else trans(0, pos + 1, str)
    | 1 => pos
    | _ => fail
  }
}

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

А какой будет не частный, но реалистичный?

VD>>У меня другие проблемы есть. Доберусь до него — поправлю.
WH>Закоментировать одну строку много времени не нужно.
WH>У меня просто весь проект разобран, а вытягивать еще одну копию исходников я не хочу.

В вытягивании проблем нет. Поправить надо. Но у меня еще в плане исправление бага в компиляторе из которого в Н2 кое-что сделать нельзя.

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

WH>>>Только не напиши экспоненциальный алгоритм как в случае с поиском левой рекурсии.
VD>>Там где-то баг. Просто надо поправить.
WH>Вот и поправь. Или просто выкинь.

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

У нас динамическая расширяемость таки появится? Или это снова нерешаемая в общем случае задача? Ты уже пол года ее обещаешь.

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

DG>допустим для состояния n есть правило (!predicat first-variant) / second-variant
DG>тогда для состояния n можно добавить три цвета: красный(предикат), зеленый(first-variant) и синий(second-variant)
DG>автомат начинает работу с состояния n-красный,
DG>если при разборе предиката происходит сбой (не матчится), то происходит переход в состояние n-зеленый и восстановление позиции,
DG>если предикат заканчивается, то происходит переход в состояние n-синий и восстановление позиции
Другими словами ненадо ничего делать. Ибо ровно тоже самое получается при генерации кода методом "в лоб".

DG>здесь необходимо модифицировать правила построения автомата
DG>правила перехода для first-variant должны всегда перекрывать такие же правила для second-variant
Спасибо тебе КО. Вот только засада в том что лесом пойдет вся теория автоматов и все алгоритмы придется выдумывать с нуля.

DG>в состояния автомата необходимо добавить информацию к какой именно части какого конкретного правила эти состояния относятся
И что это даст?

... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>

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

VD>Предикат вида "P any" где P литерал можно смело переписать в ~P, например.
Об этом решении тебе расказал я.
И это я делаю.
И что еще можно сделать я не знаю.

WH>>Короче разберись в вопросе или не лезь.
VD>Ты уже достал немного этим.
Это ты достал советами в теме в которой нихрена не понимаешь.

VD>Нарисованный тобой автомат не верный. Ты сливаешь то что не должно сливаться.
Читай следующую строчку:
WH>>Все что тут можно сделать это не проводить композицию двух автоматов.

VD>А что мешает просто добавить еще одно состояние? Не, я понимаю, что грамматика абсурдна. Но все же.
Какое еще состояние и куда его добавить?

VD>В прочем, вложенные автоматы тоже решение.
Какие еще вложенные автоматы?

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

... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>

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

VD>Да, я как-то упустил из виду, что речь идет о случае облома. Ну, так надо или алгоритмы сложнее плинтуса использовать или не писать абсолютно бредовые грамматики. А лучше и то, и другое. На что циклы то?

Просто у меня появилась идея, как сделать эффективную реализацию пакрата. Но возникает вопрос — а так ли сильно оно надо?

Потому и спрашиваю.. есть ли вообще реальные случаи, где это сильно нужно.

WH>>Это да. Но тут видимо имелось в виду реализация без мемоизации.
VD>Ну, раз имелось, то надо было об этом и говорить. Без этого его слова являются чушью.

Чушью является предположение, что я писал про реализацию с мемоизацией — потому что она всегда имеет линейную сложность

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

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

Кому нафиг нужно сложение без вычитания?

VD>Ассоциативность и приоритеты становятся декларируемыми.

А в какой форме это у вас записывается в грамматике?

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

L>Просто у меня появилась идея, как сделать эффективную реализацию пакрата.

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

L>Но возникает вопрос — а так ли сильно оно надо?

Потому и спрашиваю.. есть ли вообще реальные случаи, где это сильно нужно.

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

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

WH>>>Это да. Но тут видимо имелось в виду реализация без мемоизации.
VD>>Ну, раз имелось, то надо было об этом и говорить. Без этого его слова являются чушью.

L>Чушью является предположение, что я писал про реализацию с мемоизацией — потому что она всегда имеет линейную сложность

Линейную сложность имеет только тотальная мемоизация.

Более того PEG вообще не обязывает к использованию конкретных алгоритмов. Так что говоря о каких-то характеристиках нужно упоминать и алгоритм.

От:	VladD2	www.nemerle.org
Дата:	27.01.11 21:45
Оценка:	-3

	От:	WolfHound
	Дата:	28.01.11 02:38
	Оценка:	9 (2)

От:	hardcase	http://nemerle.org
Дата:	28.01.11 11:06
Оценка:	+1

	От:	lurrker
	Дата:	28.01.11 11:42
	Оценка:

От:	DarkGray	http://blog.metatech.ru/post/ogni-razrabotki.aspx
Дата:	28.01.11 21:22
Оценка:	+1