Шпаргалка по "Языкам программирования"

3.

Годом рождения языка - 1968-ой (тогда было опубликовано первое официальное сообщение о нем) Его автор - Никлаус Вирт, директор Института информатики Швейцарской высшей политехнической школы, профессор, лауреат премии Тьюринга. В 1970 г. был разработан первый транслятор, в 1974 г. их насчитывалось не более 10, в 1979 - более 80.  За свою тридцатилетнюю историю язык не только не утратил популярности, но и получил мощное развитие в дальнейших реализациях, начиная с объектно-ориентированных версий и заканчивая визуально-ориентированными. Этот язык можно применять с целью описания других языков. Он стал основой для обсуждения языков программирования и своеобразным эталоном для сравнения алгоритмических языков. Среди отличительных особенностей языка отметим следующее:

1.по своей идеологии  язык близок к современной  методике и технологии программирования. В частности он наиболее полно  отражает идеи структурного программирования;

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

3.язык предоставляет  разработчикам многообразные структуры данных.

 

4.

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

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

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

<…> - метапеременная;

{…} - повторение конструкции 0 и более раз;

| - черта альтернативы;

: : = - символ метаприсваивания.

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

Пример: <двоичная цифра>: : = 0|1,

<двоичный код>:: =<двоичная  цифра>|<двоичный код><двоичная  цифра>

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

 

5.

Рассмотрим понятие  «алфавит языка»:

<алфавит> :: = <буква>|<цифра> | <слецсимвол>

<буква> :: = A|В|C|D|E|F|G…

<цифра> :: = 0|1|2|3|4|5…

<спецсимвол> :: = <знак  арифметической операции>|<знак  операции сравнения>|<разделитель>|<слово-символ>

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

<знак операции сравнения> ::=<|>|<=|>=|=|<>

<разделитель> ::= ,|.|^|:|;|(|)|{|}|[|]|:=|'

<слово-символ>::= and|array|begin|case|...

Всякая программа состоит  из лексем и символов-разделителей. К лексемам относят спецсимволы, имена, числа, метки, строки символов,директивы, к символам-разделителям — пробел, разделитель строк и комментарий.

 

6.

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

В отношении структур данных существуют следующие особенности

1)  всякое данное  считается входящим в ту или  иную структуру, самостоятельное  данное рассматривается как простейшая, или тривиальная, структура;

2) элементом, или компонентой,  структуры данных может быть  не только тривиальная, но и  нетривиальная структура, т. e. структуры  данных обладают иерархическим  характером;

3)  в некоторые классы  структур могут объединяться данные разных типов.

Как следует из пп. 1) — 3), понятие «значения» трактуется достаточно широко — это вся совокупность значений, образующих структуру. Понятие  «тип значения» также понимается широко: это и количество компонент  в структуре, и тип каждой из них, и способ их объединения в структуру.

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

 

7.

Рассмотрим две различные  классификации типов данных:

1.Типы данных делятся  на основные и производные  (не делятся) -> основные делятся на ссылочный и скалярный (не делятся), скалярные делятся на стандартные и описанные.

2.Типы данных  делятся  на простые, ссылочные(не делятся)  и составные(не делятся); простые  делятся на вещественные+совместимые(не  делятся) и ординальные; ординальные делятся на перечислимые (не делятся), диапазонные (не делятся), и стандартные, стандартные делятся на логический, символьный и целый+совместимые

ОРДИНАЛЬНЫЕ   ТИПЫ  ДАННЫХ

Общие черты ординальных  типов таковы:

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

2) для любого ординального  типа определены минимальное и максимальное значения;

3) для всякого значения, кроме первого, определено предшествующее, и для всякого значения, кроме  последнего, — последующее;

4) для любых пар  однотипных значений ординальных  типов допустимы операции сравнения;

5) стандартные функции Succ (x), Pred (x), Ord (x) воспринимают аргументы любого ординального типа:Succ (x) — последующее для x значение; Pred (x) — предшествующее для x значение; Ord (x) — ординальный номер значения x.

 

13

Значения регулярного  типа — массивы. Как обычно, под массивом будем понимать упорядоченный набор некоторого фиксированного количества однотипных данных, объединенных одним именем.

Говоря о массивах, вводят в рассмотрение понятия полной переменной и частичной переменной. Полная переменная — имя переменной регулярного типа.

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

В качестве типа индекса  можно использовать любой перечислимый тип.

МНОГОМЕРНЫЕ МАССИВЫ

Определение регулярного  типа допускает рекурсию. Так как  компоненты массива не обязаны быть скалярными, то конструкцию array[<ординальный  тип>] of <тип> можно записать следующим  образом array[<ординальный тип>] of array[<ординальный тип>] of <тип>

 

