Я хотел бы узнать больше о времени выполнения рекурсивных парсеров спуска. Меня также интересует пространство стека, используемое рекурсивными анализаторами спуска (и компромиссы между временем выполнения и пространством стека). Каковы некоторые хорошие источники информации?Что является хорошим источником анализа пространства/стека для рекурсивных парсеров спуска?
Я читал wikipedia article и искал по сети, но я не нашел ничего, что вдавалось в детали.
Runtimes для синтаксического анализа рекурсивного спуска довольно быстро; обычно используется служебная инструкция CALL/RET для реализации рекурсии. Ручные письменные версии, которые не отступают или смотрят в будущее, обычно должны быть очень быстрыми. Но важно не раз разбирать токен-поток; важно то, что обработанные символы обрабатываются временем для создания токенов и/или семантической проверки/генерации кода. Почему ты беспокоишься об этом?
Пространство стека определяется фундаментально самым глубоким вложением, необходимым для анализа программы. Если ваш парсер принимает (...) в выражениях, а кто-то пишет выражение с 50 000 вложенных парнов, рекурсивный синтаксический анализ спуска будет повторяться 50 000 раз. Вы можете предотвратить это поведение (почти все), сделав произвольное правило о том, насколько глубокой может быть рекурсия для парсера. Я обнаружил, что 100 уровней позволят вам обрабатывать удивительно сложные программы.
Мне интересно об этих сроках выполнения, чтобы улучшить мое понимание времени выполнения для рекурсивных алгоритмов в целом :-) – SundayMonday