ОПЕРАТОРНАЯ ГРАММАТИКА ПРЕДШЕСТВОВАНИЯ

Алгоритм разбора Вирта–Вебера и отношения простого предшествования, лежащие в его основе, просты для понимания, безупречны и эффективны с теоретической точки и поэтому именно с них мы начали обсуждение детерминированных алгоритмов восходящего разбора. Но в практике построения компиляторов они не нашли широкого применения из–за причин, рассмотренных в разделе 5.2.3.

Во многих компиляторах, особенно при анализе и трансляции арифметических выражений, используется простой в реализации и эффективный метод операторного предшествования, идея которого была формализована Флойдом еще в 1963 году. Собственно Р. Флойду и принадлежит первая трактовка отношений предшествования и функций предшествования, хотя методы, основанные на этих идеях, интуитивно использовались уже в самых ранних компиляторах.

Операторной грамматикой называется КС–грамматика без аннулирующих правил, в которой правые части правил не содержат смежных нетерминалов. Иными словами в операторных грамматиках запрещены правила вида V ® aUWb, где U, W Î N.

Для операторных грамматик можно задать отношения предшествования только для терминальных символов, игнорируя нетерминалы, хотя в остальном сами отношения операторного предшествования и пути их определения ничем не отличаются от отношений простого предшествования (см. раздел 5.2).

Введем вначале понятие множества самых левых (L) и самых правых (R) терминалов для нетерминала U:

L(U) = {x | x Î S & ($ (U ® xj) or $ (U ® U₁xj) or ($ (U ® U₂j) & (x Î L(U₂)))},

где здесь и далее U, U₁, U₂ Î N (нетерминалы), а j, y Î (N È S)^* (любые цепочки из терминалов и нетерминалов, возможно пустые).

R(U) = {x | x Î S & ($ (U ® jx) or $ (U ® jxU₁) or ($ (U ® jU₂) & (x Î R(U₂)))}

Определим теперь отношения предшествования для терминалов грамматики x и y:

x y, если $ (U ® jxU₁y) & (y Î L(U₁);

x y, если $ (U ® jU₁yy) & (x Î R(U₁);

x y, если $ (U ® jxyy) or $ (U ® jxU₁yy).

Пример 5.16. Рассмотрим упрощенную грамматику все тех же арифметических выражений:

E ® E+T½T

T ® T*M½M

M ® (E)½i

Множества самых левых и самых правых терминальных символов для нетерминалов этой грамматики представлены на рис. 5.19 а, а матрица операторного предшествования на рис. 5.19 б.



Для нахождения основ, состоящих из одного нетерминала, отношения операторного предшествования неприменимы, – для нетерминалов их просто не существует. Если рассмотреть, например, сентенциальную форму M+M из арифметической грамматики примера 5.16, то основой здесь является М, а отношения есть только такие: # + и + # (как и в разделе 3.4 мы предполагаем, что сентенциальная форма заключена между ограничителями # и что # x и x # для всех терминалов x). На каждом шаге разбора при использовании операторного предшествования распознается и редуцируется не основа, а так называемая самая левая первичная фраза.

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

Общий вид сентенциальной формы, выводимой в операторной грамматике и заключенный между ограничителями, выглядит следующим образом:

# N₁T₁N₂T₂... N_nT_nN_n+1 #

где N_i – нетерминалы, которые могут и отсутствовать, а T_i – терминальные символы. Иначе говоря, сентенциальная форма состоит их n терминалов, причем между каждыми двумя соседними терминалами находится не более чем один нетерминал.

Самой левой первичной фразой сентенциальной формы в операторных грамматиках предшествования является такая самая левая подцепочка N_jT_j... N_iT_iN_i+1, что

T_j–1 T_j , T_j T_j+1, T_i–1 T_i, T_i T_i+1.

Это определение очень похоже на соответствующее определение для простого предшествования. Основное различие состоит в том, что здесь из отношений исключены нетерминальные символы. Тем не менее, нетерминалы, находящиеся слева от T_j и справа от T_i, а также все нетерминалы лежащие между ними всегда принадлежат первичной фразе.

Пример 5.17. Для иллюстрации этого определения проведем разбор цепочки i*(i+i), используя матрицу предшествования с рис. 5.19 б. На рис. 5.20 а представлено дерево разбора для этой цепочки, а в таблице на рис. 5.20 б показаны символы, к которым приводятся первичные фразы. 

Как видно из рис. 5.20 б, основываясь на интуиции, первое i мы свернули к T, а второе i – к E, хотя единственное, что очевидно из отношений и грамматики – это свертка от i к M. Заметим, что при поиске самой левой первичной фразы, которую нужно редуцировать, нетерминальные символы вообще не принимаются во внимание.

# i * (i + i) # # E * (i + i) # # E * (E + i) # # E * (E + E) # # E * (E) # # E * E # # E #   Рис. 5.21

В компиляторах с каждым нетерминалом или операндом связана масса семантической информации: тип операнда, его адрес, признак принадлежности операнда к формальным параметрам и т.п. Семантические программы, которые выполняются при редукции первичных фраз, нуждаются только в семантической информации, связанной с нетерминальными символами, а не в самих символах. Например, для семантической подпрограммы связанной с редукцией фразы T*M, безразлично какая это фраза: T*M, M*T или M*M. Она использует только семантику нетерминалов. Да и само появление в грамматике арифметических выражений нетерминалов T и M не связано с какими либо семантическими целями; они позволили сделать грамматику однозначной и определить необходимое предшествование операторов. После того как это выполнено, в грамматике достаточно оставить один нетерминал с тем, чтобы максимально упростить редукцию. Так арифметическая грамматика, которую можно получить из грамматики, представленной в примере 5.16, если оставить в грамматике единственный нетерминал E, имеет вид:

E ® E+EôE*Eô(E)ôi

Рисунок 5.21 иллюстрирует свертку цепочки #i*(i+i)#, базирующуюся на полученной грамматике и отношениях операторного предшествования с рис. 5.19 б.

Конечно, семантические программы здесь могут стать более сложными, так как они должны будут проводить более подробную проверку операндов, чем в грамматиках простого предшествования. Но выигрыш здесь более существенен, так как распознаватель в целом становится значительно эффективнее. Отметим, что уменьшается объем памяти под матрицу предшествования, так как она содержит теперь отношения только для терминалов грамматики. Более того, распознаватель в явном виде не выполняет таких редукций, как E Þ T или T Þ M, поскольку T и M не первичные фразы и такого рода редукции не несут никакой семантической нагрузки.

Поиск по сайту: