Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 33
Текст из файла (страница 33)
В технологии компиляции находят применение лва класса грамматик: НФБ-грамма!лика (или контекстно-свободная грамматика) и регулярная грамматика, описанию которых и посвящены следующие ниже разделы. Краткий обзор других классов грамматик, которые, хотя и не столь полезны для раза)ттия теории компиляции, все же очень важны для понимания возможностей вычислительных машин, представлен в разделе 4.1. Обзор языка 3.2. СОНС, С0Р(. и Р(.уС Характеристика.
Компиляторы, способные автоматически исправлять ошибки в не- корректных программах, История. Во времена пакетной обработки (с начала 60-х и до середины 70-х гг.) зачастую требовался целый день, чтобы получить из вычислительного центра результаты компиляции программы. Следовательно, ошибки при компиляции обходились очень дорого. Чтобы приблизить момент начала вычислений по программе, в Корнельс ком университете (СогпеВ Оп!чете!!Ч) под руководством Ричарда Конвея (В)сваг(( Сопееау) была разработана серия компиляторов (СЕ) РС вЂ” Согпей Соптр)!!ег, Корнельский компилятор; СОРК вЂ” Согпед Опмегв1у Ргоргагпгп)пр Сариаое, язык и рограммирования Корнельского университета, и РК/С вЂ” Корнельская версия РК/!), которые автоматически диагностировали и исправляли некоторые простые синтаксические и семантические ошибки. Эта система была достаточно эффективна в отношении исправления простых ошибок.
С развитием в 70-е гг. систем, работающих в режиме разделения времени, и появлением в 80-е персональных компьютеров и рабочих станций необходимость в автоматическом исправлении ошибок отпала. Пример У* РЕУС Припер автоиатического исправяомия оюибок в ПЛУ! *! 5ЯМР(Е.РЙОСЕООЙЕ ОРТ10К5(НЯ1К) г*гпавчая процедура*! ОЕС! ЯЙЕ ЧЯЙ1 Г1ХЕО В1ДЯЙУ У*ЧЯЙ1 делая пеРеменная; Добавляет отсутствующий символ : е конце опера бра*! ОЕСЕЯЙЕ ЧЯЙ2 Г1ХЕО В1МЯЙУ: ЧЯЙ1 = 1. ЧЯЙ2 = 2: ЕГ (ЧЯЙ) к ЧЯЙ2 !"Добаепяет пропущечмую скобку ) в кочпе строки*! ТНЕЙ РОТ 5К!Р Е(5!(Чяй1, '1ем 1)тап'. Чяй2) У*добавпяет ; е копие оператора*! !*Печать 1 1еев Шеп 2"! !*по 5К1Р переходим ча човую строку*! Е5ЕГ РОТ 5К1Р (15Т(ЧЯй2.
'1евв Шап'. ЧЯЙ)). 00 ЩН)!Г(ЧЯй2ьб). РОТ 5К!Р('Соопттпд боип'. ЧЯЙ2).У*Вставпяет пропуцемчое ключевое слово (15Т*! Удй2 ЧЯЙ2 - 1; !*Вставляет змак раеечства = после первого идентификатора Чдй2*! ГЙО; !*Конец цикла*! ЕМО: У*комод процедуры 5ЯНРЕЕ*! Ссылки. В. Чу. Сопигау апб Т Чудсох, "Е)ез!Оп апб !гпр!егпеп!а(юп о(а Е)!ароса(!с Согпрдег !ог Р(.,г)", Сотгп.
АСМ (16)3 (1973), 169-179. 114 Глава Э. Вопросы трансляции языка 3.3.1. НФБ-грамматика Когда мы рассматриваем структуру английского предложения, обычно описываем его как последовательность категорий. То ость простое повествовательнос предложение обычно представляется в виде: подлежищее/глагол /дополнение, Например: Тле йй1/гап/йоагс (Девочки побежали домой). Т)ге Боу/соойз/йгппсг(Мальчик готовит обед).
Каждая из категорий может подраздсляться ца подкатегории. В приведенных примерах подлелгащее состоит из сущсствительлого с иртиклем. С учетом втого подразделения структура предложений такова: иртикль/существительное/глигол,'дополнснив. Сушествуют другие структуры предложения кромс простейшей структуры г|редставленпых здесь повсствовательных предложений. Например, простое вопросительное предложение в английском языкс формируется следующим образом: оспом огительнгчй гли гол / подлежащее / скаэусмое, что можно наблюдать в следующих предложениях 0ги'/тле йгг1/пт Боте (Побежала ли девочка домой) р Тл/г)ге Ьоу/соойпйа(ппег(Готовит ли мальчик обед)? Мы можем представить рассмотренные нами предложения набором правил. Можно сказать, что предложение может быть простым повествовательиым или простым вопросительным, пли выразить это с помошыо специальной нотации: <прсдложенис> л=.
<повествовательное> [<вопросительнос>, где символ::= обозначает «определено как», а символ [ обозначаст «или». Даль- нейшее определение предложений указанного типа может выглядеть следующим образом: <повествовитсльное> к- <подлежищее <глигол> -дополнение>. <подлежащее> х= <иртикль> <существительное>. <вопросительное> х= <вспомогительный глагол> <подлежищсе> <гказуемов>7 Такая специфическая запись называется НФБ (нормальной формой Бэкуса, или формой Бэкуса-Наура). Она была разработана Джоном Бэкусом [14[ в конце 50-х гг.
как способ выражения синтаксического определения языка А(.СО(.. Пи- тер Наур являлся председателсм комитета, занимавшегося разработкой АБСО1. Приблизительно в то же самос время Ноам Хомский предложил подобную грам- матическую форму, называемую конглекстно-свободной гриччатикой [27[, для определения синтаксиса естественного языка. НФБ и формы контекстно-свобод- ной грамматики эквившгентны по своим возможностям, различия касаются толь- ко системы обозначений. По этой причине при обсуждении вопросов синтаксиса термины НФБ-грам ватикан контекстно-свободная гриммитика обычно являют- ся взаимозаменяемымш 3,3.
Формальные модели трансляции 115 Синтаксис НФБ-грамматика состоит из конечного набора правил НФБ-грамматики, которые определяют язык — в нашем случае язык программирования. Прежде чем подробно рассматривать эти правила, следует разобраться с термином «языкы Поскольку сигпаксис нмсст отношение к форме (структуре), а нс к значению (смыслу), то язык (программирования) с точки зрения синтаксиса представляет собой множество синтиксичвски ггривильных програльи, каждая из которых есть просто послсдовапльность символов. В отношении семантики синтаксически правильная программа может нс иметь никакого смысла (то есть при выполнении она нс обязатсльно должна производить какие-нибудь полезныс вычисления, даже более того, она может вообще ничсго не вычислять).
Например, если вернуться к определенным выше повествовательным и вопросительным предложениям, то в приводимом ниже предложении синтаксис подлежии4ввг' глигол г' дополггвггие полностью соблюден: т)ге поте гг лип гг Ягн(Дои побезлтгл девочки '), но получившееся в результате предложение нс имеет смысла'. Что касается синтаксиса языков программирования, мы можем ешс больше абстрагироваться от смысла синтаксических последовательностей и определить язык как миожвство цепочек символов конечной длины, причем символы выбираются из определенного конечного алфавита. При таком определении языком можно назвать: 1) множсство всех операторов присваивания в С; 2) множество всех программ на С; 3) множество всех атомов ЫБР; 4) множество последовательностей из элементов з и Ь, таких, что всг элементы з в каждой последовательности предшествуют элементам Ь (например, а, заЬ, аЬЬ, ...).
Язык может состоять как из конечного множества цепочек (напримср, язык, составленный из всех разлслитслей языка Рапса!: Ьеоз и, епд, з 1, гйеп и т. д.), так и из бесконечного множества пеночек (напримср, из цепочек, описанных в п, 4), Единственным ограничением является то, что ллица цепочек лолжна быть конечной, а символы должны быть взяты из определенного конечного множества (алфавита). Если внимательно рагс потрети приведенные выше примеры оп редслсши языков, то можно обнаружит ь некоторые сложности, возникающие при описании языка В шалинском языка гггклсгтоввтсльногт чясоов ~~рслложепия ласта гочпо сгргпм апрелглспа, тоесть роль г шва в прсзгложс~ тогнсстггполг>жсниязтогослаоа.так,дапг шшгспо может стоять перел подлежащим, позгому ь гривсдшпшьг примере слово 1копс одиозна ша должно играть роль подлежащего.
— Примеч. перь В связи с этими рассуждениями можно привести и качестве примера паучпьш эксперимент учепоголингвиста академика Л. В. 1Цсрбы, который просил своок слушателей пайти подлежащее п сказуеиое в известной фразе. 'Глокая куздра штока буллаиулабакрв и кудрячит бггкреггкаь (смз лагом И. М. Математические структуры и математическое моделирование. Мз Сов, раппа, 1980.
144 с.) — Примеч. ггоуч. ред, 116 Глава 3. Вопросы трансляции языка программирования с помощью естественного языка (русского или английского вданном случае). Рассмотрим снова четвертый пример. Принадлежитлтт цепочка, составленная из единственного символа Ь, этому языку? Мы знаем, что в цепочке все символы а (которых в данном случае у нас просто нет) должны предшествовать символам Ь, но должна ли цепочка обязательно содержать хотя бы один символ а? Аналогично, принадлежит ли цепочка, составленная из единственного символа а, определенному нами языку? Таким образом, мы видим, что имеющееся описание языка является неполным. Эта проблема может быть решена при помощи множества формальных математических правил, точно определяютцих, какие цепочки допустимы в языке.
В простейшем случае грамматическое правило может быть задано простым перечислением элементов конечного языка, например: <цифра .= 01112)3)а)51617/а(9 Это правило простым перечислением набора возможностей определяет язык, состоящий из десяти цепочек, содержащих единственный символ: О, 1, 2, 3, 4, 5, 6, 7, 8 или 9. Это грамматическое правило читается так: «Иифри — это либо О, либо 1, либо 2, либо...» Термин цифри называется синтиксической китеаорией, или нетерминальньтм символом', и служит именем для языка, определяемого данным синтаксическим правилом.
Символы, из которых образуются цепочки в языке,— в нашем случае цифры от О до 9, называются терминальными символами. Часто символ: = заменяется на — », особенно в тех случаях, когда нетерминальные символы записываются в виде одиночных букв в верхнем регистре (например, правило <Х> .:= <В>(<С> часто записывается как Х «В)С). В этой книге используются оба обозначения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
