colorless • green • ideas• sleep • furiously• .

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

Словарные символы из β\γ: NP, VP, AP, …, Adv называются нетерминальными.

Пример 2

β\γ = {Z, A, T, Р},

γ = {(,), + , - , ×, /, a, b, c, d, e},

R={Z→A,

A→T, T →P, P →b,

A→+T, T →T×P, P→c, (5.21)

A→ -T, T →T/P, P →d,

A→A+T, P→(A), P →e}.

A→A – T, P →a,

Здесь формальный язык представляет собой язык арифметических выражений в обычной записи. Приведем вывод выражений: 1.) а; 2.) a+b; 3.) a+b×c.

1.) Z→A→T→P→a. (5.22)

2.) Z→A→ A+T→A+P→A+b →T+b→P+b→a+b.

3.) Z→A→ A+T→A+P→A+(A)→ A +(T)→A+ (T×P) → A+ (T×c)→ →A+ (P×c) →A+ (b×c) →T+ (b×c)→ P+ (b×c)→ a+b×c.

5.7 Описание автоматов и формальных языков

Формальные языки служат прежде всего для формального задания языка как запаса слов и его синтаксической структуры.

Если ограничится грамматиками Хомского типа 3, то можно вместо формальных языков рассматривать и автоматы. Представим некоторые возможности описания формальных языков.

5.7.1. Словесное описание

Язык состоит из всех двоичных слов, в которых непосредственно друг за другом следуют три L (LLL).

Пример 0LLL, LLL0, 0LLL00, и т.д.

5.7.2. Описание при помощи грамматики Хомского

грамматика Хомского типа 3 со словарным запасом:

Г=( β, γ, R, z),

β ={ D, E, F, Z, 0, L}, γ ={0,L},

R ={D→0, E→L,

D→D0, E→DL,

D→E0, E→EL,

D→D0, E→DL,

D→F0, Z→FL, (с.м.)

Z→Z0, Z→ZL}

5.7.3. Описание при помощи таблицы переходов автоматов

Автомат для примера, приведенный в §5.7.2. будет иметь состояния: s0, sD, sE, sF, sz соответствующие синтаксическим переменным: ε, D, E, F, Z.

ε – пустое слово, не содержащее ни одного символа, которое есть левая или правая единица. Необходимо для выполнения равенства εy=y и yε=y.

s0 - начальное состояние автомата.

sz - заключительное состояние автомата.

Таблица переходов

5.7.4. Описание при помощи диаграммы переходов автомата

Дано по таблице §5.7.3.

5.7.5. Описание при помощи дерева разбора

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

Деревом разбора для вывода, реализующего соотношение

X=>b, XÎβ, bÎβ*\{ε},

Называется всякое лежащее в плоскости дерево без самопересечений с корнем Х и символами из β в качестве вершин, устроенное следующим образом: для всякой продукции

(с.м.) Y→B1B2…Bk, k ≥1,

фигурирующей в выводе, имеется ровно k исходящих из вершины Y дуг, упорядоченных в направлении против часовой стрелки и направленных в вершины B1, B2, …, Bk. В данном случае принимается Y→b (с.м.) и b= B1, B2, …, Bk.

Тогда вершины, из которых не исходит ни одной дуги, если их прочитать в направлении против часовой стрелки, дадут слово «b».

Дерево разбора к примеру (5.20)

Дерево разбора для a×(b+c) в грамматике (5.21)

5.7.6. Описание при помощи программы

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

Пример лог: {цел. i:=0,n; лог z;

пока “слово не исчерпано” цикл

{чит (z);

если z=0^i<n то i:=0 end прогр.

иначе i:=i+1 end если}}

Результатом вывода является i(i=0 v i ≠0).

5.7.7. Описание при помощи блок-схемы программы

Блок-схема программы имеет схожий с конечным автоматом принцип работы.

6. Программное обеспечение САПР

6.1 Элементы программного обеспечения.

Программа состоит из элементов называемых лексемами. Лексемы – это набор символов базового словаря, распознаваемых компилятором. Набор символов включает:

- Прописные и строчные буквы английского алфавита: a, b, …, z, A, B, …, Z; и возможно, кириллицы.

- Цифры: 0, 1, 2, … , 9.

- Операторы: +, *, =, …

- Знаки пунктуации: ;, ,, ‘, …

Существует шесть типов лексем: комментарии, ключевые слова, идентификаторы, литералы, операторы и знаки пунктуации.

В С++ комментарии выглядят так:

многострочный -

/* Предложение состоит из нескольких строк */;

однострочный –

// Предложение в одну строку.

Ключевое слово – зарезервированное слово с четким конкретным значением. Ключевые слова используются: при объявлении типов: int, char, float ( в С++), …; в синтаксисе составных инструкций: do, for, if (в С++), …;

при управлении доступом: public, protected, private (в С++); и т.д. Таблица ключевых слов в С++ представлена в книге Айра Пола (стр. 38)

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

( _ ).

Пример: х – переменная, buff _ size – подчеркивание выступает в роли разделителя слов.

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

Пример из С++ : 5L - l или L означает long (длинная);

5.OL – длинная константа;

*\ а’ – звуковой сигнал (alert);

*\ r’ – возврат каретки; и т.д.

Операторы – определенные символ или последовательность символов, предназначенных для создания выражения.

Пример из С++ : +, -, *, /, %, - арифметические операторы;

+ = - оператор присваивания и сложения; и т.д.

Знаки пунктуации – символы, предназначенные для структурирования элементов программы и разделения элементов языка.

Пример из С++ : {a=b; c=d}

6.2 Целочисленные типы

Слово “целое “ - integer в математике обозначает неограниченную, упорядоченную последовательность чисел:

…, -3, -2, -1, 0, 1, 2, 3, …

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

Тип данных с набором, по сути положительных значений называется unsigned integer (целое без знака). В “C” переменная этого типа может быть объявлена как:

unsigned int V;

Перевод слова из 8 бит в десятеричную систему, например для последовательности 0100011, осуществляется следующем образом:

1*2⁷+1*2⁵+1*2¹+1*2⁰= 128+32+2+1=163

Сегодня чаще всего размер слова составляет 32 бита, и целое без знака (unsigned int) находится в диапазоне 0 – 2³² - 1 =4*10⁹. Набор математических чисел целых без знака практически не ограничен, в то время как числа типа int имеют конечный диапазон значений.

Для того чтобы получить представление числа “-m” выполняют три операции:

1. Определяют двоичное представление положительного числа “m” – В= b₁b₂…b_k.

2. Заменяют в каждом b_i ноль на единицу, а единицу на ноль.

3. Прибавляют единицу.

Пример: Процесс образования -1, -2, и –127 для 8-разрядных слов.

1 = 0000 0001 à 1111 1110 à 1111 1111 = -1

2 = 0000 0010 à 1111 1101 à 1111 1110 = -2

127= 0111 1111 à 1000 0000 à 1000 0001 =-127

6.2.1. Операции с целочисленными данными

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

a + b/c – 25 * (d – c )

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

Результат операции над целыми числами со знаком не должен выходить за диапазон допустимых значений, иначе произойдет переполнение. Предположим, что a=90, b=60 и c=80. Выражение a+b+c=110. Однако оптимизатор может выбрать другой порядок расчета: a+c-b. В результате, если предельное значение переменной составляет 127, образуется переполнение из-за a+c=170 и процесс выполнения программы прекращается.

Результатом деления двух чисел a/b является: частное q и остаток r.

а= q*b + r.

Результатом деления целых чисел может быть либо q либо r. Выражение 54/10 дает значение 5. Округление, когда частное отрицательное, производится либо до меньшего (-5/3=-3), либо до ближайшего к нулю(-5/2=-2). Реализация округления зависит от языка программирования.

6.3. Типы перечисления

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

Объявления перечислимых констант в С++:

1. typedef enum {Off, Low, Medium, High}Heat;

