- •Міністерство освіти і науки, молоді та спорту України Національний університет “Львівська політехніка”
- •Розробка системних програмних модулів та компонент систем програмування
- •Розробка системних програмних модулів та компонент систем програмування мета курсової роботи
- •Структура та обсяг курсової роботи
- •Вимоги до оформлення
- •Захист роботи
- •Теоретичні відомості
- •1. Лексичний аналіз
- •1.2.1. Особливості побудови лексичного аналізатора засобами скінченного автомату
- •1.2.2. Приклад побудови лексичного аналізатора засобами скінченного автомату
- •1.2. Побудова лексичного аналізатора засобами скінченного автомату
- •1.3. Інші способи Побудови лексичного аналізатора
- •1.3.1. Побудова лексичного аналізатора засобами регулярних виразів
- •1.3.2. Побудова лексичного аналізатора засобами спеціалізованого програмного забезпечення
- •1.3.3. Приклад файлу з правилами виділення лексем для Flex
- •2. Синтаксичний аналіз
- •2.1. Визначення синтаксичних правил мови програмування за допомогою формул Бекуса-Наура
- •2.1.1. Приклад визначення натуральних чисел за допомогою формул бнф
- •2.1.2. Формули Бекуса-Наура для мови Pascal
- •2.2. Способи побудови синтаксичного аналізатора
- •2.2.1. Низхідний аналіз
- •2.2.2. Приклад низхідного граматичного розбору
- •2.2.3. Розробка низхідного синтаксичного аналізатора
- •2.2.3.1. Опис вхідної мови в термінах нотації Бекуса-Наура
- •2.2.3.2. Розробка дерева граматичного розбору
- •2.2.4. Висхідний аналіз
- •2.2.5. Генератори синтаксичних аналізаторів
- •2.2.6. Приклад тексту специфікації для zubr
- •3. Генератор коду
- •3.1. Загальні принципи генерації коду
- •3.2. Способи внутрішнього представлення програм
- •3.2.1. Багатоадресний код з неявно іменованим результатом (тріади)
- •3.2.2. Постфіксна форма запису операцій (зворотний польський запис)
- •3.2.3. Перетворення з інфіксної нотації в зпз
- •3.3. Обчислення виразів на стековій машині
- •3.4. Генерація коду з використанням співпроцесора
- •Література
- •Завдання на курсову роботу
2.2. Способи побудови синтаксичного аналізатора
Синтаксичний аналізатор – це частина компілятора, транслятора чи інтерпретатора, яка перевіряє текст вхідної програми на відповідність синтаксичним правилам мови. При цьому синтаксичний аналізатор вирішує такі задачі:
знаходження і виділення синтаксичних конструкцій в тексті вхідної програми;
встановлює типі і перевіряє коректність кожної синтаксичної конструкції;
представляє синтаксичні конструкції у вигляді проміжного коду, який легко обробляти на стадії генерації коду.
Синтаксичний аналізатор – серце будь-якого компілятора, транслятора чи інтерпретатора. Без нього робота компілятора, транслятора чи інтерпретатора втрачає сенс. В процесі своєї роботи синтаксичний аналізатор приймає на вхід таблицю лексем і генерує проміжний код для подальшого етапу генерації коду, а також генерує файл з синтаксичними помилками.
Синтаксичний аналізатор працює у відповідності до правил контестно-вільної граматики, яка задається, наприклад, формулами Бекуса-Наура. При цьому існує неоднозначна ситуація, хто, лексичний аналізатор чи синтаксичний аналізатор має виділяти деякі конструкції задані правилами контестно-вільної граматики? До таких конструкцій належать ключові слова, константи і ідентифікатори. При цьому відсутні правила, які чітко регламентують сфери відповідальності лексичного і синтаксичного аналізаторів. Тому розподіл обов’язків між ними визначає розробник.
2.2.1. Низхідний аналіз
Розробка низхідного синтаксичного аналізатора для розділеного на лексеми тексту вхідної програми передбачає:
наявність опису граматики мови програмування формулами Бекуса-Наура;
розробка процедур для кожного з правил граматики;
кожна лексема однозначно визначає альтернативу вибору.
Синтаксичний аналіз розділеного на лексеми тексту програми починається з правила граматики найвищого рівня, що визначає кінцеву мету розбору. Тобто з кореня дерева, яке описує, наприклад, що таке програма. Далі аналіз продовжується до листків дерева граматичного розбору. При цьому проводиться аналіз послідовності лексем і здійснюється спроба виділити лексему, яка визначається одним з правил граматики. Після виділення лексеми викликають процедуру для обробки даного правила граматики. Робота процедури полягає в полексемному скануванні таблиці лексем і правила граматики та співставленні послідовності виділених лексем цьому правилу граматики. Якщо при скануванні правила граматики зустрічається нетермінальний символ, то для нього викликається процедура обробки відповідного правила граматики, яке відповідає цьому нетерміналу. Виклики процедур продовжуються доти, поки в правилі не зустрінеться термінальний символ. Оскільки правила граматики можуть містити рекурсію, то передбачається можливість рекурсивного виклику процедур. Процедура повертає істину у випадку вдалого виділення синтаксичної конструкції, або хибу, якщо виділити конструкцію не вдалося. При невдачі необхідно повернутися до початкової лексеми та продовжити пошук правила для виділення наступної конструкції. Таким чином забезпечується механізм вибору вірної альтернативи, якщо правило граматики складається з кількох альтернатив, або в наявності є кілька правил, що відповідають терміналу. Якщо для лексеми, що зустрілася, не підходить жодне з правил граматики, то видається повідомлення про граматичну помилку.