2015-07-14
643
Автоматическое построение анализаторов опирается на отношение предшествования.
Пусть имеется КС-грамматика G =(VA, VT, I, S).
Рассмотрим пару символов a 1, a 2Î VA È VT.
1) Будем считать, что для пары (a 1, a 2) в грамматике G выполняется отношение (a 1, a 2)=., если в S содержится правило вывода А Þ x 1 a 1 a 2 x 2.
|
В a 2 h.
3) Для пары (a 1, a 2) выполняется отношение (a 1, a 2).> если выполняется одно из следующих условий:
·
|
В ha 1;
·
|
|
В ha 1 C a 2 z.
В этих отношениях А, В, С – некоторые нетерминальные символы, x 1, x 2, h, z -цепочки из (VT È VА)*.
F Определение: КС-грамматика называется грамматикой предшествования, если для каждой пары символов выполнено не более одного отношения предшествования.
|
|
|
Для такой грамматики может быть построен детерминированный анализатор снизу-вверх.
LR(k)-анализатор
LR (k)-анализатор – устройство, состоящее из потенциально неограниченной вправо входной ленты и двух магазинов: верхнего и нижнего.
На входной ленте помещается еще не учтенная правая подцепочка анализируемой цепочки, к которой справа приписывается k маркеров. В верхнем магазине помещаются цепочки, состоящие из символов состояний, в нижнем – цепочки над объединением множеств нетерминальных и терминальных символов грамматики. Читая входную цепочку слева направо, анализатор пытается свернуть ее к начальному символу грамматики. В нижнем магазине находятся частично свернутые левые подцепочки входной цепочки, уже просмотренные анализатором. На каждом такте работы LR (k) – анализатор может выполнить одно из двух возможных действий: сдвиг или свертку. После выполнения определенного количества тактов анализатор допускает или отвергает анализируемую цепочку.
Число k анализатора определяет длину цепочки.
Глобальный анализатор
|
