Построение функції предшествования по заданої КС-грамматике

САМАРСЬКИЙ ДЕРЖАВНИЙ АЕРОКОСМІЧНИЙ УНІВЕРСИТЕТ імені академіка С.П.

КОРОЛЕВА.

Кафедра інформаційних систем і технологий.

ПОЯСНЮВАЛЬНА ЗАПИСКА.

до курсовому проекту по курсу.

" Інформаційні технології «на тему.

" Побудова функції предшествования по заданої КС-грамматике «.

Выполнил:

студент групи 634 Абраров А.М.

Керівник проекта:

Шамашов М.А.

Дата сдачи:

Оценка:

Самара 2001 г.

РЕФЕРАТ.

Курсової проект.

Пояснювальна записка: 30 з., 5 рис., 3 схем програм, тож алгоритмів, 3 бібліографічного источника.

ТЕРМІНАЛ, НЕТЕРМІНАЛ, ГРАМАТИКА, ФУНКЦІЯ ПРЕДШЕСТВОВАНИ, ГРАФ, ЛИНЕАРИЗАЦИЯ.

У курсовому проекті розроблений алгоритм й гарантована відповідна йому програма, що дозволяє по введённой користувачем КС-грамматике побудувати функцію предшествования, використовуючи граф линеаризации і алгоритм перерахунку з візуалізацією кроків побудови графа. Граматика може бути впроваджена як в самій програмі, що з текстового файла. Існує також можливість збереження результату. Програма написана мовою Pascal 7.0.

ЗМІСТ 3.

1. Постановка завдання 4.

2. Опис структури даних 5.

3. Граматики предшествования 6.

3.1 Граматики простого предшествования 6.

3.2 Граматики операторного предшествования 8.

3.3 Приклад побудови матриці предшествования 10.

3.4 Линеаризация матриці предшествования 13.

4. Керівництво користувача 13.

5. Текст програми 15.

6. Список використаних джерел 30.

1. Постановка задачи.

По заданої КС-грамматике побудувати ставлення простого чи операторного предшествования і функцію предшествования, використовуючи граф линеаризации і алгоритм перерахунку з візуалізацією кроків побудови графа.

2. Опис структури данных Типы:

Для зберігання терміналів і терміналів використовується тип: notTerm=^List; List=Record{список терміналів і нетерминалов}.

Name:Str10;{терминал чи нетерминал}.

Next:notTerm;

End; Для зберігання граматики (тексту) використовується: strBuf=array [1.800] of Char; Матриця предшествования: matrixPr=array [1.20,1.20] of 0.4; Функція предшествования: FuncPr=array [1.2,1.20] of Byte;

Процедуры і функції (основные):

Ввод граматики здійснюється функцією: Function InputText: Boolean; Для синтаксичного аналізу КС-грамматики використовується процедура: Procedure Check; Для перебування «лівих» і «правих» використовується процедура: Procedure SearchLR; Побудова матриці предшествования виконує процедура: Procedure Matrix; Побудова функції предшествования здійснюється процедурою: Procedure FuncPrecede;

3. Граматики предшествования.

КС-языки діляться на класи відповідно до структурою правил їх граматик. У кожному з класів накладаються додаткових обмежень на допустимі правила граматики. Однією з таких класів є клас граматик предшествования. Вони йдуть на синтаксичного розбору ланцюжків з допомогою алгоритму «зрушеннязгортка». Вирізняють такі типи граматик предшествования: простого предшествования; розширеного предшествования; слабкого предшествования; змішаної стратегії предшествования; операторного предшествования. Далі розглядатимуться обмеження на структуру правив і алгоритми розбору обох типів — граматик простого і операторного предшествования.

3.1 Граматики простого предшествования.

Граматикою простого предшествования називають таку КС-грамматику G (VN, VT, P, S), V=VT?VN в которой:

1. Для кожної упорядкованим пари термінальних і нетермінальних символів виконується лише 1 із 3 відносин предшествования: Si = Sj (? Si, Sj? V), як і лише коли? правило U> xSiSjy? P, де U? VN, x, y? V*; Si < Sj (? Si, Sj? V), як і лише коли? правило U> xSiDy? P та виведення D? *Sjz, де U, D? VN, x, y, z? V*; Si > Sj (? Si, Sj? V), як і лише коли? правило U> xCSjy? P та виведення З? *zSi чи? правило U> xCDy? P і деякі висновки З? *zSi і D? *Sjw, де U, C, D? VN, x, y, z, w? V*.

2. Різні які породжують правила мають різні праві частини. Відносини =, < і > називають відносинами предшествования для символів. Ставлення предшествования єдино кожної упорядкованим пари символів. У цьому між певними двома символами може і не відносини предшествования — це що означає, що вони можуть бути поруч в жодному елементі розбору синтаксично правильної ланцюжка. Відносини предшествования залежить від порядку, у якому стоять символи, й у сенсі їх можна плутати зі знаками математичних операцій — наприклад, якщо Si > Sj, то ми не обов’язково, що Sj < Si (тому знаки предшествования іноді позначають спеціальної точкою: =? ,.