Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 24
Текст из файла (страница 24)
у рбмк. Пример 7.35. В примере 7.35 мы нашли, что Т,'=Т', и Т;= — Т;. Приведенный автомат для автомата на рис. 7.50 изображен на рис 7.51. Состояния Т~ в Т; выбраны в качестве предсьавптелей двух классов эквивалентности, содержащих более одного элемента. Д Нв определения оп1ошения =- след)ет, что определение приведенного автомата корректно, т.е. правила (2) и (3) определенна ис зависят от выбора представителя класса эквивалентности, Нетрудно также показать, что приведенный п полуприведенный автоматы эквивалентны.
По с)ществу, эти два автомаса всегда будут совершать аналогичные последовательности тактов. Состояние приведенного ЗЗ1омата представляет класс эквивалентности, содержащий соответствующее состояние полуприведенного автомата. Формально это соответствие описано ниже. Теорема 7.13. Пусте М„.-лолулривгденный автомат и М,— соответствующий пригедсниыи автомалц Тогда для гггх 1" Осуи(естгугт талал последовательность То..., Т, Т, что (е, Т„, т, е)! — ' (Т,Т,...Т„, Т, х, и) лгогда и только тогда, когда (е, [Т,], т, е) )-', ([Т,] [Т,)... [Т ], [Т], х, и) гдг Т,— иа«алвнае состояние автомата Мо а [и] обозначает класс эквивалентности, содержащий состояние и. Показательство. Элементарная индукция по 1. Д Следствие.
М, и М„тгщалентнм. 7.5.3. Обобщонме на ьй(й).анапизаторы Каноаичегкий ннализирующий автомат можно построитьтакже и по множеству С)((й)-таблиц для С(((й).грамьзатики с й > О, Здесь мы исследуем случай й=(. Анализирующий автомат в атом случае работает во многом аналогично каноническому анализирующему автоыату для 1(((0)-грамматики, не считая того, что о каисдой таблице в отдельности нельзя сказать, является ли она таблицей переносов, сверток или допускающей таблицей.
Как и ранее, каждой таблице будет соответствовать состояние автомата. Находясь в конфигурации (Т„Т, ... Тл, Т, т, и), автомат действует так: (!) Находит аванцепочку а = Г1ВЗТ (ю). гл. |. методы оптимнзАцин синтаксических Анллизатоаоэ (2) Принимает решение о том, нужно ли выполнить перенос или свертку, т. е.
если Т = <), ду, то вычисляется 1(а). (а) Если 7"(а) =-перенос, то автомат переходит в конфигурацию (Т,Т, ... Т„Т, Т', н|', и), где Т'=д(а) и (б) Ест| 1(а)=свертка 1 и правило 1 есть А а, где )а)=г. О, то автомат переходит в конфигурацию (Т,Т, ... 7'„„„Т', ю, и|), где Т' — й'(А), если Т вЂ” <1", дО. (Если правило имеет вид А а, |о воэнйкает конфигурация |Т,Т,... Т„Т, Т', ю, л|), где Т'=й(А), Т=д, ду.) (е) Если )(а)=допуск или ошибка, то автомат останавливаегся и сообщает, что входная цепочка либо допущена, либо отвергнута. Можно по-разному расщепить состояния автомата так, чтобы операции с магазиНом оказались выделенными, имея при этом в аиду слить в дальнейшем общие операции.
Здесь мы изучим следующую схему расщепления состояний. Пусть Т вЂ” состояние, соответствующее таблице Т = ч Е В и Расщепям его иа состояния чтения, заталкивания, выталкивания н опроса: (1) Образуем состояние италия Т, в котором считывается следующий входной символ. (Состояния чтения изображены на рисунках кружками.) (2) Если 1(а) = перенос, образуем состояние заталкинаиил Т' и проведем дугу, помеченную сиыволом а, из состояния чтения Т в это состояние заталкивания. Если д(а) = Т', проведем непомеченную дугуйиз Т" в состояние чтения Т'.
Состояние заталкивания Т' имеет двойной эффект. Вкодной символ а удалкетси из входной цепочки, и имя таблицы Т заталкивается в магазин. (Состояния заталкивания изображены на рисунках квадратами.) (3) Если )ч(а) = свертка 1, образуем состояние ааалилкиаания Т, и состояние опроса Тт Из Т в Т, проведена дуга, иомеченная символом а. Если правило | есть А — а, то в состоянии Т, из магазина удаляются верхние )а) †! символов и порождается номер правила 1. Если а.=е, то в состоянии Т, в магазин помещается имя исходной таблицы Т. (Состояния выталкивания изображены треугольниками.) Затем из Т, в Т, проведем непомеченную дугу. В состоянии Т, выясняется, какой снмвол находится в данный момент в верхушке л|агазина. Если СОТО *(Т,а) сол|ржит Т', а СОТО(Т', А) = Т", проведем из Та в состояние чтения Т дугу, помеченную символом Т'.
(Состояния опроса также изображаем кружками. Метки на дугах отличтот эти состояния от состояний чтении.) |з лиллизиуую|цне Азтомлты Таким образом, если 1(а)=перенос и 1(Ь)=свертка |, то состояпие Т будет выглядеть так, как показано на рис. 7.52. (4) Состояние допуска не расщепляется. аатлалнаа читал анталии чтнлнайннл Гаатллнла ааталнлааннл Та т| аис. 7ЛП Маажас аа |.К(|)-таблин Анализирующий автомат, получающийся в результате применения оцнсанной выше процедуры расщепления состояаий, изображен на рис. 7,54. (д Лис Т.ЗЗ. Вааиажч|аа Пример 7.37.
Рассмотрим (1) (2) (3) (4) (5) Множество Ы(1)-табли|т лля Дайатйал а Ь а предстал.|Лина сае|ааииа Т. ЕК(1)-гралгматику с правилами В АВ А. аАЬ А и В ЬВ В- Ь С приведено на рис. 7.53. Т)ад анну В А В а Ь т.а лнализиоующис автоматы Рос. 7 55 Палуеэиаедеемееа аатомат.
133 гл. т. мщоды гаптимизщгии синтаКсических лнллизатооов Рос. 754 Раещеолееема аотомат гще 1РП)- реаематщем. Число состояний расщепленпога автомата для Е)1(1).гратгматики моигно уменьшить несколькима способами: (1) Если из состояния опроса иыходит только одна дуга, это состоннио опроса можно выбросить. Это уира~ценно в точности аналогично соотве1ствующсму Е)1(О)-упропгению. (2) Пусть Т вЂ” ~акое состояние чтения, что а каждом ну~и, ведущем в Т, последняя дуга, входящая в состояние аыгалки. ванна, всегда помечена одним и тем же входным символом или символом е. Тогда состояняе чтения можно исключить. (Можно видеть, что в этом случае сосаояние выталкивания имеет только одну исходящую дугу и она помечена этим символом.) Приыер 7.58.
Рассмотрим автомат, показанный на рис. 7.54. У него три состояния опроса со степенью по выходу 1, а имен. Но тало но Т„'Т; и Т;. Эги состояния и исходящие нз них дуги можно выбросить. Исследуем состояние чтения Т,. В состояние Т„ можно попасть только по путям, выходящим из Т, и Т; нли из Т„ и Т; В обоих случаях меткой предыдущего входного символа служат Ь, т. е. если в состоянии Т„ или Т, на входе появляется Ь, то автомат переходит в состояние Те или То для выполнения свертки. Символ Ь остается во входной пепочне до тех пор, пока ГЛ 7 МЕТОДЫ ОПТИМИЗАЦИИ СИНТАКСТ!'7ЕСКИХ АНАЛИЗАТОРОВ 7! АиАлизиггккциа АзтомАты автомат, находясь в состоянии ТО не прочтет его к не решит перей7и в состояние Т'„ для выполнения переноса.
Так как известно, что Ь на самом деле появляется ва входной цепочке, состояние Т, лишнее, в состоянии Т," автомат может поместить нмя состоянйя Т, в магазин, не считывая следующего входного символа, так как если автомат достиг состояния Тм то этим входным символом должен быть символ Ь Лналопщно можно исключить состояние Т,. Полученный а результате автомат показан на рнс.
? 55. Как н в случае полупркведеиного ЕК(0)-автомата, можно слить совместимые состояния, не затронув поведения автомата. Предоставляем читателю рассмотреть этот вопрос самостоятельна. На рнс. 7.55 можно слить только пару Т; и Т,', умцд. Обзор содержания главы В этой главе мы изложили ряд ме>адов, применяемых для уменьшения размера н повышения скорости работы синтаксических анализаторов. Как же нужно действовать при построении аналнзатора лля данной грамматики с ~очки зрения всех предоставляемых возможностей? Во-первых, надо принять рещение о том, какяы методоы разбора воспользоваться — восходя>цнм нлн нисходящим. Соответствующее решение прнннмаетсл в зависимости аг того, какой перевод нужно получить.
Этот вопрос мы рассыотрим з гл. 9, Если удобно воспользоваться ннсходящлм анализатором, то рекомендуется Щ()-анализатор. Для построения такого анализатора требуется проделать следующее: (1) Преобразовать грамматику н ЕЕ(1)-грамматику. Исходная грамматика очень редко оказывается Щ!)-грамматикой. Основныын средствами такого преобразования служат левая факторнзацля и исключение левой рекурсии, но гарантировать, что эти преобразования обязательно приведут к успеку, нельзя. (См. примеры 5.10 л 5.11 в томе !.) (2) Если же удается получить эквиваленты>ю Е!.(!)-грамматику С, то с помощью ыетодов равд. 5.1 (в частности, с помощью алгоритма 5.!) легко построить для С Щ1)-таблицу разбора.
Элемелтами втой таблицы на практике будут обращения к программам, которые опериру7от с магазином, генерируют выходную цепочку или выдают сообщения об ошибках. (3) Для уменьшения размера таблицы разбора прнменяюгся два метода: (а) Если правило начинается с терыинального символа, то этот терминальный символ нет необходиыоств помещать в магазин, если входной указатель перемещается. (Другнын словами, еслл нужно воспользоваться правилом А аа и а — текущий входной сяывол„то а номен!аггея в магазин, а входная головка сдвигаегся на азнп символ вправо.) Этот метод позволяет уменыпнть число различных оямаа. лаа, появляющихся в магазине и, следовательно, число строк н ЕС(1)-таблице разбора.
(б) Некоторые нетгрмнналы с аналагичньин действиями разбора можно объединить в один нетсрминал с „нндика. тором", указывающим, какой негермнпал оп представляет. 1акому объединению легко поддаются нетерминалы, представляющие выражения. (См. упр. 7.3.23 и 7.3.31.) Если >добно воспользоваться восходящим апа.тизаторам, то рекомендуется детерминированный алгоритм разбора типа „перенос- свертка", такой, как 5ЕК(1)-анализатор яли ЕЛ(.К(1)Саналязатар. Синтаксис болыпинства языков программправання легка описать с помощью ВЕК(1)-грамматики, так что предав.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
