Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
РОЗРОБКА СИСТЕМНИХ ПРОГРАМНИХ МОДУЛІВ ТА КОМПОНЕНТ СИСТЕМ ПРОГРАМУВАННЯ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп'ютерна інженерія
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2012
Тип роботи:
Методичні вказівки до курсової роботи
Предмет:
Системне програмування
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
РОЗРОБКА СИСТЕМНИХ ПРОГРАМНИХ МОДУЛІВ ТА КОМПОНЕНТ СИСТЕМ ПРОГРАМУВАННЯ
Методичні вказівки до курсової роботи з курсу “ Системне програмування ”
для студентів базового напряму 6.050102 - “Комп’ютерна інженерія”
Затверджено на засіданні кафедри ”Електронні обчислювальні машини” Протокол № 1 від 28.08.2012 року
Львів – 2012
Розробка системних програмних модулів та компонент систем програмування: Методичні вказівки до курсової роботи з курсу “ Системне програмування ” для студентів базового напряму 6.050102 - “Комп’ютерна інженерія” / Укладачі: Мархивка В.С., Олексів М.В., Мороз І.В. – Львів: Національний університет “Львівська політехніка”, 2012, 40 с.
Укладачі Мархивка В.С., ст. викл.
Олексів М. В., асистент
Мороз І.В., ст. викл.
Рецензенти
Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри
РОЗРОБКА СИСТЕМНИХ ПРОГРАМНИХ МОДУЛІВ ТА КОМПОНЕНТ СИСТЕМ ПРОГРАМУВАННЯ
МЕТА КУРСОВОЇ РОБОТИ
Метою виконання курсової роботи є закріплення теоретичних знань та практичних навичок системного програмування, набутих при вивченні дисципліни “Системне програмування”. В ході виконання курсової роботи студенти повинні навчитися самостійно працювати з літературою, розробляти типові елементи системних програм, програмуючи роботу з таблицями, словниками, інформаційними базами, виконуючи лексичний та синтаксичний аналіз, а також семантичну обробку, здійснювати їх програмну реалізацію та відлагодження на сучасних обчислювальних системах.
СТРУКТУРА ТА ОБСЯГ КУРСОВОЇ РОБОТИ
Обсяг курсової роботи повинен становити не менше 20 сторінок друкованого тексту (без врахування додатків).
Рекомендується такий склад пояснювальної записки до курсової роботи:
Титульна сторінка
Анотація
Зміст
Завдання на курсову роботу
Вступ
Огляд методів та способів проектування трансляторів
Формальний опис вхідної мови програмування
Деталізований опис вхідної мови в термінах розширеної нотації Бекуса-Наура
Термінальні символи та ключові слова
Розробка транслятора вхідної мови програмування
Вибір технології програмування
Проектування таблиць транслятора
Розробка лексичного аналізатора
Розробка синтаксичного та семантичного аналізатора
Розробка генератора коду
Опис програми (в тому числі граф-схем)
Опис інтерфейсу та інструкція користувачеві
Відлагодження та тестування програми
Виявлення лексичних помилок
Виявлення синтаксичних помилок
Виявлення семантичних помилок
Загальна перевірка коректності роботи транслятора
Висновки
Список літератури
Додатки
А. Лістинг програми
Б. Граф-схеми алгоритмів
В. Результати тестування
Обов’язковими додатками має бути документований текст програми та графічна частина, оформлені у відповідності до стандартів та ЄСКД.
Завдання на курсову роботу (1 стор.). У завданні вказується тема роботи та перелік конкретних вхідних даних. Завдання на курсову роботу видається студентові керівником курсової роботи індивідуально.
Анотація (1 стор.) В анотації викладаються короткі відомості про курсову роботу.
Зміст (1 стор.). У змісті вказуються номери та назви основних розділів курсової роботи та номери сторінок, де вони починаються. Вступ, висновки по роботі, список літератури та додаток не нумеруються.
Вступ (1 стор.). У вступі здійснюють опис проблеми у загальному вигляді, визначають її актуальність, формулюють мету курсової роботи.
Теоретична частина. Огляд методів та способів проектування трансляторів Цей розділ виконується із використанням літературних джерел і повинен містити опис методів та способів вирішення задачі. Необхідно здійснити порівняння описаних методів та способів.
Формальний опис вхідної мови програмування. В цьому розділі описується тип граматики вхідної мови програмування згідно завдання. При цьому визначається алфавіт мови та набір зарезервованих слів. Рекомендується опис вхідної мови подавати в термінах розширеної нотації Бекуса-Наура або за допомогою синтаксичних діаграм.
Розробка транслятора вхідної мови програмування. В цьому розділі:
- здійснюється вибір технології програмування;
- розробляється структура постійних таблиць для зберігання алфавіту мови, зарезервованих слів, знаків операцій, роздільників тощо та здійснюється вибір для постійних таблиць алгоритму пошуку елементів у впорядкованих таблицях;
- розробляється структура перемінних таблиць для зберігання ідентифікаторів і констант та алгоритми пошуку/вставки лексем і їх атрибутів;
- проектується лексичний аналізатор на основі детермінованих кінцевих автоматів;
- проектується синтаксичний аналізатор на основі дерева граматичного розбору;
- проектується генератор асемблерного коду
Опис програми. Програма повинна бути написана та реалізована на мові програмування C/C++. Текст програми повинен бути документований і написаний згідно вимог структурного програмування. Кожний програмний модуль на початку повинний містити інформацію про тему курсової роботи, прізвище автора та дату створення. Крім того, кожна підпрограма мусить буди також документованою
Опис програми проводиться в такій послідовності: спершу описується граф-схема алгоритму, а пізніше програмна реалізація.
Опис інтерфейсу та інструкція користувачеві В інструкції користувачеві приводять детальну послідовність дій по запуску програми на виконання та описують всі можливі режими керування роботою програми. Для ілюстрації режимів роботи програми бажано навести зображення екранних форм, вікон, меню, блоків діалогу, форм документів і т.п.
Відлагодження та тестування програми. В цьому розділі описуються вибрані технології відлагодження та тестування програми на комп’ютері.
Технологія відлагодження програми - це послідовність дій та засоби виявлення, аналізу та виправлення помилок програми. Описуються використані засоби автоматизованого відлагодження та оптимізації програми (автономні та вбудовані відлагоджувальники, профайлери). Проводиться аналіз помилок, допущених в ході програмування задачі, спосіб їх виявлення та усунення.
Для підтвердження працездатності програмного продукту розробляється система тестів та приводяться результати тестування з їх аналізом.
Висновки (1 стор.) У висновках перераховуються основні результати курсової роботи, вказуються її позитивні сторони та недоліки, даються рекомендації по практичному застосуванню розроблених алгоритмів та програм.
ВИМОГИ ДО ОФОРМЛЕННЯ
Курсова робота є індивідуальною роботою кожного студента і оформляється окремо кожним студентом згідно із виданим завданням.
Курсова робота оформляється на аркушах формату A4, які заповнюються з однієї сторони. Текст повинен бути надрукований на принтері. Використання різних чорнил не дозволяється. Заголовки розділів можуть бути виділені великими літерами або підкресленням. Текст повинен бути набраний без помилок українською мовою.
Текст на сторінці повинен бути розміщений рівномірно з дотриманням відступів: зліва, згори та знизу - 20 мм, зправа - 10 мм. При комп’ютерному наборі необхідно вибрати шрифт Times New Roman Cyr, розмір шрифта - 14, міжрядковий інтервал - 1.5 . Сторінки курсової роботи повинні бути пронумеровані. Титульна сторінка вважається першою і не нумерується. Номери сторінок вказуються у правому верхньому куті.
Кожен розділ повинен мати свій номер, який записується перед його назвою. Після номера розділу ставиться крапка, наприклад: 1.Формулювання задачі. Вступ, висновки, список літератури та додаток не нумеруються. Кожен розділ необхідно розпочинати з нової сторінки. Розділ може складатися з підрозділів. Номер підрозділу записується через крапку після номера розділу, наприклад: 4.2. Призначення програми.
Формули, на які здійснюється посилання, а також всі таблиці та рисунки повинні мати номер. Нумерація може бути наскрізною або прив'язаною до номера розділу.
Номер формули записується після неї у круглих дужках. Номер та назва таблиці вказуються над нею після слова "Таблиця". Номер та назва рисунка вказуються під ним після скорочення "Рис.".
Рисунки та рамки таблиць повинні бути виконані олівцем або чорнилом вибраного кольору. Дозволяється комп'ютерне виконання графічної частини курсової роботи. Графічні схеми алгоритмів виконуються згідно вимог міжнародного стандарту ISO 5807-85 "Обробка інформації. Символи і умовні позначення блок-схем даних, програм та систем, схем програмних мереж і системних ресурсів".
Роздруки текстів програм приводяться у додатку. Кожен окремий документ додатку повинен мати свій номер та назву, які записуються після слова "Додаток", наприклад: Додаток 1. Текст програми на мові С++.
Список літератури виконується згідно вимог стандартів. Література може бути розміщена за алфавітом або в порядку посилання на неї. У списку можна наводити тільки ту літературу, яка була використана при виконанні курсової роботи і на яку є посилання у тесті пояснювальної записки. Посилання здіснюється вказанням номера джерела у квадратних дужках. Список літератури повинен містити не менше 5 джерел.
Пояснювальна записка повинна бути сформована згідно змісту і надійно зшита з лівої довшої сторони листів формату A4. Для зручності зберігання палітурка курсової роботи повинна бути жорсткою (виконана із листа ватману чи картону).
ЗАХИСТ РОБОТИ
Готова курсова робота представляється керівнику для перевірки. При необхідності вона може бути повернута студенту для доопрацювання. До захисту приймається робота, оформлена згідно приведених вище вимог, разом з дискетою. На дискеті розміщуються текстові файли програм, тестових даних та текст пояснювальної записки до курсової роботи. Дискета повинна бути підписана з вказанням номера групи та прізвища студента. Назви файлів повинні бути виконані латинськими літерами та цифрами.
В процесі захисту роботи студент демонструє роботу транслятора на комп'ютері і дає пояснення та відповіді на поставлені питання членами комісії. Захист роботи здійснюється студентом тільки один раз. При незадовільній оцінці студенту видається нове завдання на курсову роботу за дозволом завідувача кафедри та декана.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Виконання курсової роботи полягає в розробці транслятора з вхідної мови програмування, яка задана варіантом, на мову асемблер. Здійснюючи трансляцію, транслятор типово послідовно виконує такі фази роботи: лексичний аналіз, синтаксичний аналіз, генерація коду. Розглянемо детальніше кожну з фаз.
1. ЛЕКСИЧНИЙ АНАЛІЗ
Лексичний аналіз – це перша фаза роботи компілятора чи транслятора довільної мови програмування. Він полягає у перетворенні послідовності символів тексту вхідної програми в послідовність токенів (токен - об'єкт, що утворюється із лексеми в процесі лексичного аналізу). В процесі роботи він вирішує задачі: побудова таблиці ідентифікаторів; побудова таблиці лексем шляхом ідентифікації токенів в тексті вхідної програми; видалення пробілів і коментарів оскiльки вони не мають нiякого впливу на виконання програми, отже ж й на синтаксичний розбір та генерацію коду; передача таблиці ідентифікаторів і таблиці лексем на вхід синтаксичному аналізатору (рис.1).
Рис.1.1. Взаємодія лексичного і синтаксичного аналізаторів
Таблиця ідентифікаторів містить перелік ідентифікаторів, наприклад, назв змінних, функцій. Таблиця лексем містить ідентифіковані токени тексту вхідної програми у форматі внутрішнього представлення. Цей формат може включати таку інформацію:
позиція лексеми в тексті вхідної програми (рядок і стовпець);
тип токена;
лексему;
значення (для чисел, рядкових констант);
адресу ідентифікатора в таблиці ідентифікаторів.
Таблиці лексем і ідентифікаторів можуть бути суміщеними. Приклад таблиці лексем зображено в табл. 1.1.
Крім побудови таблиць лексем і ідентифікаторів лексичний аналізатор генерує вихідний файл з лексичними помилками з зазначенням адреси літералів, які викликали лексичну помилку. Лексичною помилкою є зустріч невідомої лексеми. При виникненні лексичної помилки можливі кілька варіантів реакції на неї:
«режим паніки» - записати повідомлення про помилку у файл і припинити лексичний розбір;
видалення зайвих символів;
вставка пропущених символів;
заміна невірного символу вірним;
перестановка двох сусідніх символів місцями.
Лексичний аналізатор не обов’язково обробляє всю програму до початку всіх інших фаз. Якщо лексичний аналіз не виділяється як окрема фаза компіляції, а є частиною синтаксичного аналізу, то лексична обробка тексту програми виконується по мірі необхідності по запиту синтаксичного аналізатора.
Таблиця 1.1. Таблиця лексем
Рядок
Токен
Лексема
Значення
Адреса в таблиці ідентифікаторів
5
Vartype
Int
0
0
5
Variable
Var
0
1
6
Vartype
Char*
0
0
6
Variable
Var
0
2
7
Variable
Var
0
1
7
Assign
<<
0
0
7
Num
Num
25
0
8
Condition
If
0
0
8
Variable
Var
0
1
8
Relation
eq
0
0
8
Num
Num
25
0
9
Variable
Var
0
2
9
Assign
<<
0
0
9
Literal
Literal
“Hello, World”
Зауваження: в колонках «токен» і «лексема» таблиці.1.1 під літеральним позначенням в дійсності стоїть унікальний цифровий ідентифікатор (який може бути заданий за допомогою типу enum мови С), який однозначно ідентифікує токени і лексеми. Наявність літерального позначення лексем і токенів допускається в цілях відлагодження, але є необов’язковою.
1.2. ПОБУДОВА ЛЕКСИЧНОГО АНАЛІЗАТОРА ЗАСОБАМИ СКІНЧЕННОГО АВТОМАТУ
1.2.1. Особливості побудови лексичного аналізатора засобами скінченного автомату
При побудові лексичного аналізатора (сканера) всі символи вхідного тексту програми поділяють на символи, що належать будь-яким лексемам, і символи, що розділяють лексеми: пробiли, знаки операцiй i спецiальні символи (новий рядок, знак табуляції). Це дає можливість побудувати скінченний автомат, який видiляє та розпізнає iдентифiкатори, лiтерали i термiнальнi символи (операцiї, ключові слова, тощо), а також видаляє коментарі, прбіли, інші спеціальні символи. Розроблений скінченний автомат можна реалізувати за допомогою операцій обробки рядків реалізованих в стандартних бібліотеках мови С/С++, наприклад, strtok(), strstr(), srtcmp(). При цьому текст вхiдної програми проглядається послiдовно з початку до кінця. При виділенні лексеми вона розпізнається та записується у таблицю лексем за допомогою відповідного номера лексеми, що є унікальним для кожної лексеми із усього можливого їх набору. Це дає можливість наступним фазам компiляції звертатись лексеми не як до послідовності символів, а як до унікального номера лексеми, що значно спрощує роботу синтаксичного аналізатора. Імена ідентифікаторів записуються в таблицю ідентифікаторів з присвоєнням унікальної адреси кожному унікальному ідентифікатору в таблицях лексем і ідентифікаторів. Ця таблиця в подальшому буде використана на етапі генерації коду.
1.2.2. Приклад побудови лексичного аналізатора засобами скінченного автомату
Лексичний аналізатор, що розглядається в прикладі здійснює зчитування вхідного тексту з попередньо видаленими пробілами і символами табуляції. З вхідного тексту програми видаляють коментарі. При цьому, коментарі можуть бути вкладеними, і баланс фігурних дужок може бути порушеним. Для виявлення цих помилок будемо використовувати Стек1 в який будуть поміщатися і вилучатися дужки, і Стек2, який буде містити номер рядка в якому стоять відповідні дужки у Стек1. Вхід аналізатора – текст програми з видаленими пробілами і символами табуляції. Вихід аналізатора - масив, у який треба записати вхідну програму без коментарів і пробілів (Рис. 1.2). Далі здійснюють виявлення не термінальних символів у зчитаному тексті і виведення повідомлення про помилки (рис.1.3).
Рис. 1.2. Граф-схема аналізу вкладених коментарів.
Рис. 1.3. Граф-схема аналізу символів.
Після успішного проходження перших двох етапів генерують таблицю ідентифікаторів (рис.1.4) і таблицю лексем (1.5).
Рис. 1.4. Граф-схема аналізу сегменту даних з генерацією таблиці ідентифікаторів.
Рис. 1.5. Граф-схема аналізу сегменту коду з генерацією таблиці лексем.
Рис.1.6. Перевірка таблиці ідентифікаторів на помилки.
Після генерації таблиці ідентифікаторів її перевіряють на помилки (рис.1.6). При цьому перевіряється коректність синтаксичної будови оголошення ідентифікаторів шляхом аналізу імені та типу кожного ідентифікатора. Якщо ім’я ідентифікатора не може бути виведене з даного алфавіту за даними правилами граматики або таке ім'я вже використовується, то виводиться повідомлення про помилку. Аналіз не зупиняється при знаходженні одної помилки, а відбувається для кожного із ідентифікаторів. Якщо ідентифікатор є константою, перевіряється чи задане значення константі при оголошенні, якщо так - перевіряється правильність заданого значення.
1.3. ІНШІ СПОСОБИ ПОБУДОВИ ЛЕКСИЧНОГО АНАЛІЗАТОРА
1.3.1. Побудова лексичного аналізатора засобами регулярних виразів
Побудова лексичного аналізатора (сканера) засобами регулярних виразів можлива при використанні мов програмування з вбудованою підтримкою регулярних виразів, наприклад, C#, PHP, Python, Java, Perl, тощо. При цьому за допомогою регулярних виразів задають правила виділення лексем і ідентифікаторів з подальшим утворенням таблиці лексем і ідентифікаторів. Наприклад ідентифікатор, який починається з знаку «_» після якого іде буква після якої може зустрічатися або буква або цифра нуль або більше разів можна виділити задавши регулярний вираз: '_[a-zA-Z][a-zA-Z0-9]*'.
1.3.2. Побудова лексичного аналізатора засобами спеціалізованого програмного забезпечення
Побудова лексичного аналізатора (сканера) засобами генераторів лексичних аналізаторів, наприклад, інструменту і мови Lex або Flex відбувається в 3 етапи (рис.1.7).
Рис.1.7. Створення лексичного аналізатора засобами Lex або Flex.
Flex на вході отримує текст у вільному форматі й правила виділення лексем. На виході дає код аналізатора, в вигляді функції на мові C.
Правила задаються в вигляді регулярних виразів ліворуч і, здебільшого, коду на мові C праворуч. Правила містять три секції, відокремлені рядком «%%»:
визначення
%%
правила
%%
код користувача
Визначення містять стартові значення й визначення, правила, безпосередньо самі вирази й дії, що відповідають їм, користувацький код просто включається в вивід flex. Деякі секції можуть бути відсутніми.
Функція аналізатора отримує текст на вході й виконує заданий код для кожної знайденої лексеми. Наприклад, код:
%%
username
printf( "%s", getlogin() );
для кожного входження username в тексті, виконає код printf("%s",getlogin()).
Дана функція виведе в потік рядок, що повертається функцією getlogin(). Тобто, кожне входження username у вхідному потоці буде замінено значенням, поверненим getlogin(). Наприклад, іменем поточного користувача.
Нижче наведено правила, відповідно до яких остаточна функція має друкувати на виході тип лексеми (if, змінна, число, унарна чи бінарна операція) та значення для деяких лексем:
%%
if printf ("IF statement\n");
[a-z]+ printf ("tag, value %s\n", yytext);
{D}+ printf ("decimal number %s\n", yytext);
"++" printf ("unary op\n");
"+" printf ("binary op\n");
Приклад підрахунку кількості рядків і символів у тексті:
%{
int num_lines = 0, num_chars = 0;
%}
%%
\n
++num_lines; ++num_chars;
.
++num_chars;
%%
main()
{
yylex();
printf( "# of lines = %d, # of chars = %d\n", num_lines, num_chars );
}
Далі, функцію, створену генератором можна використати з генераторами синтаксичних аналізаторів. Зазвичай flex використовують з yacc чи bison. Синтаксичний аналізатор використовує виклик функції yylex(), створеної генератором flex для пошуку наступної лексеми.
1.3.3. Приклад файлу з правилами виділення лексем для Flex
В даному прикладі розглядається побудова файлу з правилами виділення лексем для flex для імперативної мови програмування PL/0.
Розпізнаються наступні лексеми: '+', '-', '*', '/', '=', '(', ')', ',', ';', '.', ':=', '<', '<=', '<>', '>', '>='; числа: 0-9 {0-9}; ідентифікатори: a-zA-Z {a-zA-Z0-9} та ключові слова: begin, call, const, do, end, if, odd, procedure, then, var, while.
Файл lex.l матиме наступний вигляд:
%{
#include "y.tab.h"
%}
digit [0-9]
letter [a-zA-Z]
%%
"+" { return PLUS; }
"-" { return MINUS; }
"*" { return TIMES; }
"/" { return SLASH; }
"(" { return LPAREN; }
")" { return RPAREN; }
";" { return SEMICOLON; }
"," { return COMMA; }
"." { return PERIOD; }
":=" { return BECOMES; }
"=" { return EQL; }
"<>" { return NEQ; }
"<" { return LSS; }
">" { return GTR; }
"<=" { return LEQ; }
">=" { return GEQ; }
"begin" { return BEGINSYM; }
"call" { return CALLSYM; }
"const" { return CONSTSYM; }
"do" { return DOSYM; }
"end" { return ENDSYM; }
"if" { return IFSYM; }
"odd" { return ODDSYM; }
"procedure" { return PROCSYM; }
"then" { return THENSYM; }
"var" { return VARSYM; }
"while" { return WHILESYM; }
{letter}({letter}|{digit})* {
yylval.id = (char *)strdup(yytext);
return IDENT; }
{digit}+ { yylval.num = atoi(yytext);
return NUMBER; }
[ \t\n\r] /* skip whitespace */
. { printf("Unknown character [%c]\n",yytext[0]);
return UNKNOWN; }
%%
int yywrap(void){return 1;}
2. СИНТАКСИЧНИЙ АНАЛІЗ
2.1. ВИЗНАЧЕННЯ СИНТАКСИЧНИХ ПРАВИЛ МОВИ ПРОГРАМУВАННЯ ЗА ДОПОМОГОЮ ФОРМУЛ БЕКУСА-НАУРА
Форма Бе́куса-Нау́ра (англ. Backus-Naur form, BNF) - це спосіб запису правил контекстно-вільної граматики, тобто це форма опису формальної мови.
Саме її типово використовують для запису правил мов програмування та протоколів комунікації. У 50-х роках минулого сторіччя Джон Бекус створив цю нотацію розробляючи мову ALGOL. На першому Всесвітньому Комп'ютерному Конгресі, що відбувся у Парижі 1959-го року він зробив доповідь на тему "Синтаксис та семантика пропонованої першої міжнародної алгебраїчної мови". Пізніше Наур Пітер спростив її та (за порадою Дональда Кнута) додав до назви своє ім'я.
Розши́рена фо́рма Бе́куса — На́ура (англ. extended Backus-Naur form, EBNF) є розширеною формою нотації Бекуса-Наура (BNF). Початково розроблена Ніклавсом Віртом, сьогодні вона існує в багатьох варіантах, перед усім у варіанті ISO-14977 [1].
Формули БНФ складаються з наступних мета символів:
< – лівий обмежувач;
> – правий обмежувач;
::= – визначено як;
| – або;
“” — текстовий елемент (символ або група символів).
Розширені формули Бе́куса-Нау́ра використовують додаткові мета символи:
[] – елемент у дужках входить або не входить (є необов’язковим);
() – групування елементів у дужках;
{} – нуль або більше повторень елементів розташованих у дужках;
(* – початок блоку коментарів;
*) – кінець блоку коментарів.
Формули БНФ оперують термінальними і нетермінальними символами. Нетермінальні символи – це символи які введені для визначення “правил продукції”. Вони поміщаються в трикутні дужки: <цифра>. Натомість термінальні символи представляють лексеми або їх складові частини: 0,1,2,А,В,с,;,*,/,-,+.
Лексема - це мінімальна одиниця мови, що має значення. З лексемами також пов’язане поняття токен. Воно є загальнішим і відповідає групам лексем, наприклад, множина лексем, що відповідають умовним операторам, арифметичним операторам, тощо.
Формули БНФ по суті є набором "правил продукції ", кожне з яких відповідає шаблону:
< Не термінальний символ > ::= <вираз, що містить термінальні і не термінальні символи>
Формула виду:
А ::= {B}
позначає можливе повторення не термінального символу В нуль чи більше раз і є просто скороченим записом рекурсивного, по суті, правила:
A ::= <пусто> | AB
При цьому слід чітко розуміти різницю між фігурними і квадратними дужками. Елементи між фігурними дужками можуть зустрічатися 0 або більше разів, так розділ оголошень змінних може не містити змінних (бути порожнім), або містити їх в великій кількості. Таким чином в цьому випадку слід застосувати фігурні дужки при описі синтаксичної конструкції <розділ оголошень>:
<розділ оголошень>::=Variables {<ідентифікатор>{,< ідентифікатор >}:<тип>;}
Натомість при визначені синтаксичної конструкції <число> наявність знаку перед числом є необов’язковою, тому наявність знака в цій синтаксичній конструкції визначають використовуючи квадратні дужки:
<число>::=[+|-]<цифра>{<цифра>}
Увага!!! При описі синтаксису мови за допомогою БНФ слід уникати право і ліво рекурсивних синтаксичних конструкцій, які мають вигляд A ::= zA і A ::= Az відповідно.
2.1.1. Приклад визначення натуральних чисел за допомогою формул БНФ
<нуль> ::= 0
<ненульова цифра> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<цифра> ::= <нуль> | <ненульова цифра>
<послідовність цифр> ::= <нуль> | <ненульова цифра> | <цифра><послідовність цифр>
<натуральне число> ::= <цифра> | <ненульова цифра><послідовність цифр>
В цьому прикладі 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – термінальні символи. Решта символів – не термінальні. Запис <ненульова цифра> ::= 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 слід читати ненульова цифра визначена як 1 або 2 або 3 або 4 або 5 або 6 або 7 або 8 або 9 або 10. Запис <цифра> ::= <нуль> | <ненульова цифра> слід читати цифра визначена як нуль або ненульова цифра.
2.1.2. Формули Бекуса-Наура для мови Pascal
<програма> ::= <заголовок програми> <блок> .
<заголовок програми> ::= program <і’мя> (<і’мя файла> {,<і’мя файла>});
<і’мя файла> ::= <і’мя>
<і’мя> ::= <буква> {<буква чи цифра>}
<буква чи цифра> ::= <буква> | <цифра>
<блок> ::= <розділ міток> <розділ констант> <розділ типів> <розділ змінних>
<розділ процедур і функцій> <розділ операторів>
<розділ міток> ::= <пусто> | label <мітка> {,< мітка >};
<мітка> ::= <ціле без знаку>
<розділ констант> ::= <пусто> | const <визначення константи>
{; <визначення константи>};
<визначення константи> ::= <і’мя> = <константа>
<константа> ::= <число без знаку> | <знак> <число без знаку> | <ім’я константи> |
<знак> <ім’я константи> | <рядок>
<число без знаку> ::= <ціле без знаку> | <дійсне без знаку>
<ціле без знаку> ::= <цифра> {<цифра>}
<дійсне без знаку> ::= <ціле без знаку> . <цифра> {<цифра>} |
<ціле без знаку> . <цифра> {<цифра>} E <порядок> |
<ціле без знаку> E <порядок>
<порядок> ::= <ціле без знаку> | <знак> <ціле без знаку>
<знак> ::= + | –
<ім’я константи> ::= <ім’я>
<рядок> ::= ’<символ> {<символ>}’
<розділ типів> ::= <пусто> | type <визначення типу> {; <визначення типу>};
<визначення типу> ::= <ім’я> = <тип>
<тип> ::= <простий тип> | <складовий тип> | <вказівний тип>
<простий тип> ::= <скалярний тип> | <обмежений тип> | <ім’я типу>
<скалярний тип> ::= ( <ім’я> {, <ім’я>} )
<обмежений тип> ::= <константа> .. <константа>
<ім’я типу> ::= <ім’я>
<складовий тип> ::= <неупакований складовий тип> |
packed <неупакований складовий тип>
<неупакований складовий тип> ::= <регулярний тип> | <комбінований тип> |
<множинний тип> | <файловий тип>
<регулярний тип>::= array[ <тип індекса> {, <тип індекса>}] of <тип компонента>
<тип індекса> ::= <простий тип>
<тип компонента> ::= <тип>
<комбінований тип> ::= record <список полів> end
<список полів> ::= <фіксована частина> | <фіксована частина>
<варіантна частина> | <варіантна частина>
<фіксована частина> ::= <секція запису> {; <секція запису>}
<секція запису> ::= <ім’я поля> {, <ім’я поля>} : <тип> | <пусто>
<варіантна частина> ::= case <дискримінант> <ім’я типу> of <варіант> {; <варіант>}
<дискримінант> ::= <ім’я поля> : | <пусто>
<варіант> ::= <список міток варіанту> : ( <список полів>) | <пусто>
<список міток варіанту> ::= <мітка варіанту> {, <мітка варіанту>}
<мітка варіанту> ::= <константа>
<множинний тип> ::= set of <базовий тип>
<базовий тип> ::= <простий тип>
<файловий тип> ::= file of <тип>
<вказівний тип> ::= ^ <ім’я типу>
<розділ змінних> ::= <пусто> | var <опис змінної> {; <опис змінної>};
<опис змінної> ::= <ім’я> {, <ім’я>} : <тип>
<розділ процедур і функцій> ::= {<опис процедури чи функції>;}
<опис процедури чи функції> ::= <опис процедури> | <опис функції>
<опис процедури> ::= <заголовок процедури> <блок>
<заголовок процедури> ::= procedure <ім’я> |
procedure <ім’я> ( <розділ формальних параметрів>
{; <розділ формальних параметрів>});
<розділ формальних параметрів> ::= <група параметрів> | var <група параметрів> |
function <група параметрів> | procedure <ім’я> {, <ім’я>}
<група параметрів> ::= <ім’я> {, <ім’я>} : <ім’я типу>
<опис функції> ::= <заголовок функції> <блок>
<заголовок функції> ::= function <ім’я> : <тип результату> |
function <ім’я> ( <розділ формальних параметрів>
{; <розділ формальних параметрів>}) : <тип результату>;
<тип результату> ::= <ім’я типу>
<розділ операторів> ::= <складовий оператор>
<оператор> ::= <непозначений оператор> | <мітка> : <непозначений оператор>
<непозначений оператор> ::= <простий оператор> | <складний оператор>
<простий оператор> ::= <оператор присвоювання> | <оператор процедури> |
<оператор переходу> | <порожній оператор>
<оператор присвоювання> ::= <змінна> := <вираз> | <ім’я функції> := <вираз>
<змінна> ::= <повна змінна> | <компонентна змінна> | <вказівна змінна>
<повна змінна> ::= <ім’я змінної>
<ім’я змінної> ::= <ім’я>
<компонентна змінна> ::= <індексована змінна> | <позначення поля> | <буфер файла>
<індексована змінна> ::= <змінна-масив> [<вираз> {, <вираз>}]
<змінна-масив> ::= <змінна>
<позначення поля> ::= <змінна-запис> . <ім’я поля>
<змінна-запис> ::= <змінна>
<ім’я поля> ::= <ім’я>
<буфер файла> ::= <змінна-файл>^
<змінна-файл> ::= <змінна>
<вказівна змінна> ::= <змінна-посилання>^
<змінна-посилання> ::= <змінна>
<вираз> ::= <простий вираз>| <простий вираз> <операція відношення> <простий вираз>
<операція відношення> ::= = | <> | < | <= | > | >= | in
<простий вираз> ::= <доданок> | <знак> <доданок> |
<простий вираз> <адитивна операція> <доданок>
<адитивна операція> ::= + | – | or
<доданок> ::= <множник> | <доданок> <мультиплікативна операція> <множник>
<мультиплікативна операція> ::= * | / | div | mod | and
<множник> ::= <змінна> | <константа без знаку> | (<вираз>) |
<позначення функції> | <множина> | not <множник>
<константа без знаку> ::= <
11.11.2012 14:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора