46144

ПРОГРАММИРОВАНИЕ. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Доклад

Информатика, кибернетика и программирование

Другой пример алгоритма – поиск минимального числа х в последовательности из n чисел 12 . Процесс продолжается до тех пор пока не будут просмотрены все n чисел. ниже диапазон представления чисел в машине. Для представления команд в виде чисел необходимо иметь две кодирующие таблицы.

Русский

2013-11-19

543 KB

1 чел.


Программирование

1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

  1.  Основные понятия теории алгоритмов

Алгоритмом часто называют конечную совокупность инструкций для решения некоторого класса задач. Это определение неформально, так как с его помощью нельзя однозначно ответить на вопросы, что такое “совокупность инструкций” и “некоторый класс задач”.

Для записи алгоритмов можно пользоваться обычным разговорным языком. В этом случае, например, алгоритм возведения числа X в целую положительную степень y, т.е. вычисления по формуле S = XY можно записать в виде следующей системы последовательно выполняемых правил или указаний:

  1.  Присвоить переменной S значение “единица”. Перейти к пункту 2.

Присвоить переменной  i  значение “единица”. Перейти  к пункту 3.

Если i Y, то перейти к пункту 4, иначе – к пункту 6.

Присвоить переменной S ее предыдущее значение, умноженное на

величину X. Перейти  к пункту 5.

Увеличить значение i на единицу. Перейти к пункту 3.

Считать значение S результатом. Вычисления прекратить.

Другой пример алгоритма – поиск минимального числа х в последовательности из n чисел a1,a2, ...,an. Пусть в качестве минимального числа х принимается а1, после чего х сравнивается с последующими числами, начиная с а2. Если x<a2, то х сравнивается с а3 и т. д., пока не найдется число ai. Если ai<х, то x присваивается значение ai и продолжается сравнение  х со следующими числами, начиная с ai+1. Процесс продолжается до тех пор, пока не будут просмотрены все n чисел. В результате х будет иметь значение, равное наименьшему в последовательности числу. Этот процесс может быть записан в виде следующей системы последовательных указаний:

  1.  Положить x = a1. Перейти к пункту 2.

Положить i = 2 . Перейти к пункту 3.

Если i n, то перейти к пункту 4, иначе – к пункту 6.

Если  ai < х , то положить х= ai. Перейти к пункту 5.

Увеличить i на единицу. Перейти к пункту 3.

Считать значение x результатом. Прекратить просмотр.

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

Абстрактным алфавитом называется любая конечная совокупность объектов, называемых буквами или символами данного алфавита. Иными словами алфавит - это конечное множество различимых символов (слово "абстрактный" для краткости здесь и далее опускается). Алфавит, как и любое другое множество,  может быть задан перечислением его  элементов. Например,  алфавит A есть A={a, bc}, алфавит B есть B={x, y}.

Под словом или строкой в алфавите понимают любую конечную  последовательность символов. В последовательности (цепочке) между символами стоит операция сцепки или конкатенации, т.е. менять местами символы в последовательности нельзя. Например, в алфавите А словами являются любые последовательности: aac cbacb bb,  а в алфавите B: x, y, yx, xx и т. п.   

Число символов в слове называется длиной этого слова. Так слова в алфавите А, приведенные в примере, имеют длину соответственно 1, 2, 2, 3, 2. Различают также пустые слова, не содержащие ни одного символа. Слово р называется подсловом слова q, если слово q можно представить в виде q=pr, где r - любое слово, в том числе и пустое. Очевидно, что такое понятие слова будет отличаться от аналогичного в разговорных языках. Здесь под словом можно понимать любую последовательность символов, даже бессмысленную.

При расширении алфавита понятие слова может существенно меняться. Так, например, в алфавите A={0,1,2,3,4,5,6,7,8,9} цепочка символов 69+73 представляет собой два слова, соединенные знаком суммы, а в алфавите В={+,0,1,2,3,4,5,6,7,8,9} это будет одно слово. В общем случае, в качестве символов могут использоваться не только одиночные символы, но и отдельные слова, фразы, абзацы и, даже, целые тексты.

Алфавитным оператором или алфавитным отображением называется всякое соответствие между словами некоторого алфавита и словами в том же самом или в каком-либо другом фиксированном алфавите. Первый алфавит называется входным, а второй – выходным алфавитом данного оператора. В случае совпадения входного и выходного алфавитов говорят, что алфавитный оператор задан в соответствующем алфавите. 

Пусть заданы слова в алфавитах X и Y и заданы соответствия между этими словами. Если xi– слово в алфавите X, а yj – слово в алфавите Y, то алфавитный оператор Гxi=yj  преобразуетет входное слово xi в выходное слово yj. Символ Г в алфавитном операторе означает отображение.

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

Совокупность всех слов, на которых алфавитный оператор определен, называется областью его определения. Алфавитный оператор, не сопоставляющий данному входному слову ai никакого выходного слова bj (в том числе и пустого), на этом слове не определен.

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

Пусть заданы алфавиты: A={p,r,s,t} – входной и B={a,b,c,d,f,g,h} – выходной. Тогда отображение символов А символами В, т.е. кодом (Рис.1.1), является примером кодирующего отображения. Для построения искомого отображения достаточно заменить все символы любого слова ai в алфавите А соответствующими кодами алфавита В.  Так, если слово x=sstr, то Гx=fghfghabcceg есть код исходного слова x.

Процесс, обратный кодированию, т.е. замена в слове bj кодов алфавита В символами из А, называется декодированием и обозначается как Г-1bj=ai. Например, для слова b=fghfghabcceg в алфавите В декодирование Г-1b дает слово a=sstr. 

Если при кодировании слова ai получается некоторое слово bj и декодирование дает исходное слово ai(Гai=bj, Г-1bj=ai), то имеет место обратимость кодирования. Условие обратимости кодирования иначе называется условием взаимной однозначности соответствующего кодирующего отображения. В приведенном выше примере обратимость существует.  Но, если зданы A={a,b,c}, B={r,s}, Га=r, Гb=s, Гс=rs и слово aabca в алфавите А, то обратимость отсутствует, так как Гaabca=rrsrsr, а Г-1rrsrsr=aababa ибо одно из слов acaba, aabca, acca).

