Основи побудови компіляторів:Іспит

Матеріал з USIC Wiki

Перейти до: навігація, пошук
Для ФІН

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Питання на іспит з курсу “Основи побудови компіляторів”

Зміст

Мови програмування (процедурні, візуальні, специфікацій). Концепція інструментального середовища розробки програм.

Алгоритмічна мова

Алгоритмічна мова (АМ) – формальна мова, призначена для записування алгоритмів шляхом формального задавання правил конструювання. Хоч для кожної АМ такі правила досить різноманітні і якісно відмінні, будь-який алгоритм можна скласти з невеликого числа елементарних приписів, що задають послідов­ність кроків алгоритму. АМ зветься універсальною, якщо в ній для довільного алгоритму можна описати алгоритмічно повний набір приписів. За узагальненістю способу записування алгоритмів універсальна АМ рівносильна алгоритмічній системі, наприклад, класичним алгоритмічним системам: нормальним алгоритмам Маркова, рекурсивним функціям, машинам Т’юрінга чи Поста.
АМ визначається алфавітом вхідних символів, точним описом синтаксису (граматики) і семантики. Оператори АМ переробляють інфор­мацію і можуть складатися з послідовності елементарних операцій, а опера­тори управління (переходу) визначають порядок виконання операторів у алгоритмі. Незважаючи на універсальність АМ, вони виявилися непридатними щодо розв’язання практичних задач на комп’ютерах, оскільки не враховували умов операційних середовищ, а орієнтувалися на дослідження фундамен­таль­них питань теорії алгоритмів. Наприклад, у мові АЛГОЛ-60 (1960 р.) для записування алгоритмів були відсутні навіть оператори вводу-виводу.

Мови програмування

Тому на основі АМ виникли мови програму­вання (МП) як формальні мови спілкування людини з комп’ютером, призначені для опису сукупності інструкцій, виконання яких забезпечує правильне розв’язання потрібної задачі; інструкції описують обробку даних (інформації) і алгоритмів (програм) комп’ютерної обробки даних.
Першими МП були мови машинні, що адекватні системам команд комп’ютера, безпосередньо ним реалізуються (наприклад, як асемблер), однак вимагають суттєвої деталізації розв’язування задачі. Тому з’явилися МП з вищим рівнем абстракції, орієнтовані на певні предметні області і здатні лаконічно виразити алгоритм розв’язання задачі: у 1958 р. Фортран для вирішення інженер­них і наукових задач; у 1959 р. Кобол для задач оброблення економічної інформації. Зазначимо багатоцільову Адресну мову, яку розробили у 1956 р. київські математики В.С. Королюк і К.Л. Ющенко і яка, завдяки апарату непрямої адресації, випередила появу не тільки МП вищого рівня, але й асембле­рів. Цей апарат закріпився у МП для системного програмування тільки починаючи з МП ПЛ/1 (1966 р.). Підручник з Адресної мови перевиданий у п’яти країнах світу, а Адресна мова реалізована на усіх вітчизняних комп’ютерах першого покоління.

Процедурні та проблемно-орієнтовані мови програмування

Залежно від підходу до описування задачі МП поділяють на процедурні, за допомогою яких детально визначається, як повинен діяти комп’ютер, та проблемно-орієнтовані або функціо­наль­ні, які визначають у термінах функцій, що необхідно зробити. Процедурні мови містять засоби вираження таких характерних дій, як обчислення виразів, перевірка умов, оброблення текстових рядків, організація циклів обчислень, виклик процедур тощо. Проблемно-орієнтовані мови надають засоби визначення наборів функцій, що повинні виконуватися.
За сорокаріччя розвитку відомо понад 1000 МП, серед яких поширилися і продов­жу­ють розвиватися всього півтора десятки, зафіксовані у міжнародних і національних стандартах. Необхідність стандартизації МП з’ясувалася ще наприкінці першого десяти­річ­чя їхньої появи. З процедурних сьогодні стандарти­зовані і мають по декілька поко­лінь МП для інженерних застосувань Фортран, Бейсік і ФОРТ; для оброблення даних Кобол; для структурованих запитів до реля­ційних баз даних SQL; для розмітки документів SGML; для управління реальними об’єктами Ада і Модула-2; для оброблення матриць APL; для оброблення медичних даних M[UMPS], для оброблення списків КоммонЛисп; Пролог з вбудованим механізмом логічного виведення за методом резолюцій; для розробки застосувань ПЛ/1, Паскаль, Сі та С++.
Вражає шлях розвитку МП Фортран, життєвий цикл якої нараховує вже шість поколінь, починаючи з Фортран-II у 1958 р. і першого стандарту на Фортран-IV у 1966 р.. Потім діяли стандарти на Фортран-77 та Фортран-90, поки стандарт на Фортран-95 не розділився на три частини через складність і громіздкість мовних конструктів для розпарале­лю­вання процесів, спадкування, плаваючої арифме­тики, оброблення рядків змін­ної довжини і розширення вводу-виводу та загалом експорту/ імпорту даних. Унаслідок результаті розпочатого перегляду чинного стандарту, шосте покоління Фортран-2000 не буде поступатися за потужністю МП Сі та збага­титься засобами об’єктно-орієнтованого програму­ва­ння, інтерна­ціоналіза­ції, полі­мор­­фізму, задавання посилань, асинхронного вводу-виво­ду, інтер­валь­ної арифметики, зв’язку з мовами програмування тощо.

