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

ГЛ, 5. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ

она имеет в ау корректные правый и левый контексты, то получающаяся после свертки цепочка аАу будет правовыводимой.

ОПК-грамматики связаны с некоторыми из исследованных в этой главе классов грамматик. Как уже упоминалось, они образуют подмножество LR-грамматик. Кроме того, это грамматики расширенного предшествования, и каждая обратимая грамматика [т, я)-предшествования является ОПК-грамматикой. Класс (1,1)-0ПК-грамматик содержит все обратимые грамматики слабого предшествования. Докажем сначала последнее утверждение.

Теорема 5.20. Если (N, 2, Р, 8)обратимая грамматика слабого предшествования, то она является ( \ ,\)-ОПК-грамматикой.

Доказательство. Допустим, что (1, 1)-ОПК"условие нарушается, т. е. существуют два вывода

$5$ уВх =>г убх - ау

в которых а и а оканчиваются одним и тем же символом, w и i/начинаются одним и тем же символом и л:г/, но уВхФ аАу. Так как (? -грамматика слабого предшествования, то, применяя теорему 5.14 к цепочке убх, находим, что отношение •> впервые встречается между б и х. Применяя эту теорему к aw, находим •> между р и w, а так как w и у начинаются одним и тем же символом, то •> оказывается между р и у. Поэтому аР>уб. Так как дано, что \х\\у\, то должно быть ссруб и х = у.

Если мы сможем показать, что рб, то этим докажем, что сс==у. Но из обратимости следует, что А=В, и, значит, мы получим противоречие с предположением, что уВхфаАу.

Если рзтб, то одна из этих цепочек должна быть суффиксом другой. Чтобы показать, что Р=б, исследуем отдельно каждый из возможных случаев.

Случай /; Р=еХ6 для некоторых е и X. Так как X -последний символ цепочки у, то, применяя теорему 5.14 к правовыводимой цепочке уВх, имеем X <• В или ХВ. Это нарушает условие слабого предшествования.

Случай 2: б = еХр для некоторых е и X. Этот случай симметричен только что рассмотренному.

Итак, Р-б и (?- (1,1)-0ПК-грамматика. □

Теорема 5.21. Каждая (т, куОПК-грамматика является LR(fe)-грамматикой.

Доказательство. Пусть -(N, S, Р, 5) является (m, ОПК-грамматикой, но ие LR()-rpaMMaTHKOH. Тогда по лемме 5.2

S.4. ДРУГИЕ КЛАССЫ ГРАММАТИК

В пополненной грамматике G существуют выводы

5 аЛй? арш

5 уВх =». убх сфу

где уб1ар и FIRST-FIRSTH, но уВхфаАу. Если окружить все цепочки символами $ и положить а= а, то (т,/г)-ОПК-условие будет нарушено. □

Следствие. Каждая ОПК-грамматика однозначна. □

Теперь перейдем к построению алгоритма разбора типа „перенос-свертка" для ОПК-грамматик и обсудим эффективную реализацию этого алгоритма. Допустим, что алгоритм указанного типа используется для анализа ОПК-грамматики О и что он находится Б конфигурации (а, w, л). Тогда можно задать множества и Ж, которые скажут нам, появилась ли основа право-выводимой цепочки aw наверху магазина (т. е. образует ли она суффикс цепочки а) или же правый конец основы расположен где-то в W (и тогда надо делать перенос). Если основа в магазине, то эти множества скажут, какова она и какое правило применить для ее свертки.

Определение. Пусть G = (N, 2, />, 5)-ОПК-грамматика. Для AN определим m.nW как множество таких троек (а, р, х), что ат, x=n и в пополненной грамматике есть вывод

уаАху =>г уаху

Множество tMm.n пусть состоит из таких пар (а, х), что

(1) либо а = т + /, где /-длина самой длинной правой части правил из Р, либо а<т + / и а начинается с $";

(2) \х\-п;

(3) существует вывод Pi/ =?>л Pvi/. где ах-подцепочка цепочки руу, расположенная так, что а лежит внутри цепочки ру и не содержит ее последнего символа.

В очевидных случаях мы будем опускать индексы G, т к п в обозначениях Ж (А) и сДГ.

Идея состоит в том, что появление подцепочки арх в ходе просмотра слева направо правовыводимой цепочки должно указывать, что р-основа и ее надо свернуть к Л, если (а, р, х)Ж(А). Появление такой цепочки ах, что (а, x),Jf, указывает па то, что основа еще не получена, по, возможно, расположена справа от а. Лемма 5.6 подтверждает, что так оно и есть.

Лемма 5.6. Грамматика G - {N, 2, Р, S) является (т, я)-ОПК-грамматикой тогда и только тогда, когда выполняются следующие условия:



(3) Пусть off содержит каждую пару {а, х), для которой в < найдется цепочка уВу, в Р - правило В-> б, ссх-подцепочка цепочки убу, а внутри цепочки уб, за исключением ее последнего символа. Требуется также, чтобы \х\п и а=т + /, где / - самая длинная правая часть правила, либо а начинается с и а<т4-/. □

Теорема 5.22. Алгоритм 5,6 правильно вычисляет множества Ж (Л) и сГ-

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

Алгоритм 5.17. Построение алгоритма типа „перенос-свертка" для ОПК-грамматик.

Вход, ( г, Аг)-ОПК-грамматика G--(N, 2, Р, S), пополненная до G = (iV, 2, Р. 5).

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

Метод. Функции fag зададим так:

(1) / (а, перенос, если (а, tc) £ оЛд,

(2) / (а, ш) = свертка, если ааа и (а, а, w).9n(A) для некоторого Л, но ие верно, что Л~5, «1-$ и a=Sy

(3) f{"S, допуск,

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

(5) g{a, w)-i, если a-aag, (а, а, G(Л) и Ла- правило с номером t,

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

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

Доказательство. В силу леммы 5.6 при определении функций f VI g не возникает недоразумений. По определению множества (Л) всякий раз, когда делается свертка, свертываемая цепочка а. служит основой некоторой цепочки раашг. Если бы она оказалась основой какой-нибудь другой цепочки раашг, то нарушилось бы ОПК-условие. Единственный трудный момент - доказательство того, что выполняется условие (3) определения ОПК-грамматики: Нетрудно показать, что в качестве

выводов в ОПК-определении можно взять выводы цепочек (iaawz и paawz (в любом порядке), так что условие (3) выполняется. □

В алгоритме Л = {, g), построенном алгоритмом 5.17, функции fag зависят, очевидно, только от ограниченной части цепочек, которые могут быть их аргументами, хотя в различные моменты приходится рассматривать подцепочки различной длины. Приведем реализацию обеих функций f и g в виде дерева реше-

(1) Пусть А -j-p и в -»- б-разные правила. Тогда если (а. Р, л:)е.„(Л) и (у, б, х)„(В), то а -не суффикс цепочки уб, и обратно.

(2) Для всех Л G N из {а, р, л:) „ [А) следует, что {бар, л:) не содержится в Жт, п - какой цепочки 6.

Доказательство. Достаточность. Допустим, что G -не (т, /г)-ОПК-грамматика. Тогда в пополненной грамматике G найдутся выводы

=>; aAw =Фарш .$«5$" 1 уВх =Ф,убх= аРу

где а и а совпадают в последних т позициях, w и у совпадают в первых п позициях и л:г/, но уВхфаАу. Пусть е состоит [из последних т символов цепочки а, а 2 из первых п символов цепочки w. Тогда (е, р, z) [А). Если хф у и \ х\\у\, то должно быть (бкр, z)(M для некоторой цепочки 6, так что условие (2) нарушается. Если х = у, то {i, б, г).9{В), где \] состоит из последних т символов цепочкн у. Если А ->-ри5--»-б - это одно и то же правило, то при х= у мы вопреки предположению получаем уВх = аАу. Но так как одна из цепочек цЬ и 8р является суффиксом другой, то, если правила А -i-p и В-б различны, нарушается условие (1).

Необходимость. Если нарушается условие (1) нли (2), легко доказать, что нарушается (т, /г)-ОПК-условие. Эту часть доказательства оставляем в качестве упражнения. П

Теперь можно перейти к описанию алгоритма разбора типа „перенос - свертка" для ОПК-грамматик. Так как для этого нужно знать множества {А) и (М\ займемся сначала их вычислением.

А л г о р и т м 5.16. П о с тр ое н и е множеств ,„ (Л) и с1\Г,„,„.

Вход. Приведенная грамматика G={N, 2, Р, 5). Выход. Множества „ (Л) для Л6N и off,;,-Метод.

(1) Пусть / - длина самой длинной правой части правила. Вычислим множество таких цепочек у, что

(а) \у\= т-п-\-1 или \ у\ <т-\-п-\-1 и у начинается с",

(б) у - подцепочка цепочки apw, где af>w-правовыводимая цепочка с основой р и UFIRST„();

(в) у содержит хотя бы один нетерминал.

Здесь можно применить метод, подобный тому, что применялся в первой части алгоритма 5.13.

(2) Для ЛgN пусть Ж {А) содержит каждую тройку (а, р,-)t для которой в найдется цепочка уаАху, в Р - правило Л-р и а=т, =



Это (1,0)-ОПК-грамматика. Для вычисления множеств [А), Ж (5) и Ж нам нужно множество цепочек длины 3 или меньше, которые могут встречаться в активных префиксах правовыводимых цепочек и содержать нетерминал. Это множество состоит из цепочек $5, $5, $0Л, $15, ООЛ, 115, ЮЛ и их подцепочек. Теперь вычисляем

i.o(S){($, 5, г)\

-1,о(5) ={($. ОЛ. с), (S, 15, е), (1. ОЛ, е\ (1, 15, в)} ьоИ) -={(0, ОЛ, е), (О, 1, ё)\

Множество Ж состоит из пар (а, ё), где а-любая из цепочек $, $0, $00, ООО, $1, $11, $10, 111, 100 и 110. Функции / и g приведены на рис. 5.17. Под „окончанием цепочки а" подразумевается ее кратчайший суффикс, необходимый для определеппя значений / (а, ё) и g(a, е).

Реализация / и g в виде дерева решений приведена на рис. 5.18. Так как /г=0, то ветвление, соответствующее цепочкам длины п, отсутствует. Вершины с метками Л и 5, лежащие ниже уровня 1, опущены, так как все они, конечно, имеют выход ошибка. □

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

К сожалению, реализация алгоритма d={f,g), построенного алгоритмом 5.17, требует довольно больших затрат памяти для хранения функций f п g. Можно определить класс грамматик,

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

Окончание цепочки а

f (ос. e)

g (а, е)

свертка

«

свертка

свертка

свертка

свертка

свертка

перенос

перенос

перенос

перенос

перенос

перенос

перенос

перенос

допуск

Рис. 5.17. Функции переноса и свертки

Пример 5.44. Рассмотрим (необратимую) грамматику слабого предшествования G с правилами

5 ----

D-Е-

аА\ЬВ СЛ11С1 DBE\\DE\ О О 1

G порождает язык {аО«1"/г> 1 [ U {ЙОР" /г> который, как будет показано в гл. 8, не является языком простого предшествования. Отношения предшествования для грамматики G даны на рис. 5.19. Заметим, что G -необратимая грамматика, потому что О -правая часть двух правил: СО и D 0. Однако о (ОО- О, е)] и Ж,,ЛЩ-{{Ь, О, е), (D, О, )[.

Поэтому если О выделен в качестве основы правовыводимой цепочки, то символ, расположенный непосредственно слева от О, определяет, свернуть ли О к С или к D. А именно, первое из этих правил выбирается, если это символ а или С, а второе - если это b или D. □

Пример 5.44 подсказывает следующее определение.

НИИ. Сначала для данных цепочек-а в магазине и л; на входе - можно пойти по ветви, соответствующей первым п символам цепочки X. Потом для каждой такой цепочки из п символов можно начать просматривать а в обратном направлении, на каждом шаге решая, продолжать ли просмотр дальше или объявить об ошибке, переносе или свертке. Если объявлена свертка, то у нас достаточно информации, чтобы точно сказать, какое применить правило, так что в дерево решений можно включить и функцию g. Для принятия решений можно также использовать обобщенный алгоритм Домёлки (см. упражнения разд. 4.1).

Пример 5,43. Рассмотрим грамматику 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.0019