Блог

Я хотел бы больше узнать о времени выполнения анализаторов рекурсивного спуска. Меня также интересует пространство стека, используемое анализаторами рекурсивного спуска (и компромиссы между временем выполнения и пространством стека). Каковы некоторые хорошие источники информации?

Я прочитал статью в Википедии и поискал в Интернете, но не нашел ничего, что вдавалось бы в подробности.

Время выполнения для синтаксического анализа рекурсивного спуска довольно быстрое; обычно для реализации рекурсии используются машинные команды CALL / RET. Рукописные версии, которые не отступают или не смотрят вперед, обычно должны быть очень быстрыми. Но важно не время для анализа потока токенов; важно время, затрачиваемое на обработку символов для создания токенов и / или семантической проверки / генерации кода. Почему вы беспокоитесь об этом?

Пространство стека в основном определяется самой глубокой вложенностью, необходимой для анализа программы. Если ваш синтаксический анализатор принимает (…) в выражениях, и кто-то записывает выражение с 50 000 вложенными скобками, синтаксический анализ рекурсивного спуска повторится 50 000 раз. Вы можете предотвратить это поведение (почти все делают), установив произвольное правило о том, насколько глубокой может быть рекурсия для анализатора. Я обнаружил, что 100 уровней позволят вам обрабатывать удивительно сложные программы.