Рекурсивный спуск против генерируемых парсеров - эффективность

Question

Как рукописные парсеры рекурсивного спуска (которые неизбежно являются LL (k)) по сравнению с сгенерированными парсерами LALR с точки зрения производительности?

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

Примечание. Я использую функциональный язык с оптимизацией хвостового вызова (F #), поэтому рекурсия [с учетом индивидуальных особенностей] не будет такой большой проблемой, как в других языках.

Answer 1

Я думаю, многое зависит от языка, который вы пытаетесь разобрать. Другая часть производительности, о которой иногда забывают, это часть лексического анализа (сканирования) - она ​​важна для производительности, поскольку имеет дело с символами, а не символами. Рекурсивный спуск - это хорошая первая итерация при написании синтаксического анализатора, и он делает следование логике разбираемого языка вполне естественным. Я думаю, что если анализируемый язык подходит (без левой рекурсии), вы должны начать с рекурсивного спуска. Выбор LALR для производительности на данном этапе представляется преждевременной оптимизацией. Вы можете написать анализатор диаграммы от руки, но я сомневаюсь, что вы это имеете в виду. Написание парсера LALR вручную возможно, но утомительно.

Answer 2

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

Лично я считаю, что с грамматиками LALR легко работать, а интеграция F # с fsyacc (именно так я научился разбирать) упрощает интеграцию yacc в ваш проект.