Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 3
Текст из файла (страница 3)
упр. 7.19) Кроме торо, может оказаться, что к некоторым пустым элементам анализатор никогда не Обращается, поэтому нет аеобходнмости заменять их нулями. В спязн с этим приобретает важность понятие независимых вершин в ориентированном ациклическом графе. Говорят, что две вершины У, и .Ч, орнентиронанного ациклического графа лгзиаисилнб если нет путн из Л', в Л/, или из ФА в Л!Р Алгоритм 7.
! можно было бы непосредственно применять для построения функции слабого предпюствонания для матрицы М, но а том виде, в каком оп Описан, он не позволяет максимизировать число н)лей, порождаемых для пустых элементов. Тем а ( ) т * 4 нс менее мы используем три перпых шага алгоритма 7,! для под строения графа линеаризации для М. Нз теоремы 7.! известно, что Г М имеет функции слабого пред- 1 2 3 ! Г,а„) ч ~ * 5 Рчс. 7 !О Приведенная матрачв слаб ш пргзжсстэованиа Ряс 7 Э Матрчаа отношения пргх.
иестваваэия Виртэ — Вебера лаз О,. !7 шествования тогда и ~ольио тогда, когда граф линеаризацнн для М ациклический. Независимые нар/инны графа линеаризации определяют, какие пустые элеьын~ы матрицы М лгожно сохранить. Другими словами, рааенстпо ),=д, дояжно выполняться только для независимых вершин Е, и ОГ Конечно, если нредпо пенне отдано условию )г — у,, то могут быть другие пары независимых вершин, для которых отвечающие им чисяа нельзя сделать равными.
Пример 7 5. Матрнпа отношений предшестяонания Вирта— Вебера для грамматики О„показана на рнс. 7.9. Стоябцы, отве- гл г. методы оптимиззпии синтАксичгских Анзлиззтопов чающие нетерминалам, выброшены, поскольку мы буд ем пользоват т ься этой матрнпей только в применении к алгоритм) тица „пе ренос — свертка".
Соотвегствующан приведенная матрица й по б о предшествоэапия показана на рнс. 7.!О, а построенны ог ией граф лннеэризапни изображен на рис. 7.11. В этом гр ф вершины, помеченные букиами Е, и О„независимы. Независимы также 6, и 6о а перши)гы Е, н Оп ие яиляются независимыми.
ь) Можно обобщить шаг (5) алгоритма 7.1 так, чтобы получались функции предшествования, макспмизирующие число нулей, отвечающих пу. етым элементам. Определю иие компонент векторов пред- шествования состоит в присваивании числовых меток вершинам графа линеаризапни. Всем вершинам из любого множества попарно не. зависимых вершин присваивается одно и тоже число, по О у вершины, являющейся предком одной нли более першин, присваемое число Рпс 7 11. ГраФ лппеприззэн«должно быть больше, чем у любого из ее потомков. А(псла присваияаются вершинам следугощим образом Во-первых, множество вершин графа линеаризапнн разбивается на кисти независимых вершин так, чтобы общее число пар Е, 6, объединенных в кисть, было по возможности ббльшим.
Вообще говоря, раз.тичных разбиений множества на кисти может быть много н некоторые пары Е, О могут оказаться предпочтительнее других. Эта часть пропесса вполне может оказагься большой комбнпзторной задачей. Как только граф разбит на множество кистей, иа последнем можно') иэестн линейный порядок (, прн кагором С ( С' для кистей С и С' тогда и только тогда, когда С содержит вершину, являющуюся потомком некоторой вершины из С'. Если С,, С,,...
, С вЂ” последовательность кистей, расположеппых э описан- А иом порядке, то всем вершинам из С, присваивается О, всем вершинам нз С, присваивается 1 и т, д, ') 11« пспглз — Пр«л череп. )а г ь Функции ппедшгстаоэАния Пример 7.5. Рассмотрим граф линеаризапии для О„изображенный на рнс. 7.11. Множество (Е„Ео Оз) — одна из кистей независимых вершин. То же можао сказать и о множествах (Ео 6„6,), (Е„О,), (6„6«) и (Е„О,).
Но кисть (6о 6„) не подходит, так как обе вершины в ней ( ) помечены бзкаой 6, и это не дает пулевого элемента и матрице слабого предшествоэация. Кисть (Е„Ог) может г окаааться предпочтительнее, чем (Е.„ 6,',, потом) что соотношение (и †(1, позволяет обнаружить огпибку, когда во входной кепочке появляются комбинации символов аа, а(, ) а нли ) (, ) в то время как с помощью соогпо)пения )и -= й, удается обнаружить ошибку только для пар Та и Т (. Кроме того, зэзютнм, что если мы обнаружим ошибк), когда появится аа, нам не удастся свернуть а я Е, и потому комбинации й символов Еа н 7'а никогда нс встретится. Р«с 7 12 Опопчптпз п«Ь Таким образом, одним иэ возможных и"А «птрпэп прехшс«1«ппз- п«я Аля бп. вариантов объединения першин в кисти буде~ (Е,), (Ео 6„, 6,), (Е,), (6,), (Е„О,).
Расположив кисти слева направо в описанном порядке, получим функции слабого предшествования (= (О, 2, 4, 1) ил= (4, 1, 3, 1). Зги фуикпин определяют матрицу предшествоаания, иаображенную на рис. 7.12. П 7лВ4. Преобразование матриц продшеетваввиня Пример 7.5 показывает, что к некоторым элементам матрицы предшествования Вирта — Вебера, соответствующим ошибочным ситуациям, алгоритмы разбора типа „перенос †сверт" для грамматик простого и слабого предшествоввния (алгоритмы 5.12 и 5.14) никогда нс обраща1отся.
Если удастся выделить этн этементы и чем-нибудь залюнцть, можно будет при нахождения функций слабого предшествовэпяя, покрывающих максимально возможное число элементов, которые отвечают ошибочным ситуациям, не принимать их во внимание. Чтобы понгычп как можно АюдифицггРоиать матРицы огне)пений предшествоиания, сначала договоримся, какие два алгоритма разбора типа „перенос †сверт" мы будем считать строго экниаалснгнымн.
Для записи алгоритмов разбора аоспольэуемся обозначениями, введенными в разд. 5.3 (том 1). гл г методы опгимизлции синтаксических лнллизлтоеов г ь эгнкции пгадшесгвоалпия ОпРеделеине. ПУгть Ат = ()м йг) ') и А, = ((.„д,) — два алгоритма разбора типа „перенос †сверт" для КС-грамматики 6 = (Ей 2, Р, Е). Будем иазьгзать А, и А,, строго зкзнгалетяяыли, если их пОведение одинаково дяя всех входных цепочек.
Другими словами, если входная цепочка ш принадлежит языку Е (6), то оба алгоритма разбора допускают т. Если т не принадлежит Е (6), то оба алгоритма вьщают сообщение об ошибке после одинакового чисяа шагов и на одной и той же фазе. Если это произошло на фазе свертки, то ошибочное отношение находитгя после просмотра одного и того же числа символов в магазинах.
Проанализируем, какие пустые элементы матрицы каиониче. ских отношеняй прсдшествовапня Вирта в Вебера можно изменять, нс влияя на поведение алгоритма разбора, построенного по этой матрице согласно алгоритму 5.12. Основная польаа от такого анализа состоит в том, что удается найти хорошие кисти для функций слабого предшествования, подобно тому, как юо делалось в предыдущем разделе. Пустые элементы, которые нельзя изменять, будем называть сущегтвеннымо.
Доказываемая ниже теореыа характеризует существенные пустые элементы. Сначала введем некоторые обозначения. Предположиы, что 6 -:(Н, 2, Р, Е) — КС-грамматика. Пусть М, †матри канонических отношени?1 предшествования Вирта †Вебе для 6. (Каноническими мы называем отношения, построенные прямо по определению.) Будем отмечать такие отношения предшествооання нижним индексом с.
Есяи между символамн Х и У не выполннется ни одно из отношений предшествования Вирта в Вебера, будем писать Х?,У. Ззтем можно построить произвольную ма~рину М,состоящую из ст ', и пустых элементов. Если М имеез те же размеры, по и М„то будем нааывать М матроцед отношений пргдшестголанал для 6. Есяи элемент (Х, У) матрицы М пустой, будем писать Х?У. Для построения алгоритма разбора юша „перенос †сверт" А, =()„ Е,) для грамматики 6, используюгцего отношения предшегтвояания Вирта в Вебера, которые содержатся в М„ можно применить алгоритм 5.12.
Применяя алгоритм 5.12, можно также псютроигь для 6 другой алгоритм разбора типа „переног— свертка" А = (Д рц использующий отношения предшествования, которые солержатся в М. Корректность алгоритма разбора А, гарантирует теорема 5.15, а аналогичной гарантии для А нет. Однако в теореме 7.2 устанавливается необходимое и достаточное условие для того, чтобы алгоритм А был строго эквивалентен алгоритму А,.
') Здесь (, — зто функция яереаоса †сверт, з йн — фуакаил свертке. Теорема 7.2. Алгоритм А строго зкзилатнтгн алгоритму А, тогда и только тогда, когда для осгх Х и У из Н 626 (5), а, Ь из Е 0 (б) а А из Н удоолетоорлются следующие чеглыре услозая; (1) (а) Если Х ею У, гпо Х с? У, (б) если Х ', У, то Х ' У, (в) если Х ), а, л?о Х ) а.
(2) Если Ь?,.а, гпо Ь? а. (3) Если А?,а, то либо (а) А?а, либо (б) для всех 7. из Н62, для которых А иЛ вЂ” прогала из Р, утогрждение 7.),а ложно. (4) Если Х?,А, лю лабо (а) Х? А, лабо (б) для всех 7. из Н6т, для которых А Еа — пролило из Р, утверждение Х сЕ,Л ложно. До к аз а тельство, Достатоснотаь. Согласно условию (1), шаги алгоритмов А и А, должны совпадать до тех пор, пока последний нс обнаружит ошнбку.
Следовательно, достаточно показатчь чзо если два аягорнтма разбора достигают конфигура. цин 6 =(Х, ... Х„, а,... а„я) и 61 — А ошибка, то ошибка. Более тога, механизмы обнаружепйя ошибки в алгорит- мах .,4 и А, совпадают. Сначала предположим, что в конфигурации 6 ?,(Х, а,) = ошибка, но ((Х, а,) ~ошибка. Покажем, что зто приводит и противоречию. Итак, предположим, что Х ?,а, верно, а Х ?а, не выполняется. По условию (2) символ Х долженбытьнетср- мицалом, По условию (3) для всех У, для иоторых правило Х вЂ” аУ принадлежит Р, утверждение )'),а, ложао, Из анализа алгоритма разбора, использующего технику пред- шествования, видно, что нетерминал помещается в верхушку магазина только в том случае, если предыдущим шагом была свертка.
Тогда в Р есть такое правило Х„а?', что прежде, чеы попасть в конфигурацию (), оба алгоритма сделали шаг (Х, ... Х,а?', а, ... а„я') 1-. Я. Но это означает, что У),аб получили противоречие. Другая возможность состоит в том, что н конфигурации (Г' д,(Х,... Х„, е) =-ошибка, но д(Х, ... Х, е) чьошибка. Надо рассмотреть лишь сл?чай, когда Х ),,а„Х„)а, н существует такое число з, что Х,?,Х,ч„прйчеч Х,— ',Х;„, и Х,— 'Х, для з ( г ( т, но Х,?Х,г, не выполняется. Считаем, что Х„,— нетермннал, поскольку,д, может поместить в магазин после Х, терминал только в том случае, когда Х,сй,Х,„или Х,— ',Х, „. По условию (4), если Хст Уа принадлежит Р, то ие может быгь Х, с(,У.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