2. enum Heat {Off, Low, Medium, High};

3. enum Heat {Off, Low, Medium, High} Heat;

4. Heat dial;

5. enum Heat {Off=1, Low, Medium=7, High}; и т.д.

В первых трех примерах константы по умолчанию принимают значения:0, 1, 2, 3, т.е. Off(выключено)=0, Low(слабо)=1, Medium (средне)=2 и High(сильно)=3. В четвертом примере dial обладает типом Heat. В пятом примере значение незаданного элемента больше на единицу предыдущего элемента, т.е. Low=2, а High=8.

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

6.4 Простые типы

Простыми собственными типами в С++ являются bool, double, int, и char ( собственно булевский, двойной, целый и символьный тип). Эти типы имеют набор значений и представление, привязанные к низкоуровневой архитектуре компьютера, на котором работает компилятор.

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

В языке С тип char – это ограниченный целочисленный тип, который как и int допускает следующие операции:

char C;

int I;

C=’A’+10 - Преобразует char в int и обратно.

i=’A’ -Преобразует char в int.

с=i -Преобразует int в char.

В языке С++ тип char отличается от целочисленного, но поскольку существует приведение типов, то перечисленные операторы остаются допустимыми.

В языке С и старых версиях С++ нет собственного булевского типа. В них используется нуль для обозначения false и ненулевые значения для true.В современных версиях С++ тип bool является встроенным целочисленным типом ( не типом перечисления ) с неявными взаимными преобразованиями между ненулевыми значениями и литералом true, а также нулевым значением и false.

6.5 Выражения.

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

Выражения могут находиться: в операторах присваивания, в булевых выражениях условных операторов, в границах операторов цикла, параметрах процедур и т.д.

Пример: int i;

char ch;

double b=1.9;

i=b/2.0 - i=0

ch=’A’ +1.0 -ch=’B’

6.6 Операторы присваивания.

Оператор присваивания помещает значение выражения по адресу памяти переменной. Объявление оператора присваивания:

Переменная := выражение Ada

Переменная = выражение С

Левая часть оператора присваивания также может быть выражением, если это выражение можно вычислить как адрес:

a ( i * ( j+1 )):=a ( i * j ) Ada

С++ предлагает короткие операторы присваивания:

a+ = b равнозначно a= a+b

a =a+b a= a*( a+b )

++i; i=i+1

--i; i=i-1

j= ++i; i= i+1; j=i;

j= i++ j=i; i=i+1 и т.д.

6.7. Записи.

Языки программирования поддерживают составные типы данных, к которым относятся записи и массивы. Значение типа запись состоит из набора значений других типов, называемых компонентами в Ada, членами в языке С и полями в Paskal. При объявлении типа каждое поле получает имя и тип. Следующее объявление в языке С описывает структуру с четырьмя компонентами:

Model [20] – символьный тип, строка из 20 символов;

color - тип перечисления Colors, принимает значения заданные пользователем согласно списка enum;

speed и fuel – параметры целого типа;

typedef enum {Black, Blue, Green, Red, White} Colors;

typedef struct {

char model [20];

Colors color;

int speed ;

int fuel;

} Car_Data;

Объявление объектов struct:

Car_Data C1, C2;

C2.fuel =3; C++

C1.speed =C2.fuel;

Будучи выбранным, поле записи становится обычной переменной или значением типа поля. К нему применимы все операции, соответствующие этому типу.

Значение записи представляется числом слов памяти, вмещающим все указанные поля. Покажем размещение записи Car_Data на рисунке.

0 20 24 28

Доступ к отдельному полю осуществляется через величину смещения каждого поля от начала записи. Величина смещения постоянна и известна при компиляции. Реализация доступа к полям выглядит так:

load R1,&C1 - Загрузить адрес С1 в реестр R1.

load R2,20(R1) – Загрузить в R2 адрес, равный адресу в R1+20.

load R3,24(R1) - Загрузить адрес в R3, равный адресу в R1+24.

6.8. Массивы.