Додатково

Зазначимо, що розвиток МП в Україні супроводжувався розробкою декількох оригінальних мов, серед яких доцільно назвати МП НЕДИС для описування задач моделювання подій, АНАЛІТИК для число-аналітичних викладок на 1-у в світі персональному комп’ютері серії МИР, розробленjому в Києві.
Перспективи організації розподіленого оброблення на основі обчислюваль­них мереж, що відкрилися у 90-і роки, призвели до нового витка у розвитку сучасних МП, які прийнято відносити до четвертого покоління (4GL). Причому зазначена родина стандар­ти­зо­ваних МП розвивається переважно усередині себе, не розширюючи меж та об’єктивно відбиваючи наслідки принципу спадковості поколінь МП Приклади – створення на основі SGML мови HTML для описування web-сторінок і на основі С++ мови Java для розроблення програм-аплетів у складі Web-сторінок.
Опис задачі або програма на МП перетворюється у машинну мову спеціальним процесором (транслятором чи інтерпретатором). Довільна МП машинно-незалежна, тому колись написану програму можна використовувати на різних комп’ютер­них платформах і у різних операційних середовищах. Сьогодні мовний процесор – це інтегроване середови­ще розробки прикладних програм і великих застосувань, в якому уніфіковано підтриму­ється зв’язок з іншими МП та базами даних, надаються графічні засоби і забезпечується поліекранна схема діалогу з користувачем.
У МП реалізовано принцип приховування інформації, коли абстракції даних (блоки і шаблони зовнішніх даних) чи дій (процедури та їхні параметри) можна викорис­то­вувати як чорний ящик, не знаючи подробиць їхнього облаштування та створення, і накопичувати продукти своєї та чужої праці. У сучасних МП вищий прояв цього принципу становлять абстракції типів даних, що визначають категорії даних з інкап­суляцією операцій над ними, та абстракції об’єктів, які домінують в об’єктно-орієнтова­ному програмуванні. За цим принципом визначаються інтер­фейси – правила взаємодії програм. Щоб продукт праці програмістів міг викорис­то­вуватися іншими, його функції і правила настроювання необхідно ясно визна­чати, тоді можливі колективна розробка програм і компонування їх з готових моду­лів, а також забезпечення розподіленого оброблення у середовищі відкритих систем.
Проблемно-орієнтовані мови стали підґрунтям для розвитку мов специфікацій як засобів задавання специфікацій задачі, яку повинна розв’язувати програма. Зазвичай такий опис складається за певною моделлю розв’язання задачі; специфікуються характеристики і параметри моделі, тому у м.с.п. цінується насамперед висока виразність. Наведемо два приклади м.с.п., відомих кожному програмісту, – IDL (Interface Definition Language) для описування інтерфейсів програм розподіленого застосування і синтаксична метамова розширених БНФ (бекусо-наурівських форм). Другий приклад м.с.п – мови подання знань, які почали поповнюватися специфікаціями компонентів багаторазового використання, насамперед алгорит­мів добування знань з дослідних даних. Алгоритми навчання стали настільки узагальненими, що вони включені до складу стандартних бібліотек і, як наслідок, почалася стандартизація цих алгоритмів, яка має на меті їхню фіксацію як мовних конструктів.
Здолавши сорокарічний шлях розвитку, МП збагатилися власним фор­мально-алгоритмічним апаратом, що складає інтелект інструментів розробки програм, і трансформувалися у алгорит­мічні системи із збалансованими наборами конструктів, які спрацьовують у операційному середовищі з достатньо формалізо­ваною та уніфікованою поведінкою, правила якої разом з МП інтенсивно стандартизуються. Таким чином, сьогодні МП повернули собі назву алгоритмічних мов.

