Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 23
Текст из файла (страница 23)
МЕТОДЫ ОПТИМИЗАЦИИ СИНТАКСНЧЕСКНХ АНАЛИЗАТОРОВ Таким образом, длц входной цепочки або анализирующий автомат порождает разбор 431. Рнс. 7.47. Гриф переходое кннонн вского ентонетн. ТЛ.2. Расщепление функций состояний Использование анализирующего авгома~а для построения анализаторов имеет ряд преимуществ перед другими нодходаыи Например, часто удается расщепить функции некоторых состояний и связать их с двумя различными последовательнылш состояниями.
Если состояние А расщепляется на два сосгояния А, н А,, а  — на В, и В,, то иногда можно слить, например, А, и В„ в то время кай слить А и В нельзя. Так как объем работы, выполненной в состояниях А, н А, (или В, н В,), равен объему работы, выполненной в состоянии А (или В), то общее количество работы в результате расщепления не увеличивается.
Вместе с тем, если удается слить состояния, ~о можно достичь экономии. В этом разделе мы исследуем, как расщепить функции некоторых состояний для того, чтобы затем попытаться совместить общие действия. Каждое состояние свертки расщспим на два состояния: состояние вотиыниванил и следующее за ним состояние опроса. Пред- положим, что Т вЂ” состояние свертки, вызывающее свертку по правилу А а с номером л. При расщеплении состояния Т образуйся состояние выталкивания, единственная функция которого — удалить верхние (а( — 1 символов нз магазина.
Если и=.е, то в состоянии выталкивания в верхушку магазина записывается имя Т. Кроне того, в состоянии выталкивания порождается номер правила л. После этого управляющее устройство переходит в состояние опроса, в котором выясняется имя состояния, находяптегося в данный момент в верхушке магазина, например (7, и происходит переход в состояние СОТО((7, А). Лвоыеплнннон омвоннне оранже Рнс. 7.48. Рнсмепнснне состояние свертки В графе псреходов состояние свертки Т можно заменить состоянием выталкивания с тем же именем Т н состоянием опроса, обозначенным ТС Все дуги, входящие в старое Т, будут входи~ ь также и в новое Т, а дуги, выходящие из старого Т, теперь будут выхолить из Т'.
Одна непомеченная дуга идет иэ нового Т в Т'. Это преобразование отражено на рнс 7.48, где правило г' есть А а. Состояния переноса и состояние допуска не расщепляются. Автоыат, построенный по каноническому анализирующему автомату отесанным способом, называется раслйвинвиным кано. нинволим анализирующим авто,натам.
Пример 7.33. На рис. 7.49 показан расщепленный автомат, построенный по анализирующему автомату рис. 7.47. Состояния переноса изображены квадратами, состояния выталкивания — треугольниками, а состояния опроса н допусна — кружнами. ГЛ Г НРТОЛЫ ОПТИМИЗАЦИИ СИНТАКСИЧЕСКИХ АНАЛИЗАТОРОВ Для того чтобы сравнять поведение этого рашцеплениого антомата с поведоннем автомата из прамера 7.32, рассмотрим по- Рис.
7.49. Р«сщ««лютня юнюн««ее««в ««~он«т. Следовательность тактов, пройденную расцтепленным автоматом при разборе входной пеночки аЬс: (е, Т„аде, е) ) — (Т„Т„Ьс, е) ! — (Т,Т„Т„Р, е) — (Т,Т,Т„Т„е, е) (Т,Т,Т,, Т„'е, 4) )- (Т,Т,Т„Тн е, 4) Т.З. АНАЛИЗИРУЮЩИЕ АВТОМАТЫ ) — (Т,Т„Т;, е, 43) ) — (Т,Т„Т„е, 43) ) — (Т,, Т;, е, 43!) (Т„Т„е, 43!) с) Пусть М, и М,— два аиалязнруиецнх автомата для грамматики 6.
Будем называть М, и М, зкеиеалеюпнмми, если для любой входной цепочки и опи порождают один и тот же разбор или оба выдают сигнал ошибки, прочитав одинаковое число входных символов. Таким образом, мы пользуемся тем же определением эквивалентности, что и в случае двух множеств ЕЙ(йртабли!!. Если канонический н расщепленный канонический автоматы работают параллельно, то легко видеть, что их магазины совпадают всякий раз, когда расцгепленный автомат переходит в состояние переноса или опроса. Поэтому должно быть ясно, что вти два автомата эквивалентны. Расщепленный анализирующий автомат можно упрощать двуми способами.
Первый состоит в том, что некоторые состояния, действия которых не нужны, полностью исключаются. При втором способе сливаются неразличимые состоиния. Б первом случае исключаются некоторые состояния опроса. Автомат, полученный нэ расщепленного канонического автомата после таких упрощений, будем называть лалулриееденним. ((ример 7.34. Рассмотрим расщепленный анализирующий автомат, изображенный на рис. 7.49. Состояния Т; и Т; имеют ублько по одному переходу — этот переход помечен символои Т,.
В результате наших преобразований эти состояния и переходы в Т, будут исключены. Полученный полуприведениый автомат показан на рис, 7.30, (З Теорема 7.(2, Расщеилеииый канонический анализирующий ае. томат М, и ееа палулриеедеиный автомат М, зкеиеалентны, До и а вате льство. В результате действий, производимых в состоянии опроса, содержимое магазина ие измениется. Более того, если из состояния Опроса Т есть только один переход, то сосгояние, которым помечен этот переход, должно находиться в верхугвке магазина всякий раз, когда М, переходит в состояние Т, Зто утверждение вытекает из определений канонического автомата и функции ПОТС). Таким образом, первое преобразование не влияет на последовательности операций с магазином, входом или выходом, совершаемых автоматом.
Займемся теперь задачей минимизации числа состояний лолу- приведенного автоиата. Будем сливать состояния, побочные эйз- !25 тл 7, метОды ОптьшизАпии синтаксических АиллизАтОРОА фекты которых (отличные от записи их имен в магазин) совпадают и переходы из которых по соответствующиы дугам приводят к неразличимьЬМ состояниям. Алгоритм минимизации аналогичен по духу алгоритму 2.2, хотя и отличается от него ввиду того, что надо принять во внимание операпии с магазином Определение. Пусть М =(О, Х, 6 уь (47)] — полуприведенный анализирующий автомат, где 4,— начальное состояние, а 4,— состояние допусиа.
Заметим, что () ~=Х. Символом е будем „помечать" ие помеченные егпе переходы. Будеы говорить, что р и 4 из () О-неразличимы, и писать р ='д, если граф переходов для М удовлетворяет одному из следующих условий (случай р=у не исключается); (1) р и 4 оба являются состояниями переноса; (2) р и 4 оба являются состояниями опроса; (Э) р и д оба являются состояниями выталииваннв, и в этих состояниях автомат удаляет из магазина олинаковое число символов и порождает один и тот же номер правила (другими словами, в состояниях р и 4 автоыат свертывает по одному и тому же правилу); (4) р=у=ул (звилючительное состояние).
В остальных случаях р и 4 0-различимы. В частности, состоя. ния разных типов всегда О-различимы. Будем говорить, что р и 4 й-леричличимы, н писать р— = "4, если они (й — !)-неразличимы и удовлетворяется одно из следующих условий: (!) р и 4 являются состояниями переноса и (а) для любого а 6 Х 0(е) дуги, помеченные символом а, либо выходят и из р и иа у, либо не выходят ни из р, ни из 4; если дуги, помеченные символом а, выходят из р и 4 и входят в р' и 4' соответственно, то р' и д' (й — 1)-неразличимы; (6) нет состояния опроса с переходами, помеченными буивами р и 4, в (й — 1)-неразличимые состояния; (2) р и Э являются состояниями выталкивания н выходящие из них луги ведут в (й — 1]-неразличимые состояния; (3) р и 4 являются состояниями опроса и для всех состояний з либо р и 4 оба имеют переход на ь, либо оба его не имеют (в первом случае переходы происхолят в (й — 1)-неразличимые состояния). В остальных случаях состоянии р и 4 будем называть Враз.
Аичимыльи. Будем говорить, что р и 4 неразличимы, и писать р=э, если они й-неразличимы для любого ДЪО. В противном с.тучае р и 4 будем называть различимыми. шь 7.Ь. АНАЛИЗИРУЬОШИЕ АЬТОМАТЫ Лемма 7.4. Пусть М вЂ” Я, Х, 6, 4„(4,)) лолуприееденныи аетомвп. Тогда (1) =А для есех й сеть отношение экеиеолентяссти на (7, (2) если —= ." — =.-."ь', то До к аз а тельство.
Предлагаем в качестве упраукненая (аналог лемыы 2.!!). ~) Пример 7.36. Рассмотрим полупрнведенный автомат, изображенный на рис. 7.60. Вспочинв множество БВ(0)-таблЬИИ, по Рнс. 760 Полупрнььльннмй ьвтаиат. которому был построен этот автомат (рис. 7.46), видим, что все шесть состояний выталкивания вызывают свертки по разным правилам, и значит, они 0-различимы. Состояния остальных типов по определению О-неразличимы с состояниями того же типа, так что классы эквивалентности отношения = — 'таковы: (Т„Т,, Т,), (Т,), (Т,), (Т,), (Т,), (Т,), (Т,), (Т,), (Т;, Т;, Т„, Т;), !27 Т.В. АНАЛИЗНРУЮШИЕ АВТОМАТЫ Рис.
7.51. Приведе ма автомат, 12В 12Э 5 А. Ахе, д>», ульлев, . 3 гл г. методы Оптимизацни синтАксических АнАлизАтОРОВ Для тога чтобы найти — ', заметим, что состояния Т, и Т, 1-различимы, так как нз Т; в 0-различимые состояния Т„н Т, есть переходы с метками Т„и Т„соответственно. Далее, Т„ 1-различимо с Т, и Т„, поскольку из первого есть переход с меткой а, а нв последних нет. Т; и Т, 1-различимы, так иак из них есть переходы в 0-различимые состояния, поыеченные именем Т,.
Аналогично пары состояний Т', и Т;, Т; и Т„ 'Т; и Т; 1-различимы. Остальные пары, являющиеся О-неразличимыми, также и 1-неразличимы, Таким образом, классы эивнвалснтности отношения — = ', содержащие более одного элемента,— это (Т;, Те) и (Т;, Те) Находим аалее, что =-" =- — '. О) Определение.
Пусть М, = ((), 2, 6, у„(уь)) — полуприведеиный автомат. Обозначим через Гг' множество классов эквивалентности отношения =. Класс эквивалентности, содержащий у, будем обозначать [у]. Притденным тзтоматом для М, назовем автомат М,=(м', В', 6', [уе], ([уь])), где (1) Х'=( — ЮПО, (2) 6'([у, а) =[6(у,а)] для всех уб Я и а 5 20(е) — Я, (3) 6'(Й [р])=[6(у, р)] д.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
