Я знаю, что есть два типа ограничений на грамматики, которые используются с парсерами рекурсивного спуска.
Я понимаю первое, но немного теряюсь во втором ограничении. Зачем нужно это ограничение и может ли производство вообще существовать без него?
Второе ограничение можно несколько ослабить, потребовав, чтобы синтаксический анализатор мог решать, какую продукцию использовать на основе первых токенов k (а не на основе одного токена). Это позволяет использовать эффективные (то есть линейные по времени) алгоритмы синтаксического анализа для этого класса грамматик (см. Синтаксический анализатор рекурсивного спуска).
Основная причина выбора k=1 на практике заключается в том, что синтаксические анализаторы для LL(1) грамматик легче построить. По-видимому, многие компьютерные языки предназначены для генерации с помощью LL(1) грамматики. См. парсер LL.
Грамматика, состоящая из продукций S -> A | B, A -> a A b | eps и B -> a B b b | eps, является примером недвусмысленной грамматики, отличной от LL(1), поскольку синтаксический анализатор не может решить, какую продукцию использовать на основе одного токена. (Взято из здесь.)
S -> A | B, A -> a A b | eps и B -> a B b b | eps, является примером недвусмысленной грамматики, отличной от LL(1), поскольку синтаксический анализатор не может решить, какую продукцию использовать на основе одного токена. (Взято из здесь.)
- person blazs; 24.03.2016
