Правила формального описания синтаксиса языка программирования

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

• символы в кавычках переносятся в конструкцию языка так, как они записаны. Кавычки при этом отбрасываются. Например, "while" означает, что в конструкции языка присутствует while;

• имена, записанные слитно русскими и латинскими буквами, обозначают различные конструкции языка. Например, оператор_цикла;

• квадратные скобки охватывают элементы языка, которые могут повторяться 0 или 1 раз. Например, "AB"["C"] означает, что в конструкции языка может присутствовать или AB или ABC;

• фигурные скобки охватывают элементы языка, которые могут повторяться 0 или много раз. Например, "AB"{"C"} означает, что в конструкции языка может присутствовать или AB, или ABC, или ABCC и т.д.;

• символ | обозначает или, то есть используется для задания альтернативных значений из списка элементов, разделенных знаком |. Например, "AB"|"C"|"ff" означает, что в конструкции языка может присутствовать или AB или C или ff;

• круглые скобки используются для группировки. Например, "A"("B"|"C")"D" означает, что в конструкции языка может присутствовать или ABD или ACD;

• многоточие используется для обозначения очевидных пропущенных значений в перечислении;

• символ = обозначает присвоить. Например, буква = "A"|"B"|"C".

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

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

Имена должны начинаться с букв латинского алфавита или знака подчеркивания, далее допускается использовать и арабские цифры:

БНФ:

имя = ( буква | "_" ) { буква | цифра | "_" }

буква = |"A"|"B"|...|"Y"|"Z"|"a"|"b"|...|"y"|"z"

цифра = "0"|"1"|...|"9"

При этом прописные и строчные буквы считаются разными.

Длина имени в ANSI стандарте языка Си не ограничена. В Турбо Си имя не может быть длиннее 32 символов. Например: a, a1, _a, a_b.

Выбор имен должен производиться так, чтобы имя как можно точнее соответствовало смыслу объекта или действия, которое оно обозначает. Например: speed_of_body, SpeedOfBody, BodySpeed.

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

Системы счисления. Представление данных в эвм.

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

Например, имеем запись числа

a_n ... a₃ a₂ a₁ a₀

тогда его значение можно вычислить по следующей формуле

a_n*Mⁿ + ... + a_3*M³ + a_2*M² + a_1*M¹ + a_0*M⁰ ,

где a_n...a₀ - цифры из записи числа.

Максимальное значение числа без знака, которое может быть представлено N разрядами позиционной системы счисления определяется как

M^N - 1 .

В общепринятой десятичной системе счисления для записи чисел используются десять цифр 0,1,2,3,4,5,6,7,8,9. Основание системы счисления – 10. Значение числа определяется так:

9721 (10) = 9*10³ + 7*10² + 2*10¹ + 1*10⁰

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

Все данные внутри ЭВМ представлены в двоичной системе, поскольку в этом случае достаточно всего двух цифр, а электронные схемы, как правило, тоже имеют два различных состояния. Десятичная, восьмеричная и шестнадцатеричная системы используются при выводе информации для пользователя, недостающие цифры шестнадцатеричной системы счисления заменяются буквами A,B,C,D,E,F.

Приведем несколько примеров:

1010 (2) = 1*2³ + 0*2² + 1*2¹ + 0*2⁰ = 10 (10)

2701 (8) = 2*8³ + 7*8² + 0*8¹ + 1*8⁰ = 1473 (10)

F4A (16) = 15*16² + 4*16¹ + 10*16⁰ = 3914 (10)

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

1473 : 8 = 184 остаток 1

184 : 8 = 23 остаток 0

23 : 8 = 2 остаток 7 8

2 : 8 = 0 остаток 2

---------------------------

1473 (10) = 2701 (8)

Для перевода чисел из десятичной системы счисления в двоичную используют так называемый "алгоритм замещения", состоящий из следующей последовательности действий:

1. Делим десятичное число А на 2. Частное Q запоминаем для следующего шага, а остаток a записываем как младший бит двоичного числа.

2. Если частное q не равно 0, принимаем его за новое делимое и повторяем процедуру, описанную в шаге 1. Каждый новый остаток (0 или1) записывается в разряды двоичного числа в направлении от младшего бита к старшему.

3. Алгоритм продолжается до тех пор, пока в результате выполнения шагов 1 и 2 не получится частное Q = 0 и остаток a = 1.

