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

Пример 5.38. Рассмотрим грамматику G с правилами 5 05111011

В примере 5.36 мы видели, что G пе грамматика простого предшествования, потому что 1 = 1 и 1 •> 1. Однако, если в каждое правило вместо первой единицы поставить новый нетерминал А

<•

<

<

->

<•

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

И добавить правило Л-j-1, то получится грамматика простого предшествования G с правилами

5~05Л10Л1 Л->1

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

Аналогичными преобразованиями можно устранять конфликты вида Х<*У, Х}>У (а также вида X<»F, Х = У, если желательно простое предшествование).

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

Пример 5.39. Рассмотрим грамматику G с правилами Е~Е + Т\Т T~T»F\F Fa\{F)\a{L) LL, Е\Е

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

G не является грамматикой слабого предшествования, так как Е ±S) ц. £"•>). Можно было бы устранить этот конфликт, заменив Е в правиле Я~н-{£) на Е и добавив правило Е-Е-

Таким образом, для каждой обратимой грамматики слабого предшествования можно построить алгоритм разбора типа „перенос - свертка".

Алгоритм 5.14. Построение алгоритма разбора типа „перенос-свертка" для грамматик слабого предшествования.

Вход. Обратимая грамматика слабого предшествования G = (N, S, Я, S), правила которой занумерованы числами от 1 до р.

Выход. d - (f,g), алгоритм разбора типа „перенос-свертка" для грамматики G.

Метод. Построение аналогично тому, которое было в алгоритме 5.12. Функция переноса / определяется прямо по отношениям предшествования:

(1) /(X, й)перенос, если Х<а или Ха,

(2) /(X, а)свертка, если Х}>а,

(3) /($5, $) = допуск,

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

Функция свертки g определяется так, чтобы при свертке применялось самое длинное из применимых правил:

(4) g-(Xp) -г, если fip -правило из Я с номером i и в Я пет правила вида А-*-аХр,

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

Теорема 5.18. Алгоритм 5.14 строит корректный алгоритм разбора типа „перенос-свертка" для грамматики G.

Доказательство. Теорема непосредственно следует нз лемм 5,4 и 5.5, определения обратимой грамматики слабого предшествования и конструкции самого алгоритма Л. □

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

Допустим, что в грамматике есть конфликт вида X.У X •> У. Так как ХУ, то в правой части одного или нескольких правил встречается подцепочка ХУ. Если в таком правиле заменить X новым нетерминалом А, то ХК исчезнет и тем самым конфликт будет устранен. Чтобы сохранить эквивалентность, добавим к грамматике правило Л -> X. Если X не является правой частью другого правила, то сохранится и обратимость грамматики.



Покажем, что отношения <•, JL и •> для грамматики G попарно не пересекаются. Концевой маркер не может вызвать конфликта, поэтому рассмотрим X и У из NU2. Заметим, что

(1) если X<F, то X€Nu2:;

(2) если ХУ, то X С N U 2 и У -N, так как только пункт (26) построения грамматики G дает правила, у которых правая часть содержит больше одного символа;

(3) если Х}>У, то X6NU2 и KS.

Докажем, что пересечение каждой пары отношений пусто.

Первая пара: п-> = 0. Если XJLF, то KN - N. Если Х), то Ясно, что П5>-0.

Вторая пара: <»П*>0. Допустим, что X<У и Х«>/. Тогда XENu2 и Уk- Так как Х</ в грамматике G, то в Р есть правило вида [Xkj]- X [aj], причем [aJ=gKa2 для некоторой цепочки a3£(Nu2)*. Но цепочка Хсс должна быть суффиксом некоторого правила Л--адХа из Р. Тогда адУа для некоторой цепочки «а G (N U 2)*. Таким образом, для G имеем XJ=y или Х<У.

Рассмотрим теперь Х->У для грамматики G. В Р должно

быть такое правило [SPi] -В [р], что В=сХ и [Pi]=»gKp3 для некоторых P2G(N!j2)* и рз€(и2)*. В грамматике G цепочка Bpi является суффиксом некоторого правила С-*-yBpi из Р. Кроме того, BqX и р1=с;5рз для некоторой цепочки P3€(Nu2)*. Таким образом, Х«>/ для грамматики G.

Мы показали, что если X<У и Х->У для G, то для G либо X <• F и X •> F, либо X У и Х->/. В любом случае получается противоречие с предположением о том, что G - грамматика слабого предшествования. Таким образом, < П 5> - 0 для грамматики G.

Третья пара. <• П = = 0 Предположим, что X < [Ксс] и Х[Уа\ для некоторых XeNu2 и [Уа] -N. Тогда в есть такие правила [ХЛр]-Х[Лр] и В~[Уа], что [Лр]=>5 Вур=с[Ка]уР для некоторых y€(Nu2)* и Л, В € N. Отсюда следует, что в Р есть такие правила С-бХЛр и В-»-Ка, что Л=фдВу для некоторой цепочки y(Nu2)*. Таким образом, Для G получается X <J В или X = В. (Последнее может произойти тогда и только тогда, когда В = Л.)

Теперь рассмотрим Х[Уа]. В Р есть правило [ХУа]- Х[Уа], и потому в Р есть правило D-еХУа.

Следовательно, если X <• [Уа] и X [Уа] для грамматики G, то в Р найдутся два правила вида В-Уа и В-гХУа. и для С будет Х<В или X В, что нарушает условие (2) определения грамматики слабого предшествования.

Но тогда оказалось бы два правила с правой частью. Если же устранить из G правило F-a{L), сделав подстановку вместо L, как в лемме 2.14, то получится эквивалентная грамматика G с правилами

F-a\(E)\a(L, Е)\а(Е) Е-Е, Е\Е

Так как L больше не встречается слева от ), то в этой грамматике уже нет £ •>). Легко проверить, что G- грамматика слабого предшествования. □

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

