АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

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

Читайте также:
  1. Аспект «Грамматика»
  2. Грамматика
  3. Грамматика
  4. ГРАММАТИКА АНГЛИЙСКОГО ЯЗЫКА
  5. ГРАММАТИКА И ЕЕ ПРЕДМЕТ
  6. Грамматика Пор-Рояля
  7. Грамматика. Предмет морфологии.
  8. Русская грамматика. М., 1980. Т. 2. С. 79 – 82, 137 – 143
  9. Стихотворение А.С. Пушкина «На холмах Грузии лежит ночная мгла»: поэтика и грамматика
  10. Формальная грамматика и формальный язык
  11. Формальная грамматика_ словарь филолога

 

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

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

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

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

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

 

L(U) = {x | x Î S & ($ (U ® xj) or $ (U ® U1xj) or ($ (U ® U2j) & (x Î L(U2)))},

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

 

R(U) = {x | x Î S & ($ (U ® jx) or $ (U ® jxU1) or ($ (U ® jU2) & (x Î R(U2)))}

 

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

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

x y, если $ (U ® jU1yy) & (x Î R(U1);

x y, если $ (U ® jxyy) or $ (U ® jxU1yy).

Пример 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). На каждом шаге разбора при использовании операторного предшествования распознается и редуцируется не основа, а так называемая самая левая первичная фраза.

 

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

 

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

 

# N1T1N2T2... NnTnNn+1 #

 

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

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

Tj–1 Tj , Tj Tj+1, Ti–1 Ti, Ti Ti+1.

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

Пример 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 не первичные фразы и такого рода редукции не несут никакой семантической нагрузки.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 |

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



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)