Принципы построения распознавателей для LL(k)-грамматик

Для построения распознавателей LL(k)-грамматик используются два важных мно­жества, определяемые следующим образом:

· FIRST(k,a) — множество терминальных цепочек, выводимых из aÎ(VTÈVN)^*, укороченных до k символов;

· FOLLOW(k,A) — множество укороченных до k символов терминальных це­почек, которые могут следовать непосредственно за AÎVN в цепочках вывода.

Формально эти два множества могут быть определены следующим образом:

FIRST(k, a) = {wÎVT^* | либо |w| £ k и a=>^*w, либо |w|>k и а=>^*wх, xÎ(VT ÈVN)^*}, aÎ(VTÈVN)^*, k>0.

FOLLOW(k,A) ={wÎVT^* | S=>^*aAg и wÎFIRST(g,k), aÎVT^*}, AÎVN, k>0.

Очевидно, что если имеется цепочка терминальных символов aÎVT^*, то FIRST(k,a) — это первые k символов цепочки a.

Доказано, что грамматика G(VT,VN,P,S) является LL(k)-грамматикой тогда и только тогда, когда выполняется следующее условие: " А->b Î Р и " А-> gÎ Р (b¹g): FIRST(k,bw) Ç FIRST(k, gw) = Æ для всех цепочек со таких, что S =>* aAw.

Иначе говоря, если существуют две цепочки вывода:

S =>* aAg => azg =>* aw

S =>* aAg => atg =>* au

то из условия FIRST(k,w) = FIRST(k,u) следует, что z = t.

На основе этих двух множеств строится алгоритм работы распознавателя для LL(k)-грамматик, который представляет собой k-предсказывающий алгоритм для МП-автомата, заданного так: R({q},VT,Z, d,q,S,{q}), где Z = VTÈVN, а S - целевой символ грамматики G. Функция переходов автомата строится на основе управ­ляющей таблицы М, которая отображает множество (ZÈ{l}) ´VT^*k на множест­во, состоящее из следующих элементов:

· пар вида (b, i), где b — цепочка символов, помещаемая автоматом на верхушку стека, а i — номер правила вида А->b, AÎVN, bÎZ^*;

· «выброс»;

· «допуск»;

· «ошибка».

Конфигурацию распознавателя можно отобразить в виде конфигурации МП-автомата с дополнением цепочки p, в которую помещаются номера применен­ных правил. Поскольку автомат имеет только одно состояние, его в конфигура­ции можно не указывать. Если считать, что Х — это символ на верхушке стека автомата, a— непрочитанная автоматом часть входной цепочки символов, а u= FIRST(k,a), то работу алгоритма распознавателя можно представить сле­дующим образом:

· (a, Хg, p) ¸(a, bg, pi), gÎZ^*, если M(X,u) = (b,i);

· (a, Хg, p) ¸(a’, g, p), если X = aÎ VT и a= aa’, M(a,u) = «выброс»;

· (l, l, p) — завершение работы, при этом М(l, l) = «допуск»;

· иначе — «ошибка».

Цепочка u = FIRST(k, a) носит в работе автомата название «аванцепочка».

Таким образом, для создания алгоритма распознавателя языка, заданного произ­вольной LL(k)-грамматикой, достаточно уметь построить управляющую табли­цу М. Управляющую таблицу М, а также множества FIRST и FOLLOW можно получить на основе правил исходной грамматики.

При k= 1 все существенно проще. Методы построения для LL(l)-грамматик, а также проверки принадлежности грамматики к классу LL(l)-грамматик рас­смотрены ниже.

Дата добавления: 2014-01-20