Самарського державного аерокосмічного університету імені академіка С.П.

КОРОЛЬОВА

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

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

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

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

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

Виконав:

студент групи 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;

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

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

3. Граматики передування

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

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

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

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

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