КС-грамматика обладает свойством LL(k) для k>0, если на каждом шаге вывода для однозначного выбора очередной альтернативы автомату с магазинной памятью необходимо знать один верхний символ стека и рассмотреть k символов входной цепочки.
Иными словами, КС-грамматика обладает свойством LL(k) для k>0, если выбор правила в ходе левостороннего вывода однозначно определяется не более чем k символами входной цепочки, считываемой слева направо.
Существуют LL(1), LL(2), LL(3), … грамматики. Все они в совокупности образуют класс LL-грамматик. В этом обозначении (LL) первая L означает, что входная цепочка считывается в направлении слева направо, а вторая L – что выполняется левосторонний разбор. Число k показывает, сколько входных символов нужно рассмотреть для однозначного выбора альтернативы.
Алгоритм разбора входных цепочек для LL(k)-грамматик называется k-предсказывающим алгоритмом.
Свойства LL(k)-грамматик.
- Всякая LL(k)-грамматика для любого k>0 является однозначной.
- Существует алгоритм проверки, является ли произвольная КС-грамматика LL(k)-грамматикой для строго определенного числа k.
- Всякая грамматика, допускающая разбор по методу рекурсивного спуска без возврата, является LL(1)-грамматикой. Обратное не справедливо.