Главная Промышленная автоматика.


Определение. Пусть G = (N, 2, Р, S) - приведенная КС-грамматика без £?-правил. Назовем G грамматикой {р, q; т, пусме-тайной стратегии предилествования (ССП), если выполняются такие условия:

(1) Отношение {/?, (7)-предшествовання •> не пересекается с объединением отношений (р, <7)-предшествования <• и

(2) Если А-*-оф и В-р - разные правила из Р, то утверждения

(а) Жт,п{А) содержит {у, ар, х),

(б) 3т,п{В) содержит (б. р, X),

(в) б состоит из последних т символов цепочки уа

не могут быть верными одновременно.

SABCDEab(i\il

<•

<•

<-

<•

<•

<-

<

<•

<•

•>

•>

>

•>

<-

<•

Рис. 5.19. Отиошеиия предшествования для грамматики G.

(1,1; 1,0)-ССП-грамматику будем называть/г/7ос/?шй ССП-г/?аж-матикой. Грамматика из примера 5.44 - простая ССП-грамма-тика. На самом деле каждая обратимая грамматика слабого предшествования является простой ССП-грамматнкой.

Пусть l{A) = {X\X<iA или ХА}. Для простой ССП-грам-матики приведенное выше условие (2) сводится к следующему:

(2а) Если ЛРХр и содержатся в Р, то Х1{В).

(26) Если Лр и 5-р содержатся в Р и АфВ, то / (Л) и / {В) не пересекаются.



матика и $-новый символ. Зададим отношения операторного предшествования на множестве 2и{$}:

(1) аЛ.Ь, если АаауЬ.Р и yNuH.

(2) a<ib, если А-ааВР и 5=>+уЬб, где yNuH,

(3) a*>b, если А-аВЬеР и В бау, где y€Nu{4,

(4) если Sz=yaa и у€и{},

(5) п>$, если 5=+аау и y6Nu{4-

Операторная грамматика G называется грамматикой операторного предшествования, если между любыми двумя терл-гиналь-ными символами выполняется не более одного отношения операторного предшествования.

Пример 5.45. Грамматика Go- классический пример грамматики операторного предшествования

(1) Е-Е + Т (2) £ -Г (3) ТТЕ (4) T-F (5) F{E) (6) Fa

Отношения операторного предшествования для этой грамматики приведены на рис. 5.20. □

Для грамматики операторного предшествования можно эффективно находить „остовные" разборы. Идея синтаксического ана-

•>

->

>

>

>

•>

•>

•>

<•

<•

•>

>

>

v>

<•

<•

<•

•>

•>

<

<•

<

<•

<-

<

<•

<

<

Рис. 5.20. Отношении операторного предшествования для грамматики Gq,

лиза та же, что и для грамматик простого нредшествовапия. Легко убедиться в справедливости следующей теоремы.

Теорема 5.25. Пусть G=(N, S, Р, S) -операторная грамматика и S%=f>*aAw=rP- Тогда

(1) отношение операторного предшествования <• или выполняется между последовательными терминалами (и символом ) цепочки а;

Условия (1) и (2а) - это условия слабого предшествования. Таким образом, на простую ССП-грамматику можно смотреть как па (возможно, не обратимую) грамматику, в которой одного символа левого контекста достаточно, чтобы сделать правильный выбор из правил с одинаковыми правыми частями (условие (26)). В этом и заключается смешанная стратегия разбора, использующая предшествование, для ССП-грамматик.

Алгоритм 5.18. Построение алгоритма разбора для ССП-грамматик,

Вход, (р, д\ т, /г)-ССП-грамматика G = (N, 2, Р, S) с занумерованными правилами.

Выход. Алгоритм Л = {[, g) типа „перенос-свертка" для грамматики G.

Метод.

(1) Пусть \а\ = р и \x\q. Тогда

(а) f [а, х) перенос, если а<х или ах,

(б) / (а, х) -свертка, если а»>х.

(2) /($5, $«)-допуск.

(3) / (у, w) ошибка, в остальных случаях.

(4) Пусть с,д, „ () содержит (а, р, х) и Л-р - правило с номером (. Тогда g(ap, x)-i.

(5) g{y, ш) ошибка в остальных случаях. □

Теорема 5.24. Алгоритм 5.18 строит алгоритм A-{f, g), корректный для грамматики G.

Доказательство. Упражнение. Достаточно доказать, что каждая ССП-грамматика является ОПК-грамматикой, а затем показать, что функции / и g, определяемые алгоритмом 5.18, согласуются с функциями, определяемыми алгоритмом 5.17. □

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

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

Определение. Операторной грамматикой называется приведенная КС-грамматика без t-правил, в которой правые части правил не содержат смежных нетерминалов.

Для операторной грамматики отношения предшествования можно задать на множестве терминалов плюс символ $, игнорируя нетерминалы. Пусть G= (N, 2, Р, S)-операторная грам-



Е-Е-Е-

Е + Е ЕЕ

а

(1) (3) (5) (6)

полученной из G заменой всех нетерминалов символом Е и устранением всех цепных правил. {Заметим, что в операторной грамматике правилом, не содержащим терминалов в правой части, может быть только цепное правило.)

Грамматика G, очевидно," не однозначная, но отношения операторного предшествования гарантируют единственность искомого разбора. Алгоритм разбора Л для грамматики G задается определяемыми ниже функциями f и g. Цепочки, которые служат аргументами этих функций, будут состоять только из тер-

миналов грамматики Go и символов % н Е. Далее, у обозначает Е или пустую цепочку, b и с-терминалы или $.

С перенос, если b<ic пли b с, J свертка, если Ь •> с, (О f{by> допуск, если Ь = $, у-- и с = $,

\ ошибка в остальных случаях.

(2) g{bya, х) =6, если Ь<(3,

g{bEE, х) -3, если g{bE + E, х)-1, если + . g(by{E), х) --5, если &<•(, g{a, х) =ошибка в остальных случаях.

Таким образом, для входной цепочки {а-{-а)а алгоритм Л сделает такую последовательность шагов:

[$, {а + а)*а$, а + а)*а$, е]

+а)а$, е] \-[{Е, +й)*а$, 6] Н[${Я + , а)«а$, 6] \-%{Е + а, )*а$, 6]

h-[$( + 66]

h[$(£, )«а$, 661] h[$(£), 661]

--S. 6615] 6615]

h[S*«. 6615] \-r[EE, $, 66156] [-[$E, 661563] [- допуск

Можно убедиться в том, что 661563-действительно остовный правый разбор цепочки {а\-а)а в грамматике G. Этот остовный разбор цепочки (а-\-а)а можно представить в виде дерева на рис. 5.21. □

Заметим, что можно было бы дополнить дерево остовного разбора на рис. 5.21 так, чтобы получилось соответствующее дерево в грамматике G. Но на практике в этом часто нет необходимости. Цель построения дерева -трансляция, а естественный перевод нетерминала Е, Т или F грамматики Gq -это программа машины, вычисляющая выводимое из него выражение. Поэтому если применяется правило Е -Т или Т-F, то перевод правой части будет скорее всего тот же, что и левой части.

(2) отношение <• выполняется между самым правым терминалом цепочки а и самым левым терминалом цепочки р;

(3) отношение выполняется между последовательными терминалами цепочки р;

(4) отношение •> выполняется между самым правым терминалом цепочки р и первым символом цепочки w.

Доказательство. Упражнение. □

Следствие. Если G-грамматика операторного предшествования, то к каждому из утверждений (1) -(4) теоремы 5.25 можно добавить слова „w никакие другие отношения не выполняются".

Доказательство. Вытекает непосредственно нз определения грамматики операторного предшествования. □

Итак, с помощью алгоритма разбора типа „перенос - свертка" легко выделить терминальные символы, входящие в основу. Однако возникают проблемы в связи с нетерминальными символами, поскольку на них не определены отношения операторного предшествования. Тем не менее тот факт, что мы располагаем операторной грамматикой, позволяет строить „остовный" правый разбор.

Пример 5.46. Разберем цепочку (д + а) *л в соответствии с отношениями операторного предшествования для грамматики Go, приведенными на рис. 5.20. Мы не будем заботиться о нетерминалах, а просто заменим каждый нз ннх символом Е. Тогда нам не надо беспокоиться о том, свернуть ли F к Т или Т к F {хотя в данном случае с такими проблемами можно было бы справиться, выйдя за пределы метода операторного предшествования). Можно эффективно сделать разбор в соответствии с грамматикой G с правилами





0 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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 [81] 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0021