В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова - Введение в язык Паскаль (1107618), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

При таком способе часть указаний о подлежащей выполнению•последовательности действий задается в виде обычных математическихформул, а часть таких указаний задается просто словами. Например, известный алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел п и т можно записать в виде:1. Положить А = п, В = т.2. Если А = В то перейти к п. 5, иначе — к п. 3.3.

Если А > В, то в качестве нового значения А принять А - В, а значение В оставить без изменения; в противном случае в качестве нового значения В принять В - А, оставив без изменения значение А.4. Перейти к п. 2.5. Принять НОД =А и прекратить вычисления.Впрочем, по сути дела тот же самый алгоритм можно сформулироватьи короче:1. Принять А = п, В = т.2. Пока А не равно В выполнять:если А > В то положить А = А - Виначе положить В- В - А.3.

Принять значение А в качестве НОД и прекратить вычисления.Как видно, такой способ записи алгоритмов достаточно удобен и поня•тен для человека, но он имеет и весьма существенные недостатки.Во-первых, он громоздок и может быть излишне многословным.Во-вторых, по сути дела одно и то же указание словами можно сформулировать многими различными способами, а это таит в себе серьезную опасность неоднозначности понимания.В-третьих, такая достаточно произвольная формулировка алгоритмапрактически непригодна для автоматического — с помощью ЭВМ — перевода алгоритма на язык машины.7Для устранения этих недостатков и используются формализованные,строго определенные алгоритмические языки, которые в известной мересохраняют достоинства указанного выше способа записи алгоритмов.Алгоритмический язык (как и любой другой язык) образуют три егосоставляющие: алфавит, синтаксис и семантика.Алфавит — это фиксированный для данного языка набор основных символов, т.е. "букв алфавита", из которых должен состоять любой текст наэтом языке — никакие другие символы в тексте не допускаются.Синтаксис — это система правил, определяющих допустимые конструкции из букв алфавита.

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

Скажем, в школьном курсе геометриибыло бы весьма трудно определить, что такое "прямоугольный треугольник", без использования более простых понятий "треугольник" и "угол",а последние — без использования еще более простых понятий "отрезок","луч" и т.д. Аналогично обстоит дело и в случае алгоритмических языков:очень трудно было бы дать достаточно компактное и строгое определениетого, что есть "программа" на данном языке, используя только буквы алфавита этого языка. Эта цель достигается значительно проще, если ввестив употребление (т.е.

определить) ряд промежуточных, более простыхпонятий, которые представляют отдельные фрагменты алгоритмов, а дляопределения этих понятий — в случае необходимости — ввести в употребление еще более простые понятия и т.д.Каждое понятие алгоритмического языка подразумевает некоторуюсинтаксическую единицу (конструкцию) и определяемые ею свойствапрограммных объектов или процесса обработки данных. Так что понятиеопределяется во взаимодействии синтаксических и семантических правил.Синтаксические правила показывают, как образуется данное понятие издругих понятий и (или) букв алфавита, а семантические правила определяют свойства данного понятия в зависимости от свойств используемыхв нем понятий.Запись текста на алгоритмическом языке представляет собой строголинейную последовательность символов (литер), т.е.

не допускаетсяиспользование верхних и нижних индексов (записей типа х 2 или a i k ) ,адробей вида — и т.п. Это требование связано главным образом с необходимостью ввода текста в память машины (в случае машинной его обработки, например с целью его редактирования или трансляции на какойлибо другой язык) , а на современных ЭВМ любые вводимые данные должны быть представлены в виде линейной последовательности литер.81.2.

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

Наиболее распространенными из них являются металингвистические формулы Бэкуса-Наура (язык БНФ) и синтаксические диаграммы.1.2.1. Язык металингвистических формулНа языке БНФ синтаксис языка программирования описывается достаточно компактно и совершенно строго, в виде некоторых формул, весьмапохожих на обычные математические формулы — именно по этой причинетакой способ и называется языком металингвистических формул (или,короче, метаформул).Как уже говорилось, при описании синтаксиса языка используются некоторые его понятия: определив простейшие из них, с их помощью можноуже достаточно просто определить более сложные понятия и т.д., пока небудет определено главное понятие языка — программа. С точки зрения синтаксиса каждое определяемое понятие (но не основной символ) есть метапеременная языка БНФ, значением которой может быть любая конструкция (т.е. последовательность основных символов) из некоторого фиксированного для этого понятия набора конструкций.Для каждого понятия языка должна существовать единственная метаформула, в левой части которой указывается определяемое понятие, т.е.метапеременная языка БНФ, а правая часть формулы тем или иным способом задает все множество значений этой метапеременной, т.е.

все допустимые конструкции, которые объединяются в это понятие. Для большейнаглядности все понятия (метапеременные) обычно заключаются в специальные угловые скобки " < " и " > " (предполагается, что эти скобки непринадлежат алфавиту определяемого языка, т.е. являются метасимволами), например (число), <арифметическое выражение) и т.д. Основныеже символы языка указываются непосредственно. Левая и правая частиметаформулы разделяются метасимволом " : : = ", смысл которого эквивалентен словам "по определению есть".Конечно, метаформула может определять и единственное значение метапеременной. Например, в соответствии с метаформулой( слог ) :: = А.В.С9под термином (понятием) (слог > понималась бы только указанная в правой части пятерка основных символов.

Однако такие метаформулы используются достаточно редко. Обычно в качестве значений метапеременной может приниматься любая из нескольких допустимых конструкций. В этомслучае все допустимые конструкции указываются в правой части формулы и отделяются друг от друга метасимволом " | " (вертикальная черта),смысл которого эквивалентен слову "либо" ("или").Например, метаформулы(переменная) ::= А \В<выражение >: := < переменная > | ( переменная > + < переменная > |< переменная > — < переменная >означают, что под термином ( переменная > понимается любая из букв А илиВ, а под термином (выражение > — любая из следующих десяти записей:АВА+АА+ВВ + АВ + ВА-АА-ВВ-АВ-ВВ приведенных выше примерах значениями каждой метапеременной являлись такие последовательности из основных символов, максимальнаядлина которых ограничена, т.е.

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

Ясно, что определить допустимуюпоследовательность произвольной длины можно только путем заданияправил получения таких последовательностей. В таких случаях в правойчасти метаформулы вместо перечисления- всех допустимых последовательностей на самом деле задается правило их построения.Допустим, например, что мы хотим ввести в употребление понятие< двоичный код >, под которым понималась бы любая непустая последовательность цифр 0 и 1.

Характеристики

Список файлов книги