Для обратимости кодирования должны выполняться  следующие условия:

 

коды разных символов исходного алфавита А должны быть различны;

код любого символа алфавита А не может совпадать ни с каким из начальных подслов кодов других символов этого алфавита.

Пояснение этих утверждений сводится к следующему. Пусть слово q=b1,b2, ...,bn является кодом слова p=a1,a2, ...,am в алфавите А. Тогда по коду q можно однозначно восстановить слово р. В силу второго условия только одно начальное подслово слова q будет совпадать с каким-либо символом алфавита А. Ясно, что таким подсловом является символ а1. Применяя аналогичные рассуждения к оставшемуся отрезку слова q, можно однозначно восстановить один за другим все символы слова р. Следовательно, любому данному коду может соответствовать только одно слово в А, что доказывает обратимость кодирующего отображения.

Второе условие обязательно выполняется в том случае, когда коды всех символов алфавита А имеют одинаковую длину. Кодирование, при котором все коды имеют одинаковую длину, называется нормальным.

Кодирование позволяет сводить изучение произвольных алфавитных отображений к алфавитным отображениям в некотором стандартном алфавите. Наиболее часто в качестве стандартного алфавита выбирается двоичный алфавит, состоящий из двух символов. В качестве таких символов обычно используются цифры 0 и 1, т.е. С={0,1}. Подавляющее большинство современных ЭВМ обрабатывают информацию, закодированную именно в двоичном стандартном алфавите.

Пусть А – произвольный, а С – стандартный  алфавиты и n - число символов в алфавите А, а m - число символов в алфавите С. В этом случае всегда можно выбрать длину слова L, удовлетворяющую условию mLn и закодировать все символы в алфавите А словами длины l в алфавите С так, чтобы коды различных букв были разными (действительно, число различных слов длины L в m-символьном алфавите равно mL). Любое такое кодирование будет нормальным и порождает обратимое кодирующее отображение слов в алфавите А в слова в алфавите С (см. ниже диапазон представления чисел в машине).

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

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

В случае бесконечной области определения алфавитного оператора задать его с помощью такой таблицы невозможно. В этом случае оператор задается системой правил pi (pi  P, P={pi}, i=1,2, ...,n), позволяющей за конечное число шагов найти выходное слово, соответствующее любому наперед заданному входному слову из области определения рассматриваемого алфавитного оператора.

Формальное определение алгоритма 

Концепции алгоритмов в математических терминах были впервые описаны в 1930 - 1940 г.г., когда велись поиски условий, с помощью которых возможно доказательство проблемы разрешимости задач или, в общем случае, автоматическое доказательство математических теорем. Существуют три основных типа алгоритмических моделей [2]. В первом понятие алгоритм связывается с вычислимыми числовыми функциями. Во втором алгоритм представляется как некоторое универсальное устройство, способное выполнять набор простейших операций (например, машина Тюринга). Третий тип основывается на ранее определенных понятиях абстрактного алфавита и соответствия между словами в таком алфавите, что  позволяет формально описывать процессы преобразования информации.

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

Свойства алгоритма. Всякий алгоритм любому входному слову ставит в соответствие только одно выходное слово. Это одно из основных свойств алгоритма – формальность. Иначе это свойство называют детерминированностью или однозначностью.

К числу других свойств алгоритма относятся массовость и результативность.

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

Свойство результативности определяет понятие области применимости алгоритма. Областью применимости называется множество слов, для которых алгоритм результативен.

Тогда массовость алгоритма – это применимость ко всей области  его определения.

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

Оценка сложности алгоритмов

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

А – алгоритм решения некоторого класса задач и n-размерность одной задачи из этого клааса (в частном случае n может быть, например  длинной последовательности в рассмотренном выше алгоитме, количеством слов в анализируемом тексте и т.п.);

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

Тогда алгоритм называется полиномиальным, если fA(n) растет не быстрее чем полином от n. В противном случае алгоритм А называется экспоненциальным.  Так, функции типа kn, kn2,kn3,..., где k – коэфициент, могут рассматриваться как полиномиальные, а функции типа 2n, nn, n!... как экспоненциальнные. Для достаточно больших n значение экспоненциальной функции всегда превышает значение полиномиальной функции. Для малых n это не всегда справедливо, но всегда есть такое n, для которого значение экспоненциальной функции превышает аналогичное для полиномиальной.

Время, затраченное на реализацию алгоритма, как функция размерности задачи называется временной сложностью алгоритма и обозначается как O[fA(n)]. Применительно к решению задачи на ЭВМ это время является в большинстве случаев свойством самого алгоритма и слабо зависит от машины, на которой решается соотвтствующая алгоритму программа.

Кроме временной сложности алгортмов существуют и другие меры сложности. Так, сложность можно характиризовать числом операций N (применительно к конкретной ЭВМ) и общим объемом информации Р, т.е общим количеством слов, используемых при выполнении алгоритма. Тогда время его выполнения на конкретной ЭВМ связано с числом операций, а объем информации связан с объемом памяти, необходимой машине для реализации соответствующей программы. Следовательно, время реализации алгоритма есть функция  T=f(N). При таком подходе значения Т и Р называют соответственно вычислительной и емкостной сложностью алгоритма.

Блок-схемы алгоритмов  

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

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

Операторный блок – это прямоугоник, в который вписывается некоторое действие или выражение (Рис.1.2.а). Этот блок может иметь несколько входов и только один выход, что обеспечивает однозначность в определении последовательности выполняемых действий. Исключение составляют начальный и конечный блоки. Первый не имеет входов, второй – выхода.

Условный блок обозначается ромбом, в который вписывается некоторое условие. Поскольку результатом проверки условия может быть либо “да”, либо “нет” (“истина” или “ложь”, “0” или “1”), блок имеет два соответствующих этим ответам выхода (Рис 1.2.б).

Если операторный или условный блоки имеют более одного входа, то изображение входов совмещается (Рис 1.2.в). На связях, определяющих последовательность выполнения блоков, стрелки не обязательны, если их направление сооветствует продвижению “сверху-вниз” и “слева-направо”. Ограничения на геометрические размеры блоков в этом случае не вводятся.

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

