VD>Обещают линейное время парсинга. Причем с неограниченным декларативно-выраженным заглядыванием вперед.
VD>Вроде как даже можно динамически парсер строить (очень полезно для макросов).

Линейное время — только при мемоизации, как писали выше, т.е. packrat алгоритм. Вот только здесь написано, как народ померял производительность оригинального PEG vs packrat и выяснил, что мемоизовать нужно далеко не все.

VD>Просто чудеса, да и только. А я в чудеса не верю. Какие реальные слабые места могут быть у этого чуда и чудо ли это?

Чудо — простота и мощность. Если я правильно понял, есть PEG грамматики, которые не являются LL(1) грамматиками.
Сам парсер пишется за два дня, потом неделю оптимизируется, и используется по мере надобности.

Вдогонку — обсуждение сабжа на LtU.