5.3. Операторная грамматика предшествования

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

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

Операторной грамматикой называется КС–грамматика без аннулирующих правил, в которой правые части правил не содержат смежных нетерминалов. Иными словами в операторных грамматиках запрещены правила вида V  UW, где U, W  .

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

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

L(U) = {x | x    ( (U  x) or  (U  U₁x) or ( (U  U₂)  (x  L(U₂)))},

где здесь и далее U, U₁, U₂   (нетерминалы) , а ,   (  )^ (любые цепочки из терминалов и нетерминалов, возможно пустые).

R(U) = {x | x    ( (U  x) or  (U  xU₁) or ( (U  U₂)  (x  R(U₂)))}

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

xy, если  U  xU₁)  (y  L(U₁) ;

xy, если  (U  U₁y)  (x  R(U₁) ;

xy, если  U  xy or  U  xU₁y.

Пример 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–1T_j , T_jT_j+1 , T_i–1T_i , T_iT_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 не первичные фразы и такого рода редукции не несут никакой семантической нагрузки.

Упражнения.

5.1. Построить отношения простого предшествования для грамматики с правилами S  aSbcd.

5.2. Построить отношения простого предшествования и функцию предшествования, используя граф линеаризации, для грамматики с правилами S  aSSbcd. Покажите этапы свертки фраз aacdbcb , ab , acb.

	1	2	3	4
1				
2			
3			
4

5.3. Постройте функцию предшествования, используя два известных метода для следующей матрицы:

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

E  E or TT

T  T and MM

M  a(E) not M

5.5. Постройте отношения простого предшествования для грамматики с правилами S  0S11011 и терминалами { 0, 1 }. Если данная грамматика не является грамматикой простого предшествования, то преобразуйте ее к такой грамматике.

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

5.7. Преобразуйте грамматику

S  E

E  TTBE(E)

T abz

B  

к грамматике простого предшествования. Покажите этапы свертки фразы a(b+c).

Упражнения на программирование.

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

5.9. Реализовать программу, которая по заданной грамматике строит отношения простого предшествования. Если грамматика не является грамматикой простого предшествования, то программа должна пытаться привести ее к такому виду. Визуализировать поэтапное построение отношений предшествования и работу алгоритма стратификации.

5.10. Реализовать программу, которая определяет, является ли заданная грамматика операторной, строит отношения операторного предшествования, функцию предшествования и реализует алгоритм синтаксического анализа с использованием этих отношений и функции. Визуализировать процесс построения отношений, функции и работу алгоритма разбора.