ЗМІСТ
Місце компілятора у програмному забезпеченні. 3
Основні принципи роботи синтаксичного аналізатора. 6
Дерево розбору. Перетворення дерева розбору в дерево операцій. 8
Автоматизація побудови синтаксичних аналізаторів (програма YACC) 10
Призначення семантичного аналізу. 12
Етапи семантичного аналізу. 13
Ідентифікація лексичних одиниць мов програмування. 16
Список використаних джерел. 19
Для деяких мов є досить багато реалізацій. Наприклад, реалізацій Паскаля, Модуль-2 або Сі для ЕОМ типу IBM PC на ринку десятки.
З іншого боку, постійно зростаюча потреба в нових компіляторах пов'язана з бурхливим розвитком архітектур ЕОМ. Цей розвиток йде по різних напрямах. Удосконалюються старі архітектури як у концептуальному відношенні, так і по окремим, конкретним лініях. Це можна проілюструвати на прикладі мікропроцесора Intel-80X86. Послідовні версії цього мікропроцесора 8086, 80186, 80286, 80386, 80486, 80586 відрізняються не тільки технічними характеристиками, але і, що більш важливо, новими можливостями і, значить, зміною (розширенням) системи команд. Природно, це вимагає нових компіляторів (або модифікації старих). Те ж можна сказати про мікропроцесори Motorola 68010, 68020, 68030, 68040.
У рамках традиційних послідовних машин виникає велика кількість різних напрямів архітектур. Прикладами можуть служити архітектури CISC, RISC. Такі провідні фірми, як Intel, Motorola, Sun, починають переходити на випуск машин з RISC-архітектурою. Природно, для кожної нової системи команд потрібен повний набір нових компіляторів з поширених мов.
Нарешті, бурхливо розвиваються різні паралельні архітектури. Серед них відзначимо векторні, багатопроцесорні, з широким командним словом (варіантом яких є суперскалярні ЕОМ). На ринку вже є десятки типів ЕОМ з паралельною архітектурою, починаючи від супер-ЕОМ (Cray, CDC та інші), через робочі станції (наприклад, IBM RS/6000) і кінчаючи персональними (наприклад, на основі мікропроцесора I-860). Природно, для кожної з машин створюються нові компілятори для багатьох мов програмування. Тут необхідно також відзначити, що нові архітектури вимагають розробки абсолютно нових підходів до створення компіляторів, так що поряд з власне розробкою компіляторів ведеться і велика наукова робота зі створення нових методів трансляції.
На фазі лексичного аналізу вхідна програма, що представляє собою потік літер, розбивається на лексеми - слова у відповідності з визначеннями мови. Основними формалізму, які лежать в основі реалізації лексичних аналізаторів, є кінцеві автомати та регулярні вирази. Лексичний аналізатор може працювати в двох основних режимах: або як підпрограма, що викликається синтаксичним аналізатором для отримання чергової лексеми, або як повний прохід, результатом якого є файл лексем.
У процесі виділення лексем лексичний аналізатор може як самостійно будувати таблиці об'єктів (ідентифікаторів, рядків, чисел і т.д.), так і видавати значення для кожної лексеми при черговому до нього зверненні. У цьому випадку таблиці об'єктів будуються в наступних фазах (наприклад, в процесі синтаксичного аналізу).
На етапі лексичного аналізу виявляються деякі (найпростіші) помилки (неприпустимі символи, неправильний запис чисел, ідентифікаторів та ін.)
Основне завдання синтаксичного аналізу - розбір структури програми. Як правило, під структурою розуміється дерево, відповідне розбору в контекстно-вільної граматики мови. В даний час найчастіше використовується або LL (1)-аналіз (і його варіант - рекурсивний спуск), або LR (1)-аналіз та його варіанти (LR (0), SLR (1), LALR (1) та інші) . Рекурсивний спуск частіше використовується при ручному програмуванні синтаксичного аналізатора, LR (1) - при використанні систем автоматичного побудови синтаксичних аналізаторів.
Результатом синтаксичного аналізу є синтаксичне дерево з посиланнями на таблиці об'єктів. У процесі синтаксичного аналізу також виявляються помилки, пов'язані зі структурою програми.
На етапі контекстного аналізу виявляються залежності між частинами програми, які не можуть бути описані контекстно-вільною синтаксисом. Це в основному зв'язку «опис-використання», зокрема, аналіз типів об'єктів, аналіз областей видимості, відповідність параметрів, мітки та інші. У процесі контекстного аналізу таблиці об'єктів поповнюються інформацією про описах (властивостях) об'єктів.
Основним формалізмом, що використовується при контекстному аналізі, є апарат атрібутних граматик. Результатом контекстного аналізу є атрибутовані дерево програми. Інформація про об'єкти може бути як розосереджена в самому дереві, так і зосереджена в окремих таблицях об'єктів. У процесі контекстного аналізу також можуть бути виявлені помилки, пов'язані з неправильним використанням об'єктів.
Потім програма може бути переведена у внутрішнє представлення. Це робиться для цілей оптимізації та / або зручності генерації коду. Ще однією метою перетворення програми у внутрішнє представлення є бажання мати переносимий компілятор. Тоді тільки остання фаза (генерація коду) є машинно-залежною. В якості внутрішнього подання може використовуватися префіксная або постфіксній запис, орієнтований граф, трійки, четвірки та інші.
Фаз оптимізації може бути декілька. Оптимізації зазвичай ділять на машинно-залежні та машинно-незалежні, локальні і глобальні. Частина машинно-залежною оптимізації виконується на фазі генерації коду. Глобальна оптимізація намагається взяти до уваги структуру всієї програми, локальна - тільки невеликих її фрагментів. Глобальна оптимізація грунтується на глобальному потоковий аналіз, який виконується на графі програми і представляє по суті перетворення цього графа. При цьому можуть враховуватися такі властивості програми, як межпроцедурний аналіз, міжмодульних аналіз, аналіз галузей життя змінних і т.д.
Нарешті, генерація коду - остання фаза трансляції. Результатом її є або асемблерний модуль, або об'єктний (або завантажувальний) модуль. У процесі створення коду можуть виконуватися деякі локальні оптимізації, такі як розподіл регістрів, вибір довгих або коротких переходів, облік вартості команд при виборі конкретної послідовності команд. Для генерації коду розроблені різні методи, такі як таблиці рішень, зіставлення зразків, що включає динамічне програмування, різні синтаксичні методи.
Звичайно, ті чи інші фази транслятора можуть або відсутні зовсім, або об'єднуватися. У найпростішому випадку однопрохідного транслятора немає явної фази генерації проміжного представлення та оптимізації, інші фази об'єднані в одну, причому немає і явно побудованого синтаксичного дерева.
В основі синтаксичного аналізатора лежить распознаватель тексту вхідної програми на основі граматики вхідної мови. Як правило, синтаксичні конструкції мов програмування можуть бути описані за допомогою КС-граматик, рідше зустрічаються мови, які, можуть бути описані за допомогою регулярних граматик. Найчастіше регулярні граматики застосовні до мов асемблера, а мови високого рівня побудовані па основі синтаксису КС-мов. Розпізнавач дає відповідь на питання про те, належить чи ні ланцюжок вхідних символів заданому мови. Однак, як і у випадку лексичного аналізу, завдання синтаксичного розбору не обмежишся лише перевіркою приналежності ланцюжка заданому мови. Необхідно виконати всі перераховані вище завдання, які повинен вирішити синтаксичний аналізатор. У такому варіанті аналізатор вже не є різновидом МП-автомата - його функції можна трактувати ширше. Синтаксичний аналізатор повинен мати якийсь вихідний мову, за допомогою якого він передає наступним фазам компіляції не тільки інформацію про знайдені і розібраних синтаксичних структурах. У такому випадку він вже є перетворювачем з магазинною пам'яттю - МП-перетворювачем. Синтаксичний розбір - це основна частина компілятора на етапі аналізу. Без виконання синтаксичного розбору робота компілятора безглузда, у той час як лексичний розбір в принципі є необов'язковою фазою. Усі завдання з перевірки синтаксису вхідного мови можуть бути вирішені на етапі синтаксичного розбору. Сканер тільки дозволяє позбавити складний за структурою синтаксичний аналізатор від рішення примітивних завдань з виявлення та запам'ятовування лексем вихідної програми.
Виходом лексичного аналізатора є таблиця лексем (або ланцюжок лексем). Ця таблиця утворює вхід синтаксичного аналізатора, який досліджує тільки один компонент кожної лексеми - її тип. Решта інформації про лексемах використовується на більш пізніх фазах компіляції при семантичному аналізі, підготовці до генерації і генерації коду результуючої програми. Синтаксичний аналіз (плі розбір) - це процес, в якому досліджується таблиця лексем і встановлюється, чи задовольняє вона структурним умов, явно сформульованим і визначенні синтаксису мови.
Синтаксичний аналізатор сприймає вихід лексичного аналізатора і розбирає його відповідно до граматикою вхідної мови. Однак у граматиці вхідної мови програмування звичайно не уточнюється, які конструкції слід вважати лексемами. Прикладами конструкцій, які зазвичай розпізнаються під час лексичного аналізу, служать ключові слова, константи і ідентифікатори. Але ці ж конструкції можуть розпізнаватися і синтаксичним аналізатором. На практиці не існує жорсткого правила, що визначає, які конструкції повинні розпізнаватися на лексичному рівні, а які треба залишати синтаксичному аналізатору. Зазвичай це визначає розробник компілятора виходячи з технологічних аспектів програмування, а також синтаксису та семантики вхідної мови Далі розглянуті технічні аспекти, пов'язані з реалізацією синтаксичних аналізаторів для використання результатів їхньої роботи на етан генерації коду. Тим не менш, основу будь-якого синтаксичного аналізатора завжди складає распознаватель, побудований на основі якого-небудь класу КС-граматик. Тому головну роль і те, як функціонує синтаксичний аналізатор і який алгоритм лежить в його основі, відіграють принципи побудови розпізнавачів КС-мов. Без застосування цих принципів неможливо виконати ефективний синтаксичний розбір пропозицій вхідного мови.
Проте ні ланцюжок виводу, ані дерево синтаксичного розбору не є метою роботи компілятора. Дерево висновку містить масу надлишкової інформації, яка для подальшої роботи компілятора не потрібно. Ця інформація включає в себе всі нетермінальні символи, які містяться і вузлах дерева, - після того, як дерево побудовано, вони не несуть ніякого смислового навантаження і не несуть для подальшої роботи інтересу.
Для повного уявлення про тип і структурі знайденої і розібраної синтаксичної конструкції вхідного мови в принципі достатньо знати послідовність номерів правил граматики, застосованих для її побудови. Однак форма подання цієї достатньої інформації може бути різною як залежно від реалізації самого компілятора, так від фази компіляції. Ця форма напивається внутрішнім поданням програми.
У синтаксичному дереві внутрішні вузли (вершини) відповідають операціям, а листя представляють собою операнди. Як правило, листя синтаксичного Дерена зляпати з записами в таблиці ідентифікаторів. Структура синтаксичного дерева відображає синтаксис мови програмування, на якому наш капа вихідна програма.
Синтаксичні дерева можуть бути побудовані компілятором для будь-якої частини вхідної програми. Не завжди синтаксичному дереву повинен відповідати фрагмент коду результуючої програми - наприклад, можлива побудова синтаксичних дерев для декларативної частини мови. У цьому випадку операції, наявні в дереві, не вимагають породження об'єктного коду, але несуть інформацію про дії, які повинен виконати сам компілятор над відповідними елементами. У тому випадку, коли синтаксичному дереву відповідає деяка послідовність операцій, що тягне породження фрагмента об'єктного коду, говорять про дерево операцій.
Дерево операцій можна безпосередньо побудувати з дерева виведення, породженого синтаксичним аналізатором. Для цього достатньо виключити з дерева виведення ланцюжка нетермінальних символів, а також вузли, що не несуть семантичного навантаження при генерації коду. Прикладом таких вузлів можуть бути різні дужки, які змінюють порядок виконання операції і операторів, але після побудови дерева ніякого смислового навантаження не несуть, гак яким не відповідає ніякий об'єктним код.
Те, який вузол в дерен є операцією, а який - операндом, ніяк неможливо визначити з граматики, яка описує синтаксис вхідного мови. Також нізвідки не випливає, яких операціях повинен відповідати об'єктний код в результуючій програмі, а яким - ні. Все це визначається тільки виходячи з семантики - «сенсу» - мови вхідної програми. Тому тільки розробник компілятора може чітко визначити, як при побудові дерева операції повинні відрізнятися операнди і самі операції, а також те, які операції є семантично незначущими для породження об'єктного коду.
Алгоритм перетворення дерева семантичного розбору і дерево операції можна уявити наступним чином.
Крок 1. Якщо у дереві більше не міститься вузлів, помічених нетермінальним символами, то виконання алгоритму завершено; інакше - перейти до кроку 2
Крок. 2. Вибрати крайній лівий вузол Дерена, позначений нетермінальним символом граматики і зробити його поточним. Перейти до кроку 3.
Крок 3. Якщо поточний вузол має тільки один нижележащий вузол, то поточний вузол необхідно видалити з Дерена, а пов'язаний з ним вузол приєднати до вузла вищого рівня (виключити з Дерена ланцюжок) і повернутися до кроку 1; інакше - перейти до кроку 4.
Крок 4. Якщо поточний вузол має нижележащий вузол (лист дерева), позначений термінальним символом, який не несе семантичного навантаження, тоді цей лист потрібно видалити з дерева і повернутися до кроку 3, інакше - перейти до кроку 5.
Крок 5. Якщо поточний вузол має один нижележащий вузол (лист дерева), позначений термінальним символом, що позначає знак операції, а інші вузли позначені як операнди, то лист, позначений знаком операції, треба видалити з дерева, поточний вузол позначити цим знаком операції і перейти до кроку 1; інакше - перейти до кроку 6.
Крок 6. Якщо серед нижчих вузлів для поточного вузла є вузли, помічені нетермінальним символами граматики, то необхідно вибрати крайній лівий серед цих вузлів, зробити його поточним розумом і перейти до кроку 3: інакше - виконання алгоритму завершено.
Місце компілятора у програмному забезпеченні. 3
Основні принципи роботи синтаксичного аналізатора. 6
Дерево розбору. Перетворення дерева розбору в дерево операцій. 8
Автоматизація побудови синтаксичних аналізаторів (програма YACC) 10
Призначення семантичного аналізу. 12
Етапи семантичного аналізу. 13
Ідентифікація лексичних одиниць мов програмування. 16
Список використаних джерел. 19
Місце компілятора у програмному забезпеченні
Компілятори становлять істотну частину програмного забезпечення ЕОМ. Це пов'язано з тим, що мови високого рівня стали основним засобом розробки програм. Тільки дуже незначна частина програмного забезпечення, що вимагає особливої ефективності, програмується за допомогою асемблерів. В даний час поширена досить багато мов програмування. Поряд з традиційними мовами, такими, як Фортран, широке розповсюдження отримали так звані «універсальні» мови (Паскаль, Сі, Модула-2, Ада та інші), а також деякі спеціалізовані (наприклад, мова обробки облікових структур Лісп). Крім того, велике поширення одержали мови, пов'язані з вузькими предметними областями, такі, як вхідні мови пакетів прикладних програм.Для деяких мов є досить багато реалізацій. Наприклад, реалізацій Паскаля, Модуль-2 або Сі для ЕОМ типу IBM PC на ринку десятки.
З іншого боку, постійно зростаюча потреба в нових компіляторах пов'язана з бурхливим розвитком архітектур ЕОМ. Цей розвиток йде по різних напрямах. Удосконалюються старі архітектури як у концептуальному відношенні, так і по окремим, конкретним лініях. Це можна проілюструвати на прикладі мікропроцесора Intel-80X86. Послідовні версії цього мікропроцесора 8086, 80186, 80286, 80386, 80486, 80586 відрізняються не тільки технічними характеристиками, але і, що більш важливо, новими можливостями і, значить, зміною (розширенням) системи команд. Природно, це вимагає нових компіляторів (або модифікації старих). Те ж можна сказати про мікропроцесори Motorola 68010, 68020, 68030, 68040.
У рамках традиційних послідовних машин виникає велика кількість різних напрямів архітектур. Прикладами можуть служити архітектури CISC, RISC. Такі провідні фірми, як Intel, Motorola, Sun, починають переходити на випуск машин з RISC-архітектурою. Природно, для кожної нової системи команд потрібен повний набір нових компіляторів з поширених мов.
Нарешті, бурхливо розвиваються різні паралельні архітектури. Серед них відзначимо векторні, багатопроцесорні, з широким командним словом (варіантом яких є суперскалярні ЕОМ). На ринку вже є десятки типів ЕОМ з паралельною архітектурою, починаючи від супер-ЕОМ (Cray, CDC та інші), через робочі станції (наприклад, IBM RS/6000) і кінчаючи персональними (наприклад, на основі мікропроцесора I-860). Природно, для кожної з машин створюються нові компілятори для багатьох мов програмування. Тут необхідно також відзначити, що нові архітектури вимагають розробки абсолютно нових підходів до створення компіляторів, так що поряд з власне розробкою компіляторів ведеться і велика наукова робота зі створення нових методів трансляції.
На фазі лексичного аналізу вхідна програма, що представляє собою потік літер, розбивається на лексеми - слова у відповідності з визначеннями мови. Основними формалізму, які лежать в основі реалізації лексичних аналізаторів, є кінцеві автомати та регулярні вирази. Лексичний аналізатор може працювати в двох основних режимах: або як підпрограма, що викликається синтаксичним аналізатором для отримання чергової лексеми, або як повний прохід, результатом якого є файл лексем.
У процесі виділення лексем лексичний аналізатор може як самостійно будувати таблиці об'єктів (ідентифікаторів, рядків, чисел і т.д.), так і видавати значення для кожної лексеми при черговому до нього зверненні. У цьому випадку таблиці об'єктів будуються в наступних фазах (наприклад, в процесі синтаксичного аналізу).
На етапі лексичного аналізу виявляються деякі (найпростіші) помилки (неприпустимі символи, неправильний запис чисел, ідентифікаторів та ін.)
Основне завдання синтаксичного аналізу - розбір структури програми. Як правило, під структурою розуміється дерево, відповідне розбору в контекстно-вільної граматики мови. В даний час найчастіше використовується або LL (1)-аналіз (і його варіант - рекурсивний спуск), або LR (1)-аналіз та його варіанти (LR (0), SLR (1), LALR (1) та інші) . Рекурсивний спуск частіше використовується при ручному програмуванні синтаксичного аналізатора, LR (1) - при використанні систем автоматичного побудови синтаксичних аналізаторів.
Результатом синтаксичного аналізу є синтаксичне дерево з посиланнями на таблиці об'єктів. У процесі синтаксичного аналізу також виявляються помилки, пов'язані зі структурою програми.
На етапі контекстного аналізу виявляються залежності між частинами програми, які не можуть бути описані контекстно-вільною синтаксисом. Це в основному зв'язку «опис-використання», зокрема, аналіз типів об'єктів, аналіз областей видимості, відповідність параметрів, мітки та інші. У процесі контекстного аналізу таблиці об'єктів поповнюються інформацією про описах (властивостях) об'єктів.
Основним формалізмом, що використовується при контекстному аналізі, є апарат атрібутних граматик. Результатом контекстного аналізу є атрибутовані дерево програми. Інформація про об'єкти може бути як розосереджена в самому дереві, так і зосереджена в окремих таблицях об'єктів. У процесі контекстного аналізу також можуть бути виявлені помилки, пов'язані з неправильним використанням об'єктів.
Потім програма може бути переведена у внутрішнє представлення. Це робиться для цілей оптимізації та / або зручності генерації коду. Ще однією метою перетворення програми у внутрішнє представлення є бажання мати переносимий компілятор. Тоді тільки остання фаза (генерація коду) є машинно-залежною. В якості внутрішнього подання може використовуватися префіксная або постфіксній запис, орієнтований граф, трійки, четвірки та інші.
Фаз оптимізації може бути декілька. Оптимізації зазвичай ділять на машинно-залежні та машинно-незалежні, локальні і глобальні. Частина машинно-залежною оптимізації виконується на фазі генерації коду. Глобальна оптимізація намагається взяти до уваги структуру всієї програми, локальна - тільки невеликих її фрагментів. Глобальна оптимізація грунтується на глобальному потоковий аналіз, який виконується на графі програми і представляє по суті перетворення цього графа. При цьому можуть враховуватися такі властивості програми, як межпроцедурний аналіз, міжмодульних аналіз, аналіз галузей життя змінних і т.д.
Нарешті, генерація коду - остання фаза трансляції. Результатом її є або асемблерний модуль, або об'єктний (або завантажувальний) модуль. У процесі створення коду можуть виконуватися деякі локальні оптимізації, такі як розподіл регістрів, вибір довгих або коротких переходів, облік вартості команд при виборі конкретної послідовності команд. Для генерації коду розроблені різні методи, такі як таблиці рішень, зіставлення зразків, що включає динамічне програмування, різні синтаксичні методи.
Звичайно, ті чи інші фази транслятора можуть або відсутні зовсім, або об'єднуватися. У найпростішому випадку однопрохідного транслятора немає явної фази генерації проміжного представлення та оптимізації, інші фази об'єднані в одну, причому немає і явно побудованого синтаксичного дерева.
Основні принципи роботи синтаксичного аналізатора
Синтаксичний аналізатор (синтаксичний розбір) - це частина компілятора, яка відповідає за виявлення основних синтаксичних конструкцій вхідної мови. У завдання синтаксичного аналізу входить: знайти і виділити основні синтаксичні конструкції в тексті вхідної програми, встановити тип і перевірити правильність кожної синтаксичної конструкції і, нарешті, представити синтаксичні конструкції у вигляді, зручному для подальшої генерації тексту результуючої програми.В основі синтаксичного аналізатора лежить распознаватель тексту вхідної програми на основі граматики вхідної мови. Як правило, синтаксичні конструкції мов програмування можуть бути описані за допомогою КС-граматик, рідше зустрічаються мови, які, можуть бути описані за допомогою регулярних граматик. Найчастіше регулярні граматики застосовні до мов асемблера, а мови високого рівня побудовані па основі синтаксису КС-мов. Розпізнавач дає відповідь на питання про те, належить чи ні ланцюжок вхідних символів заданому мови. Однак, як і у випадку лексичного аналізу, завдання синтаксичного розбору не обмежишся лише перевіркою приналежності ланцюжка заданому мови. Необхідно виконати всі перераховані вище завдання, які повинен вирішити синтаксичний аналізатор. У такому варіанті аналізатор вже не є різновидом МП-автомата - його функції можна трактувати ширше. Синтаксичний аналізатор повинен мати якийсь вихідний мову, за допомогою якого він передає наступним фазам компіляції не тільки інформацію про знайдені і розібраних синтаксичних структурах. У такому випадку він вже є перетворювачем з магазинною пам'яттю - МП-перетворювачем. Синтаксичний розбір - це основна частина компілятора на етапі аналізу. Без виконання синтаксичного розбору робота компілятора безглузда, у той час як лексичний розбір в принципі є необов'язковою фазою. Усі завдання з перевірки синтаксису вхідного мови можуть бути вирішені на етапі синтаксичного розбору. Сканер тільки дозволяє позбавити складний за структурою синтаксичний аналізатор від рішення примітивних завдань з виявлення та запам'ятовування лексем вихідної програми.
Виходом лексичного аналізатора є таблиця лексем (або ланцюжок лексем). Ця таблиця утворює вхід синтаксичного аналізатора, який досліджує тільки один компонент кожної лексеми - її тип. Решта інформації про лексемах використовується на більш пізніх фазах компіляції при семантичному аналізі, підготовці до генерації і генерації коду результуючої програми. Синтаксичний аналіз (плі розбір) - це процес, в якому досліджується таблиця лексем і встановлюється, чи задовольняє вона структурним умов, явно сформульованим і визначенні синтаксису мови.
Синтаксичний аналізатор сприймає вихід лексичного аналізатора і розбирає його відповідно до граматикою вхідної мови. Однак у граматиці вхідної мови програмування звичайно не уточнюється, які конструкції слід вважати лексемами. Прикладами конструкцій, які зазвичай розпізнаються під час лексичного аналізу, служать ключові слова, константи і ідентифікатори. Але ці ж конструкції можуть розпізнаватися і синтаксичним аналізатором. На практиці не існує жорсткого правила, що визначає, які конструкції повинні розпізнаватися на лексичному рівні, а які треба залишати синтаксичному аналізатору. Зазвичай це визначає розробник компілятора виходячи з технологічних аспектів програмування, а також синтаксису та семантики вхідної мови Далі розглянуті технічні аспекти, пов'язані з реалізацією синтаксичних аналізаторів для використання результатів їхньої роботи на етан генерації коду. Тим не менш, основу будь-якого синтаксичного аналізатора завжди складає распознаватель, побудований на основі якого-небудь класу КС-граматик. Тому головну роль і те, як функціонує синтаксичний аналізатор і який алгоритм лежить в його основі, відіграють принципи побудови розпізнавачів КС-мов. Без застосування цих принципів неможливо виконати ефективний синтаксичний розбір пропозицій вхідного мови.
Дерево розбору. Перетворення дерева розбору в дерево операцій
Результатом роботи розпізнавача КС-граматики вхідної мови є послідовність правил граматики, застосованих для побудови вхідний ланцюжка. За знайденою послідовності, знаючи тип розпізнавача, можна побудувати ланцюжок виводу або дерево виводу. У цьому випадку дерево виведення виступає в якості дерева синтаксичного розбору і являє собою результат роботи синтаксичного аналізатора в компіляторі.Проте ні ланцюжок виводу, ані дерево синтаксичного розбору не є метою роботи компілятора. Дерево висновку містить масу надлишкової інформації, яка для подальшої роботи компілятора не потрібно. Ця інформація включає в себе всі нетермінальні символи, які містяться і вузлах дерева, - після того, як дерево побудовано, вони не несуть ніякого смислового навантаження і не несуть для подальшої роботи інтересу.
Для повного уявлення про тип і структурі знайденої і розібраної синтаксичної конструкції вхідного мови в принципі достатньо знати послідовність номерів правил граматики, застосованих для її побудови. Однак форма подання цієї достатньої інформації може бути різною як залежно від реалізації самого компілятора, так від фази компіляції. Ця форма напивається внутрішнім поданням програми.
У синтаксичному дереві внутрішні вузли (вершини) відповідають операціям, а листя представляють собою операнди. Як правило, листя синтаксичного Дерена зляпати з записами в таблиці ідентифікаторів. Структура синтаксичного дерева відображає синтаксис мови програмування, на якому наш капа вихідна програма.
Синтаксичні дерева можуть бути побудовані компілятором для будь-якої частини вхідної програми. Не завжди синтаксичному дереву повинен відповідати фрагмент коду результуючої програми - наприклад, можлива побудова синтаксичних дерев для декларативної частини мови. У цьому випадку операції, наявні в дереві, не вимагають породження об'єктного коду, але несуть інформацію про дії, які повинен виконати сам компілятор над відповідними елементами. У тому випадку, коли синтаксичному дереву відповідає деяка послідовність операцій, що тягне породження фрагмента об'єктного коду, говорять про дерево операцій.
Дерево операцій можна безпосередньо побудувати з дерева виведення, породженого синтаксичним аналізатором. Для цього достатньо виключити з дерева виведення ланцюжка нетермінальних символів, а також вузли, що не несуть семантичного навантаження при генерації коду. Прикладом таких вузлів можуть бути різні дужки, які змінюють порядок виконання операції і операторів, але після побудови дерева ніякого смислового навантаження не несуть, гак яким не відповідає ніякий об'єктним код.
Те, який вузол в дерен є операцією, а який - операндом, ніяк неможливо визначити з граматики, яка описує синтаксис вхідного мови. Також нізвідки не випливає, яких операціях повинен відповідати об'єктний код в результуючій програмі, а яким - ні. Все це визначається тільки виходячи з семантики - «сенсу» - мови вхідної програми. Тому тільки розробник компілятора може чітко визначити, як при побудові дерева операції повинні відрізнятися операнди і самі операції, а також те, які операції є семантично незначущими для породження об'єктного коду.
Алгоритм перетворення дерева семантичного розбору і дерево операції можна уявити наступним чином.
Крок 1. Якщо у дереві більше не міститься вузлів, помічених нетермінальним символами, то виконання алгоритму завершено; інакше - перейти до кроку 2
Крок. 2. Вибрати крайній лівий вузол Дерена, позначений нетермінальним символом граматики і зробити його поточним. Перейти до кроку 3.
Крок 3. Якщо поточний вузол має тільки один нижележащий вузол, то поточний вузол необхідно видалити з Дерена, а пов'язаний з ним вузол приєднати до вузла вищого рівня (виключити з Дерена ланцюжок) і повернутися до кроку 1; інакше - перейти до кроку 4.
Крок 4. Якщо поточний вузол має нижележащий вузол (лист дерева), позначений термінальним символом, який не несе семантичного навантаження, тоді цей лист потрібно видалити з дерева і повернутися до кроку 3, інакше - перейти до кроку 5.
Крок 5. Якщо поточний вузол має один нижележащий вузол (лист дерева), позначений термінальним символом, що позначає знак операції, а інші вузли позначені як операнди, то лист, позначений знаком операції, треба видалити з дерева, поточний вузол позначити цим знаком операції і перейти до кроку 1; інакше - перейти до кроку 6.
Крок 6. Якщо серед нижчих вузлів для поточного вузла є вузли, помічені нетермінальним символами граматики, то необхідно вибрати крайній лівий серед цих вузлів, зробити його поточним розумом і перейти до кроку 3: інакше - виконання алгоритму завершено.
Автоматизація побудови синтаксичних аналізаторів (програма YACC)
При розробці різних прикладних програм часто виникає завдання синтаксичного розбору деякого вхідного тексту. Звичайно, її можна завжди вирішити, повністю самостійно побудувавши відповідний аналізатор. І хоча завдання виконання синтаксичного розбору зустрічається не так часто, як завдання виконань лексичного розбору, але все-таки і для її рішення були запропоновані відповідні програмні засоби.Автоматизована побудова синтаксичних аналізаторів може бути виконано за допомогою програми YACC. Програма YACC (Yet Another Compiler Compiler) призначена для побудови синтаксичного аналізатора контекстно-вільного мови. Аналізований мова описується за допомогою граматики до пилки, близькому формі Бекуса-Наура (нормальна форма Бекуса-Наура - НФБН). Результатом роботи YACC є вихідний текст програми синтаксичного аналізатора. Аналізатор, який породжується YACC, реалізує висхідний LALR (l) распознаватель.
Як і програма LEX, що служить дли автоматизації побудові лексичних аналізаторів, програма YACC тісно пов'язана з історією операційних систем типу UNIX. Ця програма входить в постачання багатьох версій ОС UNIX або Linux. Тому найчастіше результатом роботи YACC є вихідний текст синтаксичного розпізнавача на мові С, Однак існують версії YACC, що виконуються під управлінням ОС, відмінних від UNIX, і породжують вихідний код на інших мовах програмування (наприклад, Pascal). Принцип роботи YACC схожий на принцип роботи LEX: на вхід надходить файл, що містить опис граматики заданого КС-мови, а на виході отримуємо текст програми синтаксичного розпізнавача, який, природно, можна доповнювати і редагувати, як і будь-яку іншу програму на заданому мовою програмування.
Вихідна граматика для YACC складається з трьох секцій, розділених символом%%, - секції описів, секції правил, у якій описується граматика, і секції програм, вміст якої просто копіюється у вихідний файл. Наприклад, нижче наведено опис найпростішої граматики для YACC, яка відповідає граматиці арифметичних виразів:
% Token a
% Start e
%
e: e '+' m | e '-' m | m
m: m '*' t | m '/' t | t
a: a | '(' e ')':
%%
Секція описів містить інформацію про тому, що ідентифікатор а є лексемою (термінальним символом) гpамматікі, а символ е - її початковим нетермінальним символом.
Граматика, записана звичайним чином - ідентифікатори позначають термінальні та нетермінальні символи; символьні константи типу '+' і '-' вважаються термінальними символами. Символи:, |,; належать до метамови YACC і читаються згідно НФБН «є за визначенням», «або» та «кінець правила» відповідно.
На відміну від LEX, який завжди здатний скорчити лексичний распознаватель, якщо вхідний файл містить правильне регулярний вираз, YACC не завжди може побудувати распознаватель, навіть якщо вхідна мова заданий правильної КС-граматикою. Адже задана граматика може і не належати до класу LALR (l). У цьому випадку YACC видасть повідомлення про помилку (наявності нерозв'язного LALR (t) конфлікту в граматиці) при побудові синтаксичного аналізатора. Тоді користувач повинен або перетворити граматику, або задати YACC деякі додаткові правила, які можуть полегшити побудову аналізатора. Наприклад, YACC дозволяє вказати правила, явно задають пріоритет операцій та порядок їх виконання (зліва направо або справа наліво).
З кожним правилом граматики може бути пов'язана дія, яка буде виконана при згортку по даному правилу. Воно записується у вигляді укладеної у фігурні дужки послідовності операторів мови, на якому породжується вихідний текст програми розпізнавача (зазвичай це мова С). Послідовність має розташовуватися після правій частині відповідного правила. Також YACC дозволяє керувати діями, які будуть виконуватися розпізнавачем в тому випадку, якщо вхідні ланцюжок не належить заданому мови. Розпізнавач має можливість видати повідомлення про помилку, зупинитися або ж продовжити розбір, зробив деякі дії, пов'язані зі спробою локалізувати або усунути помилку у вхідний ланцюжку.
Призначення семантичного аналізу
Практично вся мови програмування, строго кажучи, не є КС-мовами. Тому повний розбір ланцюжків символів вхідного мови компілятор не може виконати в рамках КС-мов за допомогою КС-граматик і МП-аптоматов. Повний распознаватель для більшості мов програмування може бути побудований у рамках КЗ-мов, оскільки всі реальні мови програмування контекстно-залежні.Отже, повний распознаватель для мови програмування можна побудувати на основі розпізнавача КЗ-мови. Однак відомо, що такий распознаватель має експоненційну залежність необхідних для виконання розбору ланцюжка обчислювальних ресурсів від довжини вхідний ланцюжка. Компілятор, побудований на основі такого розпізнавача, буде неефективним з точки зору або швидкості роботи, або обсягу необхідної пам'яті. Тому такі компілятори практично не використовуються, а все реально існуючі компілятори на етапі розбору вхідних ланцюжків перевіряють тільки синтаксичні конструкції вхідного мови, не враховуючи його семантику.
З метою підвищити ефективність компіляторів розбір ланцюжків вхідного мови виконується в два етапи: перший - синтаксичний розбір на основі розпізнавача одного з відомих класів КС-мов, другий - семантичний аналіз вхідний ланцюжка.
Для перевірки семантичної правильності вхідної програми необхідно мати всю інформацію про знайдені лексичних одиницях мови. Ця інформація міститься в таблицю лексем на основі конструкцій, знайдених синтаксичним розпізнавачем. Прикладами таких конструкціями є блоки опису констант і ідентифікаторів (якщо вони передбачені семантикою мови) пли оператори, де той чи інший ідентифікатор зустрічається вперше (якщо опис відбувається за фактом першого використання). Тому повний семантичний аналіз вхідної програми може бути проведений тільки після повного завершення її синтаксичного розбору.
Таким чином, вхідними даними для семантичного аналізу служать:
· Таблиця ідентифікаторів;
· Результати розбору синтаксичних конструкцій вхідної мови.
Результати виконання синтаксичного розбору можуть бути представлені в одній з форм внутрішнього представлення програми на компіляторі. Як правило, на етапі семантичного аналізу використовуються різні варіанти дерев синтаксичного розбору, оскільки семантичний аналізатор цікавить насамперед структура вхідної програми.
Семантичний аналіз звичайно виконується на двох етапах компіляції: на етапі синтаксичного розбору і на початку етапу підготовки до генерації коду. У першому випадку кожен раз по завершенні розпізнавання певної синтаксичної конструкції вхідного мови виконується її семантична перевірка на основі наявних в таблиці ідентифікаторів даних (такими конструкціями, як правило, є процедури, функції і блоки операторів вхідної мови). У другому випадку, після завершення всієї фази синтаксичного розбору, виконується повний семантичним аналіз програми на підставі даних в таблиці ідентифікаторів (сюди потрапляє, наприклад, пошук неописаних ідентифікаторів). Іноді семантичний аналіз виділяють в окремий етап (фазу) компіляції.
У кожному компіляторі зазвичай присутні обидва варіанти семантичного аналізатора.
Етапи семантичного аналізу
Семантичний аналізатор виконує такі основні дії:· Перевірка дотримання у вхідний програмі семантичних угод вхідної мови;
· Доповнення внутрішнього представлення програми на компіляторі операторами і діями, неявно передбаченими семантикою вхідної мови;
· Перевірка елементарних семантичних (значеннєвих) норм мов програмування, безпосередньо не пов'язаних з вхідним мовою.
Перевірка дотримання у вхідний програмі семантичних угод вхідного мови полягає в зіставленні вхідних ланцюжків програми з вимогами семантики вхідної мови програмування. Кожна мова програмування має чітко задані й специфіковані семантичні угоди, які не можуть бути перевірені на етапі синтаксичного розбору. Саме їх у першу чергу перевіряє семантичний аналізатор.
Прикладами таких угоді є такі вимоги:
· Кожна мітка, на яку є посилання, повинна один раз бути присутнім у програмі;
· Кожен ідентифікатор повинен бути описаний один раз, і жоден ідентифікатор не може бути описаний більше одного разу (з урахуванням блокової структури описів);
· Всі операнди у виразах і операціях повинні мати типи, допустимі для даного виразу або операцій;
· Типи змінних у виразах повинні бути узгоджені між собою;
· При виклику процедур і функцій число і типи фактичних параметрів повинні бути узгоджені з числом і типами формальних параметрів.
Наприклад, якщо оператор мови Pascal має вигляд
a: = b + c:
то з точки зору синтаксичного розбору це буде абсолютно правильний оператор. Однак, ми не можемо сказати, чи є цей оператор правильним з точки зору вхідної мови (Pasca]), поки не перевіримо семантичні вимоги для всіх вхідних у нього лексичних елементів. Такими елементами тут є ідентифікатори a, b та с. Не знаючи, що вони собою являють, ми не можемо не тільки остаточно стверджувати правильність наведеного вище оператора, але і зрозуміти ого сенс. Фактично необхідно знати опис цих ідентифікаторів.
У тому випадку, якщо хоча б один з них не описаний, має місць явна помилка. Якщо це числові змінні і константи, то ми маємо справу з оператором складання, якщо ж це рядкові змінні і константи - з оператором конкатенації рядків. Крім того, ідентифікатор а, наприклад, у жодному разі не може бути константою - інакше порушена семантика оператора присвоювання. Також неможливо, щоб одні з ідентифікаторів були числами, а інші рядками, або, скажімо, ідентифікаторами масивів або структур - таке поєднання аргументів для оператора складання неприпустимо.
Слід також зазначити, що від семантичних угод залежить не тільки правильність оператора, але й його зміст. Дійсно, операції алгебраїчного додавання і конкатенації рядків мають різний зміст, хоча і позначаються у розглянутому прикладі одним знаком "+". Отже від семантичного аналізатора залежить також і код результуючої програми.
Якщо будь-яка з семантичних вимог вхідного мови не виконується, то компілятор видає повідомлення про помилку і процес компіляції на цьому, як правило, припиняється.
Доповнення внутрішнього представлення програми операторами і діями, неявно передбаченими семантикою вхідної мови, пов'язані з перетворенням типів операндів у виразах і при передачі параметрів у процедури і функції.
Якщо повернутися до розглянутого вище елементарного оператору мови Pascal:
a: = b + c:
то можна відзначити, що тут виконуються дві операції: одна операція додавання (або конкатенації, в залежності від типів операндів) і одна операція присвоєння результату. Відповідним чином має бути породжений і код результуючої програми.
Однак не все так очевидно просто, припустимо, що десь перед розглянутим оператором ми маємо опис його операндів у вигляді:
Var
а: real;
b: integer;
c: double;
з цього опису виходить, що а - речова мінлива мови Pascal, b - цілочисельна мінлива, с - речова змінна з подвійною точністю. Тоді сенс розглянутого оператора з точки зору вхідної програми істотно змінюється, оскільки в мові Pascal не можна безпосередньо виконувати операції над операндами різних типів. Існують правила перетворення типів, прийняті для даної мови. Хто виконує ці перетворення?
Це може зробити розробник програми - але тоді перетворення типів у явному вигляді будуть присутні в тексті вхідної програми (у розглянутому прикладі це не так). В іншому випадку це робить код, породжуваний компілятором, коли перетворення типів у явному вигляді в тексті програми не присутні, але неявно передбачені семантичними угодами мови. Для цього у складі бібліотек функції, доступних компілятору, повинні бути функції перетворення типів Виклики цих функції як раз і будуть вбудовані в текст результуючої програми для задоволення семантичних угоді про перетворення типів у вхідному мовою, хоча в тексті, в явному вигляді вони не присутні. Щоб це сталося, ці функції повинні бути вбудовані і у внутрішнє представлення програми в компіляторі. За це також відповідає семантичний аналізатор.
З урахуванням запропонованих типів даних, у розглянутому приклад будуть не дві, а чотири операції: перетворення цілочисельний змінної b у формат дійсних чисел з подвійною точністю; складання двох дійсних чисел подвійною точністю; перетворення результату в дійсне число з одинарною точністю; присвоєння результату змінної c. Кількість операцій зросла вдвічі, причому додалися нетривіальні функції перетворення типів. Перетворення типів - его тільки один варіант операцій, неявно додаються компілятором в код програми на основі семантичних угоді. Іншим прикладом такого роду операцій можуть служити операції обчислення адреси, коли відбувається звертання до елементів складних структур даних. Існують й інші варіанти такого роду операцій.
Таким чином, і тут дії, що їх семантичним аналізатором, істотним чином впливають на породжуваний компілятором код результуючої програми.
Перевірка елементарних смислових норм мов програмування, безпосередньо не знизилася з вхідним мовою, - це сервісна функція, яку надають більшість сучасних компіляторів. Ця функція забезпечує перевірку компілятором деяких угод, застосовних до більшості сучасних мов програмування, виконання яких пов'язано зі змістом як всієї вхідної програми і в цілому, так і окремих її фрагментів.
Ідентифікація лексичних одиниць мов програмування
Ідентифікація змінних, типів, процедур, функцій та інших лексичних одиниць мов програмування - це встановлення однозначної відповідності між цими об'єктами і їх іменами в тексті вихідної програми. Ідентифікація лексичних одиниць мови найчастіше виконується на етапі семантичного аналізу.Як правило, більшість мов програмування вимагають, щоб у вихідній програмі імена лексичних одиниць не збігалися як між собою, так і з ключовими словами синтаксичних конструкцій мови. Проте, найчастіше цього буває недостатньо, щоб встановити однозначне співвідношення між лексичними одиницями та їх іменами, оскільки існують додаткові смислові обмеження, що накладаються мовою на вживання ці імен.
Наприклад локальні змінні в більшості мов програмування маю область видимості, яка обмежує вживання імені змінної рамками того блоку вихідної програми, де ця змінна описана. Це означає, що з одного боку, така змінна не може бути використана поза межами своєї області видимості. З іншого боку, ім'я змінної може бути не унікальним, оскільки у двох різних областях видимості допускається існування двох різних змінних з однаковими іменами. Повний перелік таких обмежень залежить від семантики конкретної мови програмування. Всі вони чітко задані в описі мови і не можуть допускати неоднозначності в тлумаченні, але не можуть бути повністю визначені на етапі лексичного розбору, а тому вимагають від компілятора додаткових дій на етапах синтаксичного та семантичного аналізу. Загальна спрямованість цих дій така, щоб дати кожній лексичної одиниці мови унікальне ім'я в межах всієї вихідної програми і потім використовувати це ім'я при синтезі результуючої програми.
Можна дати приблизний перелік дій компіляторів для ідентифікації змінних, констант, функцій, процедур та інших лексичних одиниць мови:
· Імена локальних змінних доповнюються іменами тих блоків (функцій, процедур), в яких ці змінні описані;
· Імена внутрішніх змінних і функцій модулів вихідної програми доповнюються ім'ям самих модулів, причому це стосується тільки внутрішніх імен і не повинно відбуватися, якщо змінна або функція доступна ззовні модуля;
· Імена процедур і функцій, що належать об'єктам (класами), в об'єктно-орієнтованих мовах програмування доповнюються найменуванням типу об'єкта (класу), якому вони належать;
· Імена процедур і функцій модифікуються залежно від типів їх формальних аргументів.
Звичайно, це далеко не повний перелік можливих дій компілятора, кожна реалізація компілятора може припускати свої набір дій. Те, які з них будуть використовуватися і як вони будуть реалізовані на практиці, залежить від мови початкової програми і розробників компілятора.
Як правило, унікальні імені, які компілятор присвоює лексичним одиницям мови, використовуються тільки у внутрішньому представленні вихідної програми компілятором, і людина, що створила вихідну програму, не стикається з ними. Але вони можуть знадобитися користувачеві в деяких випадках - наприклад, при налагодженні програми, при породженні тексту результуючої програми на асемблері або при використанні бібліотеки, створеної версією компілятора для однієї мови програмування і іншою мовою (або навіть просто в іншій версії компілятора). Тоді користувач повинен знати, за якими правилами компілятор породжує унікальні імена для лексичних одиниць вихідної програми.
У багатьох сучасних компіляторах (і оброблюваних ними вхідних мовах) передбачені спеціальні настройки і ключові слова, які дозволяють відключити процес породження компілятором унікальних імен для лексичних одиниць мови. Ці слова враховані в спеціальних синтаксичних конструкціях мови (як приплив, це конструкції, що містять слона export плі external). Якщо користувач використовує ці кошти, то компілятор не застосовує механізм породження унікальних імен для зазначених лексичних одиниць. У цьому випадку розробник програми сам відповідає за унікальність імені даної лексичної одиниці в межах всієї вихідної програми або навіть в межах всього проекту, Якщо вимога унікальності не буде виконуватися, можуть виникнути синтаксичні або семантичні помилки па стадії компіляції або ж інші помилки на більш пізніх етапах розробки програмного забезпечення. Оскільки найбільш широко використовуваними лексичними одиницями в різних мовах програмування є, як правило, імена процедур і функцій, то це питання, перш за все, стосується саме їх.
Список використаних джерел
1. Серебряков - Мови програмування: http://infonet.cherepovets.ru/citforum/programming/theory/serebryakov2. Вільна енциклопедія - Вікіпедія http://ru.wikipedia.org/wiki/% D0% A2% D1% 80% D0% B0% D0% BD% D1% 81% D0% BB% D1% 8F% D1% 82% D0 % BE% D1% 80