Розробка в структурно логічної схеми мікропроцесора

Розробка в структурно логічної схеми МП

ОП64

ШД

АЛП

У схемі мікропроцесора повинні бути включені всі пристрої, необхідні для прийому з пам'яті, зберігання, і виконання команд заданими згідно варіанту режиму адресації. Відповідно до вимоги повноти мікропроцесора, зазвичай включають наступні пристрої.
Адресна шина
Адресна шина повинна мати розрядність, достатню для передачі адреси заданої довжини.
Шина даних. Розрядність шини даних зазвичай збігаються з довжиною байт. У випадки, коли всі команди мають однакову довжину, вона збігається з основним словом.
Програмний лічильник - містить адресу поточної виконуваної програми. Автоматично збільшує довжину команд, при переході на наступну.
Регістр команд (IR) - призначений для прийому з пам'яті і зберіганні коду команд.
Дешифратор-визначає що це за команда.
Блок управління і синхронізація - виконує управлінням мікропроцесором.
DAK - регістр даних і адреси.
Рони - регістри загального призначення.

Режими адресації

Адреса виконавчий (адреса комірки пам'яті або регістра) з яким працює команда, можна вказувати різними способами, керуюся такими міркуваннями.
Виконання команд з більш коротким адресою.
Забезпечення простого доступу до можливо більшого об'єму пам'яті.
Можливість зміни вмісту адресної частини без зміни команди.
Забезпечення більш швидкої адресації.
Використання більш простого методу адресації під уникнення помилок.
Пряма адресація ADD B - в прямій адресації адреса виконавчий є частиною команди. Довжина команди залежить від адреси.
Пряма реєстрова - місце адреси виконавчого зберігається номер регістра.
Непряма адресація - адреса виконавчий знаходиться за адресою, вказаною в команді.
Побічно реєстрова - адреса виконавчий знаходиться за адресою регістру.
Безпосередня адресація - оброблювані дані є частиною команди.
Відносна - Адреса виконавчий формується шляхом складання програмного лічильника та зміщенням, яке знаходиться в команді.
Індексна адресація - адреса виконавчий утворюється шляхом додавання індексного регістра з адресою, яка перебуває в команді.
Базова адресація - використовується для організації переміщення програми в пам'яті. Для цього пишеться псевдо команда, яка закріплює один з регістрів у якості базового. У цей регістр записується адреса завантаження і всі виконавчі адреси записуються.
Адресація з авто збільшенням або авто зменшенням - застосовується для організації циклів. Перед виконанням команди або після, вміст регістрів, в якому знаходився операнд збільшується або зменшується на одиницю.
Стекова - адресою даних є вміст покажчика стеків.
Система команд мікро процесора.
Команди мікропроцесора в пам'яті займають від 1 байта до максимальної длена.
1 байт команди містить код операції. У деяких код операцій може розміщуватися і в другому байті. Вимога до системи команд це
функціональна повнота - система команд повинна надавати максимально зручні засоби для програмування, за складеними алгоритму, в умовах обмежених ресурсів.
Мінімальність - кількість довжина команд повинна бути мінімальною.
Система команд мікропроцесора звичайно містить такі операції:
Операції пересилання забезпечую передачу операнда джерела до операнду приймача, без змістовного їх перетворювача.
Арифметичні операції - додавання віднімання, множення, ділення.
Логічні - і, або, не.
Зрушення.
Умовні переходи.
Зміна вмісту регістра коду умов (прапорці).
Команди вода, виводу і зупину.
Проектування системи команд значною мірою залежить від заданих режимах адресації.
При виборі формату команд слід враховувати такі особливості:

3 байти

1 байт

1 У коротких командах часто використовується змінна довжина коду операцій. Це дозволяє щільніше упаковувати інформацію і скоротити число форматів команд та їх довжину.

1 байт

3 байти

Максимальна кількість команд 256.
У команда з індексного адресацією потрібно забезпечити якомога більшу величину зсуву, що не перевищує оперативну пам'ять


RI 0	00
RI 1	01
RI 2	10

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

Опису мови Асемблера (28_09_07)

Асемблер - машинно-орієнтована мова, оператори які транслюються один до одного, або один до нуля (псевдо операції, передають інформацію завантажувачу, лінковщіку). Асемблер найбільш ефективно використовують ресурси ЕОМ. У загальним вигляді оператори асемблера виглядають так: мітка, код операції, [операнди], [коментар], або [ознака коментаря].
Існують різні типи асемблера:
Резидентний асемблер - програма, яка зберігається в ПЗУ і до неї є постійна доступ. Крос асемблер - виконується на ЕОМ загального призначення, і написана на мові програмування цього ЕОМ. Переваги - розробка програми передує технічної реалізації. Використовується потужна програмне забезпечення ЕМХ. Виразність мови та діагностика, забезпечується переваги машини виразності мови та діагностики.
Існую абсолютні і переміщувані асемблери. В абсолютному асемблері адреса завантаження визначається псевдокоманди. Адреса завантаження відомий під час збирання, тому при побудові адресних константи команд виконується в абсолютних адресах. У переміщуваний асемблері можливість визначити адресу завантаження відбувається не вчасно ассемблирования а під час запису програми в пам'ять. Для цього відносний адреси адресних констант команд збільшується на адресу завантаження.
Однопрохідні і двопрохідний - формуванню об'єктної програми за один перегляд перешкоджає посилання в перед, в командах передачі управління. Асемблер не може відразу визначити адресу переходу. Існує два варіанти побудови однопросмотрових асемблерів:
Невизначена мітка записується в таблицю міток. У міру знаходження міток та визначення адреси цієї мітки, в зарезервовані місця записуються адресу. Посилань на одну і ту ж мітку може бути багато.
Асемблер будує додаткову таблицю переходів. Всі команди звернення в перед здійснюють передачу побічно, через цю таблицю.
Перевагою однопросмотрового асемблера є виграш у швидкості ассемблирования. Тим не менше більшість асемблерів сучасних ЕОМ двухпросмотровие. Метою першого перегляду є визначення адреси для кожної команди в програмі і формування символічних імен або міток. Метою другого проходу є генерація машини команди констант, обробка псевдо команд а так само роздруківка лістингу.

Основні функції Асемблера

Синтаксичний аналіз вихідного тексту програми.
Розподілу пам'яті (призначення відносних адрес) для команд, констант, змінних і літералів.
Трансляції вихідної програми в об'єктний код.
Формування інформації для завантажувача, лінковщіка.
Формування лістингу програми.
Основні бази даних для формування перегляду.
Файл вихідного тексту
Значення програмного лічильника.
Таблиця машинних операцій. Довжина команди. Формат команди.
Таблиця псевдооперацій.
Таблиця імен (міток).
Таблиця літералів.
Таблиця зовнішніх імен.
Таблиця входів.
Лекція (5_10_07)
Машино залежні частини асемблера:
Формати даних та формати команд
Режими адресації або способи адресації
Переміщення.
Машино не залежні характеристики асемблера. Синтаксис мови досить простий. При написанні команд використовуються прийоми які полегшують написання програми.
Непряма адресація - для реалізації непрямої адресації використовується прийом, який називається префікс.
Безпосередньої операнда
Для літералів - дозволяє відмовитися від використання окремої пропозиції для визначення константи і відповідно його ім'я. Таблиця літералів записується після тіла програми.
Засоби визначення імен і завдання значення.
Вираз. У більшості асемблерів на ряду з поодинокими термінами дозволяють використовувати вирази. Кожне таке вираз обчислюється асемблером під час трансляції, а за тим отримане значення використовується у вигляді адреси або безпосереднього операнда.
Програмні блоки - багато асемблери надають гнучкі засоби обробки вихідних програм. Вони дозволяють розташовувати згенеровані машинні командні дані в порядку відмінного від вихідного. Створювати незалежні частини керуючі секції. Кожна з цих частин зберігає свою індивідуальність і обробляється завантажувачем окремо.
Об'єктний код
У заключній фазі своїй роботі, асемблер повинен записати отриманий об'єктний код на деякий пристрою виводу. Після цього об'єктна програма повинна поміщається в оперативну пам'ять. Для реалізації цього використовуються 3 основні процеси:
Завантаження - забезпечує розміщення в оперативній пам'яті для виконання. Це системна програма і традиційна система.
Переміщення - дозволяє модифікувати об'єктну програму так, що вона може завантажуватися з адреси, відмінного від початкового.
Зв'язування - забезпечує об'єднання двох і більше роздільно трансльовані об'єктних програм і надає інформацію необхідну для розв'язання посилань між ними. Для того щоб програма була переміщувана і ми могли вирішити всі зовнішні посилання, в об'єктній програмі повинна бути закладена інформація.
Формат об'єктної програми.
Запис заголовок.
- / / - 2-7 - ім'я програми
- / / - 8-13 - початку адреси програми
- / / - 14-19 - довжина програми в байтах
Тіло. Ознака Т.
- / / - 2-7 - Початковий адреса в цього запису.
- / / - 8-9 - довжина поточного запису
- / / - 10-69 - об'єктний код
Запис - кінець
- / / - 2-7 - адресу першої виконуваної команди
Якщо більшість команд асемблера використовую відносну та безпосередню адресацію, то для реалізації переміщення програм модифікації вимагає окремі програми асемблера. Запис у модифікатор може бути використаним як для переміщення так і для зв'язок. Він складається з:
Ознака М
- / / - 2-7 - початковий адресу модифікованого програмного об'єкта
- / / - 8-9 - довжина модифікованого поля в полубайта
- / / - 10 - ознака модифікації
- / / - 11 - 16 - зовнішнє ім'я
Модифікатор виділяє всі адреси, які треба перерахувати з урахуванням адреси завантаження. Однак така схема годиться не для всіх машин, якщо більшість команд використовують пряму адресацію і фіксований командний формат, отже повинні модифікуватися для переміщення що зажадає великого збільшення обсягу пам'яті об'єктної програми.

Лекція (12_10_07)

2 варіант - використання маски. З кожним словом програми об'єктного коду, зв'язується в розряд переміщення. Ці розряди утворю разом маску, яка записується відразу після довжини тіла програми в кожному записі.
3 спосіб організації переміщення. У багатьох ЕОМ переміщення організується апаратним чином. Для цього використовується базова адресація - базовий адреса + зсув.
4 варіант. Будь-який адресу вираховується відносно.
Керуюча секція - частина програми, після ассемблирования зберігає свою індивідуальність, і може переміщатися і завантажуватися незалежно від інших. Так як ці частини логічно пов'язані і не можуть існувати окремо, повинен бути реалізований механізм скріплення і об'єднання. Найчастіше керуючої секцією виступає процедура функція. Команди однієї керуючої секції повинні мати можливість посилатися на команди і на області даних, розташованих в інших секціях. Посилання не можна обробляти звичайним чином, оскільки УС завантажується і переміщається незалежно дуг від одного і асемблер нічого не відомо. Для кожної зовнішньої посиланням асемблер генерує інформацію, яка дає можливість виконати необхідну зв'язування програми. Імена визначені в однієї керуючої секції можуть безпосередньо використовуватися в іншій секції. Для того щоб завантажувач зміг їх обробити вони повинні бути описані як зовнішні імена.
Запис визначення - Стовпець 1 D
- / / - 2-7 - ідентифікатор зовнішнього імені, визначеної даної керуючої секцією.
- / / - 8-13 - відносний адресу імені
Запис посилання - стовпець 1 R
- / / - 2-7 - ідентифікатор зовнішнього імені
Приклад ілюструє керуючі секції і зв'язують програми.
Copy start 0
Варіанти побудови завантажників -
Абсолютний завантажувач - записує об'єктну програму в оперативну пам'ять і передає управління на адресу її виконання.
Зв'язуючий завантажувач - важливою інформацією для зв'язує завантажувача є об'єктні файли, які пов'язані один з одним за допомогою зовнішніх посилань. Зв'язування не може бути виконано поки не будуть призначені адреси для всіх необхідних імен. Тому що зв'язує завантажувач виконує два перегляду вхідного перегляду. Під час першого призначаються адреси всіх зовнішніх посилань. Під час другого виконується завантаження переміщення зв'язування.

Лекція (19_10_07)

Завантажувачі, які використовують редактор зв'язку.
Редактор зв'язку використовується для мов високого рівня.
Динамічні завантажувачі
Зв'язування відкладається до моменту виконання програми. У цьому випадки завантаження і зв'язування програм здійснюється тоді, коли відбувається перше звернення. Використовується в інтерактивних діалогових системах.
Розкручує завантажувач.
Застосовується метод рекурсії, коли одна програма виконує свою функцію і завантажує наступну.
Макропроцесор
У міру програмування мовою асемблер, деякі частини програм доводиться повторювати і переписувати знову і знову. Одним із прийомів запису часто використовуваних груп пропозицій використовуваної мови, є застосування макро визначень і макро інструкцій. Програміст записує компактний варіант своєї програми, а макропроцесор формує остаточний варіант тексту. Процес заміни макро команд відповідними групами пропозицій здійснюваним макро процесором називається макро розширенням, або макро генерацією.
Основні функції макропроцесу.
Основною функцією - заміна одних груп пропозицій або символів на інших. Питання трансляції їх в коди машини не мають безпосереднього відношення до процесу макро генерації. Тому механізм роботи макропроцесора практично не пов'язаний зі структурою машин. Будь-який процесор макро команд має вирішувати такі 4 основні завдання.
Розпізнавання макро визначення. Завдання ускладнюється якщо в нутрії можуть бути використані інші макро визначення.
Запам'ятовування макро визначення.
Розпізнати макро виклики, представлені у форматі мнемонічного коду операції. Це передбачає, що імена команд обробляються як один з типів коду операцій.
Виконати розширення макро команд, постановку, і підстановку фактичних параметрів.
Після обробки макро визначень розширений файл може бути використаний у якості вхідного файлу для асемблера.

Варіанти побудови Макропорцесори

Однопросмотровий
Для того що б реалізувати однопросмотровий, макро визначення повинні знаходиться до макро команд. На першому етапі відбувається розпізнавання макро процесу і запам'ятовування. Другий прохід це вже макро генерація.
Таблиця фактичних параметрів.
Макро процесори загального призначення.
Вони не залежать від конкретної мови програмування.
Переваги: можуть бути використані для різних мов. Мінімум часу для вивчення.
Розкручують Макропорцесори.
Допускає хибність, і вимагає стільки проходів, скільки необхідно для того щоб отримати вихідний текст.

Процес компіляції.
Мови високого рівня з'явилися в кінці 50 початок 60 років, такі як Фортран, Алгол. Пізніше Паскаль, Сі. Програма яка транслює будь-яку програму написану мовою високого рівня в еквівалентну програму іншою мовою (зазвичай це машинний код) називають компілятором. Два компілятора, що реалізують один і той же мова, на одній і тій же машині, можуть відрізняться хоча б тому, що розробники переслідували різні цілі при їх створенні.
Мета:
1. отримання ефективного об'єктного коду програми.
2. Мінімізація часу компілювання програми.
3. Розробка невеликих об'єктних програм.
4. Розробка компілятора мінімального розміру.
5. Створення компілятора володіє широкими можливостями виявлення та виправлення помилки.
6. Забезпечення надійності компілятора.
Існує й інший підхід, який називається інтерпретація, представником є Basic. Інтерпретація полягає в тому, що замість трансляції в машинний код і наступне виконання програма спочатку по операторно транслюється в проміжний мова, а потім транслюється і виконується кожен оператор проміжної мови.
Передати повідомлення про помилки користувачеві, часто буває легше в термінах вихідної програми.
Версія програми на мові не рідко виявляється компактніші, ніж машинний код, що видається компілятор.
Зміна частини програми не вимагає перекомпіляції всієї програми.
Недоліки:
Повільність роботи.
Загальна схема обробки мов високого рівня

Скелет вихідна програма

Предпроцессор
макропроцесор

компілятор

Цільова асемблер
програма

Редактор зв'язків

транслятор

Переміщуваний машинний код

Абсолютний машинний код

Загальна структура компілятора
Вихідна програма ЯВУ

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

Стандартна форма
Таблиці символів

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

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

Оптимізація коду

генерація коду та розподілу пам'яті

Лекція (1_11_07)

Лексичний аналізатор - представляє собою першу фазу компілятора. Його основне завдання полягає в читанні нових символів і видачі послідовності лексем. Заміна об'єктів змінної довжини символами фіксованої довжини. З теоретичної точки зору лексичний аналізатор не є обов'язковою частиною компілятора. Усі його функції можуть виконуватися на етапі синтаксичного розбору, оскільки повністю регламентовані синтаксисом вхідної мови. Проте існує декілька причин по яким складу практично всіх компіляторів включає лексичний аналіз.
Застосування лексичного аналізатора спрощує роботу з текстом програми, за рахунок видалення коментарів і прогалин, тобто символів не несуть смислового навантаження.
Збільшення ефективності компілятора. Оскільки на читання вихідної програми і розбір її на лексеми витрачається багато часу, спеціальні технології утилізації та обробки лексем можуть істотно підвищити продуктивність компілятора.
Збільшення переносимості компілятора.
Лексема - мінімальна одиниця мови. Вихідна програма на МВР є ланцюжком утворюючи послідовність всіх листів програми. Мова паскаль використовує алфавіт, який використовує підмножина наборів символу таблиці кодів.
Спеціальні символи.
Керуючі символи. Деякі символи розширеного набору кодів включають букви і кирилиці. Вони використовуються в рядках, але не застосовуються для побудови лексем. Серед допустимих для всіх мов символів роздільників, завдяки пропозиції вихідної програми поділяються на окремі слова. У паскалі можна виділити кілька категорій лексем:

Мінімальна значуща одиниця тексту програм

Ідентифікатори - послідовність літер і цифр. Стандартними, перед певними ідентифікаторами в мові паскаль є: імена вбудованих процедур і функцій.
Теги - числові і символьні і відокремлюються двокрапкою.
Числа. Число розрізняють ціле - десяткове, речовий,
Строки - послідовність символів з розширеного набору кодів, укладена в лапках.
Синтаксичний аналізатор
Перевіряє чи є програма граматично правильного, інакше кажучи задовольняє вона законам мови програмування, на якому вона написана. Синтаксис мови зачіпає тільки форму мови. Якщо пропозиції задовольняє нормальним правилам, воно не залежно від його значення розглядається як синтаксично правильне.
Формальне визначення мов програмування
Під формальним визначенням мови програмування ми розуміє повний опис синтаксису та семантики. Бажано мати такий опис.
Відомості про мову міститься в підручниках і посібниках. Часто ці описи не однозначні і не висвітлюють всіх тонкощів.
Формальний опис треба для розробників компілятора. Синтаксичне визначення може задаватися формальними чи не формальними способами.
Метамова (металінгвістичних символи)
Формальне опису мови.
Метамова
Використовую синтаксичні діаграми
Дужкові конструкції
За допомогою множин
Метамова
Опис будь-якого формального мови описується на мето мовою. Він може описувати синтез, або семантику (сенс конструкцій), або всі разом. Для мов програмування найбільш поширеним методом мовою для опис синтезу служить нормальна форма БНФ. Перелічимо основні поняття і конструкції цієї мови:
Термінальний символ - символ, що складається тільки з букв алфавіту описуваного мови. Одна або декілька літер.
Чи не термінальний символ - сформульована російською або іншою мовою поняття описуваного мови програмування. Металінгвістичних змінні. Для того щоб розкрити поняття мови означає не термінальними символами, використовуються правила підстановки. U і u - довільні кінцеві послідовні ланцюжки термінальних символів. Знак:: = є за визначенням або представляє собою. При описі мов програмування U - це один не термінальний символ. u - будь-яка послідовність термінальних або не термінальних символів розкриває сутність не термінального символу з ліва.
Символічне ім'я>:: = <буква> | <символічне ім'я> <БЦ>
<БЦ>:: = <буква> <цифра>
По одному з правил визначають найбільш загальних понять мови будується першим і називається початковим символом мови.
Класифікація мов за Хомського
В основі цієї класифікації лежить форма лівої і правої частини правил підстановки. Мови діляться на 4 класи:
0
1
2
3
При чому кожен клас більшого номера, є підмножиною кожного класу з меншим номером.
Клас 0. (Граматика з фразовой структурою). Не накладається ні яких обмежень на правила підстановки. Правило має вигляд наведений вище, де U - довільна не порожня послідовність термінальних і не термінальних символів. Клас 0 є найбільш потужним мови цього класу можуть слугувати моделлю природних мов.
Клас 1 Контекстно-залежна граматика. U1 - нетермінальний символ. XY u - довільна ланцюжок термінальних і нетермінальних символів. Сенс цього правила полягає в тому, що заміна U на u здійснюється тільки в контексті X Y. Якщо довжину позначити, то видно що ліва частина завжди менше ніж права.
Клас 2 Контекстно-вільні граматики. U рівно один не термінал. Граматика класу 2 зазвичай використовується для опису синтаксису мов програмування.
Клас 3 Регулярної граматикою. U - один не термінал. t - один термінал. n - один не термінал. Граматика три може використовуватися для опису символу простих мов. Використовується для збірки лексем. Якщо б хоча б одне правило підстановки відноситься до більш високого класу ніж інші, то і вся граматика відноситься до цього класу. Для опису синтаксису формального мови досить задати граматику за допомогою 4 об'єктів.
S → aS
S → a
S → b
S → bY
Y → bY
Y → b
S → ξ
G3 = ({a, b}, {S, Y}, P3, S)
Дві граматики генеруючі один і той же мова називаються еквівалентні граматики.
Кожен рядок, яку можна вивести з початкового символу називається сентенціальний символ.
Синтаксичні діаграми.
Інший поширений спосіб опису синтаксису мови є графічним зображенням форм Бекуса Наура. Чи не термінальні символи записуються на діаграмі прямокутниках, а термінальні в гуртках або овалах.
Приклад визначення символічного імені.

Синтаксичний аналіз мов програмування.
Після того, як на етапі лексичного аналізу, програма розбивається на її основні елементи, наступна фаза компілятора повинна розпізнати структуру висловлювання, що складається з цих елементів і інтерпретувати їх. Синтаксичний аналіз, являє собою завдання протилежну завдання породження (висновку). Завдання розбору формулюється наступним чином: визначити чи відповідає дана конструкція деякої мови, граматиці цієї мови. Чи є дана конструкція правильним пропозицією мови, тобто не містить синтаксичних помилок. Розрізняють два типи розбору. Лівобічний і правобічний.
Лівосторонній розбір - на кожному етапі виведення, починаючи з першого початкового символу мови заміщується за допомогою одного з породжують правил граматики самий лівий НЕ термінальний символ в сентенціальной формі.
Якщо порівняти два висновки, то можна виділити в правосторонньому зворотний порядок породжують правил. Так як правобічний розбір зазвичай асоціюється з приведенням пропозиції до початкового символу, а не з генерацією початкового символу.
Синтаксичне дерево розбору
Висновок можна описати і в термінах побудови дерева розбору. Дерево являє собою ієрархічну структуру, корінь дерева - початковий символ граматики, вузли проміжні зазвичай не термінальні символи, а всі інші вузли не термінальні символи. У більшості випадків ліво і правобічний розбір і синтаксичне дерево є унікальним. Однак, існують граматики, які мають більше одного дерево розбору, такі граматики називаються не однозначними. Встановити неоднозначність є не вирішуваною завданням. Не існує алгоритму, який взяв би будь-яку граматику як входу, і визначив однозначна вона чи ні. Методи розбору можуть бути детерміновані і не детерміновані, в залежності від того, можливе повернення чи ні. Чи не детерміновані методи дуже дорогі з точки зору пам'яті і часу., Загальний перебір.

Лекція 23.11.07

Базові методи синтаксичного аналізу.
Варіант побудови синтаксичного аналізу.
Спадний розбір - синтаксичне дерево будується від кореня до листя, його відмінна риса є цілеспрямованість, так як відправляючись від нетермінального символу мови, ми прагнемо знайти таку підстановку, яка б призвела до частини ланцюжка термінальних символів. Досягається це шляхом спрямованого перебору різних варіантів. У списку правил підстановці відшукується правило, які в лівій частині містять не термінальні символи, а в правій частині символи термінальні аналізованого пропозиції. Якщо таке правило є, то дерево не розраховується і правило повторюється. Якщо правило не знайдено, то повертаємося на один або кілька кроків назад, намагаючись змінити вибір зроблений раніше. Процес розбору закінчується в одному з двох випадку.
Побудоване дерево, все листя якого є термінальними символами і при читанні з ліво на право утворюють аналізоване пропозицію. У цьому випадки результат позитивний, синтаксично розглядається пропозиція відповідає граматиці мови.
Розпізнавач переробив всі можливі варіанти, але так і не прийшов до дерева, значить аналізоване пропозиція не належить даному мови або містить помилку.
«Константа»:: = «КФТ» | «знак» «КФТ»
Крок 1 константа
Крок 2 КФТ
Висхідний розбір - дерево будується від листя до кореня, тобто алгоритм відправляється від заданого рядка, намагається застосувати правило підстановки з ліва на право і все це привести до початкового символу граматики. Частина рядка, який можна привести до нетермінальному символу називають фразою. Якщо приведення здійснюється приведенням одного правило підстановки, фраза називається безпосередньо приводиться. Найлівіша безпосередня фраза називається основою. Алгоритм розбору полягає в наступному: у вихідному реченні відшукується основа і приводиться до нетермінальному символу. Ця операція застосовується до тих пір, поки не отримаємо єдиний символ і він повинен бути початковим символом граматики. Або в ланцюжку не може бути знайдена фраза, в цьому випадки робиться повернення на один або кілька кроків, вибирається інша основа, якщо всі можливі варіанти перебрані, а корінь дерева так і не побудований, робиться висновок про наявність помилки. Висхідний розбір представляє собою перебір варіантів, але вони не цілеспрямованими.
Спадні і висхідні методи вимагають великої кількості перебору. Тому вимагаю тільки детерміновані методи.
Метод рекурсивного спуску - добре відомий легко реалізований і детермінований метод розбору з верху в низ. З його допомогою на підставі відповідної граматиці, можна швидко написати синтаксичний аналізатор. Основне переваги - швидкість створення аналізатора. Інша перевага полягає у відповідності між граматикою і аналізатором, завдяки тому що збільшується ймовірність того, що аналізатор правильний. Основний недолік - повільність, багато викликів. Вручну граматику змінимо, в ведемо два нетермінальних символу. За граматиці пишемо програму синтаксичного аналізатора. Lex - функція, яка виділяє лексему.

Лекція 30.11.07

Ll (1) - граматика
Контекстно-вільні граматики традиційно служать основою створення синтаксичних аналізаторів. Для того щоб побудувати де терминированной аналізатор працює за принципом зверху в низ використовується Ll (1) граматика. Перша l означає, що вихідна рядок розбивається з ліво на право, друга літера - лівобічний розбір, а цифра означає, що варіанти породжують правил вибирається за допомогою одного попереднього проглядається символу.
Визначимо S-граматику.
Права частина породжує правила починається з терміналу.
У тих випадках, коли в лівій частині більш одного однакових не терміналу, то відповідні праві частини починаються з різних терміналів.
Для того що б граматика була, необхідною умовою є безліччю символів попередників не повинно перетинатися. Граматику називають Ll (1) якщо для кожного не терміналу з'являється в лівій частині більше одного разу безлічі напрямних символів відповідних правил не перетинаються. Виникає питання, чи всі граматики. Чи існує алгоритми, що визначають властивості. Однак, граматику, можна перетворити що б вона стала Ll (1).
Що б замінити ліву рекурсію на праву ми впорядковуємо НЕ термінали.
Факторизація - у багатьох ситуаціях граматику не володіють ознаками Ll (1) можна перетворити в граматику Ll (1). Процес факторизації можна автоматизувати, поширивши його на загальний випадок.

Лекція 07.12.07

Ll (1) - граматика
Після знаходження граматики, можна перейти до побудови синтаксичного розбору. Цей етап аналогічний рекурсивному спуску, тільки тут виключається численні виклики процедур, завдяки представленню граматики в табличному вигляді. Уявімо граматику у вигляді схеми, номери відповідні елементам будуть номерами рядків у таблиці розбору.

У таблицю розборів включають по одному елементу на кожне правило граматики. І на кожен примірник терміналу і не терміналу правій частині правильної граматики. Таблиця складається з шести стовпців.
1 стовпець - напрямні символи (термінал)
2 стовпець - поле переходу, звичайно дає наступний елемент для обробки (номер рядка). Якщо значення поля повернення, не виявиться істинної, то адреса наступного елемента береться з стека. Це відповідає кінця правила.

3 стовпець - напрямні символи, перехід

№	Термінал	Перехід	Приймати	стек	повернення	помилка
1	Begin	2	f	f	f	t
2	Begin	3	t	f	f	t
3	d	7	f	t	f	t
4	coma	5	t	f	f	t
5	s	15	f	t	f	t
6	end	0	t	f	t	t
7	d	8	f	f	f	t

1 дію - begin зчитується і перевіряється. Стек порожній, і використовується в стек розборах для вказівки адрес повернення. Переходимо на рядок 2. Перевіряємо і приймаємо begin.
У таблиці кожному кроці розбору відповідає один елемент. У процесі розбору здійснюється:
Прочитуємо і перевіряємо попередньо переглядається символ. З тим, щоб з'ясувати чи не є він напрямних для будь-якої конкретної правій частині породжує правила. Якщо цей символ не спрямовує, то вона перевіряється на наступному етапі.
Здійснюється перевірка терміналу, що з'являється в правій частині породжує правила.
Перевірка не терміналу. Вона полягає у перевірці знаходження попередньо проглядається символу, в одній з множин напрямних символів. Приміщення в стек адреси повернення і переходу до першого правилом відноситься до даного правилом. Якщо нетермінал з'являється в кінці правій частині, то немає необхідності розміщувати в стек. Програма містить цикл процедури. Тіло яке обробляє елемент таблиці розбору і визначається наступний елемент для обробки. Якщо попередньо проглядається елемент відсутній у списку системи і значення полі помилки виявиться брехнею, потрібно обробляти наступний елемент з тим же символом. Їли попередньо переглядається символ не міститься в поточному і поле помилки t, то видається повідомлення про синтаксичну помилку.
Переваги:
Ніколи не потрібно переваги повернення, оскільки цей метод не терминированной.
Є добрі діагностичні характеристики, і існує можливість виправлення помилок. Так як синтаксичні помилки розпізнаються по першому не прийнятного символу, а в таблиці розборів є список можливих символів продовження.
Таблиця розбору менше ніж відповідні таблиці в інших методах, значить швидкість вище.
LL1 розбір застосовується до широкого класу мов, однак у більшості випадків потребує ручного перетворення.
LR (1) - знизу в верх, розбирається детермінований. К - використовується правобічний розбір, від початкового сімвола.1 - фіксоване число попередньо переглядаються символів. Перша дія - зрушення, під час якого зчитується і міститься в стек символ, це відповідає просуванню на один пункт вздовж якого або правила граматики. Приведення, під час якого безліч елементів верхньої частини стека заміщається яким або не терміналом граматики.

Лекція 14.12.07

S -> real IDLIST
IDLIST -> IDLIST
IDLIST -> ID
ID -> ab з d
Стек символів
A ID IDLIST
Real real real
ID
IDLIST
Real
Щоб побудувати таблицю розбору необхідно знайти всі стани граматики.
Таблиця розбору представляє собою матрицю складається з шпальт - для кожного терміналу і не терміналу граматики + ознака закінчення, і рядків відповідного кожному стану.

Стан	S	IDLIST	ID	real	,	ABSD
1	HALT			S2
2		S5	S4			S3
3					R4		R4
4					R3		R3
5					S6		R1
6			S7			S3
7					R2		R2

Таблиця розбору включає елементи 4 типів. Зрушення S 2 - 2 означає стан, помістити в стек символів відповідні стовпцю символ. У стек стану помістити 2 і перейти в стан 2. Якщо вхідний символ термінал, прийняти його.
R4 - r означає елемент приведення, 4 означає 4 правило висновку. Виконати приведення. Видалити елемент.
3 елемент - пробіл, відповідає помилку.
Порівняльний аналіз методів
Обидва методи детерміновані і можуть виявляти синтаксичні помилки на самому ранньому етапе.2 метод застосовується до більш широкого класу мов і граматик і не вимагає перетворення граматики. ДД1 вимагає перетворення, і за наявності хорошого перетворювача не викликає труднощі.
Експериментальні дані виконані за допомогою аналізатора при порівнянні максимального і мінімального час розбору пропозиції прийшли до думки, що метод LL швидше на 50%, тобто метод з верху в низ швидше на 50%.
Після синтаксичного аналізатора, останнім кроком процесу компіляції є генерація коду. Як тільки розпізнаний фрагмент вихідного тексту програм відповідний деякому правилу граматики, викликається семантична підпрограма, яка не посередньо генерує код.
Все реально існуючі компілятори, на етапі розбору вхідних ланцюжків, перевіряє тільки синтаксис вхідного мови не враховуючи його семантику. Для перевірки необхідно мати інформацію про знайдені лексичних одиницях мови.

Лекція 21.12.07

Генерація коду

Оператор вводу

Readln

IDLIST

Складні компіляторах можуть компілюватися проміжні форми представлення програм, придатні для подальшого аналізу, з метою створення більш ефективного об'єктного коду.
Проміжні форми
Послідовність четвірок
Послідовність трійок
ПолИЗ - дозволяє представляти будь-математичне вираз без дужок
S-> EVP
EVP-> TERM
TERM-> FACT
FACT-> FACT
ID-> A | B | C | D
Граматика четвірок
QUAD-> OPERAND OPI OPERAND = INT
OP2 OPERAND = INT
OPERAND-> INT | ID
INT-> DIGIT | DIGIT INT
DIGIT-> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
OP |+-|*
ID-> a | b | c | d | e
Оптимізація
На підставі четвірок може здійснюватися аналіз та модернізація проміжного коду.
Мета: оптимізація.
Можна виключати деякі операції запам'ятовування і завантаження.
Ефективно використовувати проміжні форми.
Зменшується довжина програми, зменшується кількість змінних. Існує і Машино незалежна оптимізація.
Лекція 28.12.07
Розподіл пам'яті. Структуровані змінні.
Компілятор для зберігання структурованих елементів повинен виконати кілька етапів:
Виділити пам'ять під масив, для цього він повинен знати межі масиву.
Заповнити інформацію характеризує структурну змінну, розмір, тип масиву і покажчик на його початку.
Згенерувати інформацію для звернення компонентів структурованої змінної.
Породити описувач структурованої змінної, для тих випадків, коли необхідна інформація відсутня під час компіляції.
Аналогічна інформація виникає при обробки запису рядків і множин.
Рекурсивний виклик процедур, у випадки використання статичного розподілу пам'яті не працює. Цю проблему вирішують за допомогою динамічний розподіл пам'яті. Кожен виклик призводити до утворення області ініціалізації. Звичайна область ініціалізації розташовується в стеки, і розташовується наступною інформацією. Містить всі змінні, адреса повернення, зберігає адресу наступного і попереднього виклику. Цей метод називається метод автоматичного розподілу.
Варіанти створення компіляторів.
Швидкість роботи
Якість коду
Діагностика помилок
Переносимість
Підтримка
Якщо важлива швидкість компіляції, то одна переглядових схема краще. Однак не всі мови високого рівня.
Якщо з скомпільований об'єктні модулі використовуються багаторазово, або пам'яті інші ресурси істотно обмежені або модулі обробляють великі масиви даних, то швидкість виконання програми стає більш важливим фактором.

Інтерпретатор 3

Інтерпретатор 2

Інтерпретатор 1

Об'єктний код

Компілятори з використанням проміжного коду.
Генератори, компілятори.