Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 108
Текст из файла (страница 108)
Нижние семь элементов легко получаются по правилу ( ). я (2) и читывая, что элемент третьего столбца, лдмент четвертого соотве ствующ, р ий Р, авен 1, находим, что э столбца (4= 3+1), соответствующи, тоже образом, элемент третьего столбца, соответствующи +, ра 2(= 1+ !). () Рнс. 6.5. Твблнца ресоознанання, построеннея алгоритмом б,х. за которым' следует любое выражение, а если знака + нет, то— пустую цепочку (распознаваемую г'). Тогда можно так проин.терпретировать правило (1): выражение — это терм, за которым следует нечто, распознаваемое Ее, а именно либо пустая цепочка, ' либо цепочка из чередующихся знаков + и термов, начинаю- 3е щаяся с + и окапчивакнцаяся термам. Аналогично интерпретируются правила (3) и (4). Правила (6) и (6) говорят о том, что множитель (цепочка, распознаваемая Р) — это либо заключенное в скобки выражение, либо символ а (если скобок нет).
Пусть (а+а)»а †входн цепочка для алгоритма 6.2, Тогда он построит матрицу (!ей, изображенную на рис. 6.2. Вычислим для примера элементы последнего столбца этой' матрицы. Элементы, соответствующие нетерминалам Р, М, А, Е и )с, принимюот значение ), так как каждый из указанных нетерминалов распознает символ из Х, а последний символ — это концевой маркер.
Х всегда дает значение Г, а 1' — всегда О. Применяя шаг (3) нашего алгоритма, находим, что первый проход по нетерминалам на шаге (4) дает значения для Е„Т„Р и они равны соответственно О, О, (. После второго прохода Т получает значение (.
Значения для Е и Р' можно вычислить на третьем проходе. 532 ЬА„Р. Реалиаация ОВНРОВ праграмм На практике системы синтаксического анализа, подобные ОЯНРОВ-программам, реализуются .не в табличной форме, как это сделано в алгоритме 6.2, а обычно с помощью метода проб и ошибок. Мы поствоим сейчас автомат, „реализующий" распознающую часть ОЯНРОВ-программ, Читателю предоставляем самому показать, как расширить этот автомат до преобразователя, выдающего последовательность успешных вызовов процедур, по которой можно построить „разбор" или перевод. Автомат состоит из входной ленты с указателем, положение которого можно восстанавливать, управляющего устройства с тремя состояниями и магазина, в котором помещаются символы из некоторого конечного алфавита и указатели входных позиций. В работе этого автомата воплощается наше интуитивное представление о вызывающих друг друга процедурах (нетермипалах) и возвратах входного указателя„ происходящих при каждой неудаче.
Указатель возвращается туда, где он находился в тот момент, когда состоялся вызов неудачной процедуры: Определение. Анализирующей машиной назовем шестерку М = (Я, Х, Г, 6, начало, Хе), где (!) Я =-(успех, неудача, начало); (2) Х вЂ” конечное множество вхоаных символов; (3) à — конечное множество магазинных символов; (4) 6 — такое отображение множества !ех(ХО(е))хГ в множество ыхГ"е, что (а) если д — успех или неудача, то 6(д, а, Х) не определено, если аЕХ, и 6(4, е, Х), имеет вид (начало, Р) для некоторого УРГ; (б) если 6(начало, а, Х) определено для некоторого а6Х, то 6(начало, 6, Х) ие определено для всех 6~а из Х()(е); (в) для а 6Х значением 6(начало, а, Х), если оно определено, может быть только (успех, е)„ (г) 6(начало„е, Л) может иметь только вид (начало, )'Х) для некоторого У~Г или вид (д, е) для д=-успех либо ~) =- неудача; 533 Гл, б. АлГОРитмы РАЗБОРА с ОГРАниченными БОВБРАТАми (5) начало — начальное состояние; (6) Ео Šà — начальный магазинный символ.
Машина М похожа на автомат с магазинной памятью, но ', между ними есть несколько важных различий. Элементы множества Г можно представлять себе как процедуры, вызывающие. ', друг друга илн „переходящие" одна в другую. Магазин используется .. для записи рекурсивных вызовов и положения входной головки ., в момент вызова. Состояние начало обычно служит для вызова другой процедуры, зто Отражается в том, что если 6(начуло, е, 7) ==(начало, У7), где У 6Г н 7 — верхний символ магазина,,'.
то 1' помещается в магазин непосредственно над 7. Состояния, 6 успех и неудача служат для перехода к другой процедуре, а не, для вызова се. Если, например, 6(успех, е, 7) =(начало, У), то У просто заменяет 7 наверху магазина. Определим формально ' действия машины М. Конфигурацией машины М назовем тройку (б), бв«х, у), где (1) д Е (успех, неудача, начало); (2) бв и х принадлежат Х*, « — метасимвол, указывающий положение входной головки; (3) у — содержимое магазина, имеющее вид (7„1,)...(7, 1 ), где ХГЕГ и 1 — целое число при 1 =1(лз.
Верх магазина расположен слева. Хб для каждого 1 — это вызов „процедуры", а 17— входной указатель. Зададим на множестве конфигураций отношение «-А,(или « †, когда М подразумевается): (1) Пусть 6(начало, е, 7) = (начало, УЕ) для У Е Г. Тогда (начало, бв«х, (2, 1) у) «-(начало, бв «х, (У, 1)(2, 1) у) где 1=-«бв(. Здесь происходит „вызов" У и регистрируются поло-:ф жение входной головки в момент вызова и вызываемая „процедура" У. ' (2) Пусть 6(б), е, 2)=(начало, у), где уЕГ и дЕ(успех, неудача).
Тогда (д, бв«х, (2, г) у) « — (начало, бв«х, (У, к) у) Здесь 7 „переходит" в У. Входная позиция, соответствующая У, та же, что и позиция, соответствующая 2. (3) Пусть б(начало, а, 2) — (д, е) для а Е Х («(е«, Если а=успех, то (начало, бв)ах, (Х, 1) у) « — (успех, бва «х, у) Если а не является префиксом цепочки х нли 4=неудача, то , (начало, бв«х, (7, б) у) « — '(неудача, и«о, у) бл. нисхОдящии РА3БОР с ОГРАничениыми БОзБРАТАми « — ( « — (успех, а«Ьаа, (У, 0)(7 0)) «- (начало, а «Ьаа, (1', О) (~о 0)) « — (на ало, а«ьа, (А, 1)(У, О)(Р„О)) « — (неудача, а Ьаа, (1', 0) (2о 0)) « — (начало, а+Ьаа, (В, 0)(2о 0)) 535 где ио=-бвх и «и «=~'.
В последнем случае входной указатель возвращается на позицию, задаваемую указателем, находящимся наверху магазина. Заметим, что при 6(начало, а, 7)=(успех, е) Очередным сосгоянием анализирующей машины будет успех, если иеобработанна» часть входной цепочки начинается символом а, и неудача в противном случае. Пусть « — + обозначает транзитивное замыкание отношения « —. Языком, определ»емым машиной М, назовем множество Е(М) = (бв«бвЕ Хо и (начало, «ш, (2„0)) « —" (успех, бе«, е)«.
Пример 6.7. Пусть М= (е, «а„Ь), (7„У, А, В, Е), б, начало, 7о), где 6 задается равенствами (1) 6(начало, е„Е,) =(начало, УЛо) (2) 6(успех, е, 7,) = (начало, 7„) (3) 6(неудача; е, Х„)= (начало, Е) (4) 6(начало, е, У)== (начало, АУ) (5) 6(успех, е', У) = (начало, У) (6) 6(неудача, е, У)=-(начало, В) (7) 6(начало, а, Л)= (успех, е) (8) 6(начало, Ь, В) = (успех, е) (9) 6(начало, е, Е) — (успех, е) М распознает цепочки, состоящие из символов а и Ь и Оканчмва~ощиеся символом Ь, но делает это довольно своеобразно.
Л и В распознают соответственно а и Ь. Когда начинает действовать символ У, он ищет символ а и, если отыскивает его, „переходито в себя. Таким образом, магазин не меняется, а на входе „потребляется" символ а. Если достигнут символ Ь или конец входной цепочки, то У в состоянии неудача стирает верхнюю ячейку магазина. Иными словами, У заме~яется символом В и независимо от того, приводит В к успеху илн неудаче, В в конце концов стирается. 7, вызывает У (и переходит в себя) так же, как У вызывает А. Поэтому любая цепочка, состоящая из символов а и Ь и оканчивающаяся символом Ь, приводит к тому, что Ео сотрется и наступит успех, Действии машины 64 на входной цепочке абаа образуют такую последовательность конфигураций: (начало, «аЬаа, (2„0)) « — (начало, «абаи, (У, 0) (7о, 0)) начало, «аЬаа, (Л, О)(У, 0)(2„0)) ГЛ. Ь. АЛГОРИТМЫ РАЗБОРА С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ «-(успех, аЬ«аа, (2м О)) « — (начало, аЬ ! Оа, (2„0)) «-(начало, аЬ!Оа, (У, 2)(2„0)) « — (начало, аЬ 1 аа, (А, 2) (У, 2) (2„0р: «-(Успех, аЬа(а, (У, 2) (2„0)) ! — (начало, аЬа!а, (у, 2)(7„0)) г-(начало, аЬа!а, (А, 3)(у, 2)(2м 0)): 1 — '(Успех,' аЬаа« (У, 2) (2„0)) ! — ( ч оо, аь (, (у,' 2)(2„0)) «-(начало, аЬаа«, (А, 4)(у, 2)(2м 0) ! — (Неудача, аЬаа(, (У, 2) д, О)) 1 — (начало, аЬаа 1, ' (В, 2) (Еа, 0)) «-(неудача, аЬ(аа, (2, ОИ « — (начало, аЬ«аа, (Ез,' О)) « — (успех, аЬ(аа, е) у кается, потому что конец Заметим, что цепочка аЬаа не допуска оп ен .
ее не достигается на последнем шаге'. Однако . Ь б д пущена. Важно также отметить, что в четвертой с конца кон- ', фигурации В не „вызывается", а заменяет 1'. Поэтому паве х входная головка возвращается назад. (1 У шиной тог а н Докажем теперь; что язык определяется ана анализирующей маз ' иной тогда н только тогда, когда оя определяется ОЯНРОВ-:,' программой. Лемма 6.6, Если Е=Е(М) для некоторой анализир и ей:' рой ОЯНРОВ-программы Р. Доказательство. Пусть Р==(Ь), л, 1г, 2), где Ь«=ГО (Х«и Х вЂ” новый символ.
Определим К: (1) Для Х правила нет. (2)-Если 6(начало, а, 2)=(о, е)„то для 2 будет пр и д=-успех, и правило 2 — 1, если у=неудач». авила (3) Для других 26Г зададим 1'„У, и 1', так: (а) если 6(начало, е, 2)=-(начало, У2); положим У, -У, (б) если 6(д, е, Х)=(начало, У), положим 1',=У, если о=-успех, и 1;=-У, если о=-неудача, (в) если 1'Г не определен в (а) и (б), положим Уг— - Х. Тогда для 2 введем правило 2- 1' ~ГУ, У ".
1). 3 ВЗ' .6$ Покажем, что для каждого 26Г ')й( =Ф" (в«х, з) тогда и только тогда, когда (6.1.3) -2 — " (начало, !.вх, (2, 0)) «-" (успех, в!х, е) 555 ЗЛ, НИСХОДЯШИЙ РАЗБОР С ОГРАНИЧЕННЫМИ ВОЗВРАТАМИ (6.1.4) Е=Ь" («в,1) тогда н только тогда, когда (Начало, ! в, (2, 0)) « — (неудача, «в, е) Докажем оба утверждения одновременно иидукцией по числу шагов вывода программы Р или вычисления машины М, Необходимость. Базисы для (6.1.3) и (6.!.4) получаются непосредственно из определения отношения « —. Чтобы доказать шаг индукции для- (6.1.3), допустим, что У=У' (в«х, з) н утверждения (6.1,3) и (6.1.4) верны для меньших значений л.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
