Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 66
Текст из файла (страница 66)
д. (2) Четверкой (з, 1, а, б) будем обозначать конеригура4(шс алгоритма: (а) з обозначает состояние алгоритма; (б) 1 указывает позицию входного указателя (предполагается, что (и+ 1)-м „входным символом" служит правый концевой маркер б); (в) а представляет содержимое первого магазина (Е1); (г) !з представляет содержимое второго магазина ((,2). Будем считать, что верх первого магазина расположен справа, а верх второго магазина †сле.
Магазин В2 служит для представления .,текущей" левовыводимой цепочки, т. е. той, которая получилась к данному моменту в результате развертки нетерминалов. В соответствии с неформальным описанием нисходящего разбора в равд. 4.1.1 верхний символ магазина В2 будет .символом, помечающим активную вершину порожденного к данному моменту дерева вывода. В магазине Ц представлены текущая история проделанных выборов альтернатив и выходные символы, по которым прошла входная головка. Алгоритм находится в одном нз трех состояний д, Ь нли 1, где д — состояние нормальной деятельности, Ь вЂ” состояние возврата, 1 — заключительное состояние.
(3) Начальная конфигурация алгоритма — (д, 1, е, Вз",). (4) Существует шесть типов шагов. Эти шаги будут описаны в терминах их воздействия на конфигурацию алгоритма, Ядро алгоритма — вычисление последовательных конфигураций, определяемое через „отношение перехода" ) —. Запись (в, 1, с4, р) '- (з', 1', а', ()') означает, что если (в, 1', а, (!) — текущая конфигурация, то нужно перейти в следующую конфигурацию (з', 1', а', б') Если не оговорено противное, то 1' — число от 1 до и+ 1 326 а а (Х(! 1')', где 1' — множество индексов альтернатив, р Е (1ч () Х)'.
Шесть типов шагов определяются так: (а) Разрастание дерева (4), 1', а, АР) ) — (д, 1, аА„у1р) где А у,— правило из Р и у,— первая альтернатива нетерминала А. Этот шаг соответствует разрастанию частичного дерева вывода, при котором применяется первая альтернатива самого левого нетерминала дерева. (б) Успеи1ное сравнение входного символа с порожденным символом (д, 1, а, ар) ) — (д, 1+ 1, аа, !1) при условии, что а; — а (1 и).
Если 1си входной символ совпадает с очередным порожденным терминальным символом, то оп передается из 1.2 н В1, а позиция входного указателя увеличивается на единицу. (в) Успешное завершение (д, и+ 1, 44, $) ,'— (1, и+ 1, а, е) Достигнут конец входной цепочки и найдена левовыводимая цепочка, совпадающая с входной, Левый разбор входной цепочки восстанавливается по цепочке а с помощью такого гомоиорфизма Ь, что 6(а)=е для всех асх, Iг(А1)=р, где р — номер правила А — у и у — 1чя альтернатива нетерминала А. (г) Неудачное сравнение входного символа с порожденным символом (а, 1, а, а()) )- (Ь, 1, а, а)т) (а, ~ а) Надо перейти в состояние возврата, как только обнаружится, что порожденная левовыводимая цепочка не совместима с входной цепочкой.
(д) Возврат по входу (ь, 1, аа, 1!) ) — (ь, 1 — 1, и, ар) для всех аЕХ. В состоянии возврата входные символы переносятся назад из Ь! в 1,2. (е) Испытание очереднои альтернативы (ь, 1„аА, тт, 11) )— (!) (д, 1, аАт41, у~„()), если ут+1 — (1+!)-я альтернатива нетерминала А. (Заметьте, что ут В Е2 заменяется на ут41.) (В) Следующая конфигурация невозможна, если 1=1, А =5 и В имеет только ) альтернатив. (Это условие указывает на то, что всевозможные левовыводимые це- 327 ГЛ. 4. ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА 4Л.
СИНТАКСИЧЕСКИЙ АНАЛИЗ С ВОЗВРАТАМИ почки, совместимые с входной цепочкой и>, уже вечер. паны, а ее разбор не найден.) (Ш) (Ь, ъ, а, А11) в оставшихся случаях. (Здесь нсчерпавы все альтеРнативы нетерминала А н дальнейший возврат происходит путем удаления Ат из Е1 и замены в 52 цепочки у, на А.) Алгоритм выполняется следующим образом: Шаг 1. Исходя из начальной конфигурации, вычислять последующие конфигурации С, « — С; « —...
1 — С; « —..., пока их можно вычислить. Шаг 2. Если последняя вычисленная конфигурация — (1, а+ 1, 4», е), выдать Ь(у) и остановиться. В противном случае выдать сигнал об ошибке. () Алгоритм 4.! — это по существу описанный ранее неформально алгоритм, к которому для выполнения возвратов добавлена некоторая „бухгалтерия". Пример 4.1. Рассмотрим работу алгоритма 4.1 на грамматике 6 с правилами (1) Š— Т+ Е (2) Е- Т (3) Т вЂ” Т»Р (4) Т- Р (5) Р- а Пусть Е; служит индексом для Т+Е, Е,— для Т, Т,— для Р>>Т, Т,— для Р и Р,— для а. Для входа а+а алгоритм 4.1 вычисляет такую последовательность конфигурации: (д, 1, е, Е $) « — (д, 1, Е„Т+Е $) «- (4), 1, е,т„Р т+ е$) « — (41, 1, Е,Т,Г,, а Т+Е$) « — (4),2, Е,Т,Г,а, >Т-1-Е$) «-(Ь, 2, Е,Т,Г,а, НТ+Е$) « — (Ь, 1, Еът>Г„аъ>Т+Е$) « — (Ь, 1, Е,Т» Р>>Т+Е$) «-(>), 1, Е;Т„Г+Е$) « — (д, 1, Е,Т,РТ, а+Е$) « — (а, 2, Е,Т,Г,а, +Е$) «- (41, 3, Е,Т,Г,а +, Е $) 1 — (41, 3, еът>Р>а+е» т+е $) « — (4), 3> Е;Т,Р а+Е;Т,, Р»Т+Е$) « — (д, 3, Е;Т,Г,а+ Е;Т,Р>, а» Т+ Е $) « — (41, 4, Е,Т,Р,а+Е,Т,Р,а, » Т+Е$) «-(Ь, 4, Е,Т,Р,а+Е,Т;Р,а, » Т+Е$) « — (Ь, 3, Е,Т,Г,а+ЕГТ,Р;, а»т+Е$) « — (Ь, 3, ЕГТ,Р,а+Е>Т» Р»Т+Е $) «- (4), 3, Е,Т,Г,а+ Е,Т„Р+ Е $) « — (д, 3, Е Т,Г,а+ Е,Т,Р„а+Е$) (Ч 4 Еът>Р>а+Е>1>Г>а +Е$) (Ь 4> Р' ГъР>а+ЕъГаРаа +Е$) « — (Ь, 3, Е,Т,Р,а+ Е,Т,Р,, а+Е $) «-(Ь, 3, Е;Т>Р>а+Е>Т„Г+Е$) « — (Ь, 3, Е т Г а+Еъ, Т+Е $) « — (41, 3, Е>Т,Р,а+Е„Т $) « — (41, 3, Е,Т,Г,а+Е,Т,„Р»Т $) «- (4), 3, ЕЕТ,Р,а+ Е,Т,Г>, а в Т $) « — (а, 4, Е,Т,Р,а+Е,Т,Г,а, ».Т$) « — (Ь, 4, Е,Т Г,а+Е,Т,Г,а, »Т $) «(Ь> 3 ЕътаГ>а+Еъ1>Г» а»Т$) « — (Ь,З, Е,Т,Г,а+Е,Т„Р>>Т$) « — (41, 3, Е,Т,Р,а+ Е,Т„Р $) «-(а, 3, Е,Т,Р,а+Е,Т,Р„а$) « — (4„4, Е, Т,Г,а + Е,Т,Р,а,ь $) « — ((, 4, Егт>Р>а+Еат>Г а, е) В результате получается левый разбор Ь(Е>т>Гьа+Еат>Г>а) = =145245.
Теперь покажем, что алгоритм 4.1 действительно дает левый Разбор цепочки и> в соответствии с грамматикой 6, если он существует. Определение. Частичным лееыл> разбором назовем последовательность правнл, использованных прн левом выводе левовыводнмой цепочки. Будем говорить, что частичный левый разбор еоемеетим с входной цепочкой и>, если соответствующая левовыводнмая цепочка совместима с и>, т. е. ес терминальный префнкс до первого нетерминала является префиксом цепочки и>.
Пусть 6=(51, Х, Р, Я) — не леворекурсивная грамматика и и>= аа... а„— входная цепочка. Определим последоеательыоеть па пг °, Яо ... Соеместимых с и> ьтстичных левых РазбоРов. (1) 'п„=е представляет вывод нетермивала $ нз 5 (строго говоря, и — не разбор). ГЛ. 4. ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА 4.1, СИНТАКСИЧБСКИЙ АНАЛИЗ С ВОЗВРАТАМИ (2) л,— помер правила 5 — а, где а — первая альтернатива нетерминала 5.
(3) и; определяется так. Допустим, что 5„, ~хАУ, Пусть!)в такая альтернатива нетерминала А с наименьшим номером, если она существует, что х!Зу — хуб, где б либо е, либо начинается нетерминалом, и ху — префикс цепочки со. Тогда и;=.И,,АА, где й †ном альтернативы !3. В этом случае будем называть л, продолжением разбора и,, Если, с другой стороны, такой альтернативы р иет или 5 ,,=чьх для некоторой терминальной цепочки х„ то пусть ! †наибольш из чисел, меньших 1 в 1, для которых выполняется следующее условие: Пусть 5н =4ьхВУ и пу41 — продолжение разбора и,, причем у на последнем шаге разбора пу41 нетерминал В заменяется аль- тернативой аь.
Пусть а — первая из альтернатив нетерминала В, которая следует за аа в упорядочении альтернатив этого нетср- минала, и если записать ха„у — хуб, где б либо е, либо начи- нается нетерминалом, то ху — префикс цепочки ьо. Тогда и;= и;В, где  — номер правила  — уь .
В этом случае назовем п, модифьькаь)ией разбора и,, Если сформулированное условие не выполняется, то разбор и, не определен. !!ример 4.2. Для грамматики 6 из примера 4,1 и входной цепочки а+а получается такая последовательность совместимых частичных левых разборов: е 1 !3 14 145 1451 14513 !4514 1452 14523 14524 145245 2 23 24 Заметим, что последовательность совместимых частичных ле. вык разборов вплоть до первого корректного разбора тесносвязана с последовательностью цепочек, появля1ощихся в магазине Ы, Если отвлечься от терминальных символов, которые 330 могут быть в 11, то эти две последовательности совпадают, эа исключением того, что 4.! МожЕт содеРжать последовательности, не совместимые со входом. Когда в 1.1 появляется такая последовательность, сразу происходит возврат.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