Інструментальне середовище

Debuger і візуальна оболонка інструментального середовища
Лінкувальник складає частину не транслятора, а інструментального середовища розробки програм. Сюди входить Debuger, за допомогою якого модуль тестують і налагоджують, тобто в ньому шукають і виправляють помилки. Головна функція Debuger’а – емуляція злінкованого модуля для отримання траси його виконання і перевірки проміжних і підсумкових результатів виконання програми.
Ще одна складова інструментального середовища – текстовий редактор для формування початкового тексту програми, яку пишуть конкретною МП. Інколи цей редактор працює у візуальному режимі, скажімо, у інструментальному середовищі Delphi чи мови UML

Синтаксис і семантика мов програмування, набори мовних конструктів: описи, оператори, лексеми, поняття, атрибути, ділянки дії, блоки.

Принцип модульності у мовах програмування.

Контекстні умови МП відбивають дві їхні властивості: (1) категоризація (типізація) даних та (2) реалізація модульного принципу через зв’язування окремо скомпільованих модулів та ділянки дії (адресний простір чи область видимості) імен. У Фортрані використовують тільки зв’язування через лінкування за іменами об’єктів головної програми і підпрограм. Структурні мови (Сі/С++), крім зв’язування, використовують механізм вкладених блоків.

Мовні процесори: компілятори, інтерпретатори, макрогенератори, метакомпілятори.

Транслятор – языковый процессор, преобразующий исходную программу на входном языке в рабочую программу, представленную на машинном или некотором промежуточном языке. Приведенное определение относится ко всем разновидностям языковых процессоров. Однако у каждого из таких процессоров есть свои особенности организации процесса трансляции. Принято разделять трансляторы на три основные группы: ассемблеры, компиляторы и интерпретаторы.
  • Ассемблер преобразует символические конструкции в команды машинного языка, т.е. осуществляет дословную трансляцию одной символической команды в одну машинную. Таким образом, язык ассемблера (ранее назывался автокодом) предназначен для облегчения восприятия системы команд компьютера и ускорения программирования. Программисту легче запомнить мнемоническое обозначение машинных команд, чем их двоичный код. Поэтому основной выигрыш достигается за счет повышения эффективности восприятия команд, а не увеличения их мощности. Кроме аналогов машинных команд, ассемблер содержит множество дополнительных директив, облегчающих управление ресурсами компьютера, написание повторяющихся фрагментов программ, построение многомодульных программ.


  • Компилятор транслирует в машинный язык программу, записанную на исходном языке программирования. Также как ассемблер, компилятор обеспечивает преобразование программы с одного языка на другой; этот процесс называется компиляцией. Однако конструкты исходного языка значительно отличаются организацией и мощностью от команд машинного языка. Иногда один конструкт исходного языка транслируется в десятки машинных команд. Кроме того, в некоторых языках программирования используется строгая типизация данных, осуществляемая через их предварительное описание. Здесь программирование опирается не на кодирование алгоритма, а на тщательное продумывание структур данных или классов.


  • Интерпретатор осуществляет пооператорную трансляцию и выполнение исходной программы без порождения в итоге программы на машинном языке. Распознав команду исходного языка, он тут же выполняет ее. В компиляторах и интерпретаторах используются одинаковые методы анализа исходного текста программы. Но интерпретатор позволяет начать обработку данных после написания даже одной команды; поэтому процесс разработки и отладки программ более гибкий. Кроме того, отсутствие выходного машинного кода позволяет не "захламлять" компьютер дополнительными файлами, а сам интерпретатор можно достаточно легко адаптировать к любой архитектуре, разработав его один раз на распространенном языке программирования. Поэтому интерпретируемые языки типа Java Script, VB Script получили широкое распространение. Недостатком интерпретаторов является низкая скорость выполнения программ. Обычно интерпретируемые программы выполняются в 50-100 раз медленнее программ в машинных кодах.


  • Макропроцессор обеспечивает замену одной последовательности символов на другую и есть разновидность компилятора, генерирующего выходной текст путем обработки специальных вставок макрорасширений, располагаемых в исходном тексте. Эти вставки оформляются как макрорасширения специальных конструкций, называемых макроопределениями и принадлежащих макроязыку. Макрорасширение – это параметризация или родовая конкретизация макроопределения. Исполнение макрорасширения производится макросом, т.е. конкретным модулем.
Макропроцессоры часто используются как надстройки над языками, увеличивая функциональность систем программирования. Любой ассемблер содержит макропроцессор, чем повышается эффективность разработки машинных программ.

Макропроцессоры увеличивают функциональные возможности таких языков, как ПЛ/1, Cи, C++. Особенно упростилось написание C++-программ благодаря библиотеке классов, например, MFC. Причем макропроцессоры повышают эффективность программирования без изменения синтаксиса и семантики языка.


  • Метакомпилятор (иногда называется компилятором компиляторов) обеспечивает построение компилятора по заданию входного языка этого компилятора. Разумеется, язык нового компилятора принадлежит весьма узкому классу языков, преимущественно спецификаций, описанных набором образцов. Чаще всего метакомпилятор строится как параметризуемый (generic) модуль, способный оценить правильность (полноту и непротиворечивость) заданной системы правил нового языка, отобрать и настроить необходимую совокупность образцов, превратив их макрорасширения. Затем компонуется монитор как главная программа нового компилятора, которая поддерживает выполнение макрорасширений через подключение конкретных макросов, реализующих отобранную совокупность образцов.

Синтаксичне управління мовного процесора. Задачі семантичного (контекстного) аналізу та генерації коду.

Схеми компіляції з визначенням проходів і етапів: лексичний аналізатор (сканер), синтаксичний аналізатор, генератор коду.

  • Синтаксический анализатор (парсер) - компонент компилятора, проверяющий исходные операторы на соответствие синтаксическим правилам и строящий дерево грамматического разбора, отображающее конкретные семантические связи языковых конструктов программы. Для упрощения выделения и опознания языковых конструктов используется лексический анализатор (сканер).
Синтаксический анализатор проверяет правильность входной программы по грамматике языка, реализуя принцип синтаксической управляемости языкового процессора.
  • Лексический анализатор (сканер) - не только перекодирует входную программу, но и собирает (агрегирует) информацию в специальных сводных таблицах.
  • Семантичний або контекстний аналізатор як компонент мовного процесора перевіряє семантичну узгодженість вживання у програмі мовних конструктів. Це найбільш залежна від мови програмування частина транслятора, проте для кожної мови реалізуються наступні функції:
- виконати перевірку контекстних умов в програмі;
- провести розподіл пам’яті;
- провести синтез програмного коду у єдиний модуль.
  • Генератор коду – компонент компілятора, який збирає скомпільований код у єдиний модуль. При цьому обов’язково проводиться оптимізація.
Потім цей модуль компонується (лінкується) з іншими, чим підтримується модульний принцип програмування. Проте компонувальним складає частину не транслятора, а інструментального середовища розробки програм. Сюди входить і Debuger, за допомогою якого модуль тестується і налагоджується, тобто в ньому шукаються і виправляються помилки. Головна функція Debuger’а – емуляція злінкованого модуля для отримання траси його виконання і перевірки проміжних і підсумкових результатів виконання.


Розглянемо схему компілятора, в якому:

1 - исходный текст программы;
2 - таблица терминальных символов языка (ключевые слова if, then и т.д.);
3 - лексическая свертка программы (промежуточная программа, удобная для работы парсера);
4 - правила грамматики (правила и аксиомы грамматики);
5 - дерево вывода (дерево грамматического разбора программы);
6 - абстрактная программа (атрибутное дерево программы) Отличия атрибутного дерева от дерева вывода: узлы снабжаются атрибутами (со ссылками на таблицу имен или к другим узлам атрибутного дерева, конкретными вычисленными значениями);
7 - некоторая промежуточная программа после машинно-независимой оптимизации. Может быть несколько этапов такой оптимизации и несколько форм представления машинного кода;
8 - таблица содержит кодовые продукции или заготовки, шаблоны по которым строится следующая версия промежуточной формы 9;
9 - код ассемблера или команды, напоминающие ассемблер. Возможно, для кода 9 еще не было распределения регистров.

Зображення:Compiler.GIF


Схема синтаксичного аналізатора

