Синтаксичні аналізатори та алгоритми з ними

Граматика мови програмування визначається множиною БНФ-правил, що записані в текстовому файлі. Кожне провило обов’язково починається з першої позиції рядка. Для зручності правило можна продовжити в наступних рядках, але не з першої позиції. Нетермінал граматики — це ланцюжок літер, який починається з символу # та закінчується символом #, наприклад #програма#. Термінальні ланцюжки записуються традиційно, наприклад, begin. Альтернативи правила для зручності позначаються символом ! в першій позиції рядка, при цьому ліва частина правила опускається. Оскільки символи #, \ та ! є метасимволами при визначенні граматики, то для їх запису в термінальних ланцюжках використовується ще один метасимвол, а саме \. Правило граматики в текстовому файлі записується так:

#Pascal - програма#  program ( #список параметрів# ) #блок#

Лабораторний практикум другого семестру з дисципліни «Системне програмування» передбачає освоєння навиків створення власних програмних Java-проектів з використанням базового проекту, який повністю реалізований, та надається студенту у використання.

Визначимо основні положення базового проекту. Клас class MyLang забезпечує повне рішення та надає програмісту можливість замінити в екземплярі результуючого класу певне значення на власний результат та виконати проект в цілому. Якщо новостворена програмна система надає фінальний результат, який відповідає результату базового проекту, то алгоритм, який реалізований студентом, рахується вірним.

Таким чином, студенту надається «конструктор цеглин» якими можна скористатися на етапі реалізації власного алгоритму (звичайно, не викликаючи «будівельний матеріал» базового проекту, який надає аналогічний результат).

Пакет можна завантажити за посиланням (.7z, 21 Kb).

Блок 1

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

2. Реалізувати алгоритм пошуку недосяжних не терміналів. Правила, що починаються з недосяжних не терміналів вилучити з граматики;

3. Реалізувати алгоритм пошуку непродуктивних правил. Непродуктивні правила вилучити з граматики.

4. Перевірити, чи $L(G)$ — пуста множина.

5. Реалізувати алгоритм пошуку $\varepsilon$-нетерміналів. Результат занести до опису граматики — екземпляр класу MyLang;

6. Реалізувати алгоритм пошуку ліво-рекурсивних не терміналів.

7. Реалізувати алгоритм пошуку право-рекурсивних не терміналів.

8. $^{\star\star}$ Розробити та реалізувати алгоритм пошуку всіляких виводів мінімальної довжини (без повторів), які призводять до лівої рекурсії.

9. $^{\star\star}$ Розробити та реалізувати алгоритм пошуку всіляких виводів мінімальної довжини (без повторів), які призводять до правої рекурсії.

Блок 2

1. Реалізувати алгоритм пошуку множин $\text{First}_k(A_i)$, $A_i \in N$. Результат занести до опису граматики — екземпляр класу MyLang.

2. Реалізувати алгоритм пошуку множин $\text{Follow}(A_i)$, $A_i \in N$. Результат занести до опису граматики — екземпляр класу MyLang.

3. Реалізувати алгоритм пошуку множин $\text{First}_k(w)$ для правил $A_i \to w$, $A_i \in N$. Результат занести до опису граматики — екземпляр класу MyLang.

4. Реалізувати алгоритм пошуку множин $\text{First}_k(w) \oplus_k \text{Follow}_k(A_i)$, для правил $A_i \to w$, $A_i \in N$. Результат занести до опису граматики — екземпляр класу MyLang.

5. Перевірити, чи є побудована граматика $LL(1)$-граматикою.

6. Перевірити, чи є побудована граматика сильною $LL(k)$-граматикою (для $k = 2$);

7. Перевірити, чи є побудована граматика сильною $LL(k)$-граматикою (для $k = 3$);

8. Побудувати таблицю управління $LL(1)$-синтаксичного аналізатора.

9. $^{\star\star}$ Побудувати множини $\text{Local}_k(S, A_i)$, $A_i \in N$. Результат занести до опису граматики — екземпляр класу MyLang.

10. $^{\star\star}$ Перевірити, чи є граматика $LL(k)$-граматикою ($k > 1$).

Блок 3

1. Реалізувати синтаксичний аналізатор мови Pl/0 методом магазинного автомата.

2. Реалізувати синтаксичний аналізатор мови Pl/0 методом рекурсивного спуску.

3. Реалізувати синтаксичний аналізатор мови Pl/0 методом рекурсивного спуску на правилах грамматики (рекурсивний алгоритм руху по правилах граматики);

4. Реалізувати синтаксичний аналізатор мови Pascal методом магазинного автомата.

5. Реалізувати синтаксичний аналізатор мови Pascal методом рекурсивного спуску.

6. Реалізувати синтаксичний аналізатор мови Pascal методом рекурсивного спуску на правилах грамматики (рекурсивний алгоритм руху по правилах граматики);

7. Реалізувати синтаксичний аналізатор мови C методом магазинного автомата (за умови наявності колізій для декількох не терміналів).

8. Реалізувати синтаксичний аналізатор мови C методом рекурсивного спуску (за умови наявності колізій для декількох не терміналів).

9. Реалізувати синтаксичний аналізатор мови C методом рекурсивного спуску на правилах грамматики (рекурсивний алгоритм руху по правилах граматики) за умови наявності колізій для декількох не терміналів;

Назад до усіх лаб

Назад на головну