Введение

Техника разбора
Разбор сверху вниз в информатике — это стратегия разбора, при которой сначала рассматривается самый верхний уровень дерева разбора, а затем осуществляется движение вниз по дереву разбора с использованием правил переписывания формальной грамматики. LL-парсеры — это тип парсеров, использующих стратегию разбора сверху вниз. Разбор сверху вниз — это стратегия анализа неизвестных связей данных путем выдвижения гипотез об общих структурах дерева разбора и последующей проверки совместимости известных базовых структур с этими гипотезами. Он применяется при анализе как естественных, так и компьютерных языков. Разбор сверху вниз можно рассматривать как попытку найти левосторонние выводы входного потока путем поиска деревьев разбора с использованием последовательного расширения правил формальной грамматики сверху вниз. Для учета неоднозначности используется включительный выбор, который заключается в расширении всех альтернативных правых частей правил грамматики. Простые реализации разбора сверху вниз не завершаются для леворекурсивных грамматик, а разбор сверху вниз с возвратом может иметь экспоненциальную временную сложность относительно длины входных данных для неоднозначных контекстно-свободных грамматик. Однако более сложные парсеры, разработанные Фростом, Хафизом и Каллаганом, способны обрабатывать неоднозначность и левую рекурсию за полиномиальное время и генерировать представления полиномиального размера для потенциально экспоненциального числа деревьев разбора.

Уместительность левой рекурсии в анализе сверху вниз

Формальная грамматика, содержащая левую рекурсию, не может быть разобрана наивным рекурсивным методом спуска, если она не преобразована в слабо эквивалентную правую рекурсивную форму. Однако, недавние исследования показывают, что можно использовать левые рекурсивные грамматики (наряду со всеми другими формами общих CFG) в более сложном нисходящем парсере, применяя отсечение. Алгоритм распознавания, который обрабатывает неоднозначные грамматики и пресекает постоянно растущий прямой левый рекурсивный разбор, накладывая ограничения на глубину в зависимости от длины входной последовательности и текущей позиции во входных данных, был описан Фростом и Хафизом в 2006 году. Этот алгоритм был расширен до полного алгоритма разбора для обработки как прямой, так и косвенной (путем сравнения ранее вычисленного контекста с текущим контекстом) левой рекурсии за полиномиальное время, а также для генерации компактных полиномиальных представлений потенциально экспоненциального числа деревьев разбора для сильно неоднозначных грамматик Фростом, Хафизом и Каллаганом в 2007 году.

Временная и пространственная сложность анализа сверху вниз

Когда нисходящий анализатор пытается разобрать неоднозначный ввод относительно неоднозначной контекстно-свободной грамматики (CFG), ему может потребоваться экспоненциальное количество шагов (относительно длины ввода), чтобы перебрать все альтернативы CFG для построения всех возможных деревьев разбора, что в конечном итоге потребует экспоненциального объема памяти. Проблема экспоненциальной временной сложности нисходящих анализаторов, построенных как наборы взаимно рекурсивных функций, была решена Норвигом в 1991 году. Его метод аналогичен использованию динамического программирования и множеств состояний в алгоритме Эрли (1970) и таблиц в алгоритме CYK Кокке, Янгера и Касами. Ключевая идея заключается в сохранении результатов применения анализатора p в позиции j и повторном использовании этих результатов при возникновении той же ситуации. Фрост, Хафиз и Каллаган.

Используя PEG – другое представление грамматик – packrat-анализаторы предоставляют элегантный и мощный алгоритм разбора. См. Грамматику выражений.