Блок-схемы алгоритмов вычисления степенной функции и решения квадратного уравнения  иллюстрируется соответственно рисунками Рис.1.3.а,б и 1.4.

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

  1.  Структура ЭВМ неймановского типа

Традиционная структура, предложенная Дж. Нейманом для однопро-цессорных ЭВМ в 1947г., до настоящего времени не претерпела принципиальных изменений. В качестве основных устройств ЭВМ (Рис.1.5.) можно выделить Оперативную Память (ОП), Арифметико-Логическое Устройство (АЛУ) и Устройство Управления (УУ), назначение которых сводится к следующему.

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

ОП структурирована, т.е. в простейшем случае содержит n ячеек, каждой из которых ставится в соответствие номер от нуля до n-1. Этот номер называется  адресом  ячейки.

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

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

Понятию адреса в полной мере соответствует понятие переменной в алгебре. Действительно, адрес соответствует уникальному имени переменной и как ячейке с некоторым адресом, так и переменной можно присвоить определенное значение.  Например, присваивание i := i+1, следует понимать как присваивание содержимому ячейки с адресом "i" ее предыдущего значения, увеличенного на единицу.

Арифметико-логическое устройство позволяет выполнять некоторое (заранее заданное) множество инструкций и настраивается на выполнение конкретной инструкции управляющими сигналами, поступающими из устройства управления. Как правило, АЛУ сохраняет результат выполненной инструкции до выполнения очередной, что позволяет использовать и одноадресные команды (см. ниже).

Устройство управления обеспечивает чтение и запись информации в ячейки с заданным адресом и формирование управляющих сигналов, необходимых для управления АЛУ и Устройствами Ввода-Вывода (УВВ) в процессе выполнения команд. Устройства ввода-вывода информации иначе называют внешними устройствами, назначение которых – обеспечить  взаимодействие человека с машиной.

Команда (Рис.1.6.) представляет собой число, разделенное на группы цифр, первая из которых содержит код операции, а следующие – адреса ячеек памяти. Например, трехадресная команда соответствует обычному представлению двухместных алгебраических операций вида x := y * z, которая читается как выполнить операцию * над переменными   y и z (содержимым ячеек c адресами y и z) и результат присвоить переменной x (ячейке с адресом х), а при выполнении одноместных операций значение "лишних" адресов не используется.

Код операции

адрес 1

адрес 2

адрес 3

Рис 1.6. Упрощенная структура трехадресной команды.

В общем случае команда может содержать один, два, три или даже четыре адреса. Например, одноадресная команда – удобная инструкция для таких действий, как передача значения переменной из устройства ввода в ячейку памяти с заданым адресом, передача содержимого ячейки с заданым адресом в АЛУ, сложение содержимого АЛУ с содержимым заданой ячейки и т.п. Одноадресные команды удобны тем, что не содержат “лишних” адресных полей, но приводят к увеличению необходимого для решения задачи количества инструкций. В четырехадресных командах четвертый адрес обычно используется для указания места, где расположена следующая выполняемая инструкция. Выбор структуры команд осуществляется на этапе проектирования самой ЭВМ и к рассматриваемой  предметной области прямого отношения не имеет.

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

Для формирования и временного хранения адреса выполняемой команды используется узел УУ, называемый СЧетчиком Адреса Команды (СЧАК) или регистром-указателем номера команды (Pointer Instruction – PI). Понятие адреса команды и назначение СЧАК (PI) определяется ниже.

  1.  Принцип программного управления

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

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

Фрагмент первой таблицы (Таблица 1.а) позволяет поставить в соответствие операциям некоторые коды. Так из этой таблицы следует, что операции записи в ячейку памяти с адресом, указанным в первом из адресов команды – А1, некоторого значения соответствует код 01 (операция ввода числа), чтения числа из ячейки с адресом А1 с выдачей результата на УВВ – код 02 (операция вывода), сложению – код 03 и т. д. Такого типа таблица является принадлежностью конкретного типа ЭВМ, т.е. “заложена” в нее при проектировании.

Таблица 1.а. Фрагмент системы команд абстрактной ЭВМ.

Действия, выполняемые командой

Код команды

Ввод (запись) числа из УВВ в [А1]

01

Вывод  [А1]  на УВВ

02

Сложить [А1} с [А2] и результат поместить в [А3]

03

Вычесть из [А1]  [A2] и результат поместить в [A3]

04

Умножить [А1] на [А2] и результат поместить в [А3]

05

Разделить [А1] на [А2] и результат поместить в [А3]

06

. . .

. . .

Закончить выполнение программы

00

Количество строк в таблице соответствует мощности множества команд, составляющих систему команд этой ЭВМ (для современных ЭВМ система команд может содержать более тысячи инструкций; коды операций, также как и структура команды, выбираются при проектировании ЭВМ ).

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

Пусть необходимо выполнить  вычисление величины а, которая задана выражением а=((b+c)d2 - e)/f при условии, что свободной является память ЭВМ, начиная с 100 ячейки. Тогда под переменные можно "распределить память”, например, таким образом (выбор в общем случае произволен):  переменной а поставить в соответствие ячейку с адресом 100,  переменной b - ячейку с адресом 101; и т.д. (Таблица1.б), в которой  переменная r предназначена для хранения промежуточных   результатов.

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

Таблица 2. Программа вычисления выражения а=((b+c)d2 - e)/f.

No

КОП

А1

А2

А3

Примечание(коментарий)

1

01

101

000

000

ввод значения b 

2

01

102

000

000

ввод значения c 

3

01

103

000

000

ввод значения d

4

01

104

000

000

ввод значения e

5

01

105

000

000

ввод значения f

6

03

101

102

106

r := b+c(сложение b и c, результат в r)

7

05

103

103

103

d := d x d   (вычисление величины d2)

8

05

106

103

106

r := r + d      (b + c) x d2

9

04

106

104

106

r := r - e      ((b + c) x d2) - e

10

05

106

105

100

a := r : f      (((b + c) x d2) - e) / f

