Рекурсивный спуск против сгенерированных парсеров - эффективность
Как соотносятся рукописные парсеры рекурсивного спуска (которые неизбежно являются LL(k)) с генерируемыми парсерами LALR с точки зрения производительности?
Я знаю, что парсеры LALR способны обрабатывать гораздо больше грамматик, чем LL(k); однако я намерен написать свой парсер вручную, и рекурсивный спуск кажется наиболее подходящим выбором. Можно ли написать какой-либо другой вид от руки (разумно читаемый) из интереса?
NB. Я использую функциональный язык с оптимизацией хвостовых вызовов (F#), поэтому рекурсия [хорошо подобранных] не будет такой большой проблемой, как в других языках.
2 ответа
Я думаю, что многое зависит от языка, который вы пытаетесь разобрать. Другая часть производительности, о которой иногда забывают, это часть лексического анализа (сканирования) - она важна для производительности, поскольку имеет дело с символами, а не символами. Рекурсивный спуск - это хорошая первая итерация при написании синтаксического анализатора, и он делает следование логике разбираемого языка вполне естественным. Я думаю, что если анализируемый язык подходит (без левой рекурсии), вы должны начать с рекурсивного спуска. Выбор LALR для производительности на данном этапе представляется преждевременной оптимизацией. Вы можете написать анализатор диаграмм вручную, но я сомневаюсь, что вы это имеете в виду. Написание парсера LALR вручную возможно, но утомительно.
Выбор между LALR и LL по соображениям производительности на данный момент звучит как преждевременная оптимизация. Время анализа редко является узким местом в компиляторе. Если бы я был вами, я бы выбрал, основываясь на том, удобнее ли вам определять свою грамматику снизу вверх или сверху вниз.
Лично я нахожу, что с LALR грамматиками легко работать, а интеграция F# с fsyacc (так я научился разбирать) позволяет очень легко интегрировать yacc в ваш проект.