Формальна мова, відповідна не терміналу

семантика дужок (), [], {} у розширених БНФ.
Доповнимо мову БНФ кількома зручними конструкціями. Для цього знадобиться ще одне поняття — еквівалентність БНФ.

Дві системи БНФ називаються еквівалентними, якщо задають одну й ту саму формальну мову.

Для коротшого й наочнішого запису еквівалентних БНФ в метавирази додають метасимволи (,), [, ], {, }. Метавираз із такими символами називається розширеним, а БНФ — розширеною, або РБНФ. Розглянемо утворення РБНФ.

Нехай букви X, Y, Z, …, T позначають довільні метавирази (можливо, порожні), N — нетермінал.

1. Декілька альтернатив вигляду X Z Y |... | X T Y у метавиразі, які мають спільні початок X та закінчення Y, можна замінити таким метавиразом.

X (Z |... | T) Y

Метасимволи (та) тут просто відокремлюють частину метавиразу з альтернативами Z, …, T від інших частин.

Приклад. Правило

<вираз>::= <ім’я> '+' <ім’я> | <ім’я> '-' <ім’я>

можна замінити еквівалентним.

<вираз>::= <ім’я> ('+' | '-') <ім’я>

2. Замість двох альтернатив вигляду X Z Y | X Y можна записати такий еквівалентний вираз.

X [ Z ] Y

Приклад. Замість БНФ

<вираз>::= <ім’я> | <ім’я> ('+'| '-') <ім’я>

запишемо таку.

<вираз>::= <ім’я> [ ('+'| '-') <ім’я> ]

Аналогічно, замість БНФ

<інструкція_розгалуження>::=

if '(' <умова> ')' <інструкція> |

if '(' <умова> ')' <інструкція> else <інструкція>

запишемо таку.

<інструкція_розгалуження>::=

if '(' <умова> ')' <інструкція> [ else <інструкція> ]

3. Семантику метасимволів {, } означимо за допомогою прикладу.

Приклад. Ім’я, або ідентифікатор, у мовах програмування — це послідовність букв і цифр, що починається з букви. Нехай буквами є тільки A, B, C, цифрами — 0 і 1. Для імен вище було означено таку систему БНФ.

<ім’я>::= <Б><ПБЦ>

<ПБЦ>::= <> | (<Б> | <Ц>) <ПБЦ>

<Б>::= 'A' | 'B' | 'C'

<Ц>::= '0' | '1'

Узагальнимо букви й цифри поняттям “буква-цифра” з нетерміналом <БЦ>, додавши таке правило.

<БЦ>::= <Б> | <Ц>

Тоді <ПБЦ> можна задати двома такими правилами.

<ПБЦ>::= <> | <БЦ> <ПБЦ>

За допомогою цих правил із нетермінала <ПБЦ> можна вивести всі можливі послідовності <БЦ>:

<>, <БЦ>, <БЦ><БЦ>,...,

і тільки їх. Позначимо множину послідовностей, складених з <БЦ>, метавиразом {<БЦ>} із новими метасимволами {, }. Будемо вважати, що всі послідовності <БЦ> вивідні з цього метавиразу. Тоді правилу

<ПБЦ>::= {<БЦ>}

еквівалентні такі.

<ПБЦ>::= <> | <БЦ> <ПБЦ>

Якщо X — довільний метавираз, то метавираз { X } позначає всі скінченні послідовності <>, X, XX, XXX, …. Дужки {} називаються ітераційними й підкреслюють ітеративну природу різного роду послідовностей.

 

Масив

У багатьох задачах у пам’яті програми треба зберігати великі набори однотипних даних. Для цього використовують масиви.

Масив — це змінна, утворена послідовністю змінних, які називаються елементами (компонентами), є однотипними й ідентифікуються номерами (індексами). Елементи масиву рівнодоступні — можливість їх обробки не залежить від їх місця в масиві.

Означення масиву має вигляд T a[n], де T — тип елементів, a — ім’я масиву, n — ціла константа, можливо, іменована. Константа задає розмір масиву. Елементи можуть мати довільний скалярний або структурний тип (масив та інші, про які йдеться в наступних главах). Індексами елементів є цілі числа від 0 до n -1.

Тип та кількість елементів масиву (його розмір) фіксується в означенні або під час створення й далі не змінюється.

Елемент масиву

Елемент масиву ідентифікується іменем масиву та індексом. Наприклад, елемент масиву зі ста елементів, int a[100], позначається виразом вигляду a[ IE ], де вираз IE повинен мати ціле значення від 0 до 99.

Рівнодоступність елементів масиву

Індексна множина масиву

Розмір масиву

Що являє собою значення масиву з точки зору математики

Ініціалізація масиву.

