Тема 15

Практическое занятие № 15

Тема: LR(k) – грамматика

План:

1. LR(k)-грамматик

2. Алгоритм разбора для LR(k) – грамматики

3. Грамматическое вхождение

4. Алгоритм разбора для цепочки

Рассмотрим наиболее широкий класс КС-грамматик, для которых можно построить детерминированный восходящий анализатор. Такие грамматики получили название LR(k)-грамматик (входная цепочка читается слева (Left) направо, выходом анализатора является правый (Right) разбор, k — число символов входной цепочки, на которое можно "заглянуть" вперед для выделения основы).

Наиболее наглядно LR(k)-грамматику можно определить в терминах деревьев вывода. Грамматика G= (N, ∑, Р, S) является LR(k)-грамматикой, если, просмотрев только часть кроны дерева вывода в этой грамматике, расположенную слева от данной внутренней вершины, часть кроны, выведенную из нее, и следующие k символов входной цепочки, можно установить правило вывода, которое было применено к этой вершине при порождении входной цепочки.

Например, рассмотрев цепочку w и первые k символов цепочки w (рис. 8.2), можно определить, какое правило было применено к вершине А.

В определении LR(k)-грамматики используется множество FIRSTk(γ), состоящее из префиксов длины k терминальных цепочек, выводимых из γ. Если из γ выводятся терминальные цепочки, длина которых меньше k, то эти цепочки также включаются в множество FIRSTk(γ). Формально:

Очевидно, что определение множества FIRST(γ), приведенное при определении LL(k)-грамматики в гл. 7, полностью согласуется с данным определением.

Введем еще одно понятие, которое понадобится для определения LR(k)- грамматики.

Если правила грамматики G' пронумерованы числами 1, 2, ... ,р, то будем считать, что S’→S - нулевое правило грамматики G', а нумерация остальных правил такая же, как и в грамматике G. Начальное правило S’→S вводится для того, чтобы свертку, в которой используется это правило, можно было интерпретировать как признак того, что входная цепочка допустима.

Дадим теперь определение LR(k)-грамматики.

Это определение говорит о том, что если αβw и αβy - правовыводимые цепочки пополненной грамматики G', у которых FIRSTk(w)= FIRSTSk(y) и А→β - последнее правило, использованное в правом выводе цепочки αβw, то правило А→β должно использоваться также в правом разборе при свертке αβy к αAу.

Поскольку правило грамматики А→β не зависит от w, то из определения

LR(k)-грамматики следует, что во множестве FIRSTk(w) содержится информация, достаточная для определения основы.

Алгоритм разбора для LR(k) – грамматики

Для любой LR(k)-грамматики G = (N, ∑, Р, S) можно построить детерминированный анализатор, который выдает правый разбор входной цепочки.

Анализатор состоит из магазина, входной ленты, выходной ленты и управляющего устройства (пара функций f и g) (рис. 8.3).

Магазинный алфавит Vp представляет собой множество специальных символов, соответствующих грамматическим вхождениям или их множествам. Грамматическое вхождение — это символы полного словаря грамматики, снабженные двумя индексами. Первый индекс задает номер i правила грамматики, в правую часть которого входит данный символ, а второй индекс j -номер позиции символа в этой правой части.

Тогда грамматическое вхождение А5,2 представляет собой нетерминал А из второй позиции правой части пятого правила вывода. Если символ входит в правую часть i-го правила только один раз, то второй индекс будем опускать. Например, А1 - это грамматическое вхождение нетерминала А в первое правило, а А5 - грамматическое вхождение нетерминала А в пятое правило.

Перед началом работы алгоритма магазин пуст (содержит маркер дна).

Управляющее устройство анализатора представляет собой таблицу строки которой отмечены символами Одна строка такой таблицы называется LR(k)-таблицей. Каждая LR(k)-таблица задает две функции: функцию действия f и функцию переходов g.

Функция действия f, аргументом которой служит цепочка принимает значения из множества {ДОПУСК, ОШИБКА, ПЕРЕНОС, (СВЕРТКА, i)}.

Рассмотрим алгоритм, управляющая таблица которого приведена в табл. 8.3. Работу алгоритма опишем в терминах конфигураций, представляющих собой тройки вида (αТ,ах,π), где αТ - цепочка магазинных символов (Т - верхний символ магазина), ах - необработанная часть входной цепочки, начинающаяся символом а (для k = 0 длина цепочки и равна 1), π - выход, построенный к настоящему моменту времени.

Рассмотрим последовательность тактов, которую выполнит LR(k)-алгоритм при анализе входной цепочки abcb.

Шаг 1. Начальная конфигурация алгоритма - (, abcb, ε) (в вершине магазина находится маркер дна магазина, а текущим входным символом является символ а).

Для строки управляющей таблицы, отмеченной символом , f(a) = ПЕРЕНОС и g(а) = а1, поэтому:

□ в магазин записывается символ а1 (грамматическое вхождение символа а в правую часть первого правила);

□ входная головка сдвигается на один символ вправо.

Алгоритм переходит в конфигурацию (а1,bcb,ε).

Шаг 2. Для строки таблицы, отмеченной символом а1,f(b) = ПЕРЕНОС, a g(b) = b3, следовательно, алгоритм перейдет в конфигурацию (а1b3c2,cb,ε).

Аналогично для магазинного символа b3, и текущего символа входной цепочки магазин перейдет в конфигурацию (а1b3c2,b,ε).

Шаг 3. Рассмотрим теперь строку управляющей таблицы помеченную грамматическим вхождением c2. В этом случае f(b) = (с, 2), значит, необходимо выполнить свертку с использованием правила (2) S→с.

Правая часть этого правила содержит только один символ, поэтому:

□ удаляем из магазина символ c2

□ определяем значение функции переходов для символа S из левой части правила (2) в строке управляющей таблицы отмеченной символом b3, который стал верхним символом магазина. Значение функции переходов g(S)=S3.

Алгоритм переходит в конфигурацию (а1b3S3,b,2), и в выходную цепочку записывается число 2 (номер использованного правила).

Поступая дальше подобным образом, получим следующую последовательность тактов работы анализатора:

Заметим, что конфигурация (S0,,231) является заключительной, а цепочка 231 – правым разбором цепочки abcb.

Приведем последовательность тактов, которую выполнит алгоритм при анализе входной цепочки aabc, содержащей синтаксическую ошибку.

f(ε)=ОШИБКА. Алгоритм должен выдать сообщение об ошибке и закончить работу.

Продемонстрировав работу LR(k)-анализатора для конкретных входных цепочек, рассмотрим построение управляющей таблицы LR(k) -анализатора для k = 0 и некоторого подмножества LR(1)-грамматик. Это связано с тем, что алгоритм проверки принадлежности грамматики классу LR(k)-грамматик для произвольного k предполагает построение большого числа вспомогательных множеств, поэтому его использование в случаях k > 1 для решения практических задач не оправдано.