Системне програмне забезпечення (стр. 7 из 7)
Тетради являють собою лінійну послідовність, а тому для них нескладно написати тривіальний алгоритм, що буде перетворювати послідовність тетрад у послідовність команд результуючої грами (або послідовність команд асемблера). У цьому їхня перевага перед синтаксичними деревами. На відміну від команд асемблера тетради не залежать від архітектури обчислювальної системи, на яку орієнтована результуюча програма. Тому вони являють собою машинно-незалежну форму внутрішнього представлення програми.
Тетради вимагають більше пам'яті для свого представлення, ніж тріади, вони також не відображають явний взаємозв'язок операцій між собою. Крім того, є складності з перетворенням тетрад у машинний код, тому що вони погано відображаються в команди асемблера і машинні коди, оскільки в наборах більшості сучасних комп'ютерів рідко зустрічаються операції з трьома операндами.
Багатоадресний код з неявно іменованим результатом (тріади)
Тріади являють собою запис у формі трьох складових:
<операція>(<операнд1>;<операнд2>)
Їх особливістю є те, що один або обидва операнди можуть бути посиланнями на іншу тріаду. Це в тому випадку, якщо в якості операнда даної тріади виступає результат виконання іншої тріади. Тому тріади при записі нумерують послідовно для зручності посилань.
Кожна тріада обчислюється таким чином: операція, яка задана тріадою, виконується над операндами, якщо в якості одного із операндів або двох є посилання на іншу тріаду, то береться результат обчислення тієї тріади. Результат обчислення кожної тріади потрібно зберігати в тимчасовій пам’яті, так як він може знадобитися наступним тріадам. Якщо один операнд відсутній, він може бути упущений.
Переваги:
легке написання алгоритму;
легко перевести в асемблер ний код.
Недолік: необхідний алгоритм для зберігання в пам’яті проміжного результату.
Тріади є машинно незалежні, вимагають менше пам’яті ніж тетради.
Обернений польський запис
Перевага: ефективний для обчислення математичних виразів.
Недоліки:
необхідно використовувати стек
важко робити оптимізацію
Нехай задано арифметичний вираз виду: (A+B)*(C+D)-E
Представимо цей вираз у вигляді польського запису: AB+CD+*E-
Обернений польський запис володіє властивостями, які перетворюють його в ідеальну проміжну мову при трансляції:
1. обчислення виразу може проводитися шляхом одноразового перегляду, що зручно для генерації коду
2. отримання польського запису просто здійснити на основі алгоритму DX3.
13. Визначення формальної мови і граматики
Формальні мови - це математичний апарат, що дозволяє математично грамотно створити мови програмування і писати компілятори для них.
Формальну мову можна задати як послідовність слів. Слово – це послідовність символів. Тоді навіть програму можна вважати просто словом.
Словами даної мови може бути не довільний набір символів, а лексично і синтаксично правильно побудований. Для того, щоб задати граматику, треба задати множини термінальних і не термінальних символів.
Термінальні – це символи, які використовуються в мові, а проміжні або нетермінальні – це символи, які використовуються для створення слів мови. Створюються слова за граматичними правилами. Застосування правила полягає в заміні в перетворюваному рядку якоїсь послідовності символів, що співпадає з лівою або правою частиною правила.
Компілятор, отримавши на вхід програму, робить зворотну роботу. Він згортає за граматичними правилами від правої до лівої частини початкові символи.
Кінцева множина символів, яка є неподільною, називається словником або алфавітом, а символи, що входять в множину – буквами алфавіту. Послідовність букв алфавіту називається словом або ланцюжком цього алфавіту, число букв, що входить у слово, називається його довжиною.
Якщо задано алфавіт А, то А* - це множина всіх ланцюжків, які можна побудувати з алфавіту А. $ - порожній рядок (рядок, що не містить жодної букви) також входить в А. Для позначення всіх ланцюжків алфавіту А, що не містять порожнього використовується А+.
Формальною граматикою Г називається сукупність таких об’єктів:
Г={VT,VN,<I>,R},
Де VT – термінальний алфавіт (словник). З букв цього алфавіту будуються ланцюжки, які породжуються граматикою.
VN – нетермінальний (допоміжний) алфавіт. Його букви використовуються при побудові ланцюжків, вони можуть входити в проміжні ланцюжки, але не можуть входити в результат побудови.
<I> - початковий символ.
R – множина правил виведення.
Множина кінцевих ланцюжків термінального алфавіту VT граматики Г, виведених з початкового символу <I> називають мовою, яка породжена граматикою Г і позначається L(Г).
Якщо правило виведення граматики мінить один нетермінальний символ, як в лівій, так і в правій частині, то таке правило називається рекурсивним.
Типи формальних граматик
Виділяють 4 типи формальних граматик. Ці граматики визначаються шляхом накладання обмежень на правила граматики.
Граматика типу 0 – граматика загального вигляду, немає обмежень на правила породження.
Граматика типу 1 – контекстно залежна.
Правило: χ1<A>χ2→ χ1ωχ2.
Ланцюжки χ1 і χ2 залишаються незмінними при застосуванні правил, тому їх називають контекстом, а граматику – контекстно залежною.
Граматика типу 2 – контекстно вільна.
Правило: <A>→α, де
.Ці правила слідують із правил граматики типу 1 за умови χ1 = χ2 = $.
Граматика типу 3 – автоматна.
Правила виведення: <A>→a або <A>→a<B> або <A>→<B>a, де
.Способи задання схем граматик
Схема граматики містить правила виведення, які визначають синтаксис мови або всі ланцюжки породженої мови. Для задання правил використовують різні форми опису:
символічна
форма Бекуса-Наура (ФБН)
ітераційна
синтаксичні діаграми
Символьна мова передбачає використання елементів нетермінального словника і стрілки, як роздільника правої і лівої частини. Але при описі конкретних мов програмування доводиться вводити велику кількість не термінальних символів і символьна форма запису втрачає свою наочність.