Способи внутрішнього представлення програм

12. Способи внутрішнього представлення програм

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

Відомі наступні форми внутрішнього представлення програм:

зв'язані облікові структури, що представляють синтаксичні дерева;

багатоадресний код з явно іменованим результатом (тетради);

багатоадресний код з неявно іменованим результатом (тріади);

обернений (постфиксна) польський запис операцій;

асемблерний код або машинні команди.

Синтаксичні дерева

Синтаксичні дерева – це структура, що представляє собою результат роботи синтаксичного аналізатора. Вона відображає синтаксис конструкцій вхідної мови і явно містить у собі повний взаємозв'язок операцій. Очевидно також, що синтаксичні дерева — це машинно-незалежна форма внутрішнього представлення програми.

Недолік синтаксичних дерев полягає в тому, що вони являють собою складні зв'язні структури, а тому не можуть бути тривіальним чином перетворені в лінійну послідовність команд результуючої програми. Проте вони зручні при роботі з внутрішнім представленням програми на тих етапах, коли немає необхідності безпосередньо звертатися до команд результуючої програми.

Синтаксичні дерева можуть бути перетворені в інші форми внутрішнього представлення програми, що представляють собою лінійні списки, з урахуванням семантики вхідної мови. Алгоритми такого роду перетворень розглянуті далі. Ці перетворення виконуються на основі принципів СК-компіляції.

Багатоадресний код з явно іменованим результатом (тетради)

Тетради являють собою запис операцій у формі з чотирьох складових: операції, двох операндів і результату операції. Наприклад, тетради можуть виглядати так: <операція>(<операнд1>,<операнд2>,<результат>).

Тетради являють собою лінійну послідовність команд. При обчисленні виразу, записаного у формі тетрад, вони обчислюються одна за іншою послідовно. Кожна тетрада в послідовності обчислюється так: операція, задана тетрадою, виконується над операндами і результат її виконання міститься в змінній, заданій результатом тетради. Якщо якийсь з операндів (чи оба операнда) у тетраді відсутні (наприклад, якщо тетрада являє собою унарну операцію), то він може бути опущений чи замінений порожнім операндом (у залежності від прийнятої форми запису і її реалізації).

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

Тетради вимагають більше пам'яті для свого представлення, ніж тріади, вони також не відображають явний взаємозв'язок операцій між собою. Крім того, є складності з перетворенням тетрад у машинний код, тому що вони погано відображаються в команди асемблера і машинні коди, оскільки в наборах більшості сучасних комп'ютерів рідко зустрічаються операції з трьома операндами.

Багатоадресний код з неявно іменованим результатом (тріади)

Тріади являють собою запис у формі трьох складових:

<операція>(<операнд1>;<операнд2>)

Їх особливістю є те, що один або обидва операнди можуть бути посиланнями на іншу тріаду. Це в тому випадку, якщо в якості операнда даної тріади виступає результат виконання іншої тріади. Тому тріади при записі нумерують послідовно для зручності посилань.

Кожна тріада обчислюється таким чином: операція, яка задана тріадою, виконується над операндами, якщо в якості одного із операндів або двох є посилання на іншу тріаду, то береться результат обчислення тієї тріади. Результат обчислення кожної тріади потрібно зберігати в тимчасовій пам’яті, так як він може знадобитися наступним тріадам. Якщо один операнд відсутній, він може бути упущений.

Переваги:

легке написання алгоритму;

легко перевести в асемблер ний код.

Недолік: необхідний алгоритм для зберігання в пам’яті проміжного результату.

Тріади є машинно незалежні, вимагають менше пам’яті ніж тетради.

Обернений польський запис

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

Недоліки:

необхідно використовувати стек

важко робити оптимізацію

Нехай задано арифметичний вираз виду: (A+B)*(C+D)-E

Представимо цей вираз у вигляді польського запису: AB+CD+*E-

Обернений польський запис володіє властивостями, які перетворюють його в ідеальну проміжну мову при трансляції:

1. обчислення виразу може проводитися шляхом одноразового перегляду, що зручно для генерації коду

2. отримання польського запису просто здійснити на основі алгоритму DX3.

13. Визначення формальної мови і граматики

Формальні мови - це математичний апарат, що дозволяє математично грамотно створити мови програмування і писати компілятори для них.

Формальну мову можна задати як послідовність слів. Слово – це послідовність символів. Тоді навіть програму можна вважати просто словом.

Словами даної мови може бути не довільний набір символів, а лексично і синтаксично правильно побудований. Для того, щоб задати граматику, треба задати множини термінальних і не термінальних символів.

Термінальні – це символи, які використовуються в мові, а проміжні або нетермінальні – це символи, які використовуються для створення слів мови. Створюються слова за граматичними правилами. Застосування правила полягає в заміні в перетворюваному рядку якоїсь послідовності символів, що співпадає з лівою або правою частиною правила.

Компілятор, отримавши на вхід програму, робить зворотну роботу. Він згортає за граматичними правилами від правої до лівої частини початкові символи.

Кінцева множина символів, яка є неподільною, називається словником або алфавітом, а символи, що входять в множину – буквами алфавіту. Послідовність букв алфавіту називається словом або ланцюжком цього алфавіту, число букв, що входить у слово, називається його довжиною.

Якщо задано алфавіт А, то А^* - це множина всіх ланцюжків, які можна побудувати з алфавіту А. $ - порожній рядок (рядок, що не містить жодної букви) також входить в А. Для позначення всіх ланцюжків алфавіту А, що не містять порожнього використовується А⁺.

Формальною граматикою Г називається сукупність таких об’єктів:

Г={V_T,V_N,<I>,R},

Де V_T – термінальний алфавіт (словник). З букв цього алфавіту будуються ланцюжки, які породжуються граматикою.

V_N – нетермінальний (допоміжний) алфавіт. Його букви використовуються при побудові ланцюжків, вони можуть входити в проміжні ланцюжки, але не можуть входити в результат побудови.

<I> - початковий символ.

R – множина правил виведення.

Множина кінцевих ланцюжків термінального алфавіту V_T граматики Г, виведених з початкового символу <I> називають мовою, яка породжена граматикою Г і позначається L(Г).

Якщо правило виведення граматики мінить один нетермінальний символ, як в лівій, так і в правій частині, то таке правило називається рекурсивним.

Типи формальних граматик

Виділяють 4 типи формальних граматик. Ці граматики визначаються шляхом накладання обмежень на правила граматики.

Граматика типу 0 – граматика загального вигляду, немає обмежень на правила породження.

Граматика типу 1 – контекстно залежна.

Правило: χ₁<A>χ₂→ χ₁ωχ₂.

Ланцюжки χ₁ і χ₂ залишаються незмінними при застосуванні правил, тому їх називають контекстом, а граматику – контекстно залежною.

Граматика типу 2 – контекстно вільна.

Правило: <A>→α, де .

Ці правила слідують із правил граматики типу 1 за умови χ₁ = χ₂ = $.

Граматика типу 3 – автоматна.

Правила виведення: <A>→a або <A>→a<B> або <A>→<B>a, де

.

Способи задання схем граматик

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

символічна

форма Бекуса-Наура (ФБН)

ітераційна

синтаксичні діаграми

Символьна мова передбачає використання елементів нетермінального словника і стрілки, як роздільника правої і лівої частини. Але при описі конкретних мов програмування доводиться вводити велику кількість не термінальних символів і символьна форма запису втрачає свою наочність.

Похожие работы

Історія розвитку прикладного програмного забезпечення персонального комп'ютера

Скачать

29613

0

0

... , що вхідна мова і системне забезпечення такого пакету можуть бути достатньо легко реалізовані силами прикладного програміста. Тому у разі, коли подібний пакет задовольняє конкретних користувачів, його розробка є цілком виправданою. 3. ВИСНОВОК Сучасний український ринок прикладного програмного забезпечення є, значною мірою, ринком піратського ПО. Це пов'язано з тим, що український спожива

Використання комп'ютерної техніки в суспільстві, роль програмного забезпечення

Скачать

40072

1

6

... і MS Excel загальні відомості про електронні таблиці, призначення і можливості, вікно електронної таблиці, вікна книг Термін «електронна таблиця» вживається для позначення простої у використанні комп'ютерної програми Excel, що призначена для обробки інформаційних даних за допомогою таких операцій, як: ■ проведення різних обчислень із використанням потужного апарату функцій і формул; &# ...

Програмне забезпечення ПК

Скачать

9432

5

1

... процедур, правил і документації, необхідних для використання програмних продуктів. Усі програми, з якими працюють на сучасних комп’ютерах, можна розділити на 3 категорії: Програмне забезпечення Системні програми Інструментальні системи Прикладні програми ·    СИСТЕМНІ ПРОГРАМИ- ті, що використовуються для забезпечення працездатності комп’ютера, експлуатації інших програмних продукт ...

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

Скачать

36049

2

1

... також усі індійські цифри (0–9), латинські букви (a-z, A-Z), символи табуляції, символ переходу на нову стрічку, пробіл та синтаксичні знаки (!,?,,/, %,$,@,^,_). 3. Розробка транслятора вхідної мови програмування 3.1 Вибір технології програмування Необхідно вибрати ефективні методи розв’язку загальних задач, таких як розпізнавання лексем, синтаксичний розбір, семантичний аналіз та ...