Способы описания синтаксиса языков
Интерпретация конструкций языка программирования должна быть абсолютно однозначной, ибо фраза на языке программирования превращается в машинный код автоматически, с помощью программы-транслятора, и любой намек на неоднозначность либо делает эту фразу непереводимой, либо приводит к ошибке. В этом отношении языки программирования значительно отличаются от естественных языков, допускающих неоднозначно интерпретируемые фразы, рассчитанные на здравый смысл и жизненный опыт человека — слушателя и исполнителя, способного додумать содержание фразы. «Додумывание» не входит в способности компьютеров, поэтому необходимы приемы описания конструкций языков программирования типа: «Оператором присваивания называется . », причем продолжение подобной фразы на естественном языке чаще всего оказывается либо слишком громоздким, либо неоднозначным, либо и тем, и другим одновременно.
Для строгого и точного описания синтаксиса языка программирования, как правило, используют специальные метаязыки (языки для описания других языков). Наиболее распространенными метаязыками являются металингвистические формулы Бэкуса — Наура (язык БНФ) и синтаксические диаграммы Вирта.
Язык БНФ (называемый также языком нормальных форм) представляет компактную форму в виде некоторых формул, похожих на математические. Для каждого понятия языка существует единственная метаформула (нормальная форма). Она состоит из левой и правой частей. В левой части указывается определяемое понятие, а в правой — задается множество допустимых конструкций языка, которые объединяются в это понятие. В формуле используют специальные метасимволы в виде угловых скобок, в которых заключено определяемое понятие (в левой части формулы) или ранее определенное понятие (в ее правой части), а разделение левой и правой частей указывается метасимволом «::=», смысл которого эквивалентен словам «по определению есть».
означают, что в том (сугубо модельном) языке, на который эта метаформула распространяется, под термином понимается любая из букв А или В, а под термином — любая из следующих десяти записей: А; В; А+А; А+В; В+А; В+В; А-А; А-В: В-А; В-В Знак 1 следует читать «или».
Правая часть метаформулы может содержать правило построения допустимых последовательностей. Допускаются рекурсивные определения терминов и понятий, т.е. когда в правой части формулы участвует понятие, определяемое левой частью. Например, пусть необходимо ввести понятие , под которым понимался любая непустая последовательность цифр 0 и 1. Тогда простое и компактное рекурсивное определение с помощью метаформул выглядит так:
Рекурсия здесь не мешает конструктивному построению понятия , так как по принятым правилам при первом обращении к рекурсивно определяемому понятию следует ограничиться нерекурсивной частью формулы, т.е. под двоичным кодом понимать двоичную цифру — 0 или 1. Но при втором обращении к метаформуле, определяющей двоичный код, мы имеем варианты (конечно, неполные) понятия , и можем применить рекурсию, которая даст нам следующие варианты этого понятия: 0 1 00 01 10 11, т.е. все возможные одно- и двухцифровые двоичные коды. Очевидно, что при следующих применениях рекурсии мы получим любой возможный двоичный код.
Для задания синтаксических конструкций произвольной длины часто используют фигурные скобки как метасимволы. Фигурные скобки означают, что конструкция может повторяться нуль или более раз. В частности, термин можно определить по другому, а именно:
И еще, для полноты множества синтаксических конструкций, необходимо определить конструкцию :
В большинстве учебных пособий по программированию, технических описаний языков, метаформулы рассматриваемого языка представлены полностью.
Синтаксическая диаграмма является графическим представлением значения ме-тапеременной метаязыка. Диаграмма состоит из основных символов или понятий языка.
Каждая диаграмма имеет входящую и выходящую стрелки, означающие начало и конец синтаксической конструкции и отражающие процесс ее чтения и анализа . Из каждого элемента выходит одна или несколько стрелок, оказывающих на те элементы, которые могут следовать непосредственно за данным элементом.
Для сравнения с метаформулами приведем несколько примеров.
цсвивалентна метаформуле ::= А\В.
Читатель может поупражняться в составлении синтаксических диаграмм для известных ему языков программирования.
Металингвистические формулы в некотором виде заложены в трансляторы; с их помощью ведется проверка конструкций, используемых программистом, на формальное соответствие какой-нибудь из конструкций, синтаксически допустимых в этом языке (синтаксический контроль).
Источник
4.5. Способы описания синтаксиса
Синтаксис – это набор правил и соглашений, описывающих правильные предложения языка. Для записи правил синтаксиса языков программирования применяют различные формализованные системы обозначений, называемые
Мы рассмотрим два метаязыка, широко используемых для описания синтаксиса языка Паскаль:
1) язык металингвистических формул. Одна из его разновидностей – это расширенная форма Бэкуса-Наура (РБНФ);
2) синтаксические диаграммы.
4.5.1. Расширенная форма Бэкуса-Наура (РБНФ)
В метаязыках, описывающих синтаксис языка программирования, используются следующие понятия: метапеременная, метаконстанта, синтаксическая единица и метасимвол.
Метапеременная – это определенная синтаксисом конструкция языка (исключая основные символы). Для записи метапеременных используются последовательности слов русского языка и служебных слов, между которыми находится символ подчеркивания.
Метапеременные при записи заключаются в угловые скобки. Примеры записи метапеременных:
Метаконстанта – это лексема языка программирования. В программе метаконстанте соответствует она сама.
В РБНФ метаконстанты заключаются в кавычки. Примеры метаконстант:
Синтаксическая единица – это строка, описывающая состав и порядок следования элементов конструкций языка программирования. Синтаксическая единица состоит из метапеременных, метаконстант и метасимволов.
Метапеременная в синтаксической диаграмме означает, что соответствующий фрагмент диаграммы должен быть детализирован подстановкой синтаксической диаграммы с именем, соответствующим данной метапеременной.
Метасимволы – специальные символы, используемые в метаязыках для
описания синтаксиса языков программирования.
В РБНФ используется следующий набор метасимволов;
(или ::= ) имеет смысл «определяется как», «по определению
есть»; справа от знака ::= записывается синтаксическая единица,
точка; обозначает конец определения;
вертикальная черта; обозначает выбор, альтернативу (смысл
эквивалентен словам «либо», «или»);
заключенной в них конструкции ноль, один или более раз;
конструкции, т.е. возможность повторения заключенной в них
конструкции ноль или ровно один раз; например, запись [“+”]
означает, что знак + перед числом может писаться или нет;
круглые скобки вместе с используемой внутри них вертикальной
заключенного в скобки; например, запись (“X”|“Y”|. |“Z”) означает вхождение в конструкцию элемента “X” или “Y” или .
Рассмотрим простейшие примеры записи в РБНФ.
Вспомним, что идентификатор – по определению – последовательность латинских букв, цифр и знаков подчеркивания, начинающаяся с буквы или символа подчеркивания.
В РБНФ это определение может быть представлено так:
“a” | “b” | “c” | “d” | “e” | “f” | “g” | “h” | “i” | “j” | “k” | “l” | “m” | “n” | “o” | “p” | “q” | “r” | “s” | “t” | “u” | “v” | “w” | “x” | “y” | “z” | “A” | “B” | “C” | “D” | “E” | “F” | “G” | “H” | “I” | “J” | “K” | “L” | “M” | “N” | “O” | “P” | “Q” | “R” | “S” | “T” | “U” | “V” | “W” | “X” | “Y” | “Z” .
::= “0” | “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9” .
Запись в РБНФ синтаксиса комментария.
метасимволы, означающие любое количество
повторений заключенной в них метапеременной;
основные символы языка Паскаль (метаконстанты),
относящиеся к его алфавиту; они заключены в РБНФ
в кавычки, чтобы отличить их от метасимволов.
Если учесть, что
(* *) , то запись в РБНФ синтаксиса комментария
будет иметь вид:
4.5.2. Синтаксические диаграммы
Синтаксическая диаграмма графически изображает структуру синтаксической единицы.
Каждая синтаксическая диаграмма имеет имя, в качестве которого используется соответствующая метапеременная.
Синтаксическая диаграмма представляет собой ориентированный граф с размеченными ребрами. Для разметки ребер используются метапеременные и метаконстанты. Метасимволы на синтаксической диаграмме не используются. Поэтому метаконстанты в синтаксических диаграммах в кавычки не заключаются.
Метапеременные заключаются в угловые скобки .
Для отделения имени синтаксической диаграммы от графа используется метасимвол ::= .
Символы и ::= являются единственными используемыми метасимволами.
Метапеременная на размеченном ребре графа означает, что соответствующий фрагмент диаграммы должен быть детализирован подстановкой синтаксической диаграммы с именем, соответствующим данной метапеременной.
Ниже рассмотрено представление в виде ориентированных графов некоторых из метасимволов языка РБНФ.
1) Выбору, альтернативе (метасимволу | (Или)) соответствует разветвление в синтаксической диаграмме с последующим объединением.
Например, переменная может принимать значение А или В ( А, В – это лексемы языка Паскаль, т.е. метаконстанты).
В виде синтаксической диаграммы это запишется так, как представляет рисунок 4.2.
А 
В
Рисунок 4.2 – Синтаксическая диаграмма, представляющая выбор
В РБНФ это будет записано так:
В данном случае — это имя синтаксической диаграммы. Вход синтаксической диаграммы находится слева, выход – справа. Стрелки указывают возможных преемников каждого из элементов диаграммы. Основное направление ребер графа – слева направо и сверху вниз.
2) Необязательной части конструкции (повторению ноль или один раз ,
т.е. метасимволам [ ] ) соответствует диаграмма, которую представляет рисунок
Рисунок 4.3 – Синтаксическая диаграмма, представляющая необязательную часть конструкции
Это соответствует записи в РБНФ:
3) Возможности повторения конструкций ноль, один или более раз
(метасимволам < >) соответствует фрагмент синтаксической диаграммы, который представляет рисунок 4.4.
Рисунок 4.4 – Синтаксическая диаграмма, представляющая возможность повторения конструкций
ноль, один или более раз
Это соответствует записи в РБНФ:
Синтаксическая диаграмма определения «Идентификатор» (идентификатор – это последовательность букв, цифр и знаков подчеркивания, начинающаяся буквой или знаком подчеркивания).
Данное определение, представленное в виде синтаксической диаграммы, иллюстрирует рисунок 4.5.
Рисунок 4.5 – Синтаксическая диаграмма определения «Идентификатор»
Если сравнивать между собой язык РБНФ и синтаксические диаграммы, то можно сделать следующие выводы.
Язык РБНФ более строг и точен, более удобен для представления синтаксиса в памяти машины, более компактен.
Синтаксические диаграммы более наглядны и просты для понимания, но более громоздки.
Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.
Источник
Описание синтаксиса
Для обоснования таких структур нам потребуется определение их синтаксиса. Первое представление структур управления использовало для их описания естественный язык, как например: «Условный оператор начинается ключевым словом if , за которым следует…». Такой стиль полезен для первого знакомства, но не позволяет задать общий способ спецификации – он многословен и недостаточно точен. Нам нужно нечто обратное – сжатость определения и математическая строгость.
Таким требованиям отвечает БНФ , Бэкуса-Наура форма ( BNF – Backus-Naur Form ), главный предмет изучения этой лекции. Наряду с этой темой будут рассмотрены способы описания абстрактного синтаксиса , даны набросок разработки синтаксического анализатора ( parser ), введение в теорию конечных автоматов и кратко описана история вопроса.
2.1. Роль БНФ
Мы видели, что полное описание языка программирования включает три уровня: лексический, синтаксический, семантический. БНФ задают только спецификацию синтаксиса. Перед продолжением чтения следует освежить в памяти ранее введенные понятия – категория, терминал , нетерминал , образец, синтаксическое дерево .
Почувствуй историю
История языков программирования началась в пятидесятые годы прошлого столетия. Первым языком, получившим широкое распространение, стал язык Фортран (FORTRAN – FORmula TRANslator), предназначавшийся для научных вычислений и спроектированный командой из фирмы IBM под руководством Джона Бэкуса в 1954 году. В 1956 году для него был разработан компилятор, что предопределило успех и послужило толчком к созданию множества языков программирования.
Вскоре американские и европейские группы объединили усилия для проектирования международного стандарта языка, ставшего известным в 1956 году под именем Algol 58 (имя произведено от ALGOrithmic Language и вначале писалось буквами в верхнем регистре – ALGOL ). Наибольшее распространение получила следующая версия этого языка – Algol 60.
При подготовке спецификаций обнаружилась необходимость лучшего способа описания синтаксиса, чем тот неформальный подход, который использовал Джон Бэкус при описании Фортрана. К этому времени Джон Бэкус входил в состав рабочей группы, создававшей язык Algol и предложившей нотацию, которая была известна первоначально как БНФ (Бэкуса Нормальная Форма). В 1964 году Дональд Кнут в письме в журнал «Communications of the ACM» просил учесть заслуги по разработке нотации другого члена комитета – Питера Наура из Дании, сохранив акроним БНФ , но изменив его расшифровку (Бэкуса-Наура Форма).
С тех пор было предложено много различных вариаций БНФ . В спецификациях языка Pascal – потомка языка Algol – его автор Никлас Вирт предложил графический вариант БНФ , который также стал широко использоваться.
Источник
