Лексичний аналізатор

Лабораторна робота №2

Мета роботи: вивчити принципи лексичного аналізу на основі використання теорії кінцевих автоматів. Практично застосувати теоретичні знання мови програмування С.

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

Щоб полегшити розпізнавання речень граматики G, варто намалювати діаграму станів. У цій діаграмі кожний нетермінал граматики G представлений вузлом або станом. Крім того, є початковий стан S (передбачається, що граматика не містить нетермінала S). Кожному правилу Q ® Rt відповідає дуга з позначкою t, спрямована від стану R до стану Q. Необхідно використати діаграми станів, щоб розпізнати або розібрати речення х у такий спосіб:

1.Першим поточним станом вважати початковий стан S (Start – початок). Почати із самої лівої літери в ланцюжку х і повторювати крок 2 доти, поки не буде досягнутий правий кінець ланцюжка х.

2.Сканувати наступну літеру х, просунутися по дузі, позначеною цією літерою, переходячи до наступного поточного стану.

Якщо при якомусь повторенні кроку 2 такі дуги не виявляється, то ланцюжок х не є реченням й відбувається зупинка. Якщо досягається кінець х, то х – речення тоді й тільки тоді, коли останній поточний стан є Z.

Тому що нетермінали зустрічаються лише як перші символи правої частини, на першому кроці перший символ речення завжди приводить до нетермінала. На кожному наступному кроці перші два символи UT сентенціальної форми UTt приводять до нетермінала V, при цьому використовується правило V ® Ut. При виконанні цієї редукції ім'я поточного стану – U, а ім'я наступного стану – V.

Малюнок 2.1. – Діаграма станів

Не нашли, что искали? Воспользуйтесь поиском: