о парсерах

[wizzard]

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

черт, я всегда подозревал что все эти LL(1), LR, LALR и прочие - это страшная ересь. самая страшная ересь - это генераторы парсеров. SLR, LR(1) и комбинаторы парсеров - тоже ересь, но меньшая.

PEG (Packrat) парсеры рулят недвусмысленностью, комбинаторы и TDOP парсеры – простотой, а TDOP удобством + скоростью. в принципе, мне кажется, что TDOP можно писать руками со скоростью не меньшей, чем комбинаторы, при O(n log n) размера кода от кол-ва продукций в грамматике, и O(n) сложности разбора от длины файла, но я еще не привык. Зато на комбинаторах тривиально задаются вложенные грамматики, а на TDOP (пока) не получается. И BNF в них напрямую переводить нельзя :(

Кстати, а кто знает, где TDOP парсеры находятся в терминах множеств DFA, LL(k), LR(k) и т.д.? понятие binding power как-то срывает мне крышу, ибо формальной теории на эту тему я не нашел, сравнений тоже не нашел, а изобретать вряд ли осилю :)