Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 58
Текст из файла (страница 58)
Такой метод построения процессоров для работы с языком при помощи поэтапного уточнения, или, скорее, поэтапного дополнения, очень полезен. Он позволяет разработчику сосредоточить внпмание исключительно на каком-то одном аспекте обработки языка, прежде чем обратиться к другим аспектам, н поэтому облегчает проверку правильности транслятора илн, во всяком случае, обеспечивает высокий уровень надежности при разработке программы. В нашем довольно простом примере разработка транслятора состоит из двух этапов, Более сложные язьпси и более сложные задачи трасляцнн требуют значительно большего числа отдельных этапов дополненная:) Очень рчорчаш «епега1раггег (1при1, ои1ри1)1 1аЬе1 99; соей етргу = '»', Фуреро1п1ег = 9поЫе; Ьро1п1ег = ~Ьеайсг; поде = тесотв гис, ай: ро!пгег; саче гегтгпа!: Ьоо1еап о« 1гие: (1гут: СЬаг); ~а1ее: (лгут: Ьрот1ег) еа4 ; Ьеайег = тесочй гут: сЬаг; епиу: рощ1ег; кис: Ьро1п1ег еао; чач 11г1, кеп11пе1, Ь: Ьро1п1ег1 р: ро1п1ег; аут; сЬаг; оЬ: Ьоо1еап; рчоседш'е вегеучп; Ьее1а череа1 геаИ(еут); иг!1е(гут) оа1П еут Ф ' ' Еай (ее1еут); рчоеейшеЯт((х: сЬаг; чач Ь: Ьротгег); (поиск в списке нетерминального символа х если его нет, включение его) чач Ы: Ьро1пгег; Ьея1а И;= 11г1; геи11ве11.гут ',= г; чгййе ЬЦ.гут че г бо Ы:= Ы1.гис; ИИ =' гепггпе1 йеа Ьеяш.( включение) пев (геп11пе1)1 Ы~,гис:= гепгие1; ЬЦ.епггу:= и11 еао; Ь:=И Ь(М); рчосеооче ег'ог; Ьефа ьгйе1п; мг11е(п (пнсояяест зчнтас); био 99 еай (еггог); «еосеаоее 1егт (чы'р,д,г: рояпгег); чач а,Ь,с: рой1ег; реосвйте3ас1от (чае р,ц: ройиег); Ьеа[п [г зут ш ['А' ..
'Е', етргу) $Ьеа Ьеа[п [символ) пею(а); 1$ зут [п ['А' .. 'Н'] 1Ьеп Ьее[п [нетерминальигнй) у$пй(зут,б); а1пегт(ла[:= За[зе; а[,лгут:=- Ь епй е1ее Ьеп[п [ терминальный ) а[.гегтта1:= вие; а[лгут:=- зут ев$; р:= а; р:= а; гегзут еа4 е[ее 1$зут = '['$Ьеп Ьей[п ревут; гегт(р,а,б); Ь[.зис:= р; пеи(Ь); Ь [аегтапаЕ г ггие; Ь [лгут: еп[ргу а~.а(г".= Ь; а:= Ь; 1г" зут = ')' $Ьеаеегзут е[ее еггог ев$ е1ее еггог ев$ [уасгог); Ье~[пУасгог(р,а); а : = а; пЬПе зут в ['А' .. 'Е', '[', етргу) йо Ьей(п,$асгог(а).зис, Ь); Ь[,а[г:= в1; а;= Ь' ев$; г:=а ев$ [гегт); ргоседпге ехргезз[оп (гег р>а: ротгег); гег а,Ь,с: ро!лгег; .ЬеФа гегт(р,ас); с[.зис:= пИ; аЬ[1езут = ','до Ьей[п еегзут; гегт(а).а1г, Ь, с): с)'.зис: аП; а:=* Ь епй; д;= а епй (ехргезз(ол); ргоеейагерагзе (еоа): Ьро[п[ег; гег та[сб: боо!еал)$~ тег з: роЫег; [Ьеа1а з: = уоаЦ.епггу,' герее1 $$з[легт[па! $Ьеп ЬеПЬе $( [.Гзут зут $Ьеа ЬеП$а та[об: = Згие; ре[зут ев$ а[ее та[сЬ 1 (з[лзут етргу) еий е)яе'расее(з) тзут, тазсЬ); .
И тазсЬ кЬеи з: з).зис е)ае'з ~= з).а11 иийз = иИ еий (рагзе); Ъеи)и )порождающие правила) 9еззут; пем(зепйпе1); Ьзг:= зепз1пе1; згЫе аут оя '5' до Ьеи)и бпд(зут,Ь); аегзут; И зут = '=' ЗЬеи аеззут еИе еггог; ехргезаоп (Ц.епггу, р\; р1.а1г: = и1$; Изут оа ".' ЗЬеи еггог„ загйе1п; геад1п; Веззут еий; Ь:= 1!зз; о1с:= згие; (проверка, все ли символы определены) иЫе Ь Ф зепйпе1до Ъев)и И Ь'~,епггу = ий ЗЬеи Ъеф)и иг1ге1п(' сиюееепеи зтмв01 'э ЬТ зут)) оЬ:= Ха)зе еЫ; Ь:= Ь).
еид; 1Е -зоЬ зЬеи уйо 99; (Чела) ге1зут; Ьп4зут,Ь); геаг11п) юг)за1п) (предложения) иЫ)е - ео1'(1прйз) Йо Ъери кт)гс(' '); 8етзут; рагзс(Ь,оЬ); И о1с Л (зут=",) яЬеи ггг11е1п (' соввест) е!ае зрг11е)п ( всоввест); геад1п еий ) 99: еий. Программа 5,3. Транслятор для языка (5д3). 848 д Структура языков и трансляторы похожая разработка, состоящая из трех этапов, будет рассматриваться в равд. 5.8 — 5.11. Как видно из разработки программы 5.3, программы, управляемые синтаксическими таблицами, или, вернее, управляемые структурой данных, обеспечивают свободу и гибкость, отсутствующие в специальных программах грамматического разбора. Хотя такая дополнительная гибкость в принципе ие нужна, она оказывается весьма существенной в трансляторах для так называемых расширяемых языков.
расширяемые языки можно дополнять новыми синтаксическими конструкциями более или менее по усмотрению программиста. Так жа как входной файл программы 5.3, входной файл для транслятора с расширяемого языка содержит раздел, определяющий расширения языка, используемые в последующей программе. Более сложные схемы позволяют даже изменять язык в процессе трансляции, чередуя части транслируемой программы с разделами новых определений языка., Однако, хотя эти идеи могут показаться весьма привлекательными, попытки реализовать подобные трансляторы оказались довольно неудачными. Дело в том, что синтаксический анализ — лишь часть всей задачи трансляции и на самом деле даже ие самая существенная часть, Ее легче всего формализовать и, следовательно, представить с помощью систематизированной табличной структуры.
Гораздо труднее формализовать смысл языка, т. е. выход, или результат трансляции. До сих пор эта задача не была сколько-нибудь удовлетворительно решена, и этим объясняется то, почему разработчики трансляторов относятся к расширяемым языкам с гораздо большим энтузиазмом до их реализации, чем после. Остальную часть этой главы мы посвятим разработке скромного транслятора для конкретного, небольшого языка программирования.
Р.т. язык пРОГРАммиРОВАния пп/в Оставшиеся разделы этой главы посвящены разработке транслятора для языка, который мы назовем ПЛ/О. При создании этого языка учитывались два условия: во-первых, транслятор не должен оказаться слишком громоздким для этой книги, во-вторых, желательно было продемонстрировать большинство основных принципов трансляции языков программирования высокого уровня.
Несомненно, можно было выбрать как более простой, так и более сложный язык; ПЛ/О является одним из возможных компромиссов между языками достаточно простыми для ясности изложения и достаточно сложными, чтобы ими стоило заниматься. Значительно более Х.7, язык праграммиравания ПЛ!О сложный язык — Паскаль, транслятор для которого был разработан с применением тех же методов. Его синтаксис дан в приложении В, Если говорить о структуре программы, то ПЛ/О достаточно полон.
Конечно, в ием в качестве основной конструкции на уровне языка содержится оператор присваивания. Другие структурные концепции — это следование, условное выполнение и цикл, представленные знакомыми формами ЬеяГп/епб-. !Г-, заЬ!!е, В ПЛ/О включено также н понятие подпрограммы, следовательно, там есть описания процедур и оператор вызова процедуры.
Что же касается типов данных, то ПЛ/О, бесспорно, удовлетворяет требованию простоты: единственный тип данных— это целые числа. Разумеется, в ПЛ/О присутствуют обычные операции арифметики и сравнения. Наличие процедур, т, е. более или менее самостоятельных частей программы, дает возможность ввести концепцию локальности объектов (констант, переменных и процедур). Поэтому в заголовке каждой процедуры есть описания объектов; эти объекты считаются локальными для процедуры, в которой онн описаны.
Это краткое введение позволяет представить себе синтаксис ПЛ/О. Этот синтаксис изображен на рис. 5.4 с помощью 7 диаграмм. Преобразовать диаграммы во множество эквивалентных порождающих правил БНФ мы предоставляем читателю. Рис, 5.4 является убедительным примером выразитель. ности этих диаграмм, которые позволяют сформулировать синтаксическое описание целого языка программирования в столь краткой н хорошо воспринимаемой форме.
Следующая программа, написанная на ПЛ/О, демонстрирует некоторые свойства этого мини-языка. Эта программа содержит знакомые алгоритмы умножения, деления и нахождения наибольшего общего делителя двух натуральных чисел. З.В. ПРОГРАММА Г'АММАГИЧБСИОГО РАЗБОРА ДЛЯ ПЛ(В В качестве первого этапа построения транслятора для ПЛ/О нужно разработать программу грамматического разбора. Это можно сделать, строго следуя правилам построения В! — В7, приведенным в разд.
5.4. Но этот метод применим, только если синтаксис удовлетворяет ограничениям 1 н 2. з!взлому мы обязаны проверить это условие в его формулировке для синтаксических графов. Ограничение ! требует, чтобы каждая ветвь, выходящая из разветвления, вела к отличному от других начальному символу. Это очень просто проверить по синтаксическим диа- условие Выраисниь Миоиитеа» Рне 54. Синтаксис ПЛ/О, о. Структура яэыкоа а трансляторы еопаг т = 7, и = 85; тпг х>у,г,гЬг; ргосе»ше ти1»р1у; чш а,Ь; Ье»1п сс:= х; Ь:= у: х:= О; псе Ь > О»о Ье»1п Ко»» Ь гЬепя:= я + а; сг г= 2ла; Ь:= Ь/2; еЫ ргосе»ше йпЫе; тш и э Ье»1п г:=* х; д:= О; гс:= у; ггИ!е и ~ г»он:= 2ни'; еЬПеи >у»о Ье»1п д:= 2ад; и := и72; П'и> < г гпеп Ье»1п г:= г — и>; »:=* »+1 » еп» ргосе»ше »еФ; чагЯ; Ьефп1':= х; я:= у; пЬ»е,~Ф я»о Ье»1п 1г',Г" < р гЬеп у .'= г-Я.
И г <,1'Пгеп,7':= У вЂ” 81 еп»; еп»; Ье»1п х:= и; у:= и; саИ тиЬр1у1 х:= 25; у:= Э; саП йгИе1 х: — 84; у;= 36; сай»с»; еп» . 6,8. (?рограмма грамматического разбора длл ПЛ(0 вбз гриммам рис. 5,4. 11равпло 2 относится ко всем графам, которые могут проходиться без чтения какого-лабо символа. Единственный такой граф в синтаксисе ПЛ?Π— это тот, который описывает операторы. Ограничение 2 требует, чтобы все начальные символы, которые могут стоять сразу после оператора, отличались от начальных символов операторов. Поскольку в дальнейшем будет полезно знать множества начальных и последующих символов для всех графов, мы определим зтн множества для всех 7 нетерминальных символов (графов) синтаксиса ПЛ/О (кроме «программы»).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
