Синтаксические диаграммы Вирта

Формальные языки и теория автоматов

Лабораторная работа № 1

Описание языка программирования

Описание языка программирования

Вопросы разработки, использования и реализации языков программирования тесно связаны с проблемой точного описания (определения) языка. Для определения языка требуется задать множество основных символов языка и описать его синтаксис и семантику. Синтаксис языка определяет правила составления корректных программ как цепочек, состоящих из основных символов языка. Семантика задает смысловые значения конструкций языка, а также интерпретацию различных синтаксических конструкций языковым процессором. Руководство по языку программирования должно включать в себя описание синтаксиса и семантики каждой конструкции языка, как по отдельности, так и в совокупности с другими конструкциями.

С точки зрения пользователя, описывающего на языке программирования алгоритмы решения своих задач, точное определение языка необходимо для того, чтобы он мог понимать, правильно применять и записывать конструкции этого языка. Разработчикам языковых процессоров (компиляторов, интерпретаторов) точное описание языка требуется для правильной реализации языкового процессора, поскольку вид и смысл языковых конструкций Должны быть в точности такими, как их задумал автор языка. Все реализации языкового процессора должны выдавать идентичные результаты для одной и той же программы.

Основными функциями языкового процессора являются:

□ контроль соответствия исходной программы описанию языка программирования;

□ перевод правильной программы с языка программирования в машинный код, который может быть выполнен на процессоре (виртуальном или физическом).

Для реализации перечисленных функций средства описания синтаксиса и семантики языка должны иметь возможность определять синтаксис, контекстные условия (статическую семантику языка) и отображение операций, предоставляемых языком программирования, в операции процессора, на котором будет выполняться программа (динамическую семантику языка).

Определение синтаксиса языка

Разработка языка программирования начинается с определения его синтаксиса. Естественный язык мало пригоден для этой цели, поэтому для точного описания синтаксиса языка программирования нужен некоторый вспомогательный язык. Язык, предназначенный для описания другого языка, называется метаязыком.

Метаязык задает систему обозначений, понятий языка и образованных из них конструкций, позволяющих представить описываемый язык с помощью определенных ранее понятий и отношений между ними. При этом каждое понятие языка подразумевает некоторую синтаксическую единицу (конструкцию) и определяемые ею свойства программных объектов или процесса обработки данных.

Для описания синтаксиса языков программирования наибольшее распространение получили:

□ форма Бэкуса-Наура и ее различные модификации;

□ синтаксические диаграммы Вирта;

□ формальные грамматики.

Форма Бэкуса-Наура

Форма Бэкуса-Наура (БНФ) представляет собой очень естественный способ описания синтаксиса. В БНФ каждое определяемое понятие – это металингвистическая переменная. Значением металингвистической переменной может быть любая конструкция из некоторого фиксированного для этого понятия набора конструкций. Каждая металингвистическая форма определяет одну металингвистическую переменную и состоит из двух частей: левой и правой. В левой части записывается определяемая металингвистическая переменная, которая заключается в угловые скобки '<' и '>' (предполагается, что эти скобки являются метасимволами и не принадлежат алфавиту определяемого языка), например: <двоичное число>, <метка>, <арифметическое выражение>. В правой части формы записываются все варианты определения конструкции, задаваемой этой формой. Каждый вариант представляет собой цепочку основных символов определяемого языка и металингвистических переменных. Варианты разделяются металингвистической связкой '|', имеющей смысл "или". Левая и правая части формы разделяются метасимволом '::=', означающим "по определению есть". Например, следующие металингвистические формы определяют множество целых чисел:

<целое число> ::= <целое без знака> |+<целое без знака> | –<целое без знака>

<целое без знака> ::= <цифра> | <целое без знака ><цифра>

<цифра> ::=0|1|2|3|4|5|6|7|8|9

Характерной особенностью многих металингвистических форм является наличие в них рекурсии. Рекурсия имеет место в том случае, когда для определения конструкций языков программирования используются металингвистические переменные, обозначающие саму определяемую конструкцию. Рекурсия может быть явной или неявной. Явная рекурсия используется, например, в определении конструкции "двоичное целое". Неявная рекурсия имеет место в случае, когда металингвистическая переменная, обозначающая какую-либо конструкцию, используется на некотором промежуточном шаге определения этой конструкции.

Наличие рекурсивных определений затрудняет чтение и понимание БНФ, хотя и является наиболее удобным способом описания бесконечных языков с помощью конечного числа правил. На практике для описания синтаксиса языков программирования часто используют расширения БНФ, позволяющие более естественно представлять альтернативные, необязательные и покоряющиеся части металингвистических формул. Так, одно из расширений БНФ (РБНФ) разрешает использовать следующие упрощения:

□ необязательные элементы синтаксической конструкции заключаются в квадратные скобки '[' и ']';

□ альтернативные варианты могут в случае необходимости заключаться в круглые скобки для образования многовариантного выбора;

□ элементы синтаксической конструкции, повторяющиеся нуль и более раз, заключаются в фигурные скобки '{' и '}'.

С учетом указанных расширений приведенное ранее определение множества целых чисел можно записать в таком виде:

<целое число> ::= [ + | – ] <целое без знака>

<целое без знака> :: <цифра> { <цифра> }

<цифра> ::=0|1|2|3|4|5|6|7|8|9

Оба описания эквивалентны, но второе описание более компактно и естественно. Любая синтаксическая конструкция, полученная с помощью РБНФ, Может быть получена с помощью БНФ и наоборот.

Синтаксические диаграммы Вирта

Синтаксические диаграммы были предложены Никлаусом Виртом для описания синтаксиса языка Pascal и являются удобной графической формой представления РБНФ.

Элементами синтаксических диаграмм Вирта являются: прямоугольники, кружки или овалы, стрелки. В прямоугольниках записываются имена металингвистических переменных, в кружках или овалах – основные символы языка, а стрелки определяют порядок сочетания металингвистических переменных и основных символов языка для образования определяемой синтаксической конструкции. Каждой синтаксической конструкции соответствует одна диаграмма Вирта. Имя определяемой синтаксической конструкции записывается над стрелкой, входящей в диаграмму (точка входа в диаграмму), которая, как правило, располагается в левом верхнем углу. Любой путь от точки входа в синтаксическую диаграмму к выходу (исходящая из диаграммы стрелка) представляет собой цепочку металингвистических переменных и основных символов языка, соответствующую одному из вариантов правой части РБНФ. На рис. 2.1 приведены синтаксические диаграммы, определяющие множество целых чисел.

Рис. 2.1. Синтаксические диаграммы для определения множества целых чисел

БНФ, РБНФ и синтаксические диаграммы Вирта дают возможность косвенно включать в формальное описание синтаксиса языков программирования элементы семантики, т. к. в них входят металингвистические переменные, являющиеся осмысленными названиями описываемых конструкций. При использовании автоматических методов анализа языков элементы семантики, заложенные в эти формальные модели, теряют смысл, поэтому в теории и практике проектирования языковых процессоров используются формальные грамматики.

Формальные грамматики и рассмотренные в разд. 2.1 формальные модели не позволяют описать синтаксис языка программирования полностью. Некоторые его аспекты, например контекстные условия, могут быть описаны только семантическими правилами.