Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 87
Текст из файла (страница 87)
Зги конфигурации имеют тот же вид, что и конфигурации расширенпого МП-преобразователя, только в пих опущеио состояние и магазин предшествует входу. В равд. Ь.З.! мы дадим формальиое описание алгоритма типа „перенос †сверт'*. Вначале алгоритм находится в конфигурации ($, ааЬЬ$, е). Ему Надо догадаться, что осиовой правовыводимой цепочки ааЬЬ Явлиетса входЯщаЯ в иее иа левом конце пУстаи цепочка е и что эту основу надо свернуть к 5. Отложим пока описание самого механизма, обеспечивающего распознавание основы. Итак, алгоритм должен перейти в конфигурацию ($5, аа66$, 2). После этого ои перенесет в магазин входной символ, перейдя в коифигурацию ($Яа, и66$, 2). Затем догадается, что наверху магазина находится основа е и сделает свертку, перейдя в коифигурацию ($5аБ, аЬЬ$, 22).
Продолжая в том же духе, алгоритм сделает такую последовательность тактов: ($> ааЬЬ$, е) ) — ($5, аа66$, 2) ) — ($5а, аЬЬ$, 2) )--($5аБ, аЬЬ$, 22) 1 — ($5аБа, ЬЬ$, 22) ) — ($5аБаЬ, ЬЬ$, 222) ! — ($5аБаБЬ, 6$, 222) ! — ($5аБ, 6$, 2221) ) — ($5аБЬ, $, 2221) ! — ($5, $, 22211) )- допуск Г) $.2.2. 1.м [Ц-грвммвтмим В этом разделе мы опишем широкий класс грамматик, для которых всегда можно построить детерлп|иироваииые правые анализаторы. Ои состоит из ЕК(й)-грамматик. Говоря неформально грамматика будет ЕК(Ь)-грамматикой если для произвольного правого вывода Б=-я, =>я, =Р,я,.-„... =>,я,.=г в каждой правовыводимой цепочке яо читая ее слева «Вправо, можно выделить основу и определить, каким иетерми"алом надо ее заменить, дойдя при этом ие более чем до й-го и 1вола, расположенного справа от правого коица этой основы. Допустим, что я,,=яАш и я,=я))ш, где )) — основа цепоч.
"" ЯР Допустим далее, что яр=-Х,Х,...Х„. Если КС-грамматика является ЕК(й)-грамматикой, можно быть уверенным в следующем; гл. ь. однопроходный сннтлксит~гскин лнллнз вез возвратов (1) Зная Х,Х,... Хт и первые Й символов цепочки Х „... Х„тг, можно не сомневаться, что правый конец основы не будет достигнут до тех пор, пока не станет (=г '). (2) Зная ар и не более й символов цепочки со, всегда можно определить, что 11 — основа и ее надо свернуть к А. (3) Если а,,=5, то можно уверенно сигнализировать о том, что входную цепочку следует допустить. Заметим, что, проходя по последовательности аег а „,, а, мы вначале видим только цепочку НКЗТь (ам) = г(КЗТ„(г).
На каждом шаге цепочка символов, на которые мы „заглядываем вперед" (аванцепочка), состоит из й или менее терминальных символов. Теперь перейдем к определению ЕК (й)-грамматики, но преж- де введем простое понятие пополненной грамматики. Определение. Пусть 6=(М, Е, Р, 5) — КС-грамматика. Попол- ненной грамматикой, полученной из 6, будем называть грамма- тику 6'=(р)()(5'), Е, Р0(5' — 5), 5'). Другими словами, это просто 6 с новым начальным правилом 5' 5, где 5' — новый начальный символ, не принадлежащий р). Будем считать, что 5 — 5' — нулевое правило грамматики 6', а остальные правила занумерованы числами 1, 2, ..., р. Это начальное правило до- бавляется для того, чтобы свертку, в которой используется ну- левое правило, можно было интерпретировать как сигнал о том,' что цепочка допускается.
Дадим точное определение ЕК (й)-грамьтатики. Определение, Пусть 6= — (!ч, Е, Р, 5) — КС-грамматика и 6'= (М', Е, Р', 5') — полученная из нее пополненная грамматика. Будем называть 6 1К(й)-грамматикой для й) О, если из ус- ловий (1) 5' ~с,,аАсг=>она~со, (2) 5' =р,„уВх~о,,айу, (3) Р1КЗТ (нт) =НКЗТ (у) следует, что аАу=уВх (т. е. а=-у, А =В и х=у), Грамматика 6 называется ).К-гральнатикой, если она ЕК(й)- грамматика для некоторого й) О. Ннтуитивно это определение говорит о том, что если а()со и а))у — правовыводимые цепочки пополненной грамматики, у ко торых НКЗТь (со) = НКЗТь (у), и А — () — последнее правило, использованное в правом выводе цепочки арке, то правило А- () должно использоваться также в правом разборе при свертке ') Утверитдеиие ие очень четко сфтрчулироиаио и, ссли его по оииигть буквально, для Ж (и)-триммятики неверное.— Прим.
ред. лзс дгтгнмнниговлннын восходяшия синтлксичгскин лнллиз а()у к аАу. Так как А дает (1 независимо от нт, то ЬК(й)-условие говорит о том, что в г!КЗТь(со) содержится информация, достаточная для определения того, что а(1 за один шаг вывоится из аА. Поэтому никогда не может возникнуть сомнений относительно того, как свернуть очередную правовыводимую цепочку пополненной грамматики.
Кроме того, работая с 1 К (й)- грамматикой, мы всегда знаем, допустить ли данную входную цепочку или продолжать разбор. Если начальный символ 5 не встречается в правых частях правил, то в определения 1.К(Й)- грамматики вместо 5' можно взять 5, а именно 6 = (!ч, Е, Р, 5) будет )-К (й)-грамматикой, если из трех условий (1) 5=>,'аАсо=,>,а~в, (2) 5 =>,' уВх=>,айу, (3) Е!КЗТь(цт) =Р1КЗТ„(у) следует, что аАу.=уВх.
Мы не всегда можем пользоваться этим определением, потому что если начальный символ встречается в правой части некоторого правила, то нельзя сказать, достигнут ли конец входной цепочки н ее нужно допустить, или надо продолжать разбор. Пример 3.22. Рассмотрим грамматику 6 с правилами 5 — Ва(а Если игнорировать ограничение, касающееся появления начального символа в правых частях правил, и тюльзоваться вторым определением, то 6 придется считать ЕК(0)-грамматикой. Однако, согласно правильному определению, 6 не 1.К(0)- грамматика, так как из трех условий (1) 5Ф ~оо,, 5' -Ьо,,5 (2) 5':- "о'5'=>о т5а (3) НКЗТ, (г) =Р!КЗТо (а) =-и не следует, что 5'а=5.
Применяя определение к этой ситуации, имеем а=г, р=-5, тз=е, у.=г, А =5', В =-5, х =г и у = О. Проблема здесь заключается в том, что нельзя установить, является ли 5 основой правовыводимой цепочки 5а, не видя символа, стоящего после 5 (т. е. наблюдая „нулевое" количество символов). В соответствии с интуицией 6 не должна быть К(0)-грамматнкой и она не будет ею, если пользоваться первым определением. Зто определение мы и будем использовать иа протяжении всей книги.
Е) В данном разделе мы покажем, что для каждой 1К (Й)-грамматики 6 =- ()т(, Е, Р, 5) можно построить детерминированный "равый анализатор, который ведет себя следующим образом. 425 ГЛ. 3. ОДНОПРОХОДНЫЙ СИНТАКСИЧЕСКИЙ АНАЛИЗ БЕЗ ВОЗВРАТОВ зл, детеРминиРОВАнный восходящип синтАксическип АнАлиз Прежде всего, этот анализатор строится по пополненной грам. матике 6'. Ведет он себя во многом так же, как анализатор типа „перенос — свертка", введенный в примере 5.21, за исклю. чением того, что после каждого символа грамматики в магазин будет записываться специальный информационный символ, называемый 1К(й)-таблицей.
Эти 1 К(А)-таблицы помогут определять, Двиалтаиа ууар алла а Ь а 8 а Ь то т, тз т, тт Рис. 5.9. сй (1).анализатор длн грамматики О (~ — свертка, при которая применено Ье правило, о — перенос, А — допуск, Х вЂ” ошибка). что надо делать на очередном шаге — свертку или перенос, и в случае свертки — какое правило при этом применить. По-видимому, наилучший способ описать поведение 1К(Ь)- анализатора — это рассмотреть подходящий пример. Возьмем грамматику 6 из примера 5.21, котораи, как легко проверить, является (.К(!)-грамматикой.
Пополненная грамматика 6' состоит из правил (0) 5' — 5 (1) 5 --5 ИЬ, (2) 5 — е (.К(1)-анализатор для грамматики 6 приведен иа рис. 5 й ЕК(й)-анализатор для КС-грамматики 6 — это ие что иное, как множество строк большой таблицы, каждая строка которой на зывается 1.К(й)-таблицей. Одна строка, здесь это Т„, выделяется в качестве начальной ( К(й)-таблицы. Каждая 1К(и)-таблица состоит из двух функций — функ~(ми действия 1 и функции переходов яг 426 (1) Аргументом функции .действия 1' служит цепочка и Е Х*" (оиа называется аванцспочкой), а соответствующее значение ) (и)— Один из символов „действий": перенос, свертка 1, ошибка или допуск. (2) Аргументом функции переходов у служит символ ХЕ Ь) 0Х, а соответствующее значение а(Х) — либо имя некоторой 1.К(й)- таблицы, либо ошибка.
Сейчас мы не будем объяснять, иак построить такой анализатор, а Отложим это до разд. Ос.2.3 и 5.2.4. 1К-анализатор ведет себя так же, как алгоритм типа „перенос — свертка", используя в процессе работы магазин, входную и выходную ленты. Вначале магазин содержит начальную ).К(й)- таблицу Т, и ничего больше. !1а входной ленте находится анализируемая цепочка, а выходная лента вначале пустая. Если предположить, что надо разобрать входную цепочку ааЬЬ, то начальной конфигурацией анализатора будет (Т„ааЬЬ, е). Затем разбор будет осуществляться согласно следующему алгоритму. Алгоритм 5.7.
1.К(й)-алгоритм разбора. Вход. Множество лх ).К(Ь)-таблиц для ЕК(й)-грамматики 6=-(Х, л, Р, 5) с таблицей Т, Евг, выделенной в качестве начальной, и Входная цепочка ЗЕ 2,", которую надо разобрать, Выход. Если ЗЕЕ(6), то правый разбор цепочки г в грамматике 6, в противном случае сигнал об ошибке. Метод. Выполнять шаги (1) и (2) до тех иор, пока не будет допущена входная цепочка или не встретится сигнал об ошибке. В случае допуска цепочка на выходной ленте представляет собой правый разбор цепочки г. (1) Определяется аванцепочка и, состоящая из й очередных входных символов (или менее чем й символов, если обрабатывается конец входной цепочки).
(2) Функция действия ) таблицы, расположенной наверху магазина, применяется к аванцепочке и. (а) Если ) (и)=- перенос, то следующий входной символ, скажем а, переносится со входа в магазин. К а применяется функция переходов д верхней таблицы магазина и определяется новая таблица, которую надо поместить наверху магазина. После этого вернуться к шагу (1). Если следующего входного символа нет или значение д(а) не определено, остановиться н выдать сигнал об ошибке.
(б) Еслиу(и)=свертка (и А — сз — правило с номером(, то '~х-. =х, ..х,,- ° „н.,х з"д ТзХхтхХх Х,Т,. Устраняя из магазина 2(сх( символов, мы устраняем основу вместе с промежуточными ск-таблицамн. 427 Гл. 3. ОднОпРОхОдный синтАксическип А нАлиз Без возвРАтов зд, детенминииовАннып восходящии синтАксическии ~нАлиз выходной ленте записывается номер правила с'. Наверху магазина оказывается тогда новая таблица Т', и ее функ цня переходов применяется к А для определения следую. щей таблицы, которую надо поместить наверху магазина, Помещаем А и эту новую таблицу наверху магазина и переходим к спагу (!).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
