Производительность парсеров: PEG против LALR (1) или LL (k)

Я видел некоторые утверждения о том, что оптимизированные парсеры PEG в целом не могут быть быстрее оптимизированных парсеров LALR (1) или LL (k). (Разумеется, выполнение анализа будет зависеть от конкретной грамматики.)

Я хотел бы знать, существуют ли какие-либо конкретные ограничения парсеров PEG, как действительные вообще, так и некоторые подмножества грамматик ПЭГ, которые сделают их хуже LALR (1) или LL (k) по производительности.

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

Ответ 1

Нашел хороший ответ о разборе Packrat против LALR. Некоторые цитаты из него:

L (AL) R парсеров также являются линейными анализаторами времени. Таким образом, теоретически, парсер Packrat и L (AL) R "быстрее".

На практике важно, конечно, реализация. Переходы состояния L (AL) R могут выполняться в очень немногих машинных инструкциях ( "искать код токена вверх в векторе, получать следующее состояние и действие" ), поэтому они могут быть чрезвычайно быстрыми на практике.

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

Ответ 2

PEG синтаксические анализаторы могут использовать неограниченный просмотр (при одновременном поддержании линейного времени синтаксического анализа в среднем через packrat), в отличие от (по умолчанию) LL(k) или LR(k) парсеров, которые используют ограниченный просмотр, при одновременном определении времени линейного анализа.

В последнее время (2014-2015) ANTLR4 сделал расширения для обработки произвольного вида (как в PEG), поддерживая при этом время линейного анализа в среднем (как говорят, более эффективное, чем алгоритм packrat), однако это включает новые расширения и варианты алгоритма синтаксического анализа LR (а не алгоритм по умолчанию LR).

Анализатор packrat (и связанные с ним парсеры для LL, LR) необязательно практичен, но предоставляет теоретические оценки для синтаксического анализа, поэтому сравнение может быть выполнено.

Но обратите внимание, что неограниченный просмотр может использоваться для синтаксического анализа грамматик/языков в линейном времени (например, через packrat или antlr), которые невозможно анализировать через LL(k) или LR(k) даже в нелинейном времени, Поэтому важно понимать , что по сравнению с тем, что.