Грамматические ограничения на токен смотреть в будущее

Я знаю, что есть два типа ограничений на грамматику, которые используются с парсерами рекурсивного спуска.

  1. грамматика не может иметь никаких левых рекурсивных произведений
  2. Грамматика не должна требовать больше, чем на токене.

Я понимаю первое, но немного заблудился во втором ограничении. Почему это ограничение необходимо и может ли вообще существовать производство без него?

Источник

1 ответ

Решение

Второе ограничение можно несколько ослабить, потребовав, чтобы парсер мог решить, какую продукцию использовать, основываясь на первом k токены (в отличие от основанных на одном токене). Это позволяет использовать эффективные (т. Е. Линейные по времени) алгоритмы синтаксического анализа для этого класса грамматик (см. Анализатор рекурсивного спуска).

Основная причина выбора k=1 на практике кажется, что парсеры для LL(1) грамматики легче построить. Очевидно, что многие компьютерные языки предназначены для LL(1) грамматика. Смотри LL parser.

Грамматика состоит из произведений S -> A | B, A -> a A b | eps, а также B -> a B b b | eps является примером не однозначногоLL(1) грамматика, потому что синтаксический анализатор не может решить, какую продукцию использовать на основе одного токена. (Взято отсюда.)

Источник
Другие вопросы по тегам