Зображення:Syntax_analizer.GIF

Стеки операторів і операндів мовного процесора, підпрограми виводу і діагностика помилок.

Компонувальник скомпільованих програм, завантаження і виконання програм. Debuger і візуальна оболонка інструментального середовища.

Debuger і візуальна оболонка інструментального середовища. Лінкувальник складає частину не транслятора, а інструментального середовища розробки програм. Сюди входить Debuger, за допомогою якого модуль тестують і налагоджують, тобто в ньому шукають і виправляють помилки. Головна функція Debuger’а – емуляція злінкованого модуля для отримання траси його виконання і перевірки проміжних і підсумкових результатів виконання програми.
Ще одна складова інструментального середовища – текстовий редактор для формування початкового тексту програми, яку пишуть конкретною МП. Інколи цей редактор працює у візуальному режимі, скажімо, у інструментальному середовищі Delphi чи мови UML У 1990-ті роки з’явилася процедура інсталяції (рис. 4), яка допомагає відтворювати у ОС певні риси інструментального середовища для виконання злінкованих програм. Насамперед це стосується уточнення схем оверлея, які прив’язуються до правил адресації прикладної платформи комп’ютера.

Типи даних, функції перетворення даних з одного типу на інший.

Проверка (контроль) типов основана на информации о синтаксисе языковых конструктов, представле­нии типов и правилах присвоения типов данных языковым конструктам. Такую проверку выполняет компилятор и называют статической (в отличие от динамической, выполняемой в процессе работы целевой программы), Проверка гарантирует выявление некоторых разновидностей ошибок. Скажем, компилятор сообщает об ошибке, если оператор применяется к несовместимому с ним операнду (например, при попытке сложения идентификатора массива и функции, использовании числовых (кроме 0 и 1) или символьных (кроме «ИСТИНА» и «ЛОЖЬ») операндов в логическом выражении оператора условного перехода либо указании вместо метки имени какой-то переменной).
В каждом языке программирования типы данных делят на базовые (фундаментальные) и создаваемые (конструируемые). Базовые типы – это атомарные или примитивные типы данных без внутренней структуры, чаще всего integer, real, boolean, char, void. Специальный базовый тип type-error сигнализирует об ошибке контроля типов данных. Обычно в языке зафиксированы некоторые штатные конструкторы типов данных: массивы, записи, множества, последовательности, указатели, функции и процедуры. Кроме того, через задание специальных выражений типа данных в программе объявляют производные типы данных; выражение типа данных содержит перемен­ные, значения которых сами являются выражениями штатных или производных типов данных.
Каждый языковой конструкт описывают выражением типа. Поскольку их можно именовать во многих языках программирования, то имя типа является выражением типа. В языках действуют правила умолчания для присвоения выражений типа. Так, в Фортране тип integer имеют переменные с первыми буквами имен I, J, K, L, V, N. Если контекстный анализатор присвоит каждому языковому конструкту его объявленный тип данных, отличный от type-error, то (1) гарантируется, что в целевой программе не возникнут ошибки, связанные с типами данных, (2) отпадает необходимость динамической проверки типов в процессе исполнения целевой программы. Язык имеет строгую или сильную типизацию, если его компилятор может гарантировать, что скомпилированная программа будет выполняться без ошибок, связанных с типами данных. Проверяя типы, компилятор способен выловить и гарантированно правильно интерпретиро­вать только первую ошибку, а все последующие могут быть следствием этой первой ошибки. Поэтому после сообщения о природе и месте ошибки, желательно восстановить нейтраль­ное состояние контекстного анализатора, чтобы он продолжил проверку типов данных.
Преобразование типов. Пример такого преобразования – выражения, в которых чаще всего целые числа переводятся в вещественные (а не наоборот, поскольку не всякое вещественное можно загнать в разрядную сетку представления целых чисел). Преобразование типов называется неявным, если выполняется компилятором автоматически и не вызывает потери информации, как при преобразовании целых чисел в вещественные. Явные преобразования задаются в программе, например, через встроенные Паскаль-функции ord для отображения символа целым числом или chr для обратного преобразования целого числа в символ. В Си/С++ в арифметических выражениях действует неявное преобразование символов в целые числа от 0 до 127.
Перегруженный (overload) символ допускает разные значения согласно контексту. В ПЛ/1 перегруженными являются круглые скобки, используемые как ограничители в операторе вызова процедур CALL … (…), для задания элементов массивов или в вызовах функций, в арифметических и логических выражениях. В большинстве языков арифметические операторы перегружаются. Перегрузка разрешаемая (resolved), если значение перегружаемого символа определяется однозначно. Разрешение перегрузки называют идентификацией операторов, поскольку она устанавливает тип операции, обозначенной символом. Не всегда идентификация операторов однозначно устанавливается; чаще арифметические операторы и подвыражения, а также параметры функций допускают множество типов данных, поэтому требуется достаточно сложный анализ немалого по объему контекста, в первую очередь определяющих вхождений операндов подвыражений и фактических параметров функций. Так, в Аде требуется установить единственный тип полного выражения, исходя из этого типа резко сужается выбор типов данных для каждого подвыражения. Причем, если в результате не установлен единственный тип данных для каждого подвыражения, то в этом выражении фиксируется ошибка проверки типа данных.
Тело обычной процедуры выполняется с параметрами фиксированных типов, а при вызове полиморфной функции ее тело всякий раз исполняется с параметрами разных типов данных. Термин «полиморфный» обычно указывает на полиморфизм не только функций, но и операторов. Обычно полиморфны встроенные операторы для индексирования массивов и работы с указателями. Полиморфные языковые конструкты привлекательны тем, что облегчают реализацию алгоритмов, работающих со структурами данных независимо от типов элементов этих структур. Например, удобно иметь подпрограмму обработки записей переменной длины со встроенной в них группой полей одного типа данных. Такую группу достаточно часто используют в обработке баз данных.
Полиморфизм языковых конструктов допускают языки, не требующие обязательного описания объектов до их использования (контекстное условие 3-го вида). При анализе употреби­тельного вхождения идентификатора находится его определительное вхождение и только после этого проверяется тип по выражению типа, т.е. по текущему значению переменной в этом выраже­нии. Так, в одной точке программы текущее значение переменной указывает тип integer, а в другой – тип массива. Полная проверка типов полиморфных объектов может быть только динамической.

