Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 13
Текст из файла (страница 13)
Рр-недостижимое множество Т' ЕЕ(й)-таблиц, эквиналентное Т. дбстад. (1) для каждого элемента (Т, и, г) из уг, где Т=(ПАХ заменгнь ) (и) на свертку г. (2) Предположим, что (Т,и, г)Ела и правило г есть А а. Для всех 7" = <)', й'>, для когорых ПОТО(7', и) .= Т н и' (Л) — яд заменить д'(А) на ошибку. (3) Предположим, что (Т, и, 1) принадлежит У и Т'=<7', 8'у принадлежит ХЕХТ(7', г).
Если Д (и) ..:Рр, зацепить П (и) иа ошибку. (4) Полученвое многкество таблиц, имена когорых сохранены, представляет собой ЦГ'. Г) Пример 7.21. Рассмотрим грачмвтпк) С с правилами (1) В-ЛВ (2) В Ь (3) А — Р ИВ (4) В ОВ (5) В Ь вс-недостижимое множество 1.11(1)-таблиц для С, построенное в реаультатс применения алгоритма 7.6 к каноническому миожестоу ЕК(1)-таблгиг для С, приведено па рис. 7.28. Можно, например, заыенить аба элемента ошибка у функггий действия таблицы 7', на свертку 5 и элемент ошибка в таблике Т, на свертку 2. Другими словами, мы выбираем множество Отсрочки уз= ((7'„и, 5), (Т„Ь, 5), (Т„е, 2)г.
Правило 5 есть Ь и СОТО(Т,, Ю=(АОТО(ТН Ь) =7',. Таким обРазом, эле- Дейемйае а Ь е Перешй Л В а б "а 77 гя 77 Гя т, г, Дж емйае а Ь е Перелей Л В а Ь г, 79 г, Гг г, г, гя Рнс. 7.2В. Ч.няяасгяжння«множества табяян яея Вя. Рна. 7.2З. Мнажястяа табянц нагая прямяняння ятгаратмя отсрочки в абнаружшнн ажябак.
7.9. НРВОВРХВОВяння ня 91ножестВях еягы.тьВлиц менты, расположенные в Т, и Т, под В, нужно изменить с 27 на ошибку. Аналогично элементы, расположенные в Т„и Т, под 5, заменяются на ошибку. Поскольку БРЕХТ(Т„5) и 7чЕХТ(Т„, 2) пусты, никакие элементы 27 у функ7гий действия зацепить на ошибку нельзя. Полученное множество таблиц показано иа рнс. 7.22. Л>ажно, если угодно, воспользоваться алгоритмоьг 7.7, взяв в качестве совместимого разбиения разбиение, в котором таблица Т, сгруппирована с Т„Тт с Т, и Т, с Т,.
(Бозмож79ы шкже три другие попарные комбинации ) Йовое множество таблиц приведено на рис. 7 30. Д дейеаяуее 77ерешй а Ь е В Л В а Ь Рнс 7.ЗО. Саямжцянная няожяс7яа гаолян. Теорема 7.7. Алгоритм 7.8 порождает фр-недогпгижимое мно. жегтяо тиблиН,Т', эквивалентное множегтей Г. Доказательство. Пуст С,=(Т„ш, е) — началыгая кгзнфнгурация Ек(й)-анализатора )использующего либор', либо Г'— ииена таблиц совпадают). Пусть С,',— С, ,'—...'. ф— вся последовательность тактов, выполненных анализатором, работающим с Г, и С, ' С;,.
—... 7 — С' — соответствук7цгая последова7елыюсть для,Г. Так как Т' образ>ется из й' в рев>льтаге замены только элементов ошибка и 7р, должно быть пг) и и С; =С, для 1(7(п. (Это означает, что хотя имеются в виду разные таблицы, имена их совпадают.) Покажем, что либо т = п, либо, если т) и, после того как достигается конфигурация С„', не выполняются переносы и не будет допуска.
Если т = п, то утверждение теорсмьг очевидно, и если ф— допускающая конфигурация, то т = и. Поэтому предположим, м ГЛ 7 А!ЕТОДЫ О7ПИИИЗАЦИИ СИНТАКСИЧЕСКИХ Л77АЛИЗЛТОРОВ 7 3. ПРСОБРлзОВАния нл мнОжестззх еаи)-тзглин что С„сигнализирует аб Ошибке и ш ) п. Согласно определению множества отсрочки, поскольку в конфигурации С„действием является ошибка, э в конфигурации С;, нет, действием в С„' должна быть свертка. Поэтому пусть з — наименьшее целое, большее а и такое, что дейсгвие в коифиг>рации С; есть перенос ил7! допуск.
(Если такого з ис с>п!естаует, то теорема показана.) Итак, найдется такое наименыпее г, п . гм,з, что элемент у функции действия, к которому происходит обращение в конфигурации С„, присутствует в одной из таблиц множества Зг. Сл>чан г =-ь пе исключается, поскольку, безусловно, в,.У был перенос или допуск конфигурации С,. Элемент действия, запрашиваеь7ый в конфигурации С; „имел вид свертка 7 для некоторого 7 Согласно на7пему определению 7, этот алемент должен был появяться в резульгате применения алгоритма 7.8. Пусть Т, и ҄— упраэляющис таблицы в конфигурациях С;, и С; соответственно. Тогда Т,ЕМЕХТ(ТО !), что противорачит условию (4) определения множества отсрочки. Е] Приведем теперь достаточно полный пример, который демонстрирует, как находить множества отсрочки и совместимые разбиения.
Здесь во ьпюгом нспольз>ются эвристичесьие методы. Поскольку этн методы нигде далее ие ошюываются, мы настоятельно рекоменд>ем читателю внимательно разобраться в данкам примере. Пример 7.22. Рассмотрим множества таблиц для С„по!Та>энное на рнс. 7.25. Наш подход заключается и том, чтобы д.ш увеличения числа таблиц с аналогичными функциями действия применить алгоритм 7.8, заменяю7ций действия ошибка дейст. внвми свертка.
В частности, попытаемся слить в оди> всо таблицы, вызывающие одинаковые свертки. Попробуем слить таблицы Т„ и Тм, поскольку онн обе свертывают по правил> 5, и таблицы Т, и Ти, свертывающпе по правилу 6. Для того чтобы слить таблицы Т,„ТИ, нужно сделать так, чтобы лействвем таблицы Т,, ив ) и 7аблицы Т„на е стала свертка 5.
Затем нужно проверить, какие действия отвечают символам ) и е в таблицах из множеств ХЕХТ(Т„, 5) —. (Т„7'ы) и ХЕХТ(Т,„5) =- (Ты, Тм). Поскольку Т, и Т„ва ) обе йл7еют дейс7вием 2, нужно заменить эти 77 на ошибку и на этом закон оиь преобра. зозание. Правда, тогда Т, и Т„не буд>т более совиестимьи7и, как и таблицы Ты и Тм; поюому мы заменим действия таблиц Т, и Ты на символе ] йа свертку 4 и свертку 3 соотве>Отвеина. Теперь проанализируем множества таблиц )(ЕХТ(ТА, 4)= =>)ЕХТ(Т77, 3) == (Тм Ты).
Дналогичныг рассуждештя приводят нас к выводу, что действия таблиц Т, и Тм па ) нужно заме- 72 нить не на ошибку, а на свертку 2 и свертку 1 соответственно. Далее видим, что МЕХТ(Т„2) =- (Т,'7 =ВЕХТ(ТО, 1) Нужно заменить действие таблипы Т, на символе ) на ошибку, и тогда будут учтены все изменения, необходимые для замены действия 7',з на символе ) на свертку 5. Посмотрим, что произойдет, если ваменить действие таблицы Ти на сиешоле е па свертку 5. БРЕХТ(ТИ, 4) =- (Ты, Ты), но за. менять действия таблиц 7'и и Ты ва символе е иа ошибку не- желательно, поскольку, возможно, не удастся слить эти таб- лицы с Тз и Т,, Поэтому замеииы действия таблиц Ты и Т„ на симвояе з на свертку 4 и свертку 3 соответственно. Далее находим, что !СЕ Х7(7'77, 4) = )(Е Х7(ТИ, 3) —..
(7'„Ты) йбы не будем заменять действия таблиц Т„и Ти иа символе е на ошибку, так что п~сть действием таблицы Т, на символе Р будет свертка 2, а таблицы Ты — свертка 1. Затем находим, что '7ЛЕХТ(ТО 2) =7(ЕХТ(ти, 1) =-(Тм Т Д В этих таблицал замсниы действия на символе е па ошибку. Абы сделали таблицы 7'и и Тм совместимыми, и это ие по- влияло на возможную совместимость таблиц Т, и 7'ы, Ты и Т„, Т, и Т„ТО и 7'и, Ты и Тм Исследуем возможность сделать Т, и Т„совместимыми, заменив действие таблицы Т, на сим- воле ) и таблицы Ти на символе е иа свертку 6. Поскольку ЕЕХТ(Т„6) — (Тз, Т,,) и ВЕХТ(ТН, 6) =-(Ти, Т7„), изменения, в7шсенные в Т„ТИ и Ти, Т,„без затруднений переносятся пэ таблицы Т, и 7'„.
Все мяожестзо отсрочки состоит из эле. ментов (Т„], 2] !Т,, е, 2] ]Ти ), 4( ]Ты, е, 4] (ТО ), 6] ]Ти, е, 6] )7„, ], 1] (Т„, 1Т„, ), 3] ]То Е, 3] ТТ„, ), 51 (Т„, е, 5] Рез>льтат применения алгоритма 7.8 к множеству таблиц рис. 7.25 с таким множеством отсрочки показан на рис. 7.31. Захгетим, что к функциям переходов не добавлено ни одного элемента ошибка.
Из рис, 7.31 видно, что следующие пары таблиц совместимы: Тл, Ты Т„тн Т„, 73 Т.а. преОВРАВОВАння нА мнОжестВАх ьжм тАВлиц Дайанбиа Ттайелай * 1 ) а е т Т а а а < Р с 7 3). Результат прпмеивиин апгоривми Отсрачин и абиаружанни Ошибок. та т, Тв Та тв т, Твв Твг Т,а Тв, т„ Тв в Твг т, дм Тп 8 Х Х 8 Х Х г Ф 4 4 Р и 4 Х б 6 Х Л' 6 8 Х Х 8 Х Х 8 Х Х 8 Х Х 8 Х Х 8 Х Х Ф 2 8 Ф 2 4 и 4 Ф Х 6 6 Х 6 Х 8 Х Х 8 Х Х Р 4 8 Ф Ф 5 Ь и Ф 3 Х Ь 5 Х Х Ь 8 Х Х 8 Х Х 8 Х Х 8 К Х Ф В 8 Ф 3 5 и 3 Х 5 Ь Х Ь К и Та Р Ф Р и т, Р Ф Ф Ф Ф Тв Ф и Р Р Р Ф Ф Ф Ф Ф Р Р Р Ф Ф и Ф Г, т, Гмтн и Ф ты Ф Тва Тэ )4 и Ф Та Ф Ф и тыт, Ф и Т, т„ Ф Ф тм Р Р т„Р Р Ф и Р и Ф Ф Ф Ф Ф Ф Ф Ф Ф Ф тва Та Ты тп Р и твв Ф Р Ф Ф Ф Ф Ф и Ф Ф Ф Ф Р Ф Ф и Тм Тва Т Ф Ф Твв Р Ф Ты Тв Р Ф Та Ф т„а Р т„ Ф Ф 'Ф Р Ф Тп Ф и и и Р и Ф Ф Ф Ф и Ф Ф Ф Если алгоритм 7.7 применить к разбиению, блоками которого сл)жат приведенные выше пары и одпоэлемептпые множества 1Тф) и 174), то получится множество таблиц, показанное Дейанйаа ларахвр т т а + «1 ) а 4 в 1 ) а т, Тв т т Та Тва Рнп.
7 32. Миажввтап габпип пасае примаивиин алгпригма впиниин. на рис. 7.32. Представителепв а каждом случае будет та из таблин, которая имеет меньший индекс. Интересно отметить пары , что множество таблиц на рис. 7.32 полу гается непосредственно из б„с помощью метода 221.2", излагаемого в равд. 7.4.1. Для того чтобы проиллюстрировать эффект отсрочки в обна- Р)женин ошибок, разберем опвггбочппю входную цепочку и). Используя множество таблиц рис. 7,2о, нанонический анализа- Более того, если эти пары разбиения, можно сгруппировать Т„ ! Тм ТО Т„ 74, Образуют блоки совместимого еще и такие пары: Т ° Ты Т„ Тм гл. г методы оптимизлции синтлксичсских лнллизлтогов тор выполнит только один такт [Т„а), ег) — [Т„а7',), ег Действием таблицы 7'„на символе ) будет огинбка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
