Теория синтаксического анализа, перевода и компиляции - Том 2 (943929), страница 8
Текст из файла (страница 8)
7.2.7. "7.2.11. Пользуясь метадамн этого раздела, улучшите аналн. заторы, построенные в упр. 7.2,10. Сравните полученные анализаторы с анализаторами, разрабатанвымв в примерах 8.47 н 7.14, а также с анализаторам нз упр. 7.2.8 *7.2.!2. Л!ажно лн по анализатору нв языке Флойда — Эванса определит!и является лн он корректным анализатором слабого предшествавання длв данной грамматики? *7.2.13. Разработайте алгорнтм порождения программы на языке Флойда — Эванса, маделируэощеи детерминированный МП- преобразователь.
Как можно улучшить полученную программуэ Лроблемы д.гя исследования г.э песовгдвовтния нд множествдх ья!М.тдвлиц йгприжнения ни ирогриммироэиниэ 7.2.17. Постройте набор злелэентарных операций, используе. мых для (реализации операторов языка Флойда — Эванса. Напишвте интерпретатор, выполняющий этн операция. 7.2.18. Постройте компилятор, принимающий на вход программ) нв языке Флойда — Эванса н выдающий для нее послед овательность элементарных операций, которую может вьшолннть интерпретатор нз упр.
7.2.17. 7.2.19. Напишите программу, нагорая строила бы анализаторы на языке Флойда — Эванса для нека~араго полезного класса КС-г р ам ма гик, 7.2.20. Сканструнруйте анализатор на языке Флойда — Эванса дл ля одной из грамматик, данных в приложенкн к тому 1. Вклю. чите а него программу нейтрализации ошибок, вызываем)по ка жый раз, когда обнаруживается ошибка. Программа нейтралн- Д! зацни ошибок должна корректировать магазин и)нлн вход у н ю цепочку так, чтобы можно было возобновить нормальный разбор, Замечания по литературе Ясна, что настоящий раздел не дает полного представления аб изучаемом предмете и анализаторы, написанные на языке Флойда — Эванса, можно и далее существенна улучшать.
Поэтому мы предлагаем следующие паправлення дальнейших исследований. 7,2.14. Изучите, как маткна оптимизировать различные анализаторы типа „тшревас — свертка" при реалнзапин нх нн языке Флойда --Эванса. В частности, можно рассмотреть алгоритмы разбора ГГ(й)-, ОГ!К-грамматвк, грамматнк расц~иренного пред- шествования, простых грамматик со смешанной стратегией пред. шествования н Г.!((й)-грамматик. 7.2.15. Обобщите методы оптимизации аиалнзатаров, допустив отсрочку в обнаружении ошибок, слияние операторов иунлн другие разумные изменения программ на языке Флойда — Эванса.
7.2.16. Разработайте варнавт языка Фланла — Эванса для реализации алгарнтмов разбора. Ваш язык должен обладать следующим свойством: каждый оператор языка реализуется с ио. мощью некоторого постоянного числа машинных команд на символ оператора язьпса. Прн разработке языка орненгируйтесь на чобыкковеннуэо" вычислительную машину с прямым доступом.
44 Язык Фдаадв — Эвэвсэ и эгч вэрэаэты пользуются вапудэрвестлю при вэевсэввв сивтаксижских эввдээатсрэв Методы псстроеэээ эвэвэээтсвов ээ этеы ээыле рээрэбэтмзэлвсь ридо» легаров, в теы числе в рэботэд Ьидээ 1!9691, Нвлээ и др. !!969). Дэ Реме?э !1966), Эрла !Щ661, Хещсэ и Ш|аыэ 11976!. Приемы пестрсеэвя эвээвээтсрсв ва «эыдэ Флездэ — Эвэвсв, свисли. выс в этоы Вээлэлч, впервые встречюатся у Чвтэыэ !1967! Ихбвэ и Меэээ 1!9ТО! в е эемвлэ испшшэовэть э »зыке Фдевлэ — Эванса эычэсдяэыыэ сие. вэтары верэхадэ и метОд ептвмиээанв, еписэвиыз в рээд 7. вр д 7.2 2 В эбетэ вэ ДАФРаэсв 119761 лрнэсдэзы эехетсрыэ методы эеэтээдиээш~в ашибеэ дэв эээдюэтеуов на ээыхе Фзевдэ — Эвэвсэ. 7.2. ПРЕОБРАЗОВАНИЯ, ОПРЕДЕЛЕННЫЙ НА МНОЖЕСТВАХ ЬЕ(й)-ТАБЛИЦ Оставшаяся часть главы посвящена обсуждению вопроса аптнмнзацнн Г.Г?(й)-анализаторов.
Мы уделяем так многа винманпя Г.Г((й)-анализаторалэ по двум причинам. Во-первых, Г.К(й)-грамматнкн представляют собой наиболее широкий естественный класс однозначных грамматик, для которых удается построить ДРтерминированные анализаторы. Во-вторых, применяя методы оптимизации, можно строить С(?(й)-анэлнзаторы, успешно конк) ркрующне с анализаторами других типов. В гл. 8 был дап алгоритм разбора для )-1((й).грамматик.
Ядром алгоритма служнт множество ЬЯ(й]-таблиц, управляющих работой аналнзатара, В равд. 0.2.8 приведен алгоритм, 45 ГЛ ! Ма!ОДЫ ОПТНМИЗАШгИ СИНТАКС НТАКСНЧЕСКИХ АНАЛИЗ.!ТОРОВ применяемый длв автоматического томатнческого построения канани ЛГШГШ~Ж~~~ ' ЕСКОГО ляю ( )-грамматики (алгоритм 5.7). , как отмечалось, для г л грамматики, претстаю лбожет оказаться неприемлемо большим, ское множество СКгйк обла ( )-таблиц (канани чсск .Вдает рядом прин ек ательных свойств. (!) Анализатор быстро работает.
!ины и анализируе с за сл тактов и (2) Анели заюр б р пособиостью к айна о лапает хо ошей с мер, предположим, чта к ружеАл — п рафике иеко- префикс аемого яаыка, а хсй «е Вляетсн д хору канонический 1 Й(!)-а ПОДПЕПОЗ«и образо б аз ор им, ъяаи! об оп!ибке, как только 'р станет ахали~5 снмвол 5. В ( )-анализатор при разбо сооб ае. щ г об ошибке при пе" й аз оре входной пепоч Рва же возможности. А нализато ры предшествования пе хай ан; не Обладают способно так рано. Нап имс остью ошибке, у аначизатор зе кюсю р жд, чем ообщибь об овання и е е, д О мнОТО симВОТОВ ).1.(й)-анао! ают выс .( з- .
Нзаторы совмещают выс ают высокое быстродействие анализаторам Одна к О нар)'женню О! ь(.-грамлбатику, и, в б ко не каждый дете ' ' ык лябок, свойственпь 1 К(! )- , воо бце говоря, л рминнрованный язык ык имеет ранмирования и его и Р, для описания языка бка прогдаетсл найти более „есгсщсй ~лавы мы будсм изучаю )четь методы построения кол этих штанов примени„,ь! данном аз, .р Й(й)-апализаюры о кн лп з, и о соо шабат об ошибке, на д близка к „. ылентиош~ акен акая экви ", с которой мы встретил тилнсь в при- В данном а Р здсле мы приведем песк !пения разме а В м~юльы Р о ром~ аннй, р К(й)-анализатора и пажи . (й)-анашшатор.
В разя. 7.4 из.ю- бб воляющие по некоторым типам ВЙ йволяющие по пам ( ')-грамматик тз пгеоврлзовлния нл множествлх ьягмтлзлиц непосредственно получать (.К(й)-икао!Нзвторы, эквивалентные каноническому ВК(й).анализатору, но имеющие существенно меньшие размеры. Л!етоды, расслбатриваемые в эюм разделе, можно применять н к каноническим анализаторам. Наконеп, в раза. 7.5 мы опишем ба.бее подробнтю реализацию ВК-апализагора, в которой общие операции просмотра можно совлгещать.
7.3.1. ОБЩЕЕ ПОИЯ1ИЕ ЕЕ(й)-ТАБЛИЦЫ Основу ).Й[й)-алгарнтлга разбора (алгоритма 5.7) образует лшожество ).Й(й)-зябли!С. Вообще говоря, существует много разли !ных множеств таблиц, которыми можно воспользоватьси для построения эквивалентных анализаторов для одной и тай же 1.Й(й)-грвз!ма!ихи. Следовательно, можно поставить задачу отыскания множества таблиц, обладающего векогорымн нужными свойствами, например мннимальнастью. Для того чтобы понять, как можно изменять множество 1.Й(й)-таблиц, разберем поведение ВК(й)-алгоритма разбора Во всех подробностях.
Зтот алгоритм помещает 5К(й)-таблицы в магазин. 5К(й)-тай!!Нца, находящаяся в верхушке магазина, управляет поведением алгоритма Разбора, Каждая таблица представляет собой пару функцив (Д Е) Напомним, что функния дейстоия ( по аванцепочке устанавливает, какое действие надо предпринять.
Действием может быть: (!) перенос очередного Входного символа в магазин, (2) свертка содержимого верхней части магазина в соответствии с известным правилоы, (3) сообщение об окончании разбора, (4) сообщение о том, что ао входной цепочке найдена сиитахсическая Ошибка. Вторая функция, а именно функция перехода д, вызывается после каждого пере- наса и каждой свергни. Функция перехода по символу грамматики либо определяет имя другой таблицы, либо выдает код ошибки. В качестве примера рассмотрим ВЙ(!)-таблицу, приведенну!о ка рис. 7.20.
В ! Й(й)-алгоритме разбора таблица может воздействовать на поведение анализатора двумя способалш. допустим, что таблица Т, находится в верху!яке магазина. Функция действия таблицы определяет работу анализатора Например, если аванцепочкой является символ Ь, то анализатор выполняет свертку, вримеияя правило 3. Волн же аванцепочкой является символ п, то анализатор помещает тек)щий входной символ (в паннам с з)чае а) в лгагазин и, поскольку Е (а) = Ты записывает в верхушку магазина вслед за а имп таблвпы Т,().
! ) Как огыечалось е гл. б, о обюаюльио записыэат!, в ыо! юь ои волы гРамматики. Но ток кзк !юэелояко ! Й(а).озализотор» отаоооягсо о олпыо, осла э ыаг опто есть символы грзымзтэкк, мы бузоы считать а этом розлеоо, зто символы грамыатихи тоже поыыпаются в чагозни. ат гл. г. методы оптимизации синтаксических анализатогов г,з. пгеовпазовхния на мномсествах ьпаь тазлиц Сразу после свертки таблица задает другой тип работы анализатора. Предположим, чтосодержнмое магазина естьиАТ ЬТ йТ, и таблица Т, вызывает свертку согласно правилу Я ЬВ, Тогда анализатор удалит нз магазина четыре символа (два символа грамматики и две таблицы), оставив в нем цепочку.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
