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

Теорема 5.И. Алгоритм 5.9 правильно вычисляет систему ,

Доказательство. По теореме 5.8 достаточно доказать ЧТО множество ситуаций Л помещается в тогда и только тогда, когда существует вывод S гра Лш=.apш, где у -префикс цепочки ар и Л=У,{у). Необходимость условия доказы-

Таблица 5.4

Символ грамматики

Множество ситуаций

Ль Лл Лг Ль Л

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

5.2.4. Проверка 1К(/;)-условия

Может оказаться, что нам надо знать, является ли интересующая нас грамматика ЬК(/г)-грамматикой для данного k. Алгоритм, решающий эту проблему, можно построить на основе теоремы 5.9 и алгоритма 5.9.

Определение. Пусть G = (N, S, Я, S) -КС-грамматика нецелое число. Множество Л ЬК(й)-ситуаций для грамматики G назовем непротиворечивым, если оно не содержит двух различных элементов вида [Лр., и] и [В-у-., v], где w EFFPtJ), причем р2 может быть пустой цепочкой.

Алгоритм 5Л0. Проверка LR(ft)-y с л о в и я.

Вход. КС-грамматика G = (N, 2, Я, S) и целое число kO-Выход. ,Да", если G - ЕК(/г)-грамматика, и „нет" в противном случае. Метод.

(1) С помощью алгоритма 5.9 вычислить каноническую систему < множеств ЬК()-ситуаций для грамматики G.

(2) Рассмотреть каждое множество ЕК(Л)-ситуаций из и установить, непротиворечиво ли оно.

(3) Если все множества из of непротиворечивы, выдать ответ да". В противном случае выдать „нет", т. е. объявить, что G не ЬК()-грамматика для данного k. □

Утверждение о корректности алгоритма 5.10 -это просто переформулировка теоремы 5.9.

Пример 5.31. Проверим, является ли грамматика из примера 5.30 ЬК(1)-грамматикой. Имеем <е = {Л, ...,Л). Достаточно проверить лишь множества ЬК(1)-ситуаций, содержащие точку на правом конце правила. Такими множествами оказываются

0- 1 а, -4. ъ и Л.

Рассмотрим р. Для ситуаций [S--S,] и [S~-SaSb, е\а] из Л множества EFF(S) и EFF(Sa) пусты, поэтому они совместимы с ситуацией [S-,a], т. е. Л непротиворечиво.

Рассмотрим Лу. Здесь F¥¥(aSb) = EF¥{aSba)----a, но а ие является аванцепочкой в ситуации [S-S,]. Следовательно, Лу непротиворечиво.

Множества Л и Л/у непротиворечивы, потому что EFF(Sbx) и EFF(SaSbx) пусты для всех х. Множества Лг, и Л очевидно непротиворечивы.

Таким образом, все множества системы о? непротиворечивы и, значит, G -ЬК(1)-грамматика. □

5.2.5. Детерминированные правые анализаторы для \.Щк]-грамматик

В этом разделе мы неформально опишем, как по LR(ft)-rpaM-матике построить детерминированный расширенный МП-преобразователь, заглядывающий на k символов вперед, который работает как правый анализатор для этой грамматики. На описанный ранее МП-преобразователь можно смотреть как иа алгоритм разбора типа „перенос -свертка", решающий на основании состояния верхнего символа магазина и аванцепочки, делать ему перенос или свертку, а в последнем случае -какую именно свертку.

Чтобы помочь анализатору принять правильное решение, в нужных ячейках магазина будут находиться „LR(ft)-тaблицы", содержащие необходимую для разбора информацию, извлеченную из соответствующего множества ситуаций. В частности, если а-префикс магазинной цепочки (верхняя часть ее расположена справа), то таблица, приписываемая самому правому символу цепочки а, получается из множества ситуаций V;,(a). Следовательно, построение правого анализатора состоит по существу



В нахождении ЬН(/г)-таблиц, соответствующих мно?кествам ситуаций.

