Лабораторний практикум побудови синтаксичних аналізаторів

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

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

 

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

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

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

Class MyLang

Тоді коротко, основні поля класу class MyLang наступні:

 

private int axioma;		// код аксіоми. В граматиці аксіома може бути не в першому правилі граматики
private boolean create;		// якщо екземпляп классу створено корректно, то true
private int LLK;		// значення LLK-контексту
private LinkedList<Node> language;		// список правил грамат
private LinkedList<TableNode> lexemaTable;		// таблиця перекодування лексем граматики
private int[] terminals;		// таблиця терміналів граматики
private int[] nonterminals;		// таблиця нетерміналів граматики
private int[] epsilonNerminals;		// таблиця ерсілон-нетерміналів граматики
private LlkContext[] termLanguarge;		// масив одно літерних словарних, побудованих на основі терміналів, тобто termLanguarge[i] – це одноелементна словарна множина, побудована на основі terminals[i]
private LlkContext[] firstK;		// массив словарних множин firstk, побудований выдповыдно до масиву nonterminals, тобто firstk[i] це множина Firstk для не термінала nonterminals[i].
private LlkContext[] followK;		// аналогічно попередньому поясненню
private LinkedList<LlkContext>[] LocalkContext;		// аналогічно попередньому поясненню, тобто LocalkContext[i] – це список множин Localk для нетермінала nonterminals[i].
private int[] uprTable;		// двомірний масив, який моделюється одноміпним масивом, у якого кількість стопців рівна (terminals.length+1), а рядків - nonterminals.length.

 

Конструктор екземплярів класу: public MyLang(String fileGramma, int llk).

 

Як бачимо, головний елемент (поле) класу MyLang LinkedList<Node> language – це список правил граматики. Кожне правило представляється екземпляром класу Node. У загальному випадку, аксіома – не обов’язково лівий нетермінал першого правила. Вона визначається через метод public int getAxioma().

 

Множини First_k (A_i), Followk(A_i), First_k(w) Fllow_k(A_i) (для правила A_i -> w) – визначаються як екземпляри класу LlkContext.

 

Множина Localk(S,A_i) визначається як LinkedList<LlkContext >, тобто множина (список) елементів LlkContext.

 

Для роботи з інформацією класу MyLang користувачу надається набір методів:

 

Група методів, яка забезпечує виконання алгоритмів:

public boolean isCreate(); // Перевіряє, чи створено «complite» екземпляр класу MyLang

public LinkedList<LlkContext>[] createLocalK();// побудова множин Local_k(S,A_i)

public boolean llkCondition(); // перевірка LL(k) - умови

public boolean createNonProdRools();// пошук непродуктивних правил

public boolean createNonDosNeterminals();// пошук недосяжних нетерміналів

public boolean leftRecursNonnerminal();// пошук ліво-рекурсивних нетерміналів

public boolean rightRecursNonnerminal();// пошук право-рекурсивних нетерміналів

public LlkContext[] firstK();(); // побудова множини First_k (A_i),

public LlkContext[] followK();// побудова множини Follow_k (A_i),

public void firstFollowK(); // побудова множини First_k (w) +_k Follow_k (A_i) для всіх правил

public int[] createEpsilonNonterminals();// побудова множино е-нетерміналів

private int[] createTerminals(); // побудова множино терміналів

private int[] createNonterminals(); // побудова множино нетерміналів

public boolean strongLlkCondition(); // перевірка сильноє LL(k)-умови

public int[] createUprTable(); // побудова таблиці управління для LL(1)-граматики

public int[] createUprTableWithCollision(); // побудова таблиці управління для LL(1)-граматики за умови, що декілька не терміналів мають LL(1)- колізію, але граматика взагалі задовольняє сильній LL(2)-умові. Клітини таблиці управління, де є колізія позначаються (-1).

 

Група сервісних методів – забезпечує екстракцію даних з класу або запис даних до класу:

public int getAxioma();

public void setLocalkContext(LinkedList<LlkContext>[] localK); // дає можливість внести до екземпляр класу MyLang побудовану множину Local_k; Взагалі, в цьому проекті методи set забезпечують збереження результату в екземплярі класу MyLang, а методи get – отримання результату.

public LinkedList<LlkContext>[] getLocalkContext();

public int[] getUprTable();

public LlkContext[] getFirstK();

public void setFirstK(LlkContext[] first);

public void setUprTable(int[] upr);

public LlkContext[] getFollowK();

public void setFollowK(LlkContext[] follow);

public int getLlkConst();

public LlkContext[] getLlkTrmContext(); // масив словарних множин для одноелементних термінвальних мов. I-та мова зберігає i-й термінал з масиву (множини) терміналів

public String getLexemaText(int code); //по коду лексеми ми визначаємо її текст

public int[] getTerminals()

public int[] getNonTerminals()

public int[] getEpsilonNonterminals()

public LinkedList<Node> getLanguarge()

public void setEpsilonNonterminals(int[] eps)

 

Група сервісних методів, які забезпечують друк (вивід у стандартний файл) результату:

public void printLocalk();

public void printTerminals();

public void printNonterminals();

public void prpintRoole(Node nod);

public void printFirstkContext()

public void printFirstFollowK()

public void printFirstFollowForRoole()

public void printFollowkContext()

public void printEpsilonNonterminals()

public void printGramma().

 

 

Class Node