45.

Объем памяти, используемой для программ и данных, определяется числом микросхем, физически установленных в ЭВМ. Однако, в плане программирования на память следует смотреть не с точки зрения физического объема, а с точки зрения адресации. К примеру, Intel 8088 может адресовать 1МБ памяти, это максимальное количество байтов (адресов), к которым может обратиться CPU

Обращение к байту  памяти происходит с помощью 20-разрядного адреса, т.е. шина адреса Intel8088 является 20-разрядной, диапазон адресов - 00000:FFFFFF

Оперативную память в 1МБ делят на 16 блоков размером по 64 КБ. Нумерация каждого блока совпадает  со старшей цифрой адреса. Такое  разбиение условно, но оно отражает логическую организацию памяти.

Intel8088 - 16-разрядный CPU, т.е. теоретически он может обратиться к 64 КБ памяти. Однако реально это 1 МБ. Расширение адресации стало возможным благодаря сегментированию памяти. CPU делит адресное пространство на произвольное количество блоков, размером не более 64 КБ. Адрес любого такого блока должен быть кратным 16. Такой адрес называется параграфом сегмента. Для обращения к ячейке внутри такого блока используется еще один адрес, называемый смещением. Он указывает на начало некоторой ячейки относительно параграфа. В результате реальный адрес образуется путем объединения 16-разрядного параграфа и 16 разрядного смещения.

Параграф всегда можно  записать в виде 5-значного 16-ричного, последняя цифра которого 0. Смещение записывают в виде 4-значного 16-ричного.

Если заданы FFA20 - параграф и 0015 - смещение, то реальный адрес FFA35 принято записывать в виде FFA2:0015

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8.

Отличительные особенности стандартного типа Integer:

1) значения типа — элементы подмножества множества целых чисел

2) наличие предописанной константы, хранящей максимальное целое — MaxInt, значение которой зависит от реализации языка;

3) точное выполнение операций над целыми, операнды которых также представляются точно, условие корректности операции А х В имеет вид: |А|<=MaxInt,|В|<=MaxInt, |AxB|<= MaxInt;

4) целые операции с целыми операндами:  *,div,mod,+,-

5) целые функции вещественного  аргумента: trunc(x) = [x] (округление отсечением дробной части), round(x) = a) trunc(x+0.5), x>=0; b) trunc(x-0.5) x<0;

6) целые фукции целого аргумента: abs(x)=|x|; sqr(x)=x^2; succ(x)=x+1) ;pred (x)=x-1;

7) две дополнительные операции  над целыми, дающие целый результат: a shl b сдвиг а на b двоичных разрядов  влево; а shr b сдвиг а на b двоичных  разрядов вправо

Совместиемые типы: integer,word,shortint,byte,longint

СТАНДАРТНЫЙ  ТИП  BOOLEAN

Стандартный тип Boolean характеризуется  следующими особенностями:

1)значения типа — предописанные  константы false — ложь и true —  истина;

2)Ord (false) = 0; Ord (trae) - 1 ; Succ (false) = true; Pred (true) = = false; false < true;

З)логические операции:Not — логическоеотрицание; And — логическое умножение; Ог — логическое сложение; Xor — исключающее логическое сложение;

4)odd(x),eof(f)

СТАНДАРТНЫЙ   ТИП  CHAR

Дадим краткую характеристику этому типу.

1.  Значения данного типа — это элементы конечного и упорядоченного множества символов. Набор символов определяется реализацией языка.

2.  Способы записи  констант:

a) 'A','a',T,'?' и т.д.;

6) #65, #13, #27,#9и т.д.

3.  Набор символов  считается пронумерованным начиная  с 0. Упорядоченность значений данного типа понимается так, что, к примеру, независимо от реализации языка всегда справедливы следующие отношения:'A' < 'B' и Succ ('A') - 'B'; 'B' < 'C' и Succ ('B') - 'C'; '1' < '2' и Succ ('1') - '2' и т. д.

4. Для отображений  множества символов на их порядковые номера и обратно имеется несколько функций:Chr (i) — символ с порядковым номером i; Ord (С) — порядковый номер символа С. Данные функции обратны по отношению к друг другу: Chr (Ord (C))~С;Ord(Chr(i))~i,с их помощью можно выразить стандартные функции  Pred  () и Succ ():Pred(C) = Chr(Ord(C)- 1);Succ (С) = Chr (Ord(С) + 1).                  

СТАНДАРТНЫЙ  ТИП  REAL

Тип Real характеризуется  следующими особенностями.

1.  Значения типа  — подмножество множества вещественных  чисел, определяемоереализациейязыка.

2. Значения представляются  с точностью, также определяемой  реализацией языка.