11

02

100

000

000

вывод а

12

00

000

000

000

конец вычислений (адреса не нужны)

Форма таблицы соответствует бланкам, которые использовали программисты в начале-середине 50-ых годов. Правила составления такой таблицы очевидны при условии, что А1 является адресом первого операнда, А2 – адресом второго операнда и А3 - адресом результата, а вычисление выражения "разложено” (структурировано) на двухместные и одноместные операции.

Пример тех же самых вычислений, но с использованием одноадресных команд иллюстрируется программой, которая приведена в Таблице 3. Здесь используются дополнительно введеные коды операций: 07, предписывающий передачу содержимого ячейки памяти с адресом А в АЛУ, 08 – обратные действия, а  коды 03-06 определяют выполнение соответствующих операций над переменными, одна из которых находится в АЛУ, другая - в ячейке с адресом А, и  сохранением результата в АЛУ.

Таблица 3. Программа с использованием одноадресных команд

No

КОП

 А

    Примечание

No

КОП

 А

     Примечание

1

01

101

ввод b

8

05

103

(b+c) x d

2

01

102

ввод c

9

05

103

(b+c) x d2

3

01

103

ввод d

10

04

104

(b+c) x d2-e

4

01

104

ввод e

11

06

105

((b+c) x d2-e)/f

5

01

105

ввод f

12

08

100

АЛУ заслать в a

6

07

101

b заслать в АЛУ

13

02

100

вывести a

7

03

102

b+c

14

00

00

конец вычислений

Как следует из таблицы, программа относительно предыдущей “удли-нилась” всего на две команды, но при этом не имеет “лишних” адресных полей (за исключением последней команды).

Записанная таким образом последовательность команд или программа представляет собой последовательность чисел, которые можно разместить в памяти ЭВМ.

Пусть программа размещена в свободной зоне памяти начиная, например, с ячейки 501 (такое размещение обычно осуществляется с помощю сложения номера команды с константой или так называемым смещением, которое в рассматриваемом случае равно 500). Тогда для  автоматического выполнения программы достаточно занести в СЧАК (РI) число 501 (так называемый пусковой адрес) и включить режим автоматического выполнения программы.

При этом всегда будут производится одни и тот же набор действий – цикл выполнения команды :

1. Содержимое ячейки памяти, адрес которой определяется значением СЧАК (PI), т.е. первой команды программы, передается в регистр команд устройства управления.

2. Если код операции команды не предписывает прекращение вычислений, то выполняется пункт 3, иначе пункт 7.

3. С помощью дешифрованного кода операции АЛУ настраивается на выполнение заданной операции.

4., Числа, которые хранятся в ячейках, указанных адресами команды, передаются в АЛУ в качестве операндов.

5. Выполняется операция и, если необходимо, результат заносится в ячейку памяти с адресом, указанным в команде.

6. Содержимое СЧАК (PI) модифицируется (в простейшем случае к содержимому СЧАК (PI) прибавляется единица, т.е. выполняется присваивание СЧАК := СЧАК+1) и происходит возврат в начало цикла (к пункту 1).

7. Вычисления заканчиваются т.е. прекращается автоматическое выполнение программы.

Таким образом, принцип программного управления в упрощенном виде основывается на том, что программа должна быть представлена в числовом виде, размещена в памяти ЭВМ, а сама ЭВМ должна выполнять некоторую процедуру автоматической выборки и исполнения очередной команды вплоть до окончания программы.

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

  1.  Формы представления чисел в памяти ЭВМ

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

Под системой счисления обычно понимают совокупность правил, позволяющих однозначно записать число, т.е. дать ему уникальное имя. Количество различных систем счисления достаточно велико. Строгое определение понятия системы счисления, классификацию и сравнительные характеристики последних можно найти в теории чисел или, применительно к рассматриваемой предметной области, в специальной литературе по компютерной арифметике[ ].

Наиболее широко распространенной системой счисления, используемой для представления чисел в памяти ЭВМ, является позиционная однородная система счисления с основанием р=2 (двоичная система счисления).

В общем случае число в позиционной  однородной системе счисления с основанием р определяется степенным рядом:

 

anpn + an-1pn-1 +... + aipi +...+ a2p2 + a1p1 + a0p0,

       

где ai ={0,1, ..., p-1}- цифры ситемы, p – основание системы.

Сокращенная и обычно применяемая форма записи числа представляет собой последовательность цифр:

an an-1 ... ai ... a2 a1 a0 .

Система собственно и называется однородной позиционной потому, что от позиции, которую занимает цифра в сокращенной форме записи числа, зависит ее “вес” и этот вес пропорционален степени одного и того же основания. Кроме того, для позиционных систем счисления обяазтельна цифра “0”, которая используется для обозначения “пустых” позиций.

Так при основании “десять” для обозначения чисел используются десять арабских цифр, ai ={0, 1, ..., 9}, а сокращенная запись вида 1263951 соответсвует степенному ряду:

1*106 + 2*105 + 6*104 + 3*103 + 9*102 + 5*101 + 1*100 

При основании “два” для записи чисел используются только две цифры, т.е. ai ={0, 1} и, например, число  1110101  соответствует ряду:

1*26 + 1*25 +1*24 + 0*23 + 1*22 + 0*21 +1*20

и, если подсчитать сумму членов ряда, то десятичному числу 54.

Ниже Таблицей 5. иллюстрируется изображение первых восемнадцати чисел в позиционных однородных системах счисления с основаниями 2, 4, 8, 16 и 10 (основания систем в первой строке таблицы записаны в десятичной системе). При этом для изображения цифр в системах с различным основанием использованы символы цифр десятичной системы, а для недостающих цифр шестнадцатиричной – первые шесть букв латинского алфавита.

Таблица 1.5  Представление чисел в позиционных однордн. системах счисления

Основание системы счисления

Основание системы счисления

10

16

8

4

2

10

16

8

4

2

0

0

0

0

0

9

9

11

21

1001

1

1

1

1

1

10

a

12

22

1010

2

2

2

2

10

11

b

13

23

1011

3

3

3

3

11

12

c

14

30

1100

4

4

4

