Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 14
Текст из файла (страница 14)
С другой стороны, используя для разбора этой же входной цепочки множество таблиц рис. 7.32, аяализатор выполнит поСледовательность такгов [Т„а), е|',-[Т„иТо ), е) ) — [Т,РТ„), 6) ! — (Т,ТТ„, ), 641 1-!Т,ЕТо ), 642[ Здесь, прежде чем сообщить аб ошибке, анализатор сделает еще три свертки. (3 У.й.б. Иенпгачеиме сверток по цепным прввипвм Изучим теперь важное преобразование множества ГК(й).таблиц, не сохраняющее эквивалентности в смысле предыдущих разделов.
Зго преобразование не приведет к возникновению дополнительных операций переноса и не вызовет свертки, если исходное множество таблиц обнар)жиг ошибку. Напротив, в реаульгате этого преобразования некоторые свертки будут прон)скаться. Зто приведет к тому, чю таблигта, появляющаяся в магазине, не всегда будет связана с записаннои под ней цепочкой символов граыматики (хотя она вежда будет совместима с таблицей, связанной с этой цегючкой). Преобразование, рассматриваемое в этом разделе, должно осуществляться над Пенными правилами; мы изучим его несколько менее формально, чем предыдущие преобразования. Правило вида А В, где Л и  — петерчиналы, называется цепнылг.
Правила такого вида часто встречаются в грамматикал, описывающих языки программирования. Так, цепные правили часто волникантт при использовании коитексгпо.свободной грамматики для описания приоритетов операций в языках программирования. Например, если пеночку а, ! аз « а, следует трактовать как а, + (а,« и,), то говорят, что операция « имеет более вьаокий прйарггтет, чем операция Наша грамматика С„описывающая арифметические выршкения, вводит для е более высокий приоритет, чем для — '. Грамматюка С, состоит из правил (1) Š— Е-'Т (2) Е-Т (3) Т вЂ” ТэР (4) Т Е 76 тз пгсовглзовлнггя нл множсстелх сшлгтлвлиц (5) Р (Е) (6) Р а Можно считать, что нетсрминалы Е, Т и Р порождают выражения различных приоритетон в соответствии с нриорнтетамн операций.
Е порождает выражения, приоритет которых равен !. Это цепочки символов 7', разделенные знаками +. Операцггя -1- имеет приоритет 1. Т пороигдает выражения приоритета 2; опи состоят нз символов Р, разделенных знакаыи ч. Выражения приоритета 3 — это выражения, порожденные нетерминалом Г, и их могкпо считать первичными выраженнями. Таким образоы, при разборе цепочки а, †, 'а,» а, в соответст вии с грамматикой С, сначала нужно свор«узъ а,ла, в 7', а затем свернуть это Т вместе с а, в выражение Е.
Едкнствениая цель, которои сл)жат два цепных правила Е Т в Т Р, состоит в том, чтобы позволить тривиально свертывать выражения более высокого приоритета в выражения более низкого приоритета. В компиляторе правила перевода, связанные обьшно с такими цепными правилами, озиачагот престо, что переводы нстерминалов в левой и правои частях правила совпадают. При таком условии лкгжио, если угодно, исключить свертки но цепным правилам Некоторые явыки программирования имеют 12 и более приоритетов операций Поэтому, если разбор ведется в соответствии с гралгтгатиггоиЧ отражающей иерархию приоритетов, то анализатор часто буде~ выполнять последовательности сверток по цепным правилам. Если удастся исключить такие последовательности сверток, скорость разбора значительно возрастет. В большинстве практических случаев это удается сделать, не изменив получаемого перевода В данном разделе мы опипггм преобразование на множестве !.К(!г)-таблиц, пааво.гиющее исключить свертка по цепным пра.
вилам везде, где это надо. Пусть (Г, Т,)- -гу-недостижимое множество 1.К(!г).таблиц для ! К(й)-грамматики С= (.'т, Х, Р, 5). Предположим, что ар содержит максимально возмо,кпое число элементов гр. Пустг А В— цепное правила из Р. Допустим, что 1.К(й)-алгоритм разбора, нспальзугощий это множссгво таблиц, обладае~ следующим свойством: всякнй раз, когда основа У,!', ...
У, свертывается в В при аванпепочке и, очередным шагом будет свертка В в А. Часто оказывается возможным изменить ьшогкество таблиц так, чтобы основа У,У„... !', свертывалась в Л за один шаг. Выясним, прн каких условиях это ыожко сделать. Пусть р — номер правила А †. В.
Предположим, что Т = = л)', Еу — такая таблица, что [(и) — свертка Р для некоторой 'и уэ гл т. методы оптил1нзлцнп сннтхксическнх Анхлнзхтооов аванцепочки и. Пуст~ ВУ'.=СОТО '(Т, В) и ои'.==((7(В = — СОТО(Т', А), Т'БВ'). Множество Т' сосгаит из таблиц, которые могут появиться в магазине непосредственно под В, прн условии, что над В находится таблица Т.
Бели (Г, Т,) — кано- ническое множество ).Д(й)-таблиц, то Ри= 7(ЕХТ (Т, р) („„. 7.3АЗ). Для того чтобы исключить свертку по правилу р, заменим для каждой таблипы <7', й'у из Л ' значение элемента д (В) с имени таблицы Т па й'(А). Тогда вместо двух тактов, а именно (уТ'Ух(/АУ,(ух...
У,(у„ш, л) ! — (уТ'ВТ, ж, нх) )-(ТТ'А(7, и, гбр) анализатор сделает только один такт (77" У,(7,У,(7„... У,(7„, ш, л),' - ( (Т'А(7, ш, гб) ') Такая замена элемента д'(В) возможна при »славин, что элементы таблнпы Т и всех таблиц нз .й совпадают всегда, кроме ~ех случаев, когда аваицепо пга вызывает свертку по пра- вилу р. друщгми слова ми, пусть Т =' <Д йу и й — —. (<(„д,у, <)„й.щ ., <)„, й у). Тогда требуется, чтобы (1) для всех и из 2'А если 7(и) — не ср н не свертка р, та Д (и) — либо гщ либо совпадает с )(и) при 1 (! -"щ, (2) длн всех Х из уч'()2 если й(Х)эьйх, то д,(Х] — либо гр, либо совпадает с д(Х) при 1 <х<щ.
Бели оба Этн трсбовани я удавлю вора клея, преобразуем таблицы в множествах Т' и и так: (3) положим й'(В) —.-й'(А) для всех <)', й'у из Г', (4) пря !ж !(т (а) лля каждого и Е 2'А заменим Й (и) иа у (и), если Й (и) —.Ау и )(и) — не гр и не свертка р, (б) длЯ каждого ХБВПБ заменим йг(Х) на й(Х), если о(Х) си 3. Изменение, обусловленное приыененнеч правила (3), может сделаю таблицу Т недостижимой, если ее можно достичь только в резулыатс обращения к элементам й'(В) таблиц <,', ' з множества,р', Заметим, что измененный анализатор может помещать в мага- зни символы н таблицы, которые не записывались туда исходным анализатором.
Например, прелположим, что исходный анализатор выполняет свертку в иетерх|ивал В и затем перенос; (уТ' У (),У,ОР У,()„иы, л) ! — (ТТ'ВТ, аш, лх) (7Т'ВТОТ",, и!) ') анои дело в резулыате онхсанонх ханов анализатор достигает Ыа с «оофггурхцвх (тт'ВП, а, Щ), х ве (у!'ЛП. а, л~). Впрочем, эго замечание ие охояет иа хох хххьвезшвх рхссужхехнз.— Прил лерхо. 78 х.х ПРЕОВРАВОВАння пл мнОжестВАх еиаьгАВлнц Новый анализатор выполняет ту же последовательность тактов, но в магазине будут появляться другие символы.
Б этом случае будет (уТ' У,((,У,(/,... У,(у„аш, л) — ' (ТТ'А(7', аш, лг) ,-(ут'А(7' Т". Пусть Т=-<Дйщ Т'=<!',й'У и (I=.=<)„й,ы Тогда В=й'(А), Таб.зица (7' была построена по (7 в соответствии с правилом (4), сформ)лированньгхг выше. Поэтолгу, если 7(а) =перенос, где а = = Г1ДЗТ (аш), то ясно, что Д (а) =перенос. Более того, известно, что й, (и) совпадает с й (и). Значит, новый анализатор выполняет правн.юную последовательность тактов, вв исключениел! того, что оп игнорирует вопрос а том, была ли в действительности произведена свертка по правилу А В, На последующих тактах анализатор не просматривает символы грачмагпкн, находящиеся в магазине.
Так как элементы перехода таблиц (У' и Т совпадакгг, можно быть увереиным в том, что поведение обоих анализаторов будет одинаковым (за исключением сверток по цепному правилу у1- В). Зто преобразование ыожно повторить с новыы множеством таблиц, чтобы исключить возможно бо.тырс сверток по несупгественным с точии зрения семантики цепным правилам. Прилгер 7.23. Исключим возможно больше сверток по цепным правилам в множестве БП(1)-таблиц дчя грамматики 6„ представленной на рнс.
7 32. Таблица Т, вызывает свертку по правилу 2, т. е. по правилу Е - Т. Множеством таблиц, которые могут появиться в магазине непосредственно под Тм являегсн (Т„Т,), -. как СОТО(Т., Е) =7, н СОТО(Т„Е) = Т,. Нужна проверить, что таблицы Т, и Тх, а также Т, и Т„ совместимы везде, кроме элехгептов свертка 2. Действие таблггггы Т, па о есть перенос. Действие таблиц Т, и Т, на в есть гщ Переход таблицы Т, на + есть Т,. Переход таблиц Т, н Т, на о есть а. Следовательно, Т, н ТО а также Т, и Т, совместимы. Поэтому момсно заменить переход таблицы Т, на нетерминале Т с Т, на 7', н переход таблицы Т, на петермннале Т с Т, на Т,.
Йужно также заменить действия таблиц 7', н Т, на символе о с Ар на перенос, поскольку действие Т, на в есть перенос. Н аконец, заменяем гюреходы таблиц Т, и Т„ на символео с гу на ТО потому Чта ПЕрЕХОд табпицЫ Т, На о ЕСТЬ ТО Таблица Т, теперь йедостижихга нз Т„ и, значит, ее можно исключить.
Рассмотрим операпин свертка 4, содержащиеся в таблице Т,. (Правила 4 - эта правило Т Е.) Мпожествач таблиц, которые могуг появиться непосрсдсхвенно под Тх, является (Т„ Т„ 7',). ТепеРь Сб)ТО (Т„, 7 ) = ТО СОТО (Т„Т) =-Т, н СОТО (Т„Т) =. Т „. (Ло описанного преобразования СОТО (Г„, Г) =СОТО(Т„Т) = — Т,, ) гл. т. мгжоды оптимизации синтаксичгских анализатогов Перегар а Г Т Е а а. а ( ) Дайаагйиа а ч- а ( ) Та Та газ Таз Перелей й а + а ( ) р(айаагйоа е + * ! ! е Т, Нужно проверить, что таблица Та совместима с каждой нз таб.
лиц 7'о Т, и Тге Ясно, что это так, посхольку лействпе таблицы Т,— есть .чибо р, либо свертка 4, а переходы ее все равны е. Такам образом, можно заменить переходы таблиц Т,, Т, и Т, на символе Е па Т„Т„н Т„соответственно. Зто делает таблицу Т, иедостюкимои из Т„. Полученное множество таблип показано на рис. 7.33,а. Таблицм Т, и Т, исключении Заметим, что в столбцах, расположенных под символами Е, Т и Е, все элементы перехода оказались совместимыми. Поэтому можно слить эти три стзлбца в один.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