Массив– это запись, все поля которой имеют один и тот же тип. Поля называются элементами или компонентами и задаются не именами, как в записи, а позицией внутри массива. Доступ к элементам массива производится с помощью индексов. Язык С++ разрешает использовать любое целое выражение или численное значение для задания числа элементов массива.

cont int Max=5;

float A[Max + 3];

Значение индекса i массива A[i] лежит в диапазоне от 0 до общего числа компонентов без единицы. В приведенном примере от 0 до Мах+2.

Компоненты массива могут быть любого типа:

typedef struct {…} Car_Data;

Car_Data [100];

Индекс Car_Data изменяется от 0 до 99.

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

typedef int A[10] - Тип массива;

typedef struct { - Тип запись;

А а; - Массив внутри записи;

сhar b ;

} Rec;

Rec r[10] ; - Массив записей с массивами типа int внутри;

int i, j, k;

k= r [i+1] a [j-1] - Последовательность выполнения: индексация, выбор поля, индексация, конечный результат.

Смысл элементов:

r – Массив записей, содержащих массивы целых чисел;

r[i] - Запись содержащая массив целых чисел;

r[i].a - массив целых чисел;

r[i].a[j] - целое число.

Каждая новая пара скобок в С++ увеличивает размерность массива. Объявление многомерных массивов:

int b[3][5] - двумерный массив.

int с[7][9][2] - трехмерный массив.

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

int а[4]={9,6,7}; -- a[0]=9, a[1]=6, a[2]=7, a[3]=0.

int b[2][3]={ {1, 3, 5}, {2, 4} }; -- b[1][2]=0.

6.8.1. Реализация массивов

Элементы массива размещаются в памяти последовательно. Адрес элемента A[i] массива А определяется согласно выражению:

addr (A) + size(элемент) * (i- A’First) (6.1)

Пример: Пусть задано размещение элементов массива A[i] в памяти в последовательности

20 24 28 32 36 40 44 48

size=4 - размер элемента (смещение).

addr(A) =20 - адрес A[1].

A’First =20 + 4 (5-1) = 36

Сгенерированный машинный код составленный по формуле (6.1) выглядит так:

load R1, I - Загрузить I в реестр R1.

sub R1, A’First - Вычесть из значения в R1 нижнюю границу и результат поместить в R1.

multi R1, size - Умножить значение в R1 на смещение и результат занести в R1.

аdd R1, &A - Сложить значение в R1 и адрес А[1] и полученный адрес поместить в R1

load R2, (R1) - Загрузить содержимое R1 в R2.

Если A’First=0 (нуль), то не нужно вычитать в (6.1)индекс первого элемента. Вероятно поэтому, разработчики языка С приняли начинать индексацию массива с нуля.

При работе с многомерными массивами нужно представлять размещение элементов в памяти. За исключением языка Fortran, все языки хранят двумерные массивы как последовательность строк. Размещение массива B[3][5]:

0 4 8 12 16 20 24 28 32 36 40 44 48 52 56 60

строка1 строка2 строка3

6.8.2. Контроль соответствия типов в массивах

Организация контроля соответствия типов в массивах лежит полностью на программисте. Чаще всего встречаются три вида ошибок:

1. Индекс получает значение, которое выходит за установленный диапазон.

Пример: int a[10];

for (i=0; i<=10; i++)

a[i] = 2*i;

Последним элементом массива является а[9], но а[10] тоже будет вычислено.

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

2. Передача информации через массивы с разными размерностями.

Пример: int a[5], b[2][4], c[3][5];

………………………… определены элементы матрицы В

for (i=0; i<2; i++)

for (j=0; j<4; j++)

c[i][j] = b[i][j];

for (i=0; i<5; i++)

a[i] = c[2][i];

Но значение с[2][4] не было определено. Следовательно а[4] будет присвоено значение, взятое из какой-то ячейки памяти, возможно, даже расположенное в области ОС.

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

Рассмотрим варианты хранения числа 0*04040201:

с младшего конца

40 41 42 43

со старшего конца

40 41 42 43

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