10

100

13

d

15

31

1101

5

5

5

11

101

14

e

16

32

1110

6

6

6

12

110

15

f

17

33

1111

7

7

7

13

111

16

10

20

100

10000

8

8

10

20

1000

17

11

21

101

10001

Как видно из таблицы, основание любой системы счисления в этой же системе обозначается сочетанием цифр 10, поэтому если нет ссылок на то, что рассматриваемая система является десятичной, число “10” следует читать как “один, ноль” и оно не явяется числом “десять”.

Рассматриваемая форма представления чисел называется естественной формой или формой с фиксированной точкой (запятой). Точка используется для разделения числа на целую и дробную части. Это разделение условно, поскольку определяется единицей измерения соответствующей величины, и оказывается существенным только при выполнении арифметических операций. Так, например, мера 3.5 см. может быть заменена числом 0.35 м. или целым числом 35 мм.

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

Ячейка памяти для хранения чисел в естественной форме  иллюстрируется Рис.1.6 Знаковый разряд позволяет определить знак числа, а n-разрядная мантисса хранит его значащую часть

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

Так десятичное число  625.324 может  быть  представлено  в  виде 0.625324 * 103 , 6.25324 * 102 или 625324 * 10-3 и т. п. Для записи чисел с плавающей точкой в памяти машины кроме знакового разряда числа  и мантиссы требуются разряды для отображения знака порядка (показателя степени во втором сомножителе) и значения самого порядка (Рис 1.7).

Такие числа в языках высокого уровня чаще всего называются вещественными (real) и записываются в виде 0.625324 Е+3 или 625324 Е-3 и т. п., где Е разделяет мантиссу и порядок.

Минимальным числом, которое можно представить в n-разрядной мантиссе ячейки с фиксированной точкой, будет число Аmin=0.000 . . .001 или Аmin=2-n. Числа меньше этого должны были бы размещаться в несуществующих разрядах и поэтому воспринимаются как “0”. Такие числа называют машинным нулем. Последний определяет погрешность вычислений.

Максимальное число, которое можно представить в ячейке памяти с фиксированной точкой, есть величина Аmax= 0.111 . . . 111 или Аmax=1-2-n.  В этом нетрудно убедиться,  если  из числа 1,000 . . . 000 в двоичной системе счисления вычесть единицу младшего разряда, т.е. 2-n.

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

Диапазон представления в общем случае есть отношение Amax/Amin. Это отношение позволяет в свою очередь определить кардинальное число card(А) (card – сокращенное от cardinaliti, т.е. мощность множества значений (чисел), которые могут быть представлены в ячейке памяти). Понятие диапазона представления иллюстрируется Рис. 1.8, на котором числа представлены в десятичной системе счисления.

Переполнение разрядной сетки

Amax

9

9

.

.

.

9

.

.

.

9

9

9

9

.

.

.

9

.

.

.

9

8

Область представимых в мантиссе чисел

0

0

.

.

.

0

.

.

.

0

2

Amin

0

0

.

.

.

0

.

.

.

0

1

0

0

.

Машинный ноль

.

0

0

Рис 1.8. Диапазон представимых чисел в ячейке с фиксированной точкой. 

Для n-разрядной ячейки с фиксированной  точкой  диапазон  представления D есть величина D=2-n/(1- 2-n)=2n-1.

У современных ЭВМ длина физической ячейки, как павило, равна одному байту, т.е. восьми двоичным разрядам При длине ячейки в один байт D=255. С учетом возможности представления в такой ячейке и числа “0” ее кардинальное число равно 256, т.е. card(байт)=256. Естественно, что  такое кардинальное число слишком мало для представления чисел. Поэтому реально числа представляются в  логических ячейках, длина которых соответствует нескольким физическим ячейкам (байтам) и, соответственно, таким образом увеличивается их диапазон представления.

Если длина логической ячейки, например,  равна двум байтам, то реальный диапазон представления есть величина D =215-1=32767 (показатель степени равен 15, поскольку шестнадцатый разряд - знаковый), а кардинальное число – card =216 (с учетом возможности представления отрицательных чисел и нуля).

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

Абсолютная погрешность A есть среднее арифметическое между максимальным и минимальным значениями “отбрасываемой” части числа, т.е. той части, которая соответствует машинному нулю. Максимальное значение для n-разрядной мантиссы  в пределе равно 2-n (единице младшего раряда), а минимальное – нулю. Таким образом   A=2-(n+1).

Относительная погрешность есть величина, определяемая отношенем абсолютной погрешности к самому числу, т.е. лежит в интервале [min, max]. При этом  min,= A /Amax , а  max=A/Amin. Таким образом, относительная погрешность вычислений при представлении чисел, например, в форме с фиксированной точкой может колебаться в пределах от 0 до 100%.

При желании определить диапазон и точность представления чисел с плавающей точкой лучше предварительно ознакомиться с соответствующей литературой, например, [16], поскольку числа в ячейке машины обычно представляются в нормализованной нормальной форме, т.е. у мантиссы первый разряд всегда значащий (не равен нулю).

  1.  Эволюция средств программирования

При написании фрагментов программ ранее использовались числовые коды операций и числовые значения адресов памяти. Такой способ написания программ называется программированием в числовых кодах. Его трудоемкость очевидна. Нормой для квалифицированного программиста, пишущего такие программы, считалось оформление 4-8 отлаженных относительно всей программы команд в рабочую смену, а сложность реальных программ характеризовалась несколькими сотнями команд. При большей сложности программист попадал в фазу “панической отладки”, когда устранение ошибок приводило к внесению новых и т. д. Поэтому естественным оказалось стремление облегчить труд программиста, частично возложив его на саму машину, т.е. автоматизировать процесс написания программ.

