Теория синтаксического анализа, перевода и компиляции - Том 1 (943928), страница 77
Текст из файла (страница 77)
е. сделать очередной шаг вывода, видя только законч конченную часть цепочки а; и „еще немножко", а именно следующие е й входных символов цепочки ж. (Заметим, что законченная часть ть цепочки и является префиксом цепочки ю.) Важно отметить, т , что если мы не видим всей цепочки го, когда строится то фактически не знаем, какая терминальная цепочка в конечном счете выводится из Я. Таким образом, из условия, 8 рве В 1 Дерево вывода цепочка юху НаЛаГаЕМОГО На 1.1.(й)-ГраММатниу, ВЫтЕКаЕт, Чта СС1е, ПО СущЕСтВу не зависит (не считая следующих )е терминальных символов) от того, что выводится из незаконченной части цепочки ссн В терминах деревьев этот процесс выглядит так: дерево вывода цепочки шху в 1Л (л)-грамматике строится, начиная с корня, детермииированно сверху вниз.
А именно, если уже построено частичное дерево вывода с кроной шАО, то по гп и первым й символам цепочки ху можно сказать, какое правило применить к А. Набросок завершенного дерева показан на рис. 5.1. Напомним, что в гл. 4 для КС-грамматики 6=(Х, Х, Р, В) была опРеделенафУнкциЯ НКБТао(са) (где )е — целое число и ц Е (К()л)*), равная (щЕ Х* (либо (и1) < й и а ~ого, либо )п7(=й " се=-:>оюх для некоторого х). Мы будем опускать )е и 6, если это не вызовет недоразумений, и писать просто НКБТ. Если ц состоит только из терминалов, то НКБТА(ц)=-(и1), где гэ — это первые )е символов цепочки сс при ~а()й и гя=ц "Ри ~ц~ < й.
В этом случае будем писать Е!КЯТА(а) =го, а не (я1). Значение НКЯТАо(сс) легко находится по заданной грамматике 6. Соответствующий алгоритм мы опишем в равд. 5.1.6. 375 Гл. 5. ОднопРОходнып синтАкгическип АнАлиз вез ВОВВРАтОВ КЬ СЬМРГРАЯМАТИКИ Онределение. КС-грамматика 6 =- (Ь(, л, Р, 5) называется 1Л.(л)-грахьиалгикой для некоторого фиксированного л, если из существования двух левых выводов (!) 5=О', юАа=:;>,га()и=>" гех и (2) 5 =>,' гаЛ а =>, цчнх =>* гау, для которых Р1КЗТ„(х) =-Г1КЗТ„(у), вытекает, что р=у.
Говоря менее формально, 6 будет ) Е(н)-грамматикой, если для данной цепочки гаАОЕ(1(1Х)" и первых й символов (селя онн есть), Выводящихся из Агх, существует не более одного правила, ноторое можно применить к А, чтобы получить вывод какой-нпбудь терминальной цепочки, начинающейся с га и продолжающейся упомянутыми л терминалами. Грамматика называется Е(.-грахьиалгикой, если она Щй)-грамматика для некоторого Ь. Пример 3.2.
Пусть 6, состоит из правил 5 — аЛ5 ~ Ь, А- а(Ь5А, Интуитивно 6, является Ы.(1)-грамматикой, потому что, коль скоро дан самый левый нетерминал С в левовыводимой цепочке и следующий входной символ е, существует не более одного правила, применимого к С н приводящего к терминальной цепочке, начинающейся символом е.
Переходя к определению 1.!.(1)-грамматики, мы видим, что если 5=;>",га5а=>,гейм=!>,"~гх и 5.=Ф, ю5а =>, шуа=>, юу и цепочки х и у начинаются одним и тем же символом, то должно быть р =у. В данном случае если х и у начинаются символом а, то в выводе участвовало правило 5 — аА5 и (1=-у=аА5. Альтернатива 5 — Ь здесь невозможна. С другой стороны, если х и у начинаются с Ь, то должно применяться правило 5 Ь и р= у= Ь. Заметим, что случай х=у — е невозможен, так как из 5-в грамматике 6, не выводится е.
Когда рассматриваются два вывода 5=>,*гаЛа= >,афа=о,"ахх и 5=!>,"геАО=>,анлх~;юу, рассуждение аналогично. Г( Грамматика 6, служит примером так называемой простой Щ1)-грамматикп (или разделенной грамматики). Определение. КС-грамматика 6 †.-(Ь(, Х, Р, 5) без е-правил называется простой ЕЕ(1)-грамматикой (нли разделенной грамматикой), если для каждого Л Е гч все его альтернативы начинаются различными терминальными символами. Таким образом, в простой 1.1.(1)-грамматике для данной пары (А, а), где А Е (х и а Е 5, существует нс более одного правила вида А — аа.
376 Пример 3.3. Рассмотрим более сложный случай — грамматику определяемую правилами 5 е) ОЬА, А — 5аа ( Ь. Покажем, что 6,— это Е1(2)-грамматика. Для этого докажем, что если юВа— В любая левовыводимая цепочка грамматики 6, и юхЕЕ(6), тОВ я В 6 найдется не более одного правила В- б, для которого Г(К ВТ,фа) содержит Р1К ЗТ.,(х). Допустим, что 5=О,* ю5а =>, иба=>', и 5=>,' ю5а=.;>, гауа=о, "юу, где первые два символа цепочки х (если они есть) совпадают с первыми двумя символами цепочки у. 'Гак как 6.,— линейная грамматика, то а Е (а+Ь)*. На самом деле можно сказать больше: либо ю= а =-е, либо последним участвоВало в выводе 5=>;цг5а правило А 5аа.
(Другим способом 5 в левовыводимой ц:почке появиться не может,) Таким образом, либо а =е, либо сг начинается с аа. Допустим, что при переходе от ю5а к га()а применялось правило 5 е. Тогда р =е и х †ли е, лабо начинается с аа. Аналогично, если при переходе от ге5сг к жуя применялось правило 5 †-е, то а =-е и у †ли е, либо начинается с иа. Если при переходе от ге5и к ю(1сг применялось 5 в аЬА, то (1А- аЬЛ и х начинается с аЬ. Аналогично, если при переходе от ВВ5а к алнг применялось 5 - аЬА, то у †..ОЬА и у начинается с аЬ. Итак, нет иных возможностей, кроме х=у=-е, х и у начинаются с аа, х и у начинаются с аЬ. Из любого другого условия, которое можно наложить на первые два символа цепочек х и у„ следует, что либо один, либо оба вывода невозможны.
В первых двух из рассмотренных выше случаев в обоих выводах применяется правило 5 —.е и р=-у=-е. В третьем случае должно применяться 5 — -аЬА и () у =-ОЬВ. В качестве упражнения докажите, что ситуация, при которой справа от рубежа рассматриваемой левовыводнмой цепочки стоит символ А, не противоречит определению ЕЕ(2)-грамматики. Проверьче также, что 6, не является 1Л41)-грамматикой, (~ Пример 3.4. Рассмотрим грамматику 6, = ((5, А, В), (О, 1, а, Ь), Р, 5), где р„состоит из правил 5 —.А(В, А — аАЬ)0, В аВЬЬ|1, Здесь В (6,) = (а"ОЬ" ) и ~ 0) () (а" 1Ь'" )н ~~ О). 6, не является 1)-(я)-грамматикой ни для какого й. Интуитивно, если мы начинаем с чтения достаточно длинной цепочки, состоящей нз символов а, то не знаем, какое из правил 5 А и 5 —.В было ВРименено первым, пока нс встретим 0 или 1, Обращаясь к точному определению ЕЕ((г)-грамматики, положим ю=-а.=е, р = А, у--В, х=аеОЬА и у=-аА1ЬРА. Тогда выводы 5 =>1 5=ос А =>," а'ОЬ' 5 >1 5 =->, В =>," ОА1Ь'Р ~~ответствуют выводам (1) и (2) определения.
Первые й сим'о лов цепочек х и у совпадают. Однако заключение () =у ложно 377 гл. з однопроходный синтлксичвскнп лнллиз ввз вознрлтов Так как й здесь выбрано произвольно', то бв не является ) 1-трам матикой. В гл. 8 мы увидим, что для языка Е(6,) не существует 1Л. (п)-грамматики. 5.4Л. Предсказывающие алгоритмы разбора Покажем, что разбор для ЕЦй)-грамматики очень удобно осУществить с помощью так называемого П-предсказываюи(его ал.
горитма Разбора. )з-предсказывающий алгоритм А для КС-грач. матики 6=()Я(, Х, Р, Я) использует входную ленту, магазин и иагввии Рнс. 5.2. Предсказывающий ллгорнтм разбора. выходную лепту (рис. 5.2). Этот алгоритм пытается проследить левый вывод цепочки, записанной на его входной ленте. При чтении анализируемой цепочки, находящейся на входной ленте, входная головка может „заглядывать вперед" на и очередных символов (отсюда число й в названии й-предсказывающего алгоритма).
Эту цепочку из й символов, увиденную впереди входной головкой, будем называть аеапцепочкой'). На рис. 5.2 аванцепочкой служит подцепочка и входной цепочки ших. Магазин содержит цепочку Хсзр, где Ха — -цепочка магазинных символов, 5 — специальный символ, применяемый в качестве маркера дна магазина, и Х вЂ” верхний символ магазина. Алфавит магазинных символов (без 5) будем обозначать Г. Выходная лента содержит цепочку и, состоящую из номеров правил.
Конфигурацию предсказывающего алгоритма разбора будем представлять в виде тройки (х, Ха, и), где (1) х — неиспользованная часть первоначальной входной цепочки, ') 1ермнн образован по анллогнн со словами „знансцена", „алангзрзк " т. п.(в орнгнналс 1оокэйсад з1поц). †Пр. лврвв. Зта б ! ыдл) ГРАммлтики (2) Ха — цепочка в магазине (Х вЂ” верхний символ), (3) и — цепочка иа выходной ленте. Например, на рис. 5.2 изображена конфигурация (их, Хсзр, п). работой и-пРедсказывающего алгоритма 4 руководит управляюи(алтаблицаМ,задающаяотображениемножества(Г () (8)) хл"л в япюжество, в которое входят (1) (р, 1), где (1ЕГ', а 1 — номер правила (предполагается, что 8 будет либо правой частью 1-го правила, либо некоторым его представлением), (2) выброс '), (3) допуск, (4) ошибка.
Алгоритм анализирует входную цепочку, проделывая последовательность тактов, очень похожих на такты преобразователя с магазинной памятью. На каждом такте сначала определяются аванцепочка и и верхний символ магазина Х. Затем для определения того, что действительно надо делать, рассматривается элемент М(Х, и) управляющей таблицы. Как и следовало ожидать, такты предсказывающего алгоритма мы опишем в терминах отношения ~ —, определенного на множестве конфигураций.
Пусть и=Е(рБТ (х). (1) (х, Хсз, и) )-(х, ()а, пю), если М(Х, и) = (б, 1). Здесь верхний символ магазина Х заменяется цепочкой ()ЕГ* и к выходу добавляется номер правила П Входная головка не сдвигается. (2) (х, азз, и) г-(х', а, и), если М(а, и) =выброс и х =ах'.
Когда верхний символ магазина совпадает с текущим входным символом (первым символом аванцепочки), он выбрасывается из магазина н входная головка сднигается на один символ вправо. (3) Если алгоритм достигает конфигурации (е, 5, и), работа прекращается и выходная цепочка и называется Разбором первоначальной входной цепочки. Будем предполагать, что всегда М Ь, е) =- допуск, и конфигурацию (е, $, и) будем называть допуасаюи(ей. (4) Если алгоритм достигает конфигурации (х, Ха, и) и М (Х, и) = ошибка, то разбор прекращается и выдается сообщение об ошибке, Эту конфигурацию (х, Ха, п) назовем ошибочной. КонфигУРацнЯ (ш, Хзб, е), где ги Е Е' — анализиРУемаЯ цепочка, а Х,— выделенный начальный символ, называется начальной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
