Lr(k) – грамматики
Это наиболее
широкий класс КС-грамматик, допускающих
эффективный восходящий грамматический
разбор. ‘L’
– означает, что анализируемая цепочка
просматривается слева-направо, ‘R’
– означает, что восстанавливается
правый вывод цепочки, k
– указывает количество символов, которые
алгоритм просматривает вперёд для
принятия однозначного решения.
LR(k)
алгоритм считывая цепочку посимвольно
определяет самую левую сворачиваемую
подстроку, а также тот нетерминал левой
части, которым следует заменить эту
подстроку. LR(k)
учитывает при этом информацию о всей
просмотренной части цепочки.
LR(k)
алгоритм читает цепочки и выдаёт ответ:
какое правило определяет очередную
подцепочку после просмотра ровно k
символов после этой подцепочки. Другой
взгляд: LR(k)
алгоритм – это конечный автомат,
состояния которого – множества ситуаций.
Опр. Ситуация это
помеченное правило, метка указывает, в
каком месте продукции находится алгоритм
на данном шаге. Формально ситуация –
это
<A
; >,
что соответствует
правилу A,
а знак
- метка,
- правый контекст длиной k.
Так как правил
конечное количество, их помеченных
наборов тоже конечное количество,
контекстов длины
тоже конечное количество, то множеств
ситуаций тоже конечное количество.
