Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 35
Текст из файла (страница 35)
Контекстно-свободные грамматики В середине ! 950-х годов выдаюшийся лингвист Хамски описал четыре класса порождаюших устройств, или грамматик, определяюших четыре класса языков (Словаку. 1956, 1959). Два класса из четырех, названные контекстно-свободной и регулярной грамматиками, оказались полезными лля описания синтаксиса языков программирования. С помошью регулярных грамматик можно описывать грамматические лексемы языков программирования. Языки программирования в делом, за редким исключением, описываются с помошью контекстно-свободных грамматик. Поскольку Хамски был лингвистом, то в первую очередь его интересовала теоретическая природа естественных языков.
В то время он не интересовался искусственными языками. используемыми дэя общения с компьютерами. Так продолжалось до тех пор, пока его работа не была использована в области языков программирования. З.З.1.2. Истоки формы Бэкусо-Но ура Вскоре после появления работы Хомоки о классах языков !руппа АСМ-САММ начата разработку языка А(.СО(. 58. В 1959 голу Джоном Бэкусом, выдающимся членом грчппы АСМ-САММ, на международной конференпии была представлена работа по описанию этого языка (Васкиз, 1959), ставшая вехой в истории языков программирования.
В этой работе была введена новая формальная запись лля описания синтаксиса языка программирования. Позже эта новая запись была несколько модифипирована Питером Науром для описания языка А!.СО(. 60 (Наог, ! 960). Переработанный метод описания синтаксиса стал известен как форма Бэиуса-Наура (Вас!сиз-Напг Ропп), или просто БНФ.
Форма БНФ представляет собой очень естественный способ описания синтаксиса. Похожее средство фактически использовалось Папини (Ран!и!) для описания санскрита за несколько веков до нашей эры (!пйеппап, ! 967). Несмотря на то что использование формы БНФ в отчете о языке А(.СО(. 60 не было с готовностью воспринято пользователями компьютеров, вскоре эта форма стала и все еше остается самым популярным методом краткого описания синтаксиса языка программирования. Примечательно, что форма БНФ практически идентична порождаюшим устройствам контекстно-свободных языков, названных контекстно-свободными грамматиками(сопгехг-ггее 8гашшагз).
Далее в главе мы будем называть контекстно-свободные грамматики просто грамматиками. Более того, мы будем использовать термины "форма БНФ" и "грамматика" как взаимозаменяемые. 127 3.3. Формальные методы описания синтаксиса З.З.!.3. Основы Метаязык(мега!апяцаяе) — это язык, используемый для описания другого языка. Форма БНФ является метаязыком для языков программирования.
Для описания синтаксических структур форма БНФ использует абстракции. Простой оператор присваивания языка С может, например, представляться абстракцией <присвоить>. (Угловые скобки часто используются для разделения названий абстракций.) Фактическое определение оператора <присвоить> можно представить в виде .лоисвоить> -+ <пеоеменная> = <выоажение> Символ слева от стрелочки, называемый, соответственно, левой стороной выражения (.ЧСВ).
является определяемой абстракцией. Текст, находящийся справа от стрелочки, является определением левой стороны выражения. Он называется правой стороной выржкения (ПСВ) и состоит нз смеси лексем, граматических лексем и ссылок на другие абсзракцин. (Фактически, грамматические лексемы также являются абстракцией.) Все определение называется правилом(гц1е), или продукцией(ргодцсг!оп). Очевидно, что, прежде чем абстракция <присвоить> в приведенном выше примере станет пригодной к использованию, лолжны быть определены абстракции <переменная> н <выражение>.
Отдельное правило устанавливает. что абстракция <присвоить> определяется как экземпляр абстракции <переменная>. за которой слелует лексема =, за которой, в свою очередь, следует экземпляр абстракции <выражение>. Одним нз примеров предложения, синтаксическая структура которого описывается этим правилом, является следующее: гога1 = вцЬ1 + вцЬ2 Абстракции, входяшие в форму БНФ, или грамматику, часто назывшотся нетермниальными символами (поп!епп|па1 зутЬо1з), или просто нетермииалами (попгепшпа1з), а лексемы и грамматические лексемы в правилах называются терминальными символамн цспзипа! зушЬоВ), или терминалами ([епп!па!з).
Форма БНФ, или грамматика (ягшпшаг), просто является набором правил. Нетерминальные символы могут иметь несколько различных определений, представляюших две (или большее количество) возможные синтаксические формы в языке. Множественные определения записываются одним правилом, в котором различные определения разделены символом 1, означаюшнм логическое ИЛИ. Например, оператор 1С языка Рааса! может быть описан правилами: <условный оператор> -э дк <логическое выражение> с)звп <оператор> <условный оператор> -ь дк <логическое выражение> ЕЬеп <оператос> е1ве <оператор> или <условный о..ератор> -э дк <логическое выражение> ЕЬеп <оператор> ьб <логическое выражение> сЬеп <оператор> е1ве <оператор> Несмотря на простоту форма БНФ вЂ” это довольно мощное средство описания подавляюшего большинства языков программирования.
В частности, она может описывать списки одинаковых конструкций, порядок. в котором должны появляться различные 128 Глава 3. Описание синтаксиса и семантики конструкции, вложенные структуры любой глубины, приоритет оператора и ассоциатив- ность операторов. 3.3.1.4. Описаиив списков Списки переменной длины часто записываются с использованием эллипсиса (...). например 1, 2, ....
Форма БНФ не содержит эллипсиса. поэтому возникает потребность в альтернативном методе для описания списков синтаксических элементов языков программирования (например. списка идентификаторов. вхоляших в оператор объявления данных). Самой распространенной ачьтериативой является рекурсия. Правило называетсв рекурсивным (геснгз)че). если его левая часть входит в его правую часть. Использование рекурсии для описания списков иллюстрируется слелуюшим правилом: <список идентификаторов> -ч идентификатсс идентификатор, <список идентиФикаторов> Данное правило определяет абстраюн~ю <список идентификаторов> либо как отдельную грамматическую лексему (идентификатор), либо как идентификатор, за кочорым последовательно следуют запятая и лругой экземпляр абстракции <список идентификаторов>.
В большинстве грамматик. приводимых в качестве примера лачее в главе. для описания списков используется рекурсия. 3.3.1.5. Грамматики и правила вывода Форма БНФ является порожлаюшим устройством для определения языков, Предложения языка создаются с помощью последовательности правил. которая начинается со специального нетерминечьного символа грамматики, называемого начальным символом (маа яутЬо!). Создание предложения называется выводом Иег)ча))оп). В грамматике для полного языка начальный символ прелставляет собой полную программу и обычно называется <программа>.
Для иллюстрации выводов в листинге 3.! прнвелсна простая чрамматика. <программа> -э Ьеахп <список операторов> ел<а <список операторов> -з <оператор> ! <оператор> ; <список опесаторов> <оператор> -э <переыенная> ."= <выражение> <переменная> -э А ! В ! С <выражение> -э <переменнал> , <переменная> <геременная> — <переменнал> ! <переменная> Язык, описанный в листинге 3. !. имеет только олпу операторную форму — присваивание. Программа состоит нз специального слова Ьеаьп. за которым следует список операторов, разделенных точками с запятыми, и специального слово еп<). Выражеиис— это либо отлельная переменная, либо лве переменные, разделенные операторами "-" или '"-'.
Елин<тасиными сушествуюшими в языке именами переменных являются символы А. В и С. 3.3. Формальные методы описания синтаксиса Ниже следует пример вывода программы на этом языке. <программа» = Ьедзп <список операторов> епс1 = > Ъеддп <оператор> ; <список операторов> епс1 > Ьеддп <переменная> := <выражение> <список операторов> епс1 = > Ьеддп А := <выражение> <список операторов> епс1 > Ъедзп А : <переменная> + <переменная> <список операторов> епс1 = > Ьедхп А := В + <переменная> <список операторов> епс1 > Ьеддп А : В + С ; <список операторов> епс1 = > Ьедхп А := В + С ; <оператор> епс1 > Ьедхп А := В + С ; <переменная> := <выражение> епс1 > Ьедхп А : В + С 1 В := <выражение> епс1 > Ьедзп А := В + С ; В := <переменная> епс1 > Ьеддп А : В + С ; В := С епс1 Этот вывод, как и все выводы, начинается с начального символа, в данном случае с символа <программа>.
Символ "=>" читается как "порождает". Каждая последуюшая строка приведенной последовательности выводится из предыдущей строки с помошью замены одного из нетерминальных символов одним из нетерминальных определений. Кажлая строка в выводе, в том числе и строка <программа>, называется сентенпиальной формой (зепгепг!а! Гопп). В данном выводе всегда заменяется крайний слева нетерминальный символ предыдущей формы высказывания. Выводы, используюшие такой порядок замены, называются левостороннимн выводамн (1ейшозг дептабопз).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