Определение. Пусть G - КС-грамматика и (5 -система мне жеств LR(fe)-cHTyau4& для G. L.{kyma6Auieu Т{Л), соответствую щей множеству ситуаций Л из g, назовем пару функций {f,g). Функцию / назовем функцией действия, g - функцией перехода и определим их следующим образом:

(1) f отображает 2** в множество {ошибка, перенос, допуск}! {свертка i\i - номер правила из Р, причем

(а) перенос, если [Л ~>fj-, v] содержится в Л f.e и weEFF,(M),

(б) f(n)=свертка /, если [Л-и] содержится ъ Л w А-- правило из Р с номером i,

(в) /()=допуск, если [S-+S-,e] содержится в Л,

(г) /(п) = ошибка в остальных случаях.

(2) g определяет очередную применяемую таблицу, она ис пользуется сразу после переноса и свертки. Формально, g отображает Nu2 в множество таблиц и сигнал ошибка. Значением g{X) является таблица, соответствующая множеству GOTO(, X). Если GOTO(,, X) пусто, то g(X)= ошибка.

Следует подчеркнуть, что если G -ЕН()-грамматика и ~ каноническая система множеств ЕК(й)-снтуаций для G, то по теореме 5.9 между действиями, определяемыми по правилам (1а) - (1в), не возникает конфликтов.

Будем говорить, что таблица Т {Л) соответствует активному префиксу у грамматики G, если Л~У/{у).

Определение. Канонической системой ЬК{к)-таблиц для LR(/e)-грамматики G назовем пару (<, Т), где -множество LR{k)-таблиц, соответствующее канонической системе множеств LR(/)-ситуаций для G, а Т-LR(Л)-тaблицa, соответствующая множеству Kft (е).

Обычно канонический LR(й)-aнaлизaтop представляется в виде таблицы, каждая строка которой является ЕК()-таблицей.

Если LR(г)-aлгopитм разбора, описанный ранее как алгоритм 5.7, использует каноническую систему LR()-тaблиц, будем называть его каноническим ЪЩк)-алгоритмом разбора или, короче, каноническим ЬЩк)анализатором.

Итак, опишем процесс построения по LR(/e)-rpaMMaTHKe канонической системы LR(й)-тaблиц.

Алгоритм 5.11. Построение по LR()-r р а м м а т и ке канонической системы LR()-t а б л и ц.

Вход. LR(fe)-rpaMMaTHKa G=-(N, 2, Р, S).

Выход. Каноническая система LR()-тaблиц для G.

Метод. ,

(1) Построить пополненную грамматику

G-(NU{5}, 2, PU{5 -S}, S)

где S- - нулевое правило.

(2) По G построить каноническую систему < множеств допустимых LR(fe)-cnTyaHHK для G.

(3) Взять (Г - {7 I Т - 7 {Л) для некоторого Л) в качестве множества LR(й)-тaблиц. Положить Т=Т(Л), где A,Vi(e). и

Пример 5.32. Построим каноническую систему LR(l)-тaблиц для грамматики G, которой соответствует пополненная грамматика

(0) S~S

(1) 5 -SaSb

(2) S

Каноническая система < множеств LR(l)-cHTyaHHft для G приведена в примере 5.30. По построим систему ЕК(/г)-таблиц.

Вычислим таблицу Т, (/о, go), соответствующую г,?о. Так как k\, то аванцепочками могут быть только а, b ие. Поскольку Л содержит ситуации [S->--,e\a], то f (е) = (а)свертка 2. Из остальных ситуаций, принадлежащих находим, что [о{Ь) = ошибка (так как EFF (5а) пусто). Чтобы вычислять функцию переходов g, заметим, что GOTO(/o S) и О.ОТО{Л, X) 0 в остальных случаях. Если обозначает Т (Л), то go{S) = Ti и (X)ошибка для остальных X. Вычисление таблицы Го закончено. Она имеет вид

fo en

а b е

Т,Х X

Здесь 2 обозначает свертку, в которой применено правило 2, а X -символ ошибки.

Найдем теперь элементы таблицы Tj -(f, g). Так как [S •,е]£Лт , то () допуск, и так как [S S-aSb, e\al£ Л, то /i (а) перенос. Заметим, что аванцепочки последних ситуаций здесь не играют роли. Далее, (Ь) ошибка, и, так как GOTO(i, а)=-2, полагаем ёгЛ)""2. где Т=-Т(Л.,).

Продолжая в том же духе, получаем систему ЕН(1)-таблиц, приведенную на рис. 5.9. □

В гл. 7 мы изложим другие методы построения LR(fe)-aнaли-заторов по грамматикам. Эти методы часто дают анализаторы меньшего объема, чем канонический LR(Л)-aнaлизaтop. Однако



последний обладает рядом замечательных свойств, которые будут служить эталоном для сравнения с другими ЬК(/г)-анализато-рами. Отметим несколько таких свойств.

(1) Простой индукцией по числу сделанных шагов можно показать, что каждая таблица, находящаяся в магазине, соответствует цепочке символов грамматики, расположенной слева от нее. Поэтому, как только первые k символов необработанной Части входной цепочки оказываются такими, что нет суффикса, который вместе с обработанной частью давал бы цепочку, принадлежащую L{G), анализатор сразу сообщает об ошибке. В каждый момент его работы цепочка символов грамматики, хранящаяся в магазине, должна быть активным префиксом грамматики. Поэтому ЬК{/г)-аналнзатор объявляет об ошибке при первой же возможности в ходе считывания входной цепочки слева направо.

(2) Пусть Tj = [fj, gj). Если /у (w) перенос и анализатор находится в конфигурации

(5.2.4)

{аХiTуХ . . , XjTj, X, л)

то найдется ситуация [Л-р-рз, у], допустимая для XyX,...Xj, причем uEW {v). Поэтому если SХ-Х,. .XjUy для некоторой цепочки г/€2*, то по теореме 5.9 правый конец основы цепочки XyX...XjUy должен быть где-то справа от символа Ху.

(3) Если в конфигурации (5.2.4) fj (и) = свертка i и А ККз ... У г-правило с номером г", то цепочка Xy .4 т Ху г,.2 • --Ху в магазине доллна совпадать с К-.-К., так как множество ситуаций, по которому построена таблица Tj, содержит ситуацию [АУуУ. ... К/.*, w. Таким образом, на шаге свертки не обязательно рассматривать символы верхней части магазина, надо только выбросить из магазина 2г символов.

(4) Если (w) = допуск, то w- е. Содержимое магазина в этот момент имеет вид TST, где Т - ЬК(/г)-таблица, соответствующая множеству ситуаций, в которое входит [S-S-,].

(5) Можно построить ДМП-преобразователь с концевым маркером, реализующий канонический ЬК()-алгоритм разбора. Действительно, так как аванцепочку можно хранить в конечной памяти управляющего устройства ДМП-преобразователя, то ясно, как построить расширенный ДМП-преобразователь, реализующий алгоритм 5.7 (ЕК()-алгоритм разбора).

Доказательство этих фактов оставляем в качестве упражнений. По существу это переформулировки определений допустимой ситуации и ЕК()-таблицы. Таким образом, справедлива следующая теорема.

Теорема 5.12. Канонический Ьи{к)-алгоритм разбора правильно находит правый разбор входной цепочки, если он суаествует, ti объявляет об ошибке в противном случае.

Доказательство. На основании сформулированных выше свойств индукцией по числу шагов, сделанных алгоритмом разбора, можно показать, что если а-цепочка символов грамматики, находящихся в магазине, и х - необработанная часть входной цепочки, включающая аванцепочку, то axr=jtW, где ш - первоначальная входная цепочка и -текущая выходная цепочка. В качестве частного случая получаем, что если алгоритм допускает цепочку w и выдает на выходе л, то S=:>jtW. □

Из ЕК(1)-условия непосредственно следует однозначность LR-грамматики. Пусть даны два различных правых вывода

Sz,ay=j. ... а„ =w и S р . .. р„ w.

Рассмотрим наименьшее из чисел г, для которых a, ,-p j-. Сразу получаем, что ЬК()-условие нарушается для любого k. Детали оставляем в качестве упражнения.

Итак, канонический ЕК(й)-алгоритм разбора для LR(ft)-rpaM-матики G выдает правый разбор входной цепочки w тогда и только тогда, когда w£L{G). Вначале не совсем очевидно, что канонический ЬК()-анализатор выполняет свою работу за линейное время, даже если элементарными операциями считать его собственные шаги. Докажем, что это действительно так.

Теорема 5.13. Канонический ЬЩк)-алгоритм при разборе входной цепочки длины п делает 0{п) шагов.

Доказательство. Определим С-конфигурации рассматриваемого анализатора:

(1) начальная конфигурация является С-конфигурацией,

(2) конфигурация, непосредственно следующая за шагом переноса, является С-конфигурацней,

(3) конфигурация, непосредственно следующая за сверткой, которая делает магазин короче, чем в предыдущей С-конфигурации, является С-конфигурацией.

При разборе входной цепочки длины п анализатор может оказаться не более чем в 2п С-конфигурациях. Назовем характеристикой С-конфигурации число, равное сумме числа символов грамматики в магазине и удвоенного числа необработанных входных символов. Если Су и Cg -последовательные С-конфигура-ции, то характеристика конфигурации Су по крайней мере на единицу больше характеристики конфигурации С. Так как характеристика начальной конфигурации равна 2/г, то количество всех С-конфигураций не превосходит 2п.

Теперь достаточно показать, что найдется такая константа с, что между двумя последовательными С-конфигурациями анализатор может делать не более с шагов. Для этого рассмотрим





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