Синтаксис регулярних висловів залежить від інтерпретатора, що використовується для їх обробки. Однак, із незначними відхиленнями, майже всі поширені механізми інтерпретатори регулярних висловів мають спільні правила.
Найпростіший регулярний вислів, з якого формуються складні, є звичайний символ. Більшість символів, включаючи усі літери та цифри, є регулярними висловами, що збігаються із відповідними символами в рядках.
Кожний метасимвол з особливим значенням мусить екрануватись попереду символом зворотної похилої риски.
Після регулярного вислову можна вказати один чи декілька операторів повтору (метасимволів):
.
Відповідає будь-якому символу.
?
Попередній вислів є необов'язковим і може збігтися максимум один раз.
*
Попередній вислів повинен збігтися нуль чи більше разів.
+
Попередній вислів повинен збігтись один чи більше разів.
{N}
Попередній вислів повинен збігтися рівно N разів.
{N,}
Попередній вислів повинен збігтися N чи більше разів.
{N,M}
Попередній вислів повинен збігтися не менш ніж N, однак не більше за М разів.
-
Якщо цей символ знаходиться не на початку й не в кінці списку чи інтервалу у списку, задає інтервал.
^
Відповідає початку рядка, при цьому не потребує символу. Якщо стоїть на початку списку, інвертує його (відповідає символу, якого немає у списку).
$
Відповідає кінцю рядка.
\b
Відповідає межі слова.
\B
Відповідає порожньому рядку, якщо в цьому місці не закінчується або не починається слово.
\<
Відповідає пустому рядку в початку слова.
\>
Відповідає пустому рядку в кінці слова.
Два регулярних вислови можна об'єднати. У цьому разі отриманий складний вислів буде відповідатиме рядку, що є об'єднанням двох рядків, які відповідають наведеноми регулярниму вислову.
Два регулярних вислови можна з'єднати інфіксним оператором «|»; у цьому разі складний вислів буде відповідатиме рядкам, що відповідають або першому, або другому простому регулярному вислову.
Оператори повтору мають більший пріоритет, ніж оператор об'єднання, а останній у свою чергу має більший пріоритет, ніж оператор альтернативи. Ці правила пріоритету можна змінити за допомогою круглих дужок.
Синтаксичні діаграми Мова форм Бекуса-Наура – не єдина метамова для описання структури конструкцій мов програмування. Досить поширеною є також метамова синтаксичних діаграм. В основі цієї метамови також лежать нетермінальні й термінальні символи. Але тут вони записуються у прямокутниках та колах (овалах) відповідно. Наприклад, нетермінали <A> та <оператор> позначаються так: Відповідно термінальні символи '(' таelse мають вигляд Порядок символів у метавиразах задається стрілками, наприклад: Альтернативні метавирази задаються розгалуженням стрілок. Наприклад, якщо E1, E2 – метавирази, то E1 | E2 має такий вигляд: Можливість присутності або відсутності якоїсь частини виразу задається аналогічно, тільки одна з альтернатив порожня. Наприклад, структура операторів розгалуження задається так: Фігурним дужкам {E}, які задають повторення, відповідає повернення стрілки на початок діаграми, відповідної E. Наприклад, структура непорожньої послідовності операторів задається метавиразом <оператор> { ';' <оператор>}, якому відповідає діаграма Нарешті, поняття, вказане у БНФ ліворуч від знака "::=" нетерміналом, наприклад, A, записується також ліворуч від діаграми:
4. Модель мовного транслятора. Фази мовного аналізу.
Трансля́тор (англ. translator) — програма або технічний засіб, який виконує трансляцію програми.
Транслятори поділяються на компілятори та інтерпретатори. Відмінність між ними в тому, що компілятор створює новий файл, на іншій мові (зазвичай машинній), а інтерпретатор - виконує кожну команду одразу після трансляції.
Системні і прикладні команди у виконавчому вигляді складаються з послідовності інструкцій кодованих двійковими числами кожне з яких місить двійковий код елементарної операції з одним або декількома аргументами. Аргументами можуть бути безпосередні дані, коди процесорних регістрів або адреси ОП за якими розміщенно реальні дані. Для створення програм використовується спеціальне середовище і застосовується відповідні мови програмування. Програми які перетворюють програмний код з мови програмування у будь-яку іншу мову називаються трансляторами або мовними процесорами. З точки зору режиму роботи транслятори діляться на наступні категорії:
a. Асемблери – перекладають програму з мови асемблера у машині коди. Машині коди –це форма представлення програми яку може виконувати безпосередньо ОС.
b. Інтерпретатори – програми синхронної дії які аналізують послідовно інструкції мови високого рівня і без переведення у машинні коди виконують відповідні дії.
c. Компілятори – програми які перекладають програмний текст з мови високго рівня у машині коди.
d. Препроцесори – додаток до мов високого рівня, які дозволяють покращити та розширити безпосередній початковий програмний текст самої мови.
e. Крос-компілятори- це компілятори які на потужних комп’ютерах готують виконавчий код для комп’ютерів з обмеженою памятю мікропроцесорів та мікроконтролерів.
Оскільки код програми високого рівня складається з мовних інструкцій які містять мнемонічні ключові слова з відповідними параметрами дії, то процес перекладу має таку структуру
ВП – вхідна програма, текст програми на мові високого рівня.
ЛА – лексичний аналіз, на даному етапі текст програми розбивається на елементарні мовні одиниці, такі як ключові слова, знаки операції, знак пунктуації, змінні, числові константи, текстові константи, дужки.
СА – синтаксний аналіз. На мовах високого рівня інструкції мають чітко регламентовану структуру. Лексеми в кожній структурі мають власне місце і обмежені за типом. Під час синтаксичного аналізу аналізується загальна структура суцільної програми і структура кожної інструкції. Результатом синтаксичного аналізу є розбиття програми на відповідні структурні групи.
ГПК – генерація проміжного коду. Структурні букви отримані після синтаксичного аналізу замінюються послідовностями елементарних дій, які виконують безпосередні алгоритмічні дії програми та керують загальним обчислювальним процесом.
ОК – оптимізація коду. Послідовність елементарних дій яка отримана після ГПК містить велику кількість повторних дій та використовує надлишкову пам'ять. В розділі оптимізації перестановкою, переіменуванням та арифметичними перетвореннями з послідовності елементарних дій вилучається надлишкові операції.
ГК – генерація коду. Проміжний код після оптимізації змінюється відповідними машинними інструкціями.
УТ – управління таблицями. Під час обробки програмного тексту компілятор автоматично будує і керує наступними таблицями:
1. Таблиця ідентифікаторів місить ідентифікатори, константи і змінні, їх тип і значення.
2. Таблиця допоміжних функцій, які складаються з назви функції, тип результату, кількість параметрів і адреси точок входу.
3. Таблиця проміжного коду.
4. Таблиця стекових значень для проміжних результатів.
ОП- обробка помилок. В даному блоці аналізується синтаксична структура програми, до якої входять правила використання лексем, узгодження типів даних в мовних інструкціях, узгодження операндів в елементарних інструкціях проміжного коду. Така схема відображає повний цикл компіляції
5. Представлення синтаксичної структури формальної мови. Форма Бекуса-Наура.
Форма́льна мо́ва — множина скінчених послідовностей символів, які описуються правилами певного виду, які називаються граматикою, або синтаксисом мови (див.формальна граматика).
В тому випадку, коли кожному слову формальної мови співставляється його семантика (сенс, значення, інтерпретація), формальну мову називають інтерпретованою.
Формальні мови можна класифікувати за характером формального апарату, що застосовується для їхнього описання:
Нота́ція Бе́куса—Нау́ра (англ. Backus-Naur form, BNF) є спосіб запису правил контекстно-вільної граматики, себто формою опису формальної мови.
Саме її типово використовують для запису правил мов програмування та протоколів комунікації. У 50-х роках минулого сторіччя Джон Бекус створив цю нотацію розробляючи мову ALGOL. На першому Всесвітньому Комп'ютерному Конгресі, що відбувся у Парижі 1959-го він зробив доповідь на тему "Синтаксис та семантика пропонованої першої міжнародної алгебраїчної мови". Пізніше Наур Пітер спростив її та (за порадою Дональда Кнута) додав до назви своє ім'я.
Запис
Нотація БНФ є набором «продукцій», кожна з яких відповідає зразку:
<символ> ::= <вираз, що містить символи> де вираз, що містить символи це послідовність символів або послідовності символів, розділених вертикальною рискою |, що повністю перелічують можливий вибірсимвол з лівої частини формули.
Далі,
§ < — лівий обмежувач виразу
§ > — правий обмежувач виразу
§ ::= — визначене як
§ | — або
Ці чотири символи є символами мета-мови, вони не визначені у мові, котру описують. Решта описаних символів належать до «абетки» описуваної мови.
Для прикладу подивимось на можливу нотацію BNF для поштової адреси:
<поштова-адреса> ::= <поштове-відділення> <вулична-адреса> <особа> <поштове-відділення> ::= <індекс> "," <місце> <EOL> <місце> ::= <село> | <місто> <вулична-адреса> ::= <вулиця> "," <будинок> <EOL> <особа> ::= <прізвище> <ім’я> <EOL> | <прізвище> <ім’я> <по-батькові> <EOL>
6. Представлення проміжного коду. Елементарні операції, польський запис.
Генерація проміжного коду. Відбувається перетворення вихідної програми в проміжну (наприклад, польську) форму запису.
Оптимізація проміжного коду - виділення загальних подвираженія та обчислення константних подвираженія.
Фаза оптимізації призначена для зменшення надлишковості програми за витратами часу та пам'яті. У залежності від критеріїв проектування транслятора дана фаза обробки програми може виключатися з циклу обробки програми.
