В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова - Введение в язык Паскаль (1107618), страница 3
Текст из файла (страница 3)
В этом случае можно поступить следующим образом. Сначала сказать, что любая отдельная цифра 0 или 1 по определению является двоичным кодом— тем самым выделить частный случай,когда двоичный код состоит из одной цифры. А затем сказать, что если к любому двоичному коду приписать справа еще одну, любую изэтих цифр, то по определению это тоже должно считаться двоичным кодом. То, что было сказано выше словами, можно просто и компактновыразить с помощью метаформул:< двоичная цифра > ::= 0 | 1(двоичный код >: := < двоичная цифра > |< двоичный код ) < двоичщя цифра >Как видно, в правой части формулы, определяющей понятие (двоичный код >, используется само это определяемое понятие.
Подобного рода определения называются рекурсивными. Чтобы при этом не получилось"порочного круга", правая часть формулы должна содержать по крайнеймере одно частное определение, в котором определяемый термин не используется (в данном примере — это (двоичная цифра >) .Для задания синтаксических конструкций произвольной длины частоиспользуется и другой способ: вводятся еще два метасимвола, напримерфигурные скобки " { " и " }", и заключение в эти скобки какой-либоконструкции в метаформуле означает, что эта конструкция может повто10ряться нуль или более раз.
С использованием этого способа можно датьдругое, эквивалентное определение понятия (двоичный к о д >:(двоичный к о д > ::= (двоичная цифра > { (двоичная цифра >}Заметим, что в ряде случаев в качестве допустимой конструкции может использоваться и пустая последовательность основных символов,поэтому в языке обычно используется и такое понятие, как (пусто):( пусто > : :=Эта метаформула означает, что под термином (пусто > понимается отсутствие каких-либо основных символов.
Если например, мы захотелибы выделить конструкцию, представляющую собой произвольную (в частности, пустую) последовательность цифр 0 и 1, то соответствующую мегапеременную (дадим ей имя код1) можно было бы определить следующим образом:( двоичная цифра >: := 0 | 1(код1 > ::= (пусто > | < код1 > ( двоичная цифра >1.2.2. Синтаксические диаграммыСинтаксическая диаграмма графически изображает структуру всех техконструкций, каждая из которых является значением определяемой метапеременной (понятия языка). Отдельным элементом диаграммы можетбыть основной символ или понятие языка. Из каждого элемента выходитодна или несколько стрелок, указывающих на те элементы, которые могутнепосредственно следовать за данным элементом (т.е.
стрелки указываютвозможных преемников каждого из элементов диаграммы). Стрелка, невыходящая из какого-либо элемента, является входом в диаграмму (обычно эта стрелка размещается в левой верхней части диаграммы), а стрелка,не ведущая к какому-либо элементу, означает выход из диаграммы, т.е.конец синтаксического определения.Чтобы легче было отличать в диаграммах основные символы от понятий,эти два типа элементов иногда выделяют каким-либо способом, напримерзаключают основные символы в кружки или овалы, а понятия — в прямоугольники.
Однако в таком выделении типов элементов нет особой необходимости, если для обозначения понятий не использовать отдельные буквы (обычно для этой цели используются слова из нескольких букв илигруппы слов естественного языка). Поскольку между двумя основнымисимволами, являющимися последовательными элементами диаграммы,обязательно должна присутствовать стрелка, то при выполнении указанноговыше условия всегда ясно, чем является элемент диаграммы — основнымсимволом или понятием.Ради достижения некоторой общности с языком БНФ мы сохраним общий вид метаформулы, только правую ее часть будем представлять в видедиаграммы.
Meтапвременные языка по-прежнему будем заключать в угловые скобки.Например, синтаксическая диаграмма•' слог > : : =определяет то же самое понятие, которое ранее было определено с помощью метаформулы( слог >: := A.B.C.11Синтаксическая диаграмма^.переменная> : : =т ; =г-в •эквивалентна метаформуле(переменная > ::= А I Ва диаграмма<выра*ение>::=(переменная) iЬт^эквивалентна приведенному ранее определению понятия (выражение > наязыке БНФ.С помощью синтаксических диаграмм удобно задавать и конструкциипроизвольной длины. Например, приведенное ранее понятие ( двоичныйк о д > можно определить двумя диаграммами-двоичная цифра>::—"ОI><двоичный код>::=• > сдБоичндя цифра)и даже одной диаграммой, не вводя в употребление понятия (двоичнаяцифра >, если оно не требуется для иных целей:<двоичный код>::=Как видно, при использовании синтаксических диаграмм для понятия(двоичный к о д ) оказалось возможным дать нерекурсивное его определение.В связи с тем, что в любом месте синтаксической диаграммы можнозадать произвольное число повторений какого-либо ее фрагмента, можетсложиться впечатление, что в этом способе задания синтаксиса языка можно вообще избежать рекурсивных определений.
Однако это не так: еслимежду числами повторений каких-либо элементов диаграммы должнысуществовать определенные отношения, то исключить рекурсивные определения оказывается невозможным.Действительно, пусть требуется определить понятие (слово >, под которым понимается буква t, заключенная произвольное число раз в круглыескобки — так, чтобы каждой открывающей скобке соответствовала своязакрывающая скобка: (t), ((t)), (((t))) и т.д.На языке БНФ понятие (слово >, если не вводить в употребление промежуточных понятий, придется определить так:(слово >: := (t) | (< слово >)12На первый взгляд кажется, что для этого понятия на языке синтаксических диаграмм можно дать следующее нерекурсивное определение:Однако это определение не эквивалентно предыдущему, по скольку чэ но нетребует соблюдения баланса открывающих и закрывающих скобок.Для соблюдения этого баланса придется и здесь прибегнуть к рекурсивности определения:<слово>: : —Каждый из этих двух способов описания синтаксиса языка имеет своидостоинства и недостатки.
Язык БНФ, вообще говоря, более строг иточен, удобен для публикаций и для представления синтаксиса в памятимашины. Однако он не всегда достаточно нагляден и обычно требует введения в употребление ряда промежуточных понятий. Синтаксические диаграммы более наглядны и потому более просты для понимания, но они менее удобны для публикаций, поскольку каждую диаграмму приходится,как правило, представлять в виде рисунка. Кроме того, качество такогорисунка может повлиять на однозначность понимания диаграммы, а следовательно — и определяемого с ее помощью понятия языка.
В дальнейшем —ради получения читателем практических навыков — мы будем использоватьоба эти способа.1.3. Алфавит языкаАлфавит естественного (например русского) языка состоит из фиксированного набора литер — различимых графических изображений, каждое из которых всегда рассматривается как нечто единое целое, даже в том случае,когда это изображение не является непрерывным, например русскаябуква "Ы".В алгоритмических языках дело обстоит несколько иначе, что связанос рядом обстоятельств.
Дело в том, что тексты, записанные на таких языках, обычно приходится вводить в машину для их последующей машиннойобработки, например с целью редактирования или перевода на машинныйязык. Дтя этого используются различного рода внешние (периферийные)устройства, на которых вводимый в машину текст программы набираетсяс помощью клавиатуры (как на обычных пишущих машинках).Однако на клавиатурах различных типов устройств часто предусматриваются различные наборы литер. К тому же этот набор весьма ограничен и частоне может обеспечить потребности алгоритмического языка.
Например, приформулировании алгоритмов часто приходится использовать операциюсравнения "больше или равно", которую в математике принято обозначатьзнаком (литерой) " ^ ". Но если на каком-либо внешнем устройстве такаялитера не предусмотрена, то указанную операцию сравнения приходитсяобозначать как-то иначе, например парой литер " >" и " = ", т.е. в виде13" > = " . Такой комбинации литер в языке можно предписать вполне определенный смысл, указанный выше, так что эта комбинация литер будет являться своего рода "буквой алфавита" данного языка. В связи с этим будем считать, что алфавит алгоритмического языка состоит из фиксированного набора основных символов, причем часть этих символов являетсялитерами, а часть — определенными комбинациями литер, причем каждаяиз таких комбинаций имеет предопределенный (т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
