Блок №1 лабораторних робіт

Мета: ознайомитися з методами зберігання КС-граматики в пам'яті ЕОМ для подальшої обробки та запрограмувати деякі функції доступу/ обробки наведених вище інформаційних структур.

1. Реалізувати препроцесор для вводу граматики в ЕОМ. Препроцесор перетворює послідовність правил текстового файлу в інформаційну структуру в пам'яті ЕОМ.

Вхідні дані: файл з текстом граматики мови програмування.

Вихідні дані:

- машинно-орієнтоване представлення множини КС-правил граматики;

2. Реалізувати алгоритм пошуку непродуктивних нетерміналів. Надрукувати список непродуктивних нетерміналів. Інтерфейс виклику для реалізації функції:

int prepr_std(q,r)

struct node *q; // список КС-правил

struct dnode *r; // початок хеш-таблиці

Функція повертає результат:

- 0 - коли непродуктивних нетерміналів немає,

- 1 - непродуктивні нетермінали в граматиці є.

3. Реалізувати алгоритм пошуку недосяжних нетерміналів.. Надрукувати список недосяжних нетерміналів. Інтерфейс виклику для реалізації функції:

int prepr_std(q,r)

struct node *q; // список КС-правил

struct dnode *r; // початок хеш-таблиці

Функція повертає результат:

- 0 - коли недосяжних нетерміналів немає,

- 1 - недосяжні нетермінали в граматиці є.

4. Реалізувати алгоритм пошуку ліворекурсивних нетерміналів... Надрукувати список ліворекурсивних нетерміналів. Інтерфейс виклику для реалізації функції:

int prepr_std(q,r)

struct node *q; // список КС-правил

struct dnode *r; // початок хеш-таблиці

Функція повертає результат:

- 0 - коли ліворекурсивних нетерміналів немає,

- 1 - ліворекурсивні нетермінали в граматиці є.

5. Реалізувати алгоритм пошуку праворекурсивних нетерміналів. Надрукувати список праворекурсивних нетерміналів. Інтерфейс виклику для реалізації функції:

int prepr_std(q,r)

struct node *q; // список КС-правил

struct dnode *r; // початок хеш-таблиці

Функція повертає результат:

- 0 - коли праворекурсивних нетерміналів немає,

- 1 - праворекурсивні нетермінали в граматиці є.

6. Розробити та реалізувати алгоритм пошуку різних виводів виду А=>*Aw мінімальної довжини, тобто мінімальних ліворекурсивних виводів. Надрукувати послідовність правил, які дають такий результат. Інтерфейс виклику для реалізації функції:

int prepr_std(q,r)

struct node *q; // список КС-правил

struct dnode *r; // початок хеш-таблиці

Функція повертає результат:

- 0 - коли ліворекурсивних нетерміналів немає,

- 1 - ліворекурсивні нетермінали в граматиці є.

7. Розробити та реалізувати алгоритм пошуку різних виводів виду А=>*wA мінімальної довжини, тобто мінімальних праворекурсивних виводів. Надрукувати послідовність правил, які дають такий результат. Інтерфейс виклику для реалізації функції:

int prepr_std(q,r)

struct node *q; // список КС-правил

struct dnode *r; // початок хеш-таблиці

Функція повертає результат:

- 0 - коли праворекурсивних нетерміналів немає,

- 1 - праворекурсивні нетермінали в граматиці є.

8. Реалізувати алгоритм пошуку множини для нетерміналів граматики. Надрукувати множини для кожного нетермінала. Інтерфейс виклику для реалізації функції:

int prepr_std(q,r)

struct node *q; // список КС-правил

struct dnode *r; // початок хеш-таблиці

9. Реалізувати алгоритм пошуку множини для нетерміналів граматики. Надрукувати множини для кожного нетермінала. Інтерфейс виклику для реалізації функції:

int prepr_std(q,r)

struct node *q; // список КС-правил

struct dnode *r; // початок хеш-таблиці

10. Побудувати LL(1)- граматику для мови програмування С. Якщо виконати LL(1)- умову неможливо, то спробуйте для деяких правил запропонувати LL(1)- умову. Інтерфейс виклику для реалізації функції:

int prepr_std(q,r)

struct node *q; // список КС-правил

struct dnode *r; // початок хеш-таблиці

11. Реалізуйте допоміжні функції, які використовуються для побудови множин .

- функція побудови слова довжиною не більше k символів:

int newword(mult,dwor,wrk,len)

struct fdata **mult; // масив посилок на скінчені мови

short int *dwor; // масив поточна перестановка індексів слів

short int wrk[]; // масив під результуюче слово

int len; // число множин, які перемножаться

- функція побудови нової перестановки індексів для словарних множин:

int setword(mult,max_dwor,dwor,len)

struct fdata **mult; // масив посилок на скінчені мови

int *max_dwor; // кількість слів в кожній словарній множині

int *dwor; // поточна перестановка індексів

int len; // число множин, які перемножаться

12. Реалізувати функцію, котра на основі контекстів для кожного правила виду A_i -> W обчислить значення - для кожної правої частини правила. Результат занести в поле cont-llk для кожної продукції. Інтерфейс виклику для реалізації функції:

int prepr_std(q,r)

struct node *q; // список КС-правил

struct dnode *r; // початок хеш-таблиці

int prepr_std(q,r)

13. Реалізувати функцію, котра на основі контекстів и для нетерміналів обчислить значення +_k для кожної правої частини продукції виду A -> W. Результат занести в поле cont_llk для кожної продукції. Інтерфейс виклику для реалізації функції:

int prepr_std(q,r)

struct node *q; // список КС-правил

struct dnode *r; // початок хеш-таблиці

14. Реалізувати функцію, котра на основі контекстів +_k для кожної правої частини продукції виду A -> W визначить, чи є граматика сильною LL(k)- граматикою, зокрема LL(1)- граматикою. Контексти по кожному правилу знаходяться в полі cont_llk. Інтерфейс виклику для реалізації функції:

int prepr_std(q,r)

struct node *q; // список КС-правил

struct dnode *r; // початок хеш-таблиці

15. (це приклад). Реалізувати алгоритм пошуку EPSILON-нетерміналів. Надрукувати список EPSILON-нетерміналів, а також правила граматики, які дають вивід виду: А=>*. Інтерфейс виклику для реалізації функції:

int prepr_std(q,r)

struct node *q; // список КС-правил

struct dnode *r; // початок хеш-таблиці

Функція повертає результат:

- 0 - коли EPSILON-нетерміналів немає,

- 1 - коли EPSILON-нетермінали в граматиці є.