Первым шагом в этой области можно считать разработку программ, которые “переводили” (транслировали) более привычную для человека символьную форму пошагового описания вычислений в программу, написанную в числовых кодах. Примером такой пошаговой формы может служить левая часть комментария в таблице 2, выделенная жирным шрифтом. Таким образом, в средства программирования вводится абстракции (понятие переменной, символьное изображение операций), которые позволяет программисту отвлечься от проблем, связанных с формой представления чисел, кодированием операций и  распределением памяти. Однако, в этом случае перед программой-транслятором (точнее перед разработчиком этой программы) возникает не простая задача: каким образом выбрать форму представления чисел и размер логической ячейки при формировании таблицы распределения памяти. Простейший способ ее решения – выбрать для всех переменных один и тот же размер логической ячейки “с запасом”. Такое решение мало пригодно потому, что всегда приведет к лишним затратам памяти. Кроме того, остается неясным выбор формы представления чисел. Более эффективное решение заключается в том, что транслятору в тексте программы необходимая для этих целей информация сообщается дополнительно, т.е. в программу некоторым образом вводится спецификация типов переменных и на основании этой спецификации строится таблица распределения памяти.

Подобные описанному выше языки программирования назывались языками символического кодирования, а системы программирования – системами символического кодирования (ССК). Сегодня такие языки превратились в достаочно мощные средства программирования, называемые Ассемблерами.

Дальнейшими шагами в этом направлении явилось расширение палитры средств языков (дополнительных абстракций) и параллельное совершенствование трансляторов. Здесь можно упомянуть язык FORTRAN (абревиатура от FORmula TRANslation). Эти языки (языки высокого уровня) позволяли записывать формулы в принятом для алгебраических выражений виде, управлять форматами чисел, вводом-выводом, организовать ветвящийся и циклический вычислительный процесс, работать с простейшими структурами данных и др., причем язык FORTRAN используется и совершенствуется по сей день.

По мере усложнения языков программирования создавать и анализировать программы становилось проще и удобнее, но в то же время задача перевода программ на язык числовых кодов команд, выполняемых  машиной, становилась все труднее. Эти трудности компенсировались с помощью  ступенчатой трансляции (на жаргоне – метода “раскрутки” программного обеспечения), при которой использовались уже имеющиеся трансляторы, или сам транслятор программировался на языке достаточно высокого уровня. Например, в первом случае для трансляции FORTRAN-программы достаточно “превести” ее в текст на языке АССЕМБЛЕР, а остальное завершит транслятор с АССЕМБЛЕРА.

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

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

Структура виртуальной машины позволяет определить три типа ошибок в программах.

  1.  Ошибки, которые связаны с нарушением правил грамматики в тексте программы на языке высокого уровня. Эти ошибки можно обнаружить при трансляции, поэтому их называют ошибками времени трансляции.

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

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

Однако ошибки могут быть не только в программе, они могут появляться и в данных. Примером ошибки в исходных данных является ввод значения переменной x вместо y или числа 5 - вместо числа 15. Некоторые языки высокого уровня строятся таким образом, что ошибки этого типа можно частично обнаружить.

Начала современной трактовки концепций разработки универсальных языков программирования высокого уровня были заложены в языке АЛГОЛ 60, официальное сообщение о котором появилось в 1960 году. Параллельно закладывались концепции для разработки проблемно-ориентированных языков высокого уровня для решения, например, экономических задач и  задач делопроизводства (COBOL), моделирования сложных систем (SOL, SIMULA) и т. п.

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

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

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

  1.  Формализованноеное определение понятия “язык”

Формально, хотя и недостаточно строго,  язык определяется четверкой:

L= { VT, VH, P, S },  

где :

VT = {vTi}, i=(1,2,...,n) – множество терминальных символов или терминальный словарь языка, который также называют его алфавитом. Слово “алфавит” здесь почти полностью соответствует его неформальному определению в разговорных языках и отличается тем, что включает все символы, в то время как, например, точка, запятая, знак переноса, восклицательный знак и т.п. при неформальном определении разговорных языков в алфавит не включаются;

VH = {vHi},  i=(1,2,...,m) –множество нетерминальных символов или конструкций языка ( применительно к разговорным языкам это, например, префикс, корень, подлежащее, сказуемое, простое предложение и т. п.):

P = {pi},  i=(1,2,..., m) - множество правил грамматики или синтаксических конструкций, с помощью которых строится нетерминальный словарь; множество правил грамматики иначе еще называют синтаксисом языка;

S - цель грамматики (старший нетерминальный символ); по аналогии с разговорным языком это, например, текст; в языках программирования это программа.

 

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

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

<  – открывающая угловая скобка;

>  – закрывающая угловая скобка;

|  – знак альтернативы (союз “или”);

::= – “равно по определению” или “это есть”.

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

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

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

Например, терминальный словарь языка Паскаль может быть описан с помощью следующих ниже правил грамматики. Эти правила определяют конструкции, которые задают и классифицируют алфавит языка.

 

<основной символ>          ::= <буква>

                                         <цифра>

                                         <знак операции>

                                         <ограничитель>

                                         <разделитель>

                                         <зарезервированое слово>

<буква>                           ::= abcdefghijklmnoprstuvwxyz

<цифра>                          ::= 0123456789

<знак операции>               ::= +-div/notandorin :=<><=>==<>

<ограничитель>                 ::= ( ) [ ] begin end . , ; .. :

<разделитель>                   ::= { } (* *)  

<зарезервированое слово>   ::= and array case do downto else filefor                                           

                                           function goto if label mod nilof

                                           packed procedure programrecord repeat

                                           set then to type until varwhilewith

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

Приведенными выше синтаксическими конструкциями основные символы разделены на шесть групп. Это буквы, цифры, знаки операций, ограничители, разделители и зарезервированные слова. Такое разделение условно, т.е. правила можно сформулировать иначе и определять последующие правила с учетом изменений. Например, правило определяющее знаки операций можно представить так:

<знак операции>                           ::= <знак арифметической операции>

                                                       <знак логической операции>

                                                       <знак операции отношения>

                                                       <прочие>

<знак арифметической операции>    ::= +-  div /

<знак логической операции>          ::= not and or

<знак операции отношения>            ::= <><=>==<>

<прочие>                                     ::= in :=

С другой стороны терминальный словарь можно было бы задать одним правилом, в правой части которого через разделитель “или” перечислить весь алфавит. Правило в таком виде позволит определить принадлежность символа к алфавиту языка, но приведет к необходимости определить, что такое  <буква> и <цифра> в следующем примере.

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

В качестве следующего примера рассматривается правило, определяющее конструкцию <идентификатор>. Идентификаторы используются в качестве имен переменных, процедур и т. п.

<идентификатор>                  ::= <буква>

                                               <идентификатор><буква>

                                               <идентификатор > <цифра>

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

 Грамматический разбор произвольно выбранной цепочки a12hx на соответствие ее конструкции <идентификатор> иллюстрируется рисунком (Рис.1.10).

С точки зрения грамматического разбора более сложной является конструкция <число>, определяющая допустимую форму записи чисел в языке Паскаль с помощью следующих правил.

<число>                             ::=  <число без знака>

                                             <знак><число без знака>

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

                                             <вещественное без знака>

<вещественное без знака>     ::= <десятичная дробь>

                                             <десятичная дробь>

                                             <десятичный порядок>

<десятичная дробь>             ::= <целое без знака>.<целое без знака>

<десятичный порядок>         ::= Е <целое без знака>

                                             Е <знак><целое без знака>

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

<знак>                               ::=  +-

Грамматиеский разбор произвольно выбранного вещественного числа иллюстрируется Рис.1.11.

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

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

<строка>                               ::= '<последовательность символов>'

<последовательность символов> ::= <символ>

                                                <последовательность символов>

                                                <символ>

<символ>                              ::=  <основной символ>

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

Рассмотренные выше в примерах нетерминальные конструкции по сути  являются лексемами. К лексемам обычно относят специальные символы, метки, идентификаторы, числа и строки, поскольку с позиций разработчика транслятора зарезервированные слова и некоторые группы символов (например, := или <>) также рассматриваются как конструкции, а не единичный символ. Таким образом программа на первом уровне грамматического разбора состоит из лексем и разделителей, причем разделитель обычно представляет собой пробел или комментарий. Две соседние лексемы, если они являются зарезервированным словом, идентификатором, меткой или числом, должны быть отделены друг от друга одним и несколькими разделителями. Исключение – строки, которые могут включать символ пробела.

  1.  Стандарт языка Паскаль

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

Под переносимостью обычно понимают возможность “переноса“ текста программы без изменений на другую виртуальную машину, т.е. возможность решения задачи не только с применением другой версии системы программирования, но и, возможно, другого типа ЭВМ.

Предварительное описание языка было опубликовано в 1968 году Никлаусом Виртом, профессором Цюрихского технического университета (Швейцария), в виде Сообщения о Паскале. В 1973 г. вышло в свет Пересмотренное сообщение, где язык был уже определен в терминах множества символов Международной организации по стандартизации (ISO). В сообщении описывается Стандарт Паскаля, который затем уточнялся Британской рабочей группой по стандартам (BSWG), Американским национальным институтом стандартов (ANSI) и другими организациями. Однако, предлагаемые уточнения по существу мало затрагивали авторское Сообщение о Паскале.

Наиболее распространенные версии систем программирования на основе этого языка для машин типа IBM PС и совместимых с ними разрабатывались фирмой Borland International начиная с 1983 г. и имели название Turbo Pascal  с  порядковыми номерами. Версии с номерами до 4.0 реализовали Стандарт Паскаля с незначительными расширениями. Четвертая версия (1987 г.) внесла существенные изменения в технологию организации модульнной структуры программ и имела встроенную интегрированную среду разработки (Integrated Development Environment – IDE). Начиная с версии 5.5 (1989 г.) язык был концептуально расширен, т.е. дополнен средствами объектно-ориентированного программирования. Версия 6.0 снабжалась объектной библиотекой Turbo Vision, встроеным ассемблером (BASM), усовершенствованными средствами отладки в рамках новой IDE и другими дополнениями. Очередные версии ориентированы на оконные операционные системы, более совершенные объектные библиотеки и продолжают интенсивно развиваться.

С учетом существенных расширений языка понятие “Стандарт языка Паскаль” по настоящее время не теряет смысла, поскольку именно Стандарт является ядром современных версий языка, если не принимать во внимание концептуальное расширение за счет включения в язык средств объектно-ориентированного программирования. При этом следует отметить, что для разработки версии языка Object Pascal фирмой Apple в конце восьмидесятых годов привлекался автор языка Н. Вирт.

В частности, приведенные выше примеры синтаксических конструкций соответствуют терминальному словарю и лексемам Стандарта языка Паскаль, но в последних версиях систем программирования фирмы Borland расширены.

Упражнения

  1.  Скорректируйте известные Вам синтаксические конструкции в соответствии с принятыми в Borland Pascal расширениями.
  2.  При наличии машины, не анализируя смысл и не обращая внимания на разметку текста разным  шрифтом, наберите программу:

Program XXX;

var

A,B,S : Integer;

C,D,R : Real;

begin

A := . . . ;

B := . . . ;

C := . . . ;

D := . . . ;

S := A+B;

R := C+D

end.

Замените в тексте многоточия  изображением целых чисел (Integer) в строках A := . . . ; B := . . . ; и изображениями вещественных чисел (Real) в строках C := . . . ; D := . . . ; . При ошибках в записи чисел транслятор об этом сообщит. Замените имя А (во всем тексте) на другой идентификатор. Ошибка в записи также будет отмечена транслятором. Поупражняйтесь в выборе имен.  Два последних оператора позволяют определить диапазон представления целых и вещественных чисел. Определите этот диапазон, используя сообщение транслятора о “переполнении”.

При отсутствии машины запишите различные варианты целых и вещественных чисел, а также идентификаторов. Корректность записи проверьте с помощью грамматического разбора в соответствии с приведенными выше примерами (Рис.1.10, 1.11).

2. Составьте различные варианты блок-схем алгоритмов вычисления степенной функции для Y 0 и произвольного целого (в том числе и отрицательного) значения Y. Вариантов таких блок-схем может быть более двух десятков.

  1.  Используя разложение функции в ряд (выберите подходящее по справочнику), составьте блок-схемы алгоритмов для вычисления функции ln(x) и тригонометрических функций.

4. В предположении, что индексы последовательности могут вычисляться, т.е. для индекса справедливо присваивание значения, вычисленного с помощью некоторого выражения, например I:=I+1, составьте блок схемы алгоритмов для:

вычитания из некоторого числа А последовательности n чисел b1, b2, ..., bn 

по формуле С = (...((A - b1) - b2 - ... - bn);

по формуле C = A -    bi. i=1, …, n;

вычитания из последовательности n чисел a1, a2, ..., an, последовательности чисел b1, b2, ..., bn, т.е. алгоритм вычисления по формуле

Ci = ai - bi, i=1, …, n;

вычислений по формулам:

 Ck =    ai - bk (1 I n, 1 k m);

Ci = ai  bi (1 i m);

C =  П  ai i=1, …, n;

Ci =  П  ak  bi (1 i m, 1 k m).

  1.  Составьте:

алгоритм определения количества одинаковых чисел в последовательности, заданной в виде: a1, a2, ..., an.

алгоритм определения количества одинаковых элементов в матрице В размерностью n m. 

алгоритм умножения матрицы на вектор.

алгоритм умножения матрицы на матрицу.

алгоритм транспортирования матрицы.

алгоритм, реализующий операцию пересечения двух произвольных множеств.

алгоритм, реализующий операцию разности двух произвольных множеств.

36


 

А также другие работы, которые могут Вас заинтересовать

26995. Соотношение частного и публичного права 5.71 KB
  Соотношение частного и публичного права. ПУБЛИЧНОЕ ПРАВО–та часть системы действующего праванормы которого направлены на защиту общего благагосударственного интересасвязаны с полномочиями и организационновластной деятельностью государствас выполнением общественных целей и задач. а также все процессуальные отрасли праваПУБЛИЧНЫЕ.Остальные отрасли права регулирующие общественные отношения с участием частных субъектовдействующих в своих собственных интересахобразуют блок так называемых частных отраслей...
26996. Отрасль права:понятие и виды.Основание деления права на отрасли 8.97 KB
  Отрасль права:понятие и виды.Основание деления права на отрасли. СИСТЕМА ПРАВАисторически сложившаяся ВНУТРЕННЯЯ ОРГАНИЗАЦИЯ ПРАВАкоторая выражается в единстве и разделении права на относительно самостоятельные части. ОТРАСЛЬ ПРАВАэлемент системы правасовокупность норм праварегулирующих однородную сферу общественных отношений.
26997. Понятие и признаки нормы права.структура юридической нормы 6.87 KB
  понятие и признаки нормы права.структура юридической нормы. ПРИЗНАКИ: 1 регулятор типовых общественных отношенийсоциальная роль нормы; 2 общий НЕПЕРСОНИФИЦИРОВАННЫЙ характер; 3 ОБЩЕОБЯЗАТЕЛЬНЫЙ характер; 4 имеет предоставительнообязывающий характерс одной стороны свобода действийнаправленных на удовлетворение интересовс другойобязывает совершать или не совершать определенные действияограничивая свободу отдельных лиц; 5 устанавливается или САНКЦИОНИРУЕТСЯ ГОСМ; 6 реализация нормы обеспечивается мерами ГОС.ответственность за...
26998. Классификация норм права 6.38 KB
  ПРИЗНАКИ: 1 регулятор типовых общественных отношенийсоциальная роль нормы; 2 общий НЕПЕРСОНИФИЦИРОВАННЫЙ характер; 3 ОБЩЕОБЯЗАТЕЛЬНЫЙ характер; 4 имеет предоставительнообязывающий характерс одной стороны свобода действийнаправленных на удовлетворение интересовс другойобязывает совершать или не совершать определенные действияограничивая свободу отдельных лиц; 5 устанавливается или САНКЦИОНИРУЕТСЯ ГОСМ; 6 реализация нормы обеспечивается мерами ГОС.ответственность за нарушение норм; 7 ФОРМАЛЬНАЯ ОПРЕДЕЛЕННОСТЬимеет строго...
27000. Способы изложения норм права в статьях НПА 4.22 KB
  Способы изложения норм права в статьях НПА. НПАакт правотворчества принятый в особом порядке строго определенными субъектами и содержащий норму права. Статья НПАформа выражения способ изложения правовой нормы.Логическая структура нормы совпадает со структурой статьи НПА.
27001. Правоотношения: понятие, состав, виды 6.22 KB
  ПРАВООТНОШЕНИЯ – охраняемые государством и урегулированные нормами права общественные отношениявозникающие вследствие воздействия норм права на поведение людей и характеризующиеся наличием субъективных прав и юридических обязанностей для их участников. ПРИЗНАКИ: 1 Это разновидность социальных отношений в обществе 2 возникаютпрекращаются или изменяютсякак правилона основе норм права в случае наступления предусмотренных нормой фактов. 3 Сторонами правоотношения могут быть лицаобладающие качествами субъекта права правосубъектностью 4 В...
27002. Субъекты правоотношений. Правосубъектность. Правоспособность, дееспособность, деликтоспособность 7.43 KB
  ПРАВООТНОШЕНИЯ–охраняемые государством и урегулированные нормами права общественные отношениявозникающие вследствие воздействия норм права на поведение людей и характеризующиеся наличием субъективных прав и юридических обязанностей для их участников. СУБЪЕКТЫ–участники правоотношенийимеющие субъективные права и юридические обязанностизакрепленные в нормах права. Коллективные субъекты: государственные государствоорганысубъектыгос предприятияучреждения социальные общности нациинаселение определенного районатрудовой коллектив...
27003. Содержание правоотношения. Субъективное право и юридическая обязанность 6.28 KB
  ПРАВООТНОШЕНИЕохраняемые государством и урегулированные нормами права общественные отношениявозникающие вследствие воздействия норм права на поведение людей и характеризующиеся наличием субъективных прав и юридических обязанностей для их участников. СОДЕРЖАНИЕ правоотношения составляют субъективные права и юридические обязанности. ЮРИДИЧЕСКОЕ СОДЕРЖАНИЕ–это возможность определенных действийуправомоченным лицомдолжностнымнеобходимость выполнения тех или иных действий обязанным лицома также необходимость соблюдения запретовустановленных...