Теорема 5.19. Язык определяется обратимой грамматикой слабого предшествования тогда и только тогда, когда он является языком простого предшествования.

Доказательство. Достаточность. Пусть G (N, 2, грамматика простого предшествования. Очевидно, что условие (1) определения грамматики слабого предигествования удовлетворяется. Допустим, что условие (2) нарушено, т. е. в Я есть такие правила А ~аХУ и В Кр, что либо X <• В, либо X В. Тогда по лемме 5.3 Х<»У. Но Xиз-за правила Л-аХКр. Такая ситуация невозможна, поскольку G - грамматика предшествования.

Необходимость. Пусть G = (N, S, Р, S) - обратимая грамматика слабого предшествования. Построим грамматику простого предшествования G=(Н, S, Р\ 5), для которой L(G)L{G)-

(1) Пусть N - это N плюс новые символы вида [а], где цепочка афе такова, что в Р есть правило вида Л-рсс.

(2) Пусть Р состоит из правил

(а) [X]->Х для каждого [X] £ N, для которого X G 2,

(б) [Xa]~>X[aJ для каждого [XaGN, Для которого X GNU2 и афе,

(в) Л-*-[а] для каждого Л-из Р,



Шаг (1) Применяется к парам Х=={, У - Е и У = Т.

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

. 5.16.

□ f

->

>

>

>

>

•>

•>

>

->

•>

->

>

->

•>

->

•>

>

>

>

->

->

<•

<

<

<•

<•

<

<

<

<

<

<•

<•

<

<-

<•

<•

<•

<•

<

Рис. 5.16. Матрица простого предшестиования.

УПРАЖНЕНИЯ

5.3.1. Какие нз следующих грамматик являются грамматиками простого предшествования?

(а) G,

(б) 5если Е, то S иначе S\a Е -1-Е или b I Ь

(в) SAS\A A{S)\{)

(г) SSA\A A-{S)\{)

5.3.2. Какие из грамматик упр. 5.3.1 являются грамматиками слабого предшествования?

5.3.3. Какие из грамматик упр. 5.3.1 являются грамматиками (2,1)-предшествования?

5.3.4. Приведите примеры грамматнк предшествования, для которых

477

Вид Правил множества Р позволяет сразу заключить, что Грамматика С обратима, если обратима G. Следовательно, L{G)- язык простого предшествования. Легко доказать, что/. (G) = L {G). Мы оставляем это в качестве упражнения. □

Следствие. Каждая обратимая грамматика слабого предшествования однозначна.

Доказательство. Если бы у какой-нибудь цепочки оказалось два разных правых вывода в грамматике G теоремы 5.19, то можно было бы построить разные правые выводы той же цепочки в грамматике G. □

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

Алгоритм 5.15. Переход от обратимого слабого предшествования к простому предшествованию.

Вход. Обратимая грамматика слабого предшествования G = (N, 2, Р, S).

Выход. Грамматика простого предшествования О , для которой L(G)L(G). Метод.

(1) Допустим, что в Nu2 нашлись такие X и Y, что X

и Х<»Кдля грамматики G. Устраним из Р каждое правило вида А-аХУР и заменим его па ЛаХ[Кр], где [Ур]-новый нетерминал.

(2) Для каждого символа [Ур], введенного на шаге (1), заменим правило вида б->Ур на й[Гр] и добавим [Кр]>Р-

(3) Повторим шаг (1) столько раз, сколько он окажется применимым. Если он больше неприменим, остановимся. Результатом будет грамматика G. □

Пример 5.40. Пусть G-грамматика нз примера 5.37. С помощью алгоритма 5.15 получаем грамматику G с правилами

ЕЕ + [Т]\ + [Т]\[Т]

TTF\F

F-{[E)]\a

[Е)]Е)

.476





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.0044