Устав ждать когда WolfHound закончит (обещанное им еще в феврале) встраивание расширяемости и поддержки алгоритма TDOP (Pratt), я был вынужден сесть за это дело сам.
За три вечера мне удалось встроить TDOP и получить
работающее решение (хотя там еще есть чего доделывать и усовершенствовать).
Для начала выводы к которым я пришел за время работы:
1. TDOP неплохо интегрируется с PEG.
2. Для TDOP не нужна мемоизация. Точнее правила относящиеся к TDOP делятся на префиксные (где вначале правила есть некоторые PEG-правила) и постфиксные (где первое подправило — это обращение к расширяемому правилу). Так вот префиксные правила — это обычные правила PEG. Для них не нужна ни сила связывания, ни какая-либо другая дополнительная информация или обработка. А вот постфиксные правила подчиняются логике TDOP. И для них не нужны PEG-овские нюансы. При разборе расширяемого правило в обязательном порядке разбирается хотя бы одно префиксное правило, и ноль или больше посфиксного. При этом постфиксные правила не разбираются отдельно и рассматриваются всегда только в контексте расширяемого правила (в следствии особенностей алгоритма TDOP). В результате смысла в мемоизации разбора посфиксных правил я не вижу. Зациклиться они не могут, так как перед ними всегда разбираются префиксные правила. Так что и тут мемоизация не нужна. Отказавшись же от мемоизации посфиксных правил можно существенно упростить алгоритм, а за одно и ускорить его. По сему на мой взгляд имеет смысл мемоизировать вычисление только для префиксных правил и самих расширяемых правил.
3. Данную реализацию будет совсем не сложно заставить поддерживать динамическую расширяемость (сейчас поддерживается только статическая, т.е. в рамках одного пасера, расширяемость).
4. Очень часто суффиксные расширяющие правила содержат фиксированный набор символов (строковый литерал) во втором подправиле (первое подаравило у них всегда является рекурсивным обращением к расширяемому правилу). Это позволяет реализовать оптимизацию вынеся первый символ этого набора в неизменяемое поле объекта реализующего динамическое расширение. Это позволит организовать очень быстрый "fail" для самого частого случая использования. Тоже самое касается и префиксных правил. Но в их случае "fail-символом" будет являться первый символ грамматики правила.
Теперь о вопросах которые встали передо мной...
Основной вопрос — это как быть с порядочком разбора расширяющих правил? Поясню ситуацию. Предположим, что у нас есть грамматика где есть два расширяющих правила:
expr : Ast;
...
mul is expr = expr : 20 "*"s expr : 20;
xxx is expr = expr : 20 "*"s expr : 20 "*"s expr : 20;
Очевидно, что если использовать логику оператора приоритетного выбора PEG для разрешения неоднозначности между этими правилами, то будет выигрывать то правило которое идет первым. Так же очевидно, что если первым будет идти правило mul, то правило xxx никогда не сработает. Таким образом нужно как-то задавать последовательность в которой расширяющие правила будут встречаться внутри расширяемого.
Мне видится два решения данной проблемы:
1. Введение синтаксиса задающего сортировку правил.
2. Использовать стратегию "кто длиннее тот и прав", предложенную WolfHound.
У каждого подхода есть свои плюсы и минусы. С одной стороны второе решение выглядит хороши на первый взгляд, так как устраняет проблему целиком. Но в то же время оно сделает парсер медленнее, так как при каждом разборе расширяемого правила придется произвести попытку разбора каждого расширяющего правила. Другими словами, скорость разбора обязательно снизится. Вопрос только лишь насколько сильно. В принципе большинство попыток разбора расширяющих правил будет обламываться на первых символах. Возможно это спасет от сильной деградации производительности, особенно, если воспользоваться оптимизацией описанной в пункте четыре списка приведенного выше.
Кроме того не ясно не будет ли стратегия "кто длиннее тот и прав" приводить к не интуитивному поведению. Похоже что нет, но это только догадки.
Собственно, если выбирать стратегию 1, то нужно продумать как задавать порядок следования расширяющих правил (внутри расширяемого). Если же выбрать стратегию 2, то нужно подумать не приведет ли это к проблемам.
Собственно хотелось бы услышать мнение других по поводу того какая из стратегий разрешения неоднозначностей вам больше нравится. Ну, и приветствуются любые идеи.
ЗЫ
У меня еще тлеет надежда на то, что WolfHound все же напряжется и доделает задуманное им сам. Возможно моя работа подтолкнет его к этому. Прошу его не воспринимать мою работу как давление или конкуренцию. Я буду только рад если он доведет работу до конца сам. Хотя то что он проигнорировал мой пул-реквест с простейшими исправлениями (исправлен баг в $-строке и добавлены проекты для VS 2010) не внушает оптимизма.
В виду того, что он еще и не откликается на прямые обращения я нахожусь просто в замешательстве. Дальше ждать уже невозможно. Эдак мы просрем все на свете.
Данное расширение надо доделать в ближайшее время. Так что прошу тебя откликнуться.
Если у тебя какие-то технические проблемы, то погляди на
мою реализацию. Она проста и прекрасно работает. Не надо делать вселенский всемогутер. Нам нужно просто работающее решение. Потом будет намного проще довести его до ума.