Клас сlass Node забезпечує збереження та доступ до правил граматики у списку правил LinkedList<Node> language. Поля екземпляру класу Node:

private int[] roole; // закодоване правило – це масив кодів лексем. Довжина масиву включає і лівий елемент правила. Нетермінали граматики закодовані від’ємними кодами, термінали – додатніми кодами.

private int teg; //робоче поле, доступне користувачу для маркування правил.

private LlkContext firstFollowK; // тут зберігається добуток Firstk(w)+_k Followk(Ai) (для правила Ai-> w) для правила.

 

Для роботи з правилом граматики надаються наступні методи, їх семантика зрозуміла з попередніх визначень:

public void addFirstFollowK(LlkContext rezult);

public LlkContext getFirstFollowK();

public int[] getRoole();

 

Class LlkContext

Клас сlass LlkContext – відповідає за збереження словарних множин. Слово – це масив кодів лексем (int []). Е-слово має специфікацію new int[0] (мова Java допускає таку нотацію.

 

public LlkContext(); // конструктор

public boolean wordInContext(int[] word); // слово є в словарній множині

public int[] getWord(int index); // отримати слово з індексом index з словарної множини. Індексація починається з нуля.

public int minLengthWord(); // мінімальна довжина слова у словарній множині

public int calcWords(); // кількість слів у словарній множині

public boolean addWord(int[] word); // добавляє слово до словарної множини. У випадку. Коли слово добавлено - значення методу true.

 

 

Class TableNode

Клас сlass TableNode – це допоміжний клас для зберігання текстів лексем граматики. Поля класу:

String lexemaText; // текст лексеми

int lexemacode; // код лексеми

static int numarator; // нумератор лексем

Маска коду не термінала 0x80000000, маска коду термінала 0x10000000.

В цьому класі важливий конструктор:

public TableNode (String lexema, int lexemaType);

 

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

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

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

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

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

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

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

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

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

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

 

Блок 2 Лабораторних робіт

1. Реалізувати алгоритм пошуку множин Firstk(Ai), Ai Î N. Результат занести до опису граматики - екземпляр класу MyLang.

2. Реалізувати алгоритм пошуку множин Follow(Ai), Ai Î N. Результат занести до опису граматики - екземпляр класу MyLang.

3. Реалізувати алгоритм пошуку множин Firstk(w) для правил Ai -> w, Ai Î N. Результат занести до опису граматики - екземпляр класу MyLang

4. Реалізувати алгоритм пошуку множин Firstk(w),+_k Follow(Ai), для правил Ai -> w, Ai Î N. Результат занести до опису граматики - екземпляр класу MyLang.

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

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

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

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

9. **Побудувати множини Local_k(S,Ai), Ai Î N. Результат занести до опису граматики - екземпляр класу MyLang.

10. **Перевірити, чи є граматика 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 методом рекурсивного спуску на правилах грамматики (рекурсивний алгоритм руху по правилах граматики) за умови наявності колізій для декількох не терміналів;

10.

 

 

Блок 4 Лабораторних робіт

Наведений нижче перелік лабораторних робіт - це дослідницькі роботи, які передбачають вивчення додаткового матеріалу та практичних навиків попередніх розділів.

1. Побудувати LL(k)-граматику (k=1 или k=2) для мови програмування Delphi. Реалізувати синтаксичний аналізатор мови програмування Delphi.

2. Скористайтесь інструментальним комплексом LEX/ YACC та реалізуйте синтаксичний аналізатор мови програмування Turbo Pascal 5.xx.

3. Скористайтесь інструментальним комплексом LEX/ YACC та реалізуйте синтаксичний аналізатор мови програмування C.

4. Скористайтесь інструментальним комплексом LEX/ YACC та реалізуйте синтаксичний аналізатор мови програмування C++.

5. Реалізуйте препроцесор мови програмування С++.

6. Реалізуйте препроцесор мови програмування С.

7. Скористатися системою JCC (Java Cоmpiler Compiler). Випишіть граматику Pascal для JCC.

 

Література.

1. Агафонов В.Н. Синтаксический анализ языков программирования. Новосибирск. Из-во НГУ. 1981.

2. Ахо А. Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т1. М. Мир. 1978.

3. Братчиков И.А. Синтаксис языков программирования. М. Наука. 1975.

4. Вайнгартен Ф. Трансляция языков программирования. М. Мир. 1977.

5. Вирт Н. Систематическое программирование. Введение. М.Мир. 1977.

6. Глушков В.М., ЦейтлинГ.Е., Ющенко Е.Л. Алгебра, языки, программи-рование. Киев. Наукова думка. 1974.

7. Ингерман П. Синтаксически ориентированный транслятор. М. Мир. 1969.

8. Лебедев В.Н. Введение в системы программирования. М. Статистика. 1975.

9. Миккиман У., Хорнинг Дж., Уортман Д. Генератор компиляторов. М. Статистика. 1980.

10. Пратт Т. Языки программирования: разработка и реализация. М. Мир. 1979.

11. Чантер Р. Проектирование и конструирование компиляторов. М. финансы и статистика. 1984.

12. Грис Д. Построение компиляторов для ЦЭВМ. М. Мир. 1976.

13. Бек Д. Введение в системное программирование. М. Мир. 1988.

14. Льюис Ф., Стирнз Р., Розенкранц Д. Теоретические основы построения компиляторов. М. Мир. 1979.