Реферат Семантичний аналізатор

Страница 1 из 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 та інші), через робочі станції (наприклад, IBMRS/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)

Під час розробки різних прикладних програм часто виникає завдання

Страница 1 из 3 | Следующая страница

Схожі реферати:

  • Реферат на тему: Сімейства шрифтів в Windows
    1. Сімейства шрифтів в Windows По трьом з розглянутих ознак (ширина штриха, ширина символів і
  • Реферат на тему: Сенсорний монітор
    Сенсорний монітор (>touchscreen) - одна з передових досягнень технологічного прогресу, що дозволило
  • Реферат на тему: Сервери і системи управління базами даних
    Зміст 1. >Сервери.. 2 1.1. Основні поняття серверів та його класифікація. 2 1.2. >Аппаратное
  • Реферат на тему: Сервіс електронних послуг
    >Оглавление   Запровадження Глава 1. Теоретичні основи появи електронну комерцію 1.1 Історія
  • Реферат на тему: Сервісні послуги MS Word
    >Зміст >ВСТУП 1.1 >Автоматична >перевірка >орфографії й >граматики при >введенні 1.2 >Перевірка

Навігація