Структури даних періодів компіляції і виконання програм. Організація бази даних мовного процесування. Бібліотеки.

Большинство современных языков относится к языкам с сильной или строгой типизацией, когда контроль типов языковых конструктов выполняет статически компиля­тор.. Кстати, режим интерпретации для таких язы­ков предпочтительнее компиляции. Контролируя типы компилятор организует собранную информацию в специальную базу данных и целевую (скомпилированную) программу. Большую часть информации из такой базы содержат таблицы констант и переменных; закладываемые лексическим анализатором, а затем проверяемые и дополняемые контекстным анализатором и генератором кода.
Задача контроля типов данных существенно упрощается с использо­ванием библиотек стандартных процедур языка. Здесь наиболее сложные механизмы контроля типов (полиморфизм и перегрузка) реализуются посредством параметризуемых или родовых (generic) модулей, заранее запрограммированных, отлаженных и отработанных на большом разнообразии примеров строгой типизации языковых конструктов. Таблицы констант и переменных трактуются как отображение адресного пространства программы (пространство имен), Аргументами являются использованные в программе символьные имена, а значениями – списки атрибутов объектов. Сами таблицы могут быть упорядочены и неупорядочены. Для поиска и хранения данных в таблицах применяют хэш-адресацию или ведут индексы таблиц в виде сбалансированных деревьев (AVL-деревьев или В-деревьев).
Для блочных языков таблицы организованы так, что в них отображена блочная структура программы. Используют метод сегментации таблиц имен; для каждого программного блока организована своя подтаблица имен и определен список доступных (объемлющих) блоков. К подтаблицам локализованных блоков применяют методы сортировки и поиска. Каждый элемент списка блоков представлен тройкой (surrno, noent, point):

  • surrno – номер блока, объемлющего данный блок; все программные блоки нумеруются;
  • noent – число элементов в той части таблицы имен, которая сопоставляется c блоком;
  • point – указатель на эту часть таблицы имен.

Такого вида структура организуется для всех программ блочной структуры. Например, блоки можно организовать для составных операторов.
(додати схему сюди)
Логически таблица имен представляет список блоков и подтаблиц на рис. 3.2. Здесь блоки расположены в порядке их закрытия. Нулем помечен мнимый блок, а 1-й блок самый внешний.
Схема формирования таблицы определяется так: для размещения элементов выделяется общий непрерывный фрагмент памяти. Нижняя часть таблицы используется как стек, список блоков формируется отдельно. Стек содержит идентификаторы всех блоков программы, для которых встречен «begin», но символ «end» еще не обработан. Как только встречен символ закрытия блока, относящиеся к этому блоку элементы переносятся в верхнюю часть таблицы (блок закрывается). Когда встречен символ открытия блока, то добавляется очередной элемент в список блоков.

Таблиці констант і змінних. Засоби підвищення ефективності роботи з таблицями. Впорядковані і невпорядковані таблиці. Пошук в таблицях.

Управління пам’яттю в процесі виконання програми. Статична і динамічна пам’ять. Стекова і heap-пам’ять.

Конструювання збирачів «сміття», маркірувальні та flip/flop–збирачі «сміття».

Метод «близнюків» для управління пам’яттю.

Розподіл пам'яті для констант, простих і тимчасових змінних, масивів зі статичними і динамічно обчислюваними границями

Основи теорії формальних мов і граматик. Символи і ланцюжки символів. Операції над ланцюжками символів. Визначення граматики.

Класифікація граматик за Хомським.

Граматика – це математична система для визначення мови. Для побудови граматики використовується два алфавіти, що не перетинаються:

1. N – множина нетермінальних символів.

2. S - множина термінальних символів, з яких утворюються слова або ланцюжки мови.

Σ* - всі можливі ланцюжки або замикання над алфавітом Σ.
Σ+ - всі можливі ланцюжки за виключенняс порожнього символу {Δ}(порожнього ланцюжка)


Зображення:OPK_n17.GIF


  • граматика типу 0 або граматика з фразовою структурою, якщо всі правила мають вигляд \alpha \rightarrow \beta, де \alpha \in (\Nu \cup \Sigma)+ , \beta \in (\Nu \cup \Sigma)*, породжує рекурсивно-счисленні множини.
  • граматика типу 1 безпосередньо складаних або контекстно-залежна (нескоротна), якщо всі правила мають вигляд (приклад граматики для мови anbnan з порожнім ланцюжком замість контексту): \alpha A \beta \rightarrow \alpha \gamma \beta , де A \in \Nu , \alpha , \beta \in (\Nu \cup \Sigma)* , \gamma \in (\Nu \cup \Sigma)+ породжує НС-мови.
  • граматика типу 2 або контекстно-вільна (КС) граматика, якщо всі правила виду A \rightarrow \alpha, де \alpha \in (\Nu \cup \Sigma)* породжує (КС) мови.
  • граматика типу 3 або автоматна, що породжує регулярну мову, якщо всі правила виду A->a; B->Cb; де A, B, C \in \Nu ; a, b \in \Sigma.

Співставлення класів граматик з автоматами та розпізнавачами

Нотації синтаксису мови. Граматичні продукції, нормальні форми Хомського і Грейбах.

  • Нормальна форма Хомського

Нормальна форма Хомського (НФХ - бінарна нормальна форма) встановлюється для приведеної контекстно-вільної (КС) граматики, всі правила якої мають вигляд:

1. A->BC, де A,B,C належать N (множині нетермінальних символів)
2. A-> a, де a належить Σ
3. S -> \varepsilon , якщо \varepsilon \in L(G)

Твердження 1. нехай L(G) – КС-мова. Тоді L(G) = L(G’) для деякої КС-граматики G’ в нормальній формі Хомського.

Для виконання перетворень необхідно спочатку отримати приведену форму, застосовуючи розглянуті алгоритми ([1]), а потім отримати НФХ. Отримати НФХ розглянемо на прикладі.

Нехай G – приведена КС-граматика з правилами:

S -> aAB | BA

A -> BBB | a

B -> AS | b


Введемо додаткові символи, що замінять ланцюжки AB, BB, a:

C -> AB,

D -> BB,

F -> a

Отримаємо G’ – грамматику в НФХ и L(G) = L(G’):

S -> FC | BA

A -> BD | a

B -> AS | b

C -> AB

D -> BB

F -> a


  • Нормальна форма Грейбах
Нормальна форма Грейбах (НФГ). КС-граматика (контекстно-вільна) G = (Ν,Σ,Ρ,S) перебуває в НФГ, якщо вона приведена і кожне равило із Р, відмінне від S -> \varepsilon , має вигляд A -> aα, де a \in \Sigma та \alpha \in \Nu*. При додаткових обмеженнях накладених на мову і правила, за такою граматикою будуються прості та ефективні СА, оскільки майже завжди можна одразу встановити, скільки символів треба читати із вхідного потоку, щоби однозначно обрати правила в процесі виводу. Побудова граматики в НФГ має за основу позбуття лівої рекурсії в правилах.


Діаграми як нотації синтаксису мови

Регулярні мови і скінчені автомати. Праволінійні граматики.

Скінчені автомати Побудова детермінованого автомату за недетермінованим.

Діаграма переходів скінченого автомату, побудова за нею таблиці переходів і автоматної граматики.

Побудова лексичних аналізаторів. Прямий і непрямий лексичний аналіз. Класи символів алфавіту. Навантажена діаграма стану.

Синтаксичний аналіз і дерева граматичного розбору. Алгоритми згортки та розгортки. Магазинні автомати і КН–мови.

Властивості КН-мов. Задача безпереборного синтаксичного аналізу .

Характеристика табличних методів синтаксичного аналізу. Метод Кока-Янгера-Касамі.

Характеристика табличних методів синтаксичного аналізу. Метод Ерлі.

Взяв собі Крячко Макс hitmax 01:50, 18 квітень 2008 (EEST)

Співставлення LL(k)- та LR(k)-граматик.

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

Існують відповідні класи граматик (які можна розібрати такими парсерами):
  • LL(k) - граматики, які однозначно можуть співставити (детерміновано працюють), якщо зправа від поточної позиції можна проглядати k вхідних символів
  • LR(k) - граматики, які однозначно можуть співставити (детерміновано працюють), якщо зліва від поточної позиції можна проглядати k вхідних символів
  • Граматики передування, для яких правий аналізатор знаходить основу в результаті аналізу відношень між парами суміжних символів у вхідному потоці.

Неформально: основою є таке входження послідовностей символів з (N \cup \Sigma)* - нетермінальні символи та термінальні з пустим ланцюжком, яке можна перетворити до символу з N - нетермінали (як наприклад аналізуємо вхідний ланцюг: if: i-terminal, f-terminal if-non-terminal)

Розбір для LL(1)- та LL(k)-граматик.

Взяв собі Крячко Макс hitmax 01:50, 18 квітень 2008 (EEST)

Детермінований правий аналізатор для LR(k)-граматик

Граматики простого передування. Матриця передування та обчислення функцій передування.

Граматики операторного (слабкого) передування

Польський запис і прямі методи компіляції виразів: арифметичних, умовних, з індексованими змінними.

Польський запис і прямі методи компіляції виразів з викликом функцій.

Компіляція операторів присвоєння, умовного та безумовного переходів з використанням ПОЛІЗ .

Компіляція блоків. Використання ПОЛІЗ для перекладу та стеку для динамічного розподілу пам’яті.

Компіляція процедур. Виклик параметрів за адресою, найменуванням і за значенням. Побічний ефект у процедурах.

Компіляція процедур. Використання ПОЛІЗ для виклику процедур з передачею параметрів за найменуванням.

Семантичні програми в процесі компіляції та генерація коду програми. Тетради і тріади.

Атрибутні транслюючі граматики і автомати. Синтезовані та успадковані атрибути.

Атрибутне дерево виведення (розбору).

L- та S-атрибутні граматики. Метод рекурсивного спуску для атрибутних граматик.

Задачі машиннонезалежної оптимізації програм. Оптимізація лінійних ділянок. Згортки. Виключення зайвих операцій.

Поміркована оптимізація циклів. Винесення інваріантних операцій. Заміна перевірки. Виключення вироджених присвоєнь.

Машиннозалежна оптимізація програм. Розподіл регістрів та тимчасових змінних.

Методи побудови інтерпретаторів. Покрокові компілятори. Віртуальні машини.

Механізм макрогенерації в процесі компіляції.

Отримано з http://wiki.usic.org.ua/wiki/%D0%9E%D1%81%D0%BD%D0%BE%D0%B2%D0%B8_%D0%BF%D0%BE%D0%B1%D1%83%D0%B4%D0%BE%D0%B2%D0%B8_%D0%BA%D0%BE%D0%BC%D0%BF%D1%96%D0%BB%D1%8F%D1%82%D0%BE%D1%80%D1%96%D0%B2:%D0%86%D1%81%D0%BF%D0%B8%D1%82
Особисті інструменти