Значення, що ініціалізують послідовні елементи масиву, задаються списком констант у дужках {}, наприклад, int a[4]={2,10,3,15};. Якщо констант менше ніж елементів у масиві, вони присвоюються першим елементам масиву, а решта елементів отримують нульові значення відповідного типу. Наприклад, оголошення int cnt[4]={}; ініціалізує всі елементи значенням 0. Якщо ж констант більше ніж елементів масиву, то це є помилкою.

В ініціалізації можна не вказувати розмір масиву — він стає рівним кількості констант. Наприклад, оголошення int a[]={9,8,7}; задає масив з трьох елементів.

Елементи масиву, оголошеного без ініціалізації за межами функцій, в якості початкових значень отримують нулі відповідного типу, а масиву, оголошеного в тілі функції — випадкове «сміття».

Адреса змінної та вираз, яким позначається адреса змінної

Пам’ять комп’ютера являє собою послідовність байтів з номерами 0, 1, 2, …, які називаються адресами. Кожна змінна займає залежно від її типу певну кількість послідовних байтів пам’яті. Адреса змінної — це адреса її першого байта.

У мові С++ вказівник будь-якого типу займає чотири байти. Втім, вже невдовзі можна буде говорити, що не чотири, а вісім.

«Вказівник» — це переклад англійського P ointer, тому варто дотримуватися неписаного правила: в кінці або на початку імен вказівників присутня літера p, а імена типів вказівників починаються з P.

Ім’я вказівника та вираз вигляду &x, де x — ім’я змінної, є найпростішими адресними виразами — виразами, значеннями яких є адреси. Складніші адресні вирази розглядаються нижче. Відповідно, якщо AE — адресний вираз, то вираз вигляду *AE позначає дані, адреса яких є значенням виразу AE.

Вказівник

Вказівник — це змінна, значеннями якої є адреси.

Типізований вказівник

типізовані вказівники — їхніми значеннями можуть бути адреси даних тільки певного типу. Тип адрес даних типу T позначається виразом T *. При цьому тип T називається базовим, а вказівник типу T * — вказівником на дані типу T (вказівником типу T).

Як встановити вказівник на змінну

Адресу деякої змінної задає вираз із операцієювзяття адреси &, наприклад, &x.Якщо адресу змінної присвоєно вказівнику, кажуть, що вказівник встановлено на змінну. Якщо вказівник, скажімо, p, встановлено на деяку змінну, то значенням виразу p є адреса змінної. Присвоювання значення p іншому вказівнику означає його встановлення на ту саму змінну.

Як позначається змінна, на яку встановлено вказівник

&x

Оголошення імені типу вказівників

Тип вказівників можна іменувати за допомогою інструкції typedef. Імена типів вказівників замість виразів із * спрощують вигляд заголовків функцій, особливо, оголошення параметрів-посилань, що є вказівниками. Порівняйте, наприклад, два таких прототипи функцій.

Арифметичні дії з адресами

Мова С++ дозволяє додати до адреси або відняти від неї ціле число. Можна також до цілого числа додати адресу. Отже, якщо A та I позначають, відповідно, адресний та цілий вирази, то A + I, A – I, I + A є адресними виразами.

Якщо доданок-адреса має тип T*, то ціле значення розглядається як кількість одиниць даних типу T. Наприклад, якщо x — змінна типу int, то адресні вирази &x+1 та 1+&x задають адресу цілої змінної, розташованої відразу після змінної x. Ця адреса більше адреси змінної x на sizeof(int), тобто на 4. Віднімання цілого від адреси аналогічне. Так, значенням виразу &x-1 є адреса змінної, яка в пам’яті займає місце безпосередньо перед x.

Звідси, якщо p — вказівник типу T*, то вирази p+1, p+2, … задають адреси даних типу T, розташованих після *p «на відстані» 1, 2, … від *p. Так само, вирази p-1, p-2, … позначають адреси даних типу T перед *p

До вказівників застосовні складені присвоювання +=, -= (з цілим виразом праворуч), а також ++ і --. Вони збільшують або зменшують значення вказівника на відповідну кількість sizeof(T), тобто переставляють його «з кроком sizeof(T)». Наприклад, якщо p має тип int*, то вираз p+=2 збільшує значення p (адресу!) на 8, переставляючи його вперед на дві одиниці даних типу int.

До однотипних адрес застосовна операція віднімання. Якщо AE1, AE2 — адресні вирази типу T*, то значенням арифметичного виразу AE2 - AE1 є ціла кількість одиниць даних типу T, які «уміщаються між адресами» AE1 і AE2 (можливо, це число від’ємне). Зокрема, виразами AE2 та AE1 можуть бути імена вказівників.

Нарешті, адреси однотипних даних можна порівнювати за допомогою операторів ==,!=, <, <=, >, >=. Наприклад, якщо p — вказівник на деякий тип, то значенням виразів p<p+1, p!=p-1 є істина.

Арифметичні операції з вказівниками вимагають підвищеної уваги. Помилки в цих операціях призводять, як правило, до спроб змінити зовсім не ті дані, які передбачає програміст, тому є дуже небезпечними.