Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 26
Текст из файла (страница 26)
грамматикой. В настоящей главе мы исполины иерархию соотношений между различными классами грамматин, Можно задаться вопросом о том, какой класс языков порождается грамматиками из данного класса. В этой главе мы увидим, что большинство классов грамыатнк из гл. о порождает в точности детерминированные КС.языки. Точнее, будет показано, что каждый из следующих классов грамматлгн порождает в точности детерминированные КС-языки; [1) ЩГ)-грамлгатнкн, (2) (1,1)-ОПК-грамматики, (3) обратимые граллматики (2,1)-предшествования, (4) простые грамматики со смешанной стратегией предшество- вания.
При выводе этих результатов применяются алгоритмы преобразования грамматик одного типа в грамматики другого типа. Таким образом, для каждого детерминированного КС-языка можно найти грамматику, анализируемую с помощью алгоритыа обратимого (2,!)-предшествовання или алгоритма со смешанной стратегией предшествования.
Однако многие ив этих преобразующих алгоритмов зачастую дают грамматики, слишком болыпие для практического использования. Интерес представляют три собственных подкласса детерминированных КС-языков: (П языки простого предшествовапия, (21 языки опсраторного предшествования, (3) [.1-языки.
ГЗЭ п.) теОРия ).с-языкОВ 8.1. ТЕОРИЯ ЕЫЯЗЫКОЯ 141 140 Гл В тсОРия лп1'ЯРииииРОплииОГО РлзБОРл Языки операторного предшествования образуют собствениый подкласс языков простого..предпгествованяя, и он не сравним с классом 1.]. языков В гл. 5 мы видели, что класс языкои, порождаеыых обратимыми грамматиками слабого предшестаовання, совпадает с классам языков простого предшествования. Зта иерархия язысш) гпражепа на рпс. 8.!. Рпс З.). Иерархия летппыюшраз нных Кб.япыкап.
)ПП вЂ” Языка ярк га прппвпсат~аппппп, ОП вЂ” Языка аппрптарпага прахшас~папл14япп В данной главе мы получим эту иерархию и и)метим ваиболее характерные черты кюкдага класса языков. Глава состоит из трех разделов. В первом изучаются С(.-языки и пх свойства. Во втором рассматривается класс детерминированных пзыков, а в третьем в языки простого и операторного предшествоваиия. Зта глава является своего рода лакомствол) †п строгой диете теории компиляции оаа не существенна, и при первом чтении ее можно опустить '). ') Нпрачпы, чптатппп, «атарып па лыаят лакаыстп, когут вовсе н паа пе паппппшатьсю Начнем с основных результатов, касающихся С).-языков и грамматик. Мы докажем следующие шесть утверждении: (!) Каждая Щй)-грамматика является СР(й)-грамматикой (теорема 8. !].
(2) Для каждого Щй)-языка существует 1Л(й-Р1)-грал)мятика в нормальной форме Грейбах (теорема 8.8). (3) Проблема, эквиваленп)ы ли две произвольные С!..грамматики, раарешима (теорема 8.8). (4) Язык, не содержащий пустого слова, является 1.!.(й)-язы. коч тогда и только тогда, когда оп имеет неукорачнваю)цую (т. е. без е-правил) Щ]г-~; !)-грамматику (теорема 8.7). (5) Для й" О маожество СС(й).языков является собственным подмножеством множества Щй+ !)-языков (теорема 8.8).
(8) Существуют СВ-языки, не являющиеся С(.-языками (упр. 8. !. ! ! ). 8.1.1. ЕВ и лй-грамматики Докажем сначала, что каждая ).].(й]-грамматика является СЯ(й)-грал)матикой. Зго утверждение неформально можно обосновать так. Рассмотрим дерево вывода, ввображенное схематичесии на рис.
8.2. Согласно СК(й)-условию, прп просмотре входной пепочки мху правило А а должно распознаваться после того, как станут известны подпепочка шх и множество Р]В5Тл(у). С другой стороны, в СС(й)-условий для распознавания пра. пила А м требуется знать только ю и а Р!КВТ (ху]. Поэтому Шй)-условие должно быть более сильным, чеч СВ(й)-условие, так что каждая Т С(й)- х грамматика должна быть СК(й)-грамма тикай.
Опишем теперь зто формально. Рпс а.з. ппарасап л- Пусть дана ьь(й)-грамматика б и в Рева пываха. ней два дерева разбора. Допустим, что первые т симвоюв кроа эю)х днах деревьев совпадают. Тогла каждой вершине одного дерева, слева от которой находится не более т — й листьев, помеченных терминалами, соответствует „идентичная" вершина в другом дереве,, Зта связь изображена на рис. 8.3, где заштрихованная область представляет пидентич.
ные" аер)пины Мы считаем, что ]ш) =т — й и Р1кбпТЛ(хл) =РПВТл(х„). Сформулируем иаш результат в виде леммы: гл з. ТБОРия дБРБРмиииРОнлнного РлзБОРл З.Л. ТБОРИЯ ЛЛ" ЯЗЫКОВ Лемма 8.1. Лусть 6 — (.г: (й)-гриммиггзихи и 5~~э,шхАа=р)тххх и 5~х ' ш ВО~хм х дго таких левых выводи, что Г)РВТх(тххх) =Р!КБТг(шзхз) пуи (=й+гпах((ш,(, )ш,!). Другими словами, ло крайней мере й символов, союящих в ш,х, и ш,гз пиле ш, и ш„совладают.) (1) Если т, = т„то ш, = Ы„А = В и а .= 8. (2) Если т, < ти то 5~)мы,Аа=рг * '"'ш,В(1=р*ш,х,.
г я ю ех ю юз о Рис. Б.з. Днн дерезе разбора ддя ьщд)-грзииитин». Доказательство, По определению Щй)-грамматикзг при т, -те первые т, шагов вывода 5~! 'ЫзВ(1 представляют собой вывод 5~)юшхАИ, так как ва каждом шаге этих выводов аванцепочки совпадают. Отсюда сразу следуют утверждения (1) и (2). С) Теорема 8. 1, Веяния 1).(й)-грамматики х) является ВК(й)- грамматикой.
Доказательство. Пусть 6=-(1), Х, Р, 5) — 1Л.(й)-грамматика. Предположим, что она не Щй)-грамматика. Тогда в пополненной грамматике существуют такие два правых вывода (8.16) 5' =р', аА х, =р, абхг (8 1.2) 5' ~) ТВу ~, убу что убу = а()ли для некоторой цепочки к„для которой РИ(ОТЛ(х„) — ГЦ!8ТЛ(хх). Поскольку 6 по предположению не 1 В(1)-грамматика, можно считать, что аАх,ФТВу, Можно считать, что в обоих этих выводах г и ! Оба больше нуля. В противном случае было бы, например, 5' =р' 5' =р 5 5~э Ву=р5бу ') Везде е этой денге ореднодегзегсн, ито гр,имз инз ие ннннг бесоогезних орезид.
ззз а это означало бы, что 6 леворекурснвна и, следовательно, не является С).-гралгматикой. Поэтому в оставшейся части доказательства мы будем считать, что в выводах (8.1,1) и (8.1.2) 5' можно заменить на 5. Пусть х„, хр, х„ и хе †терминальн цепочки, выводимые иа а, б, у и б соответственно, причем хехрх, хэхзу, Рассмотрим левые выводы, соответствующие выводам (8.1.3) 5=э', ИАБ, ~, а()х, =ь, 'х„хрх, (8.1.4) 5~;уду~,убу=р",х,х,у Точнее, пусть (8. !.6) 5ын; х„АО =Ргхнбц ~;х хгт) мь) х„хгхг (8.! 6) 5~;х ВО~ля 80~)х хзО=рххгхзу где ц н 0 — подходящие цепочки из (Х() 2)'.
Согласно лемме 8.1, либо последовательность зпагов в выводе 5 ~)Б,Ат) представляет собой начальную послеловательиость шагов в выводе 5~; х„В9, либо обратно, Исследуем первый случай; второй исследуется аналогично, Итак, вмвод 8.1 6 можно записать в виде (8.!.7) 5=о,'х,Аз) =ргхнбц~;х,ВО~,х„бО=Р)х„я~О~)х„х у Рассмотрим дерево разбора Т, соответствующее выпаду (8.1.7). Пусть пд — верншна, отвечающая в цепочке х„АО снлгнолу А, а пд — вершина, отвечающая в цепочке х ВО символу В.
Эти вершины показаны на рис. 8.4. Залгегим, что и мажет быть потомком верхпины я,. Цепочки ха и ле нс могут перекрываться частично: либо опн не пересеказотся, либо хз — полцепочка цепочки хр. Мы изобразили их на рис. 8.4 частично перекрывающимися лишь для того, чтобы легче было рассуждать в обоих случаях. Рассмотрим теперь два правых выпада, связанных с деревом разбора Т, В первом Т расширяется вправо до вершины ид включительно; во втором Т расширяется вплоть до верн!ивы пд. Последний вывол можно записать так: 5~1 ТВу=ь,убу На самом деле это вывод (8.1.2). Правый вывод вплоть до еер. шицы пд имеет вид (8,1.8) 5=р, а'Ахз~,а ()хз для некоторой цепочки а'.
Потом мы докажем, что а'=-а, а сейчас примем это на веру и, получив противоречие С!.(й).условию, покажем тем самым теорему. Итак, пусть а) =сз. Тогда убу — -а бхз=-айх,. Поэтому для продолжения выводов (8.1.2) н (8.1.8) до терминальной цепочки 143 ЕЛ ТЕОРИЯ Г.Ь ЯЭЫКОП шт хз Рнс, 8.4, Дерево рвзаор Т. Г45 гл в теория дгтгрминиповхниого Рхзворх х хеу можно использовать один и тот же правый вывод. Но поскольку ьеы считаем веригины иг н пв раэличнымн, выводы (8.!.2] и (8.1 8) различаются, а, следовательно, различаются и законченные выводы. Ого!ода вытекает, что цепочка х хьу имеет два разных правых вывода и, значит, грамматика В неоднозначна.
Согласно упр. 5.1.3, 1С-грамьгатика не ьюжет быть неоднозначнон. Поэтому б вопреки допущению це является (.(.-грамьгатикоут, 3 .ь. хт Теперь докажем, что а' =а. Заметим, что цепочка а' составлена иэ выписанных слева направо меток тех вершин дерева Т, прямой предок которых является предком вершины их. (Е)нтатель может самостоятельно проверить это свойство правых выводов.) Рассмотрим опять левый вывод (8.1.5), имеющий то же самое дерево разбора, что н правый вывод (8.1 3).
Пусть Тн— дерево рпчбпра, спязниное с выводом (8.1.3). Шаги выпада (8.!.5) вплоть до получения цепочки х Ат! совпадают с шагами выво да (8.1.7) вплоть до получения пеночки хпАт). Пусть пе — вершина дерева Т', соответствующая нетерминалу, который а выводе (8.1.7) заменяется на шаге х„дц=>,х Вц, Пусть П вЂ” прямо упорядоченное') множество внутренних верпшн дерева разбора Т вплоть до вершины пл, а П' — прямо упорядоченное множество внутренних вершин дерева Т' вплоть до вершины пл. Тогда т-я г) П вЂ” этп послеховвтевь ость внутренннх нершнн хереее Т, пзвтнх в тон порвлке, в котором ьетернннелы, отвечвющне зтннвершннен, рвзворвчнвеюкн в левом внвохе.
вершина множества П согласуется с г-й вершиной множества П' в том смысле, что обе они имеют одинаиовые метки и их соответствующие потомки либо согласуются, либо расположены справа от пл и л'„соответственно. Вергпины дерева Т', прямым предком которых является предок вершины пл, имени такие метки, что если их выписать слева направо, они образуют цепочку а. Но эти вершины согласуются с теми вершинами дерева Т, которые образуют а', поэтому а' —..а. Теорема доказана. Ш Грамматика В- А1В А аАЬ)Π — аВЬЬ(1 Рве, 8 5. Соотношение между классами греннвпгк. (Лà —.тееознвлнзнруенне грвннвтвкн, Пà — превовнвльзнруеные греннвтнкн.) является С)ч(О)-грамматикой, но ие ).)..грамьтатикой (пример 5.4), так что включение класса )-Ь-грань!агни в класс (.ц-грпьгматии собственное.
На самом деле, если рассмотреть классы ГС- и СВ- граьтматик вместе с классами левоанализпруемых и праноапализнруемых (при помощи ПЫП-автомата с концевым маркером) грамматик, то, согласно теоремам 5.5, 5.12 и 8.1, получится картина, изображенная на рис, 8.5. Ь!ы )тверждаем, что каждый из шести классов грамматик на рис. 8 5 непуст. Ыьг знаем, что СГ.грамматика существует, так что надо доказать следующее: гл ь. ТБОРия детеРминиРОБАнного РАЭБОРА А.! ТЕОРИЯ ЬЬ-НЗЫКОВ Теорема 8.2.
Существуют грамматики, которые ягяяютсл (1) ЕВ и лггоаиализиругмыми, ио нг 1Е, (2) '1.В, на нг яегаанализиругмыми, (3) лево- и прагаанаяизиругмыми, иа не ЕВ, (4) прагаанализируемыми, на не ЕВ и ие Аггааная1тируемыми, (5) легоанализируемыми, но кг прагаанализируемыми. Доказательство. Каждая из следующих грамматик принадлежит соответствующему классу. (1) Грамматика 6, с правилами 5 А|В А ааА |па В ааВ|а является 1В(1) и левоанзлизируемой, но не 11.. (2) Грамматика б, с правилами 5 АЬ)Ас А — Ад|а В а является 1(7(1), но не левоанализируемой. (См, пример 3.27, том 1.) (3) Грамматика 6, с правилами 5 АЬ1вс А-.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
