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

учета всех затрат времени. Грамматика G предполагается фиксированной, так что обычные операции с ее правилами и символами можно считать элементарными. Как и в предыдущем разделе, вопрос о зависимости времени от „объема" грамматики оставляем в качестве упражнения.

Шаг (1) для /„ можно, очевидно, проделать за фиксированное число элементарных операций. Шаг (3) для и шаг (6) в общем случае можно проделать за ограниченное число элементарных операций каждый раз, когда рассматривается очередная ситуация, при условии, что мы следим за ситуациями [4 а-р, (], уже включенными в Ij. Так как грамматика G фиксирована, эту информацию можно хранить для каждого i в конечной таблице. Тогда нет необходимости просматривать весь список Ij, чтобы узнать, находятся ли уже в нем эти ситуации.

На шагах (2), (4) и (5) включение ситуаций в Ij произойдет в том случае, если удастся отыскать в некотором списке (/ /) все ситуации, в которых нужный символ расположен справа от точки, причем этот символ - терминальный на шаге (4) и нетерминальный на шагах (2) и (5). Таким образом, для кавдой ситуации из списка мы должны устроить две связи.

Первая из них указывает следующую ситуацию списка. Эта связь позволяет по очереди рассматривать каждую ситуацию. Вторая указывает следующую ситуацию с тем же символом, расположенным справа от точки. Эта связь позволяет эффективно просматривать список на шагах (2), (4) и (5).

Общая стратегия заключается в том, чтобы прн включении новых ситуаций каждую ситуацию из списка рассматривать только один раз. Однако сразу после включения в Ij ситуации вида [Л-*-а"бр, (] мы справляемся в конечной таблице, заготовленной для Ij, есть ли в Jj ситуации вида [б-j-y-,/]. Если да, включаем в Ij также и [Л ~> аб-р, (].

Заметим, что в качестве первых компонент может появиться фиксированное число цепочек, скажем k. Поэтому в Ij может появиться пе более ft (/+1) ситуаций. Если мы покажем, что алгоритм 4.5 расходует на каждую ситуацию из списка фиксированное количество времени, скажем с, то этим будет доказано, что общие затраты времени составляют 0(/г), так как

(/+ 1) 2" ("+ 1) (/гЧ-2Хсп2

для некоторой константы с.

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

соответственно и п. Тогда Тз(5) = П1, г(3) = П2 а Тз (J) = Hi + ttj. Мы уже убедились, что Тз(5)-0, а S, у и б выбраны так, что т (З*) =Tj (.7)-L Поэтому ранг набора 5 равен г-1. Таким образом, [Ву" Л6", k] входит в Ij. По правилу (6) или (3) ситуация [Л-»-р, /] будет включена в /у. □

Заметим, что в качестве частного случая теоремы 4.9 мы получаем, что входит в /„ тогда и только тогда,

когда 5-*-а принадлежит Р и а=>*й: .. т. е. а- ... а„ принадлежит L(G) тогдаи только тогда, когда [5-j-ct*, 0] для некоторой цепочки а входит в /„.

Теперь исследуем вопрос о времени работы алгоритма 4.5. Читателю предоставляем доказать, что вообще для разбора любой цепочки длины п в произвольной заданной грамматике достаточно О(д) подходящим образом определенных элементарных hiarob. Мы докажем сейчас, что если грамматика однозначная, то достаточно 0{п) шагов.

Лемма 4.6. Пусть G = (N, 2, Р, S) - однозначная КС-грамматика а а- ... а„ - цепочка аз 2*. Тогда при выполнении алгоритма 4.5 мы пытаемся включить [Л-«-а-р, (] в Ij не более одного раза, если афе.

Доказательство. Ситуацию [Л а-р, г] можно включить в Ij только на шагах (2), (4), или (5). Если она включается на hiare (4), то последний символ цепочки а-терминал, а если на шагах (2) или (5), то-нетерминал. В первом случае результат очевиден. Во втором случае допустим, что [Л-*-аб.р, г] включается в /,-, когда рассматриваются две различные ситуации [б -> у., k] и [б б -, /]. Тогда ситуация [Л -бр, t] должна оказаться одновременно в и в / (возможно k = l).

Допустим, что кф1. По теореме 4.9 существуют такие 0, 9,, Оз и е„ что 5=Ф*е1Л0,=>91 абрВз=>*П1 . .. а„ и 5=* 0зЛ0,= %аа ... Uj. Но в первом выводе а *а ... Uf, а во втором 9за=>*а1 ,.. а. Тогда для цепочки ... существуют два разных дерева вывода, в которых «,-1 ... Uj выводится из аВ двумя разными способами.

Пусть k = l. Тогда должно быть уфЬ. Снова для цепочки а. ... а„ легко найти два различных дерева вывода. Детали доказательства оставляем в качестве упражнения. □

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



4.2. ТАБЛИЧНЫЕ .МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА

ЭТОГО МЫ опишем алгоритм 4.6, порождающий по такому списку правый разбор. Правый разбор выбран потому, что в этом случае алгоритм несколько упрощается. Небольшое изменение алгоритма позволит находить левый разбор.

Будем предполагать для простоты, что исходная грамматика не содержит циклов. Если в грамматике есть циклы, то некоторые входные цепочки могут иметь сколь угодно много разборов. Однако алгоритм 4.6 можно модифицировать так, чтобы приспособить его К грамматикам с циклами (упр. 4.2.23).

Следует отметить, что, как н в случае алгоритма 4.4, можно упростить алгоритм 4.6, снабдив указателями каждую ситуацию, включаемую в список алгоритмом 4.5. Они указывают одну или две ситуации, которые привели к включению этой ситуации в список.

Алгоритм 4.6. Построение правого разбора по списку разбора.

Вход. КС-грамматика G = {N, 2, Р, S) без циклов, правила которой занумерованы числами от 1 до р, входная цепочка w = ay ... а и список разбора Z, /„ для цепочки w.

Выход. Правый разбор л цепочки w или сообщение об ошибке.

Метод. Если в /„ нет ситуации вида [5-»-а*, 0J, то wL{G). Поэтому надо выдать сигнал „ошибка" и остановиться. В противном случае положить ле и выполнить процедуру R([5-+ а», 0], п).

Процедура К([Л-*р., i], /) определяется так:

(1)Если /i -номер правила Л-*-р, то пусть значением переменной л будет цепочка, начинающаяся номером h, за которым следует предыдущее значение я. (Мы предполагаем, что л -глобальная переменная.)

(2) Если р = ХуХ. .., Х,„, положить k = m и 1 = 1.

(3) (а) Если XjjEL, вычесть 1 из fe и нз I. (б) Если XjjN, найти в / ситуацию [Xf~y >, г] для некоторогодля которого [Л ~->Л:Д2.. .Xf, y - Х.Х, i]

входит в If.. Затем выполнить R {[Х-из и положить 1 - Г.

у , г], /), вычесть 1

(4) Повторять шаг (3), пока не станет k = 0. После этого остановиться. □

Работа алгоритма 4.6 состоит в прослеживании правого вывода входной цепочки с помощью списка разбора, позволяющего определять правила, примененные в ходе вывода. Вызов процедуры Н с аргументами [Л-р.,/] и / добавляет к левому концу те<ущего частичного разбора номер правила Л->-р. Если P - ayVyBv ,,, Bv, где By, S -все вхождения нетер-

чаях фиксировано. Фиксированное время расходуется также на список в целом.

Предоставляем читателю показать, что /(, можно построить за фиксированное время. Мы рассмотрим ситуации в списке Л для / > 0. На шаге (4) исследуется и предыдущий список, Для каждой ситуации из Ij y с символома, расположенным cnpaBi от точки, в Ij включается некоторая ситуация. Так как можно исследовать только те ситуации из которые удовлетворяю)

этому условию, то на каждую включаемую ситуацию тратится лишь фиксированное время, а кроме того, фиксированное время надо потратить на список /у как таковой для исследования cij и нахождения первой ситуации в /у., содержащей «ау.

Теперь рассмотрим каждую ситуацию из /у и затраты времени на нее в случаях, когда применяется шаг (5) или (6). Шаг (6) можно выполнить за фиксированное время, так как надо только исследовать таблицу, связанную с /у, которая говорит о том, включены ли уже все [Л-*-*сс,/] для соответствующего Л. За фиксированное время таблица исследуется, и, если необходимо, в /у включается фиксированное число ситуаций. Элим исчерпывается все время, затрачиваемое на рассматриваемую ситуацию.

Если применяется шаг (5), то в некотором списке для kj надо просмотреть все ситуации, содержащие В для некоторого конкретного В. Каждый раз, когда обнаруживается такая ситуация, в список /у включается другая ситуация, и это время относится к включаемой ситуации, а пе к рассматриваемой!

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

Теорема 4.10. Если исходная грамматика однозначна, то алгоритм 4.5 можно выполнить для входной цепочки длины п за 0{П) разумно определенных элементарных операций.

Доказательство. Формализацию приведенного выше рассуждения и понятия элементарной операции оставляем в качестве упражнения. □

Теорема 4.11. В случае произвольной КС-грамматики алгоритм 4.5 можно выполнить для входной цепочки длины п за 0{п) разумно определенных элементарных операций.

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

Заключительная часть анализа алгоритма Эрли касается метода построения разбора по законченному списку разбора. Для



-Pi-,y, h)

(1) ь = / -l.h (2) i>, = i,.n - \G\ 17<s.

Пример 4.11. Применим алгоритм 4.6 к списку разбора из примера 4.10, чтобы получить правый разбор входной цепочки (а + а) « а. Вначале можно выполнить R {[Е-> Г •, 0], 7). На гнаге (1) переменная л принимает значение 2 (номер правила Е-*-Т). Затем полагаем и 1 = 7 и выполняем шаг (36).

F-X-T, 0], а в /о - ситуацию

В /, находим ситуацию [7"

Г, 0]. Таким образом, будет выполнена процедура R {[Т -Е-кТу 0], 7), в результате чего к л будет добавлен слева номер 3 и станет л = 32. Согласно этому вызову процедуры R, на шаге (2) надо положить k = 3 и 1 = 7,

Затем выполняется шаг (36) для /г -3. Находим [7"-»-Р-,6] в и [ТЕ -Г, 0] в /е и вызываем R{[T~E-, 6J, 7). После завершения этого вызова положим ft = 2 и /=6. На шаге (За) придется рассмотреть » и положить ftl и / = 5. Далее находим [F->-(£)•, 0] в /5 и [Т -> «Р »Т, 0] в /(, и, следовательно,

(£)%0]. 5). том же духе, получаем правый разбор

вызываем R {[Е

Продолжая в 64642156432.

Вызовы процедуры R показаны на рис. 4.10, где они наложены на дерево вывода цепочки (а-{-а) а а. □

. Теорема 4.12. Алгоритм 4.6 правильно находит правый разбор цепочки ... а„, если таковой су1цествует, и его можно выполнить за время 0{п).

Доказательство. Прямой индукцией по порядку вызовов процедуры R можно показать, что порождается правый разбор. Эту часть доказательства мы оставляем в качестве упражнения.

По аналогии с доказательством аеоремы 4.10 можно показать, что на вызов R ([Л ~р-, (],/) расходуется время 0((/ -О), если сначала показать, что шаг (36) требует 0(/~г) элементарных операций. Ддя этого нужно предварительно обрабатывать списки так, чтобы для рассмотрения всех ситуаций из вторая компонента которых равна /, требовалось фиксированное


F RUf-(f)-.0],5) С )

ft([r-.r.,6J.7)

E R([£--*r..5],4) T R([r-*F.,g,4) F R(Iir-*fl-,3],4) a

Рис. 4.10. Диаграмма выполнения алгоритма 4.G.

Время. Иными словами, в каждом списке нужно связать ситуации с общей второй компонентой и ввести заголовок, указывающий первый элемент списка. Эту обработку можно очевидным образом проделать за время О (п).

Затем на шаге (36) исследуются ситуации списка со второй компонентой г = 1, I-1, . .., г, пока не обнаружится нужная ситуация вида [Х -*-у•, г]. Проверка того, что получена нужная ситуация, занимает фиксированное время, так как "все ситуации со второй компонентой i можно найти в списке I,. за фиксированное время. Общее количество времени, потраченного на шаге (36), пропорционально, таким образом, j - i. □

УПРАЖНЕНИЯ

4.2,1. Пусть G определяется правилами 5-> Л51 Ь, A-SA\a. С помощью алгоритма 4.3 постройте таблицы разбора следующих Цепочек:

(а) bbaab,

(б) ababab,

(в) ааЬЬа.

мнналов в цепочку р, то процедура R определяет первое правило, использованное при развертке Bt{\ s), скажем В-*-, и позицию во входной цепочке ш, непосредственно предшествующую первому терминальному символу, выводимому из Bf Затем делаются рекурсивные вызовы процедуры R в следующем порядке:





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