Например, требуется перевести десятичное число 247 в двоичное. В соответствии с приведенным алгоритмом получим: 

247₁₀ : 2 = 123₁₀

247₁₀ - 246₁₀ = 1, остаток 1 записываем в МБ двоичного числа.

123₁₀ : 2 = 61₁₀

123₁₀ - 122₁₀ = 1, остаток 1 записываем в следующий после МБ разряд двоичного числа.

61₁₀ : 2 = 30₁₀

61₁₀ - 60₁₀ = 1, остаток 1 записываем в старший разряд двоичного числа.

30₁₀ : 2 = 15₁₀

30₁₀ - 30₁₀ = 0, остаток 0 записываем в старший разряд двоичного числа.

15₁₀ : 2 = 7₁₀

15₁₀ - 14₁₀ = 1, остаток 1 записываем в старший разряд двоичного числа.

7₁₀ : 2 = 3₁₀

7₁₀ - 6₁₀ = 1, остаток 1 записываем в старший разряд двоичного числа.

3₁₀ : 2 = 1₁₀

3₁₀ - 2₁₀ = 1, остаток 1 записываем в старший разряд двоичного числа.

1₁₀ : 2 = 0₁₀, остаток 1 записываем в старший разряд двоичного числа.

Таким образом, искомое двоичное число равно 11110111₂. 

Для перевода чисел из десятичной системы счисления в шестнадцатеричную используют тот же "алгоритм замещения", что и при переводе из десятичной системы счисления в двоичную и восьмеричную, только в качестве делителя используют 16, основание шестнадцатеричной системы счисления:

1. Делим десятичное число А на 16. Частное Q запоминаем для следующего шага, а остаток a записываем как младший бит шестнадцатеричного числа.

2. Если частное q не равно 0, принимаем его за новое делимое и повторяем процедуру, описанную в шаге 1. Каждый новый остаток записывается в разряды шестнадцатеричного числа в направлении от младшего бита к старшему.

3. Алгоритм продолжается до тех пор, пока в результате выполнения шагов 1 и 2 не получится частное Q = 0 и остаток a меньше 16.

Например, требуется перевести десятичное число 32767 в шестнадцатеричное. В соответствии с приведенным алгоритмом получим: 

32767₁₀ : 16 = 2047₁₀

32767₁₀ - 32752₁₀ = 15, остаток 15 в виде F записываем в МБ шестнадцатеричного числа.

2047₁₀ : 16 = 127₁₀

2047₁₀ - 2032₁₀ = 15, остаток 15 в виде F записываем в следующий после МБ разряд шестнадцатеричного числа.

127₁₀ : 16 = 7₁₀

127₁₀ - 112₁₀ = 15, остаток 15 в виде F записываем в старший разряд шестнадцатеричного числа.

7₁₀ : 16 = 0₁₀, остаток 7 записываем в старший разряд шестнадцатеричного числа.

Таким образом, искомое шестнадцатеричное число равно 7FFF₁₆. 

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

0101 1011 1111 1100 (2) = 5BCF (16)

5 11=B 15=F 12=C

0 101 101 111 111 100 (2) = 55774 (8)

5 5 7 7 4

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

0101101111111100(2)=(0·2¹⁵)+(1·2¹⁴)+(0·2¹³)+(1·2¹²)+(1·2¹¹)+(0·2¹⁰)+(1·2⁹)+(1·2⁸)+(1·2⁷)+(1·2⁶)+(1·2⁵)+(1·2⁴)+(1·2³)+(1·2²)+(0·2¹)+(0·2⁰)= =0+16384+0+4096+2048+0+512+256+128+64+32+16+8+4+0+0=23548 (10)

Из этого примера видно, что десятичная система счисления более компактно отображает числа – 5 цифр (т.е. бит) вместо 16 цифр в двоичной системе счисления.

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

Запишем формулу представления дробного числа в позиционной системе счисления: 

A_p = a_n-1·p^n-1+a_n-2·p^n-2 +...+ a₁·p¹+a₀·p⁰ +a_-1·p^-1+a_-2·p^-2 + ... + a_-m·p^-m.

В случае десятичной системы счисления получим: 

24,73₂ = 2·10¹+4·10⁰+7·10^-1+3·10^-2

Перевод дробного числа из двоичной системы счисления в десятичную производится по следующей схеме: 

101101,101₂ = 1·2⁵+0·2⁴+1·2³+1·2²+0·2¹+1·2⁰+1·2^-1+0·2^-2+1·2^-3=45,625

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

 Сначала переводится целая часть десятичной дроби в двоичную систему счисления;

 Затем дробная часть десятичной дроби умножается на основание двоичной системы счисления;

 В полученном произведении выделяется целая часть, которая принимается в качестве значения первого после запятой разряда числа в двоичной системе счисления;

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

Пример: Требуется перевести дробное десятичное число 206,116 в дробное двоичное число.

Перевод целой части дает 206₁₀=11001110₂ по ранее описанным алгоритмам; дробную часть умножаем на основание 2, занося целые части произведения в разряды после запятой искомого дробного двоичного числа: 

.116 • 2 = 0.232

.232 • 2 = 0.464

.464 • 2 = 0.928

.928 • 2 = 1.856

.856 • 2 = 1.712

.712 • 2 = 1.424

.424 • 2 = 0.848

.848 • 2 = 1.696

.696 • 2 = 1.392

.784 • 2 = 0.784

и т.д.

Получим: 206₁₀=11001110,0001110110₂

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

Пусть требуется перевести двоичное число 10101101100110110111100101011001011₂ в восьмеричную систему счисления. Для этого следует разбить это двоичное число на триады, начиная с младшего бита (МБ). Получим: 

010 101 101 100 110 110 111 100 101 011 001 011₂

2 5 5 4 6 6 7 4 5 3 1 3₈

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

000 – 0

001 – 1

010 – 2

011 – 3

100 – 4

101 – 5

110 – 6

111 – 7 Таким образом, 10101101100110110111100101011001011₂=255466745313₈

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

0101 0110 1100 1101 1011 1100 1010 1100 1011₂

5 6 C D B C A C B₁₆

0000 – 0 0001 – 1 0010 – 2 0011 – 3

0100 – 4 0101 – 5 0110 – 6 0111 – 7

1000 – 8 1001 – 9 1010 – A 1011 – B

1100 – C 1101 – D 1110 – E 1111 – F

Заменяя двоичные тетрады на их шестнадцатеричные значения, получим искомое шестнадцатеричное число: 10101101100110110111100101011001011₂=56CDBCACB₁₆

Пусть требуется перевести восьмеричное число 2473₈ в двоичное число. Поскольку 2₈ = 010₂, 4₈ = 100₂, 7₈ = 111₂... Таким образом, 2473₈ = 10100111011₂

Двоичная система	Восьмеричная система	Десятичная система	Шестнадцатеричная система
0	0	0	0
1	1	1	1
10	2	2	2
11	3	3	3
100	4	4	4
101	5	5	5
110	6	6	6
111	7	7	7
1000	10	8	8
1001	11	9	9
1010	12	10	A
1011	13	11	B
1100	14	12	C
1101	15	13	D
1110	16	14	E
1111	17	15	F
10000	20	16	10

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

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

2473₈ = 10100111011₂ = 0101 0011 1011₂ = 53B₁₆

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

Пусть требуется перевести шестнадцатеричное число F1₁₆ в двоичное число. Воспользовавшись таблицей соответствия, получим: 

F1₁₆ = 11110001₂.

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

1F₁₆ = 11111₂, а не 00011111₂

При переводе чисел из шестнадцатеричной в восьмеричную систему счисления:

• шестнадцатеричное число переводят в двоичное;

• разбивают его на триады, начиная с младшего бита;

• заменяют триады соответствующими им эквивалентами в восьмеричной системе.

1F₁₆ = 11111₂ = 011 111₂ = 37₈

F1₁₆ = 11110001₂ = 011 110 001₂ = 361₈

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

Целые беззнаковые числа хранятся в памяти ЭВМ в виде двоичных чисел, занимающих N двоичных разрядов. Диапазон чисел в этом случае от 0 до 2^N-1. Целые числа со знаком, записанные в те же N двоичных разрядов будут иметь диапазон от -2^(N-1) до 2^(N-1)-1 .

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

Символы представлены в ЭВМ в виде соответствующих целочисленных кодов, хранимых в двоичной форме. Обычно под символ отводится один байт памяти, поэтому количество различных символов равно 2⁸-1=255.