Зачем смотреть вперед максимум на 1 входной токен?
В настоящее время я пытаюсь реализовать парсер LL, но у меня есть вопрос. Нужно ли мне смотреть не более 1 входного токена, чтобы проверить правильность синтаксического ввода пользователя или по другой причине?
1 ответ
Существует много разных алгоритмов разбора. Тот, который вы описываете, называется LL(1), и по определению он просто использует один токен упреждения. Тем не менее, есть другие алгоритмы синтаксического анализа, которые используют больше внимания, чем это. Например, синтаксический анализатор LL(2) использует два маркера просмотра, а синтаксический анализатор LL(*) имеет неограниченный просмотр. Существуют грамматики, для которых одного маркера упреждения недостаточно (то есть грамматики, которые являются LL(2), но не LL(1)). Вот пример:
S → n | n + S
Попробуйте выяснить, почему одного токена Lookahead недостаточно, но достаточно двух токенов.
Алгоритмы синтаксического анализа пытаются удержать число лексем в очереди малым для простоты и эффективности. По мере увеличения количества лексем предпросмотра увеличивается размер таблицы синтаксического анализа, необходимой для управления анализатором, а также увеличивается сложность построения этих таблиц.