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

Тип работы:
Реферат
Предмет:
Информатика, программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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

КОРОЛЕВА

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

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

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

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

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

Выполнил:

студент групи 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 (тому знаки предшествования іноді позначають спеціальної точкою: =? ,

ПоказатьСвернуть
Заполнить форму текущей работой