Разработка конвертора з текстового формату nroff в гіпертекстову формат HTML

Задание.

Розробити транслятор документів з формату nroff в формат HTML.

1. Транслятор необхідно реалізувати засобами програм lex і yacc.

2. Трансляції підлягає окремий документ. (Один файл -один документ).

3. Як тестових прикладів використовувати документи від керівництва ОС UNIX (man-файлы).

4. Як середу розробки використовувати ОС UNIX.

Нині дедалі більшого поширення знаходить використання для доступу до RISC-серверам, де працюють найпотужніші системи САПР, замість X-терминалов дешевших і навіть універсальніших персональних компьютеров.

Для зв’язок між персональними комп’ютерами і RISC-серверам використовуються програми, эмулирующие на персональному комп’ютері роботу Xтерміналів. У цьому на персональному комп’ютері, що працює під керівництвом Windows, запускається UNIX-сессия з графічним інтерфейсом користувача (GUI). Як графічного інтерфейсу придатна як будь-який з доступних на сервері графічний інтерфейс, і інтерфейс Windows.

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

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

Документація у системі UNIX представленій у вигляді про ‘manual pages'. Вона проглядається з допомогою команди системи UNIX ‘man'. У цьому викликається файл, у якому необхідну документацію. Файли, використовувані командою ‘man' написані текстовому форматі nroff, що є стандартним форматом тексту системи UNIX. Для читання цих файлів теж можна застосовувати команду UNIX ‘nroff'.

Для читання файлів, записаних в форматі ‘nroff', можна встановити персональному комп’ютері жодну з UNIX-подобных систем і, скопіювавши документацію на персонального комп’ютера, читати її з допомогою коштів системи. Та заодно втрачається одне з найважливіших переваг використання самого персонального комп’ютера — його універсальність, оскільки стане або зовсім неможливо використання програм, працюючих під керівництвом Windows (у разі повну заміну ОС), або їхнього використання знадобиться перезавантаження комп’ютера (у разі установки двох операційними системами однією компьютере).

Інший шлях полягає у перетворення файлів документації системи UNIX з формату nroff у будь-якій формат, читання якого можливо на персональному комп’ютері. Постає питання, який формат вибрати. До цього формату пред’являються такі требования:

. Тексти, записані обраному форматі, мають бути доступними для читання, принаймні, на персональному комп’ютері під управлением.

Windows. Бажано також, щоб ці тексти можна було переглядати і сервері під керівництвом UNIX.

. Тексти повинні зберігати форматування, те що в документах.

‘manual pages'. Звісно ж, що оптимальною буде вибір формату HTML. Цей формат проглядається з допомогою програм, версії яких працюють як під управлінням Windows, і під керівництвом UNIX. Формат HTML підтримує широкі можливості форматування. З іншого боку, цей формат є стандартним форматом для документів у світовій системі Internet, бо як говорилося, проблема, яка викликала необхідність перенесення частини завдань із серверу на персонального комп’ютера, набуває найбільшу гостроту саме під час зв’язку між сервером і робочим місцем користувача у вигляді Internet. Використовуючи формат HTML, можна зробити документацію, перетворену з ‘manual pages' UNIX, загальнодоступною, помістивши її в з вузлів мережі Internet. І останнє - цей формат є відкритим, в на відміну від більшості форматів тексту на персональні комп’ютери під управлінням Windows, як-от, наприклад, формат тестового редактора Word, що робить її зручним від використання, оскільки тексти у відкритих форматах легко створювати й редагувати при мінімальної ймовірності виникнення ошибки.

Є кілька шляхів розв’язання проблеми. Нині створено программы-трансляторы з формату nroff в формат HTML. Усі вони теж мають свої переваги та недостатки.

Розглянемо кілька існуючих программ.

1.Программа «nroff2HTML «(автор — Р. Ричи).

Програма написана мовою «З », працює під керівництвом ОС «UNIX ». При конвертації вставляє до тексту кінцевого файла обов’язкові теги формату HTML (такі, як, ,) і далі копіює попередньо отформатированный з допомогою програми nroff текст, Помістивши його в в пару тэгов .

2. Програма «man2html », що входить у GUI * «Gnome » .

Програма написана мовою «З », працює під керівництвом ОС «Linux », тісно інтегрована з GUI (графічний користувальницький інтерфейс) «GNOME » .

Ця програма не з реальними файлами, а постає як фільтр при виведення тексту з допомогою програми man на екран комп’ютера, перенаправляючи висновок у вікно HTML-броузера і забезпечуючи його за цьому всіма можливими командами, необхідні форматування. Отриманий на екрані текст виглядає найкраще, т.к. у ньому збережено всі необхідні види форматування і підтримуються перехресні посилання. Але програма не може працювати без пакета «GNOME », до роботи якого, своєю чергою, необхідна ОС «Linux » .

Жодна з цих програм не задовольняє наших вимог, оскільки, по-перше, слід зберігати максимально повний обсяг форматування, домігшись переносимості програми розвитку й максимальної її незалежності він наповнення операційній среды.

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

За умовами технічного завдання програма повинна функціонувати у обчислювальних системах під керівництвом ОС «Unix «і сумісних із нею («Linux »). Проблема у цьому, що виконувані файли ОС «UNIX «може бути неработоспособны серед «Linux ». У той самий час, частина з UNIX-подобных систем поставляються користувачеві як текстів вихідних файлів (исходников), виділені на компілювання. Також і у разі можна передавати програму вигляді исходников, наділених програмою компіляції. Це одного боку, підвищить перенесення програми, з другого — дозволить вносити досить досвідченому користувачеві необхідні поправки і коригування, розширюючи можливості транслятора в відповідність до потребами користувача. У цьому необхідною умовою стає написання програми з допомогою засобів, які були присутні в будь-який UNIX-подобной ОС.

Першим очевидним елементом, присутнім переважають у всіх таких ОС, є компілятор мови «З », у якому, власне, і написана ОС «UNIX ». Але мова «З «досить складним розумом і в повному обсязі користувачі обізнаний із ним. У той самий час, в ОС «UNIX «існують інші засоби написання програм: це генератори програм LEX і YACC. Опис їх команд настільки це й логічно, що дозволяє вносити корективи в існуючу програму які мають спеціальної підготовки, і, можливо, навіть будучи знайомим з описом цих коштів, маючи лише сам віршик вихідної программы.

Nroff.

Nroff використовується для форматування тексту в операційній системі UNIX при виведення на екран монітора чи принтер. Має досить прості команди, які й далі рассмотрены.

Команди керувати шрифтом: .bd — bold font .ft имя_шрифта — встановлює шрифт .p.s n — встановлює розмір символа.

Команди управління сторінками: .bp — почати нове сторінку .pl — встановити довжину сторінки .pn — встановити номер сторінки .rt — вертикальний повернення для столбцов.

Команди управління текстом: .ad l (r, c, b, n) — вирівнювання тексту вліво (вправо, у центрі, по ширині, без вирівнювання). .br — наступна рядок .ce — центрування .fi — заповнення .na — немає управління текстом (no adjust) .nf — немає заповнення (no fill).

Вертикальні пропуски: .ls — перепустку рядки .sp — пространство.

— новий рядок + пропуск.

Управління рядком: .in — відступ .ll — довжина рядки .ti — тимчасовий отступ.

Вже встановлені перемінні: % - номер сторінки dw — день тижня (1−7) dy — день місяці mo — місяць yr — рік ln — поточна рядок .з — поточна рядок від введення .f — поточний шрифт .і - поточний відступ .j — поточна регулювання (adjustment) тексту .l — довжина строки.

Використання числових змінних: .nr R v [і] - привласнити числової перемінної R значення v з необов’язковим инкрементом і .af R з — встановити формат числової перемінної (1,01,i, I, a, A) nxвикористовувати регістр x n (xy — використовувати регістр xy — дві літери n+x — додати прибуток, та був використовувати n-(xy — відняти прибуток, та був использовать.

Використання строковых змінних: .ds R str — привласнити перемінної R вміст str .as R str — дописати str насамкінець строковой перемінної R *x — використовувати регістр x *(xy — використовувати регістр xy — дві літери w’string' - розмір строки.

Коментарі: «комментарий.

Макроси: .de xx «-початок визначення макросу Today is $ 1 the $ 2.. «-кінець визначення макросу Використання макросу: .xx Monday 14th.

Получится: Today is Monday the 14th.

HTML.

Простота документів ось у чому: текст, що потрібно обробити чи застосувати щодо нього якась агресивна дія, перебуває між так званими тэгами, відповідно який відкриває і що закриває. Загальний вид тэгов:. Наведу основні теги мови HTML. Оскільки зазвичай HTML-документ використовують у ролі Webсторінки, то подальшому замість терміна HTML-документ використовуватиметься термін Web-страница.

— текст коментарю. Існує обмеження — всередині коментарю нічого не винні розташовуватися інші елементи. Текст коментарю не виводиться браузером на екран. Також коментар можна виділяти так .

— відмітний ознака Web-сторінка. Має рідко використовувані атрибути version, lang, dir. Цей тэг допускає вкладення елементів HEAD, BODY, PLAINTEXT. Кінцевим тэгом закінчуються всі гіпертекстові документы.

— область заголовка Webсторінки, служить для формування спільної структури документа. Цей елемент може мати атрибути lang, dir і допускає вкладення елементів TITLE, ISINDEX, BASE, META, LINK, NEXTID.

— елемент розміщувати заголовка Webсторінки. Рядок тексту, розташована всередині, відображається над документі, а заголовку вікна броузера.

— опис стилю деяких елементів Webсторінки. Наприклад, елемент H2 {font-family: Arial;} визначає стиль шрифту в елементі H2.

— укладає у собі гіпертекст, який власне визначає Web-страницу, отображаемую броузером. Всередині цієї елемента можна використовувати усі елементи, призначені для дизайну Webсторінки. Усередині стартового тэга можна розташовувати ряд атрибутів, які забезпечують установки для всієї сторінки повністю. Атрибути: background="Путь до файлу фону" bgcolor="#RRGGBB" - тут три 2-разрядных 16-ричных числа, які визначають інтенсивність червоного, зеленого і синього квітів. text="#RRGGBB" - колір тексту сторінки link="#RRGGBB" - колір гіперпосилання vlink="#RRGGBB" - колір використаних гіперпосилань alink="#RRGGBB" - колір останньої обраної користувачем ссылки.

— елемент заголовка. Існує 6 рівнів заголовків, які позначаються H1. H6. Заголовок рівня 1 — найбільший, рівень 6 — найменший. І тому елемента можна використовувати атрибут, ставить вирівнювання вліво, у центрі чи вправо: align="left" («center», «right»).

— горизонтальна лінія. Цей елемент немає кінцевого тэга, але допускає ряд атрибутів: align="left" («center», «right», «justify») — вирівнювання вліво, по центру, вправо, по ширині. size=толщина в пикселях — товщина лінії width=длина в пикселях width=длина у відсотках% color="Цвет" Варіюючи параметри довжини і товщини можна представляти лінію як прямоугольника.

— гіперпосилання. Приватний випадок — шаблон до створення меток:

— елемент до створення базового адреси (UR) для ссылок.

Далі розглянуті елементи, що стосуються безпосередньо до форматування тексту, тобто саме те, що буде треба для розробки программы-транслятора.

— елемент абзацу (paragraph). У принципі так дозволяє використовувати лише початковий тэг, оскільки наступний елемент Р позначає кінець попереднього і почав наступного абзацу. Разом з цим елементом використовуються атрибути: align="left" («center», «right»).

— елемент, який би примусовий перехід нові рядок. Має лише стартовий тэг. Рядок закінчується місці його размещения.

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

— елемент для позначення тексту, отформатированного заздалегідь (preformatted).

— позначення цитати. Цей елемент вимагає наявності кінцевого тэга. Текст не зазнає жодних змін, але абзац розташовується з відступом. Нині існує скорочена написання цього елемента: BQ.

— елемент для центрирования тексту, а точніше будь-якого вмісту. Прийнято, коли може бути використовувати натомість елемента атрибут align="center".

— елемент, схожий подібний до попереднього, дозволяє вирівнювати вміст із лівого, правому краю чи з центру. І тому стартовий тэг мусить мати атрибут: align="left" («center», «right»).

— виділення тексту напівжирним шрифтом.

— збільшений розмір шрифта.

— зменшений розмір шрифта.

— виділення тексту курсивом.

і - елементи, які позначають промовистість (emphasis) фрагмента тексту й визначення чогось (definition). Обидва елемента аналогічні за своєю дією елементу I, тобто у більшості випадків дозволяють виділити текст курсивом. Вона має сенс, коли необхідно однаково виділити фрагменти тексту у різних частинах документа.

— елемент, що означає текст телетайпа (teletype).

— елемент, створює перекреслене накреслення тексту. Нині його заміняють простішим .

— підкреслена накреслення текста.

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

— елемент, створює ефект нижнього індексу (subscript).

— елемент, створює ефект верхнього індексу (superscript).

— елемент, готовий до створення тексту з конструкціями HTML, які мають сприйматися саме як текст, ніж як команди для броузера. Усі теги, укладені цей елемент, сприйматимуться лише як довільні символы.

і - елементи, призначені висновку фрагментів програм. CODE використовується для форматування тексту програми. SAMP передбачається задіяти при ілюстрації прикладів (sample) виведення даних на екран. VAR створили для виділення змінних (variables).

— цей елемент призначений для вказівки тексту, який користувач повинен запровадити з клавіатури (keyboard).

— передбачається, що це елемент то, можливо використаний форматування цитат і заслань у звичайному цього слова. Текст, на нього, виводиться за умовчанням курсивом.

— подібно попередньому елементу, цей елемент відрізняється лише передбачених содержанием.

— елемент, визначальний базовий (основний) розмір шрифту. Усередині елемента необхідно вказати атрибут: size=Базовый розмір шрифту — його величина може лежати в краю від 1 до 7. За умовчанням використовується величина 3. Установка, виконувана цим елементом, має значення для елемента FONT, що дозволяє ставити відносний розмір шрифта.

— визначення типу, розміру й кольору шрифту. Всі ці характеристики визначаються з допомогою відповідних атрибутів. Наприклад, абсолютна величина шрифту задається з допомогою атрибута: size=абсолютный розмір шрифту — цей атрибут може приймати значення від 1 до 7. Також розмір шрифту може задаватися щодо базового: size=+число (-число) Атрибут кольору: color="Цвет" Тип шрифту: face="название шрифта".

Також у HTML можна використовувати таблиці, списки, посилання, малюнки, різноманітні форми, і навіть які підключаються апплеты та інших елементи. Але оскільки nroff підтримувати не може подібні елементи, де вони розглядаються у цій роботі. Докладніше дізнатися них можна в літературі, присвяченій HTML.

Вигляд документа у різних форматах.

Для наочності наведу приклад текстового документу з різними прийомами форматування тексту, та був подам їх у обох аналізованих форматах (nroff і HTML).

Результуючий текст (той, який хочемо бачити на экране):

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

Тут показані деякі можливості форматування текста.

Пропуск строки.

Фундаментальна обізнаність із розташуванням текста:

Вирівняти із лівого краю.

Вирівняти по центру.

Вирівняти по правому краю.

Є й команди, дозволяють працювати з шрифтами:

Звичайний шрифт.

Інший (викликаний) шрифт.

Підкреслений текст.

Підкреслений отцентрированный текст.

Уявімо тепер цей текст в форматі nroff.

.ft Times New Roman.

.ad l.

.nf.

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

.br.

Тут показані деякі можливості форматування текста.

.sp.

Пропуск строки.

.sp.

Фундаментальна обізнаність із розташуванням текста:

.ad l.

Вирівняти із лівого краю.

.ad c.

Вирівняти по центру.

.ad r.

Вирівняти по правому краю.

.br.

Є й команди, дозволяють працювати з шрифтами:

.br.

Звичайний шрифт.

.br.

.ft Arial.

Інший (викликаний) шрифт.

.ft Times New Roman.

.br.

.ul 1.

Підкреслений текст.

.ce 1.

.ul 1.

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

.ft Times New Roman — установка для документа певного шрифту (а його тимчасова зміна на шрифт Arial).

.ad l (з, r) — вирівнювання тексту із лівого краю (центру, правому краю).

.sp — перепустку строки.

.br — початок нової строки.

.ul 1 — підкреслення наступній (однієї) строки.

.ce 1 — центрування наступній (однієї) строки.

Це найпростіший приклад, у принципі, можливості формату nroff значно ширше. Використовуючи весь набір команд nroff, можна досить повно застосовувати різні кошти та прийоми форматування тексту. Нині ж уявімо хоча б документ, але вже форматі HTML.

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

Тут показані деякі можливості форматування тексту.

Пропуск строки.

Фундаментальна обізнаність із розташуванням текста:

Вирівняти із лівого краю.

Вирівняти по центру.

Вирівняти по правому краю.

Є й команди, дозволяють працювати з шрифтами:

Звичайний шрифт.

Другой (вызванный)шрифт.

Підкреслений текст.

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

… — ці теги свідчать, що ми маємо справу з документом в форматі HTML.

… — між тими тэгами перебувають усі команди, і навіть текст HTML-документа.

— початок нової строки.

… — початок і поклала край нового абзацу align="left" (center, right) — використовується для вказівки типу вирівнювання тексту: із лівого краю, центру чи правому краю.

… — між тими тэгами текст виводиться іншим шрифтом, зазначених у конструкції: face="font_name".

… — виводить підкреслений текст.

Аналогічно з форматом nroff, можливості HTML набагато ширше які у цьому примере.

Слід зазначити те що, у цілому формат HTML багатшими формату nroff. У зв’язку з цим розробки программы-транслятора використовувалася лише не та частина HTML, що необхідно до створення конструкцій, аналогічних конструкціям створеними форматі nroff.

Контекстно-зависимые і контекстно-независимые грамматики.

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

Насамперед слід зазначити, що розрізняють дві основні типу граматик: контекстно-зависимые і контекстно-независимые.

Якщо породжує правило має наступний вид:

(A (:= (((, то породжує правило називається контекстно-зависимым, тобто заміна нетермінального символу A на послідовність (може відбутися лише у контекстах (і (. Відповідно, і граматика, що містить подібне правило, називається контекстно-зависимой.

Якщо породжує правило має вид:

A := (, де A — нетермінальний символ, а (- термінальний чи нетермінальний. Тобто, якщо ліва частина що породжує правила складається з одного нетермінального символу, який у результаті (через ряд проміжних кроків) може замінюватись на послідовність (, вартісну у правій частині, незалежно від контексту, у якому цей нетермінальний символ зустрічається, то таке правило і, граматика називаються контекстнонезависимыми.

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

Контекстно-свободные грамматики.

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

Слова з словника мови грають роль термінальних символів (терміналів). Контекстно-свободная граматика може також утримувати будь-яке кінцеве число терміналів. У мовами програмування терміналами є фактично використовувані у яких слова символи: do, else, + і т.п.

Правила граматики іноді називаються продукциями і взагалі вигляді виглядають так:

Один_нетерминал (будь-яка кінцева ланцюжок з терміналів і нетерминалов.

У цьому ланцюжок праворуч від стрілки може бути порожній. Например,.

((.

Іноді подібні правила називають эпсилон-правилами. Контекстновільна граматика може містити будь-яке кінцеве безліч продукций. У як ілюстрацію повернуся опису мови програмування. Продукція тоді виглядає так:

(IF THEN.

Одне з нетерміналів виділено як початковий нетермінал чи початковий символ, від якого повинні починатися висновки ланцюжків мови. Для мов програмування таким нетерміналом то, можливо. Зазвичай початковий символ позначають .

Отже, контекстно-свободная граматика буде задаваться:

1) кінцевим безліччю нетерминалов;

2) кінцевим безліччю терміналів, яке перетинається з безліччю нетерминалов;

3) кінцевим безліччю правил виду ((, де A — нетермінал, а (- ланцюжок терміналів і нетерміналів (можливо, порожня); нетермінал називається лівої частиною правила, а (- правої частью;

4) одним нетермінальним символом, виділеним як начального.

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

Для описи граматик часто-густо використовують спосіб записи, який отримав назву форми Бэкуса-Науэра чи БНФ. Тут символ (замінюється символом :=, на яких може вийти будь-яке число правих частин, розділених вертикальної рисою |. Тут також нетерминалы полягають у кутові скобки.

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

Послідовність деяких підстановок називається висновком. Кожна ланцюжок, яка трапляється у Висновку, називається проміжної ланцюжком цього вывода.

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

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

Дерево виведення ланцюжка контекстно-свободного мови складно описати коротко, тому покажу приклад подібного дерева.

Нехай дана наступна граматика (початковий нетермінал):

1. (ac.

2. ((.

3. (c.

4. (b.

5. (b.

6. (a.

Нехай дана ланцюжок: ac, тоді висновок виглядатиме наступним образом:

(1) ==> ac (2) ==> abc (3) ==> acbc (4) ==> acabc (5) ==> acabc (6) ==> acabac (7).

Тепер кожної з семи пронумерованих ланцюжків побудую дерево.

(1).

(2) a c.

(3) a з b.

(4) a з b з.

(5) a з b з a.

(6) a з b з.

. a.

(7) a з b a з.

. a.

Остаточний варіант дерева називається деревом виведення термінальній ланцюжка acabac.

Коли одна ланцюжок може мати кілька дерев виведення, кажуть, що відповідна граматика неоднозначна.

Отже, резюмуючи вищесказане, можна подытожить:

1. Кожній ланцюжку, виведеної у цій контекстно-свободной граматиці, відповідає одне чи кілька дерев вывода.

2. Кожному дереву відповідає чи більш выводов.

3. Кожному дереву відповідає єдиний правий й єдине лівий выводы.

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

Для будь-якого контекстно-свободного мови існує нескінченна число граматик, що породжують цю мову. Хоча більшість із цих граматик надто складні, практично інколи буває корисно мати для описи деякого мови кілька різних грамматик.

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

Нетерминалы, які породжують жодної термінальній ланцюжка, називаються безплідними чи мертвими. Вони може бути усунуто від граматики з усіма правилами, у яких входят.

Нетерминалы, які з’являються в жодній ланцюжку, виведеної із початкового символу, називаються недосяжними нетерминалами.

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

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

Якщо всі символи правій частині правила продуктивні, то продуктивний і символ, котрий у її лівої части.

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

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

Властивості мови, які у керівництві описуються граматикою, прийнято називати синтаксичними чи граматичними властивостями, а властивості, які граматикою не описуються — семантичними властивостями. У посібнику з мови семантичні властивості описуються зазвичай на природному языке.

Створення программы-транслятора.

Для написання программы-транслятора файлів з формату nroff в файли формату HTML ми будемо використовувати генератор програм lex, компілятор компіляторів yacc, і навіть стандартний компілятор мови Сі cc.

Процедура створення програми наступна. Спочатку слід описати лексичні правила нашої конкретного завдання чи, кажучи іншими словами, написати лексичний аналізатор. Отриманий файл, який називається nroff2html. lex, ми пропускаємо через lex у результаті отримуємо на виході файл безпосередньо з ім'ям lex.yy.c (безпосередньо лексичний анализатор).

На наступний етап створюємо файл, описує граматику нашої завдання, тобто пишемо граматичний аналізатор. Отриманий файл, який називається nroff2html. yacc, ми подаємо в компілятор компіляторів yacc разом з файлом lex.yy.c. На виході yacc ми матимемо два файла ytab. c (безпосередньо граматичний аналізатор) і y. output (структура правил грамматического анализатора).

Наступним етапом буде створення виконуваного модуля. Виробляється спільне компіляція файлів lex.yy.c, y.tab.c і стандартних библиотек.

Порядок роботи з программой-транслятором nroff2html такий: на вхід програми подається текстовий файл в форматі nroff, але в виході одержуємо текстовий файл в форматі HTML.

Конкретні кроки розробки транслятора.

Для побудови конвертора обраний наступний підхід: Спочатку, з допомогою генератора програм «Lex «будується лексичний аналізатор. У завдання лексичного аналізатора входить повне поглинання вхідного файла (потоку) і передачі в синтаксичний аналізатор знайдених лексем, деяких необхідних даних (наприклад, можна знайти лексема. NUMBER, а ролі даних передається числове значення знайденого числа чи цифри). Лексеми, які у специфікації лексичного аналізатора повинні повністю описувати всіх можливих набори символів. Синтаксичний ж аналізатор будується з допомогою генератора програм YACC. У синтаксичному аналізаторі з допомогою высокоуровневых правил повністю описується структура вхідного потоку. Правила може бути рекурсивними, тобто може існувати правило, елементом якого є він сам. Першим правилом синтаксичного аналізатора зазвичай вибирається таке, який повністю описує будь-який можливий вхідний файл.

При аналізі вхідного тексту лексичним аналізатором прийнято такі припущення: 1. Передбачається, що це команди nroff розпочинаються з крапки й містять не більше двох літер латинського алфавіту. 2. Будь-яка рядок, яка має на початку точки, є рядком тексту. 3. Порожня рядок (яка містить ніяких символів, крім кінця рядки) означає команду «Переклад рядки «та виведення порожній рядки. 4. За командою може вийти чи більш пробельный символ і аргумент. 5. Після аргументу остаточно рядки може вийти нуль, чи більш пробельный символ. 6. Аргумент то, можливо рядком, символом чи цифрой.

Лексичний аналізатор розбирає вхідний потік так: 1. У початковому стані зчитується перший символ з потоку. а) Якщо символ є точкою, то аналізатор перетворюється на стан очікування команди. б) Інакше передбачається, що взятий перший символ з текстовій рядки. Аналізатор перетворюється на стан прийому тексту, причому при наступному дії узяті з потоку дані додасться до символу, що у буфері - так забезпечується цілісність тексту. в) Якщо ж символ взяти зірвалася — зустріли порожня рядок — то синтаксичному аналізатору передається лексема, що означає порожню строку.

2. У стані прийому тексту рядок із потоку приймається повністю, до символу кінця рядки. Лексичний аналізатор повертає синтаксичному аналізатору лексему, яка б означала текст, попередньо перейшовши в початкова состояние.

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

4. Передбачається, що аргументи команд може бути трьох типів — слово (наприклад, назва шрифту команда .ft); символьний (наприклад, тип вирівнювання команда .ad) чи числової (наприклад, кількість рядків команди .br). Після визначення лексеми, лексичепский аналізатор переходить в початкова стан і передає лексему синтаксичному аналізатору. а) Слід враховувати, що лексичний аналізатор, зведений будинок із допомогою генератора програм Lex, приймаючи символи, бере їх усе своєю чергою прямування правил, а вибирає правило, що задовольнить найбільшої довжині прийнятої рядки. Тому лексичний аналізатор визначить аргумент як символьний лише тоді, якщо його містить лише одне символ. б) У протилежному разі аргумент окреслюється слово. в) Якщо аргумент складається з однієї й більш цифр, він передається як число.

Для передачі (текст, що міститься у рядку; значення аргументів) використовується текстовий буфер (масив символів yytext[]), в який записує лічені з потоку дані лексичний аналізатор, побудований з допомогою lex і котрі можуть використовуватися будь-який функцією, т.к. є зовнішньої переменной.

Єдиним умовою, накладываемым на програми, створені при допомоги взаємодії генераторів програм lex і yacc, є необхідність повній відповідності в назві лексем, які повернуться лексичним аналізатором, і добре описані у розділі оголошень синтаксичного аналізатора директивою %token.

Користувач ні перевизначати таких функцій, як input (), output© і unput©, т.к. їх використовують аналізатором та його перевизначення можуть призвести до ошибке.

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

1. Якщо синтаксичний аналізатор одержує вигоду від лексичного аналізатора лексему «текст », він виводить в вихідний потік вміст буфера yytext. 2. Якщо отримана лексема «порожня рядок », то вихідний потік виводиться тэг HTML. 3. Якщо отримана лексема, відповідна одній з команд, то, можливо, запитує лексема аргументу і виконуються необхідні операции.

Оскільки переважають у всіх командах аргумент є другим елементом правила, то тут для доступу для її значенням завжди використовується псевдопеременная $ 2.

Обробка більшості команд призводить до того, що у вихідний потік записується відкриває тэг, можливе з тими чи інші аргументами. Так як формат HTML вимагає закриття тэга до його повторного відкриття, то тут для контролю закриття передбачені переменные-триггеры. Вони приймають значення, однакову одиниці, при виведення в вихідний потік відкриває тэга і щоразу перед висновком нового відкриває тэга проводиться перевірка на включення триггера. Якщо тригер включений, та над висновком стартового тэга виведуть закриває тэг.

У форматі nroff прийнята таку систему команд, коли він у більшості команд аргументом є кількість рядків, куди буде поширяться дію цієї команди. У HTML ж область дії команди визначається місцезнаходженням відкриває і закриваючого тэгов. А, що визначити місце виведення закриваючого тэга, запроваджені переміннілічильники. У час отримання команди їм присвоюється значення аргументу, і потім вона зменшується при виведення в вихідний потік черговий порції тексту. При досягненні лічильником значення «нуль », в вихідний потік виводиться закриває тэг. Якщо значення лічильника менше нуля, це отже, що він зараз неактивен.

Для виведення в вихідний потік тэга — команда перекладу рядки — застосовується спеціальна функція breakline (). Необхідність такої кроку зумовлена тим, що у nroff існує команда " .ls ", що визначає, скільки порожніх рядків виводиться за командою " .br «(аналогом якої є ярлик). По прибутті лексеми, відповідної команді «.ls «значення її аргументу присвоюється перемінної LS, що визначає скільки вже разів поспіль виведеться тэг в вихідний файл.

Особливо слід обумовити обробку команди nroff " .ex ". З отриманням лексеми, відповідної команди, синтаксичний аналізатор завершує своєї роботи, повертаючи в головну функцію значення «0 », яке свідчить нормальному завершенні работы.

LEX.

Lex (CP) — це генератор програм, виділені на лексичній обробки вхідного потоку символів. На вхід подається высокоуровневая проблемно-орієнтована специфікація виділення символьних рядків, на виході виходить програма мовою Сі для розпізнавання регулярних висловів. Регулярні висловлювання задаються користувачем у вхідний специфікації для построителя. Побудована за допомогою lex програма шукає у вхідному потоці регулярні висловлювання й розбиває його за рядки, задовольняють специфікації. Після закінчення розпізнавання ланцюжка символів виконуються поставлені користувачем фрагменти програми. У вихідному файлі для lex встановлюється зв’язок між регулярними висловлюваннями і фрагментами програмного коду. За появи на вході згенерованої програми деякого регулярного висловлювання виконується відповідний фрагмент.

Для повного оформлення завдання користувач задає додаткові частини програми, включаючи підготовлені іншими генераторами. Програмараспознаватель генерується як фрагментів програм мовою Сі. lex не є закінченим мовою, це лише генератор, що доповнює мову Сі новими возможностями.

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

Регулярні выражения.

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

До управляючим ставляться такі символы:

" []^?.*+|()$/{}%.

Якщо якісь із перелічених символів потрібно використовувати як звичайні, його потрібно екранувати або індивідуально з допомогою зворотної дробової риси (), або у формі послідовності, укладаючи в лапки. Лапки вказують, що у них рядок має як текстові символи. Екрануватися може і частина рядки. Екранування текстових символів необов’язково, хоча ніякої шкоди не приносит.

Механізм екранізування корисний й за необхідності вставки в регулярне вираз символу прогалини. Зазвичай прогалини чи табуляції завершують правила. Будь-які прогалини, не які у дужках, повинні екрануватися. Розпізнаються також кілька спеціальних послідовностей мови Си:

n переклад строки.

t табуляция.

b крок назад.

зворотна подрібнена черта.

Позаяк у вираженні переклад рядки неприпустимий, він має екрануватися. Зауважте, що кожен символ завжди є текстовим. Виняток становлять прогалини, табуляції, переклади рядки — і наведені вище управляючі символы.

Запуск программы.

При компіляції вихідної програми можна назвати два кроку. По-перше, вихідний файл може бути перетворений на сгенерированную програму мовою високого рівня. Потім цю програму компілюється і компонується, зазвичай разом із бібліотекою підпрограм lex. Сгенерированная програма поміщається в файл lex.yy.c. У конкурсній програмі можна використовувати стандартна бібліотека виводу-введення-висновку мови Сі. Результуючий вектор програма міститься у файл a. out і може згодом бути выполнена.

Класи символов.

Класи символів задаються з допомогою квадратних скобок. Конструкция:

[abc] задовольняє одному символу з багатьох a, b, з. Усередині скобок більшість операторів ігнорується. Спеціальними є лише три: зворотна подрібнена риса (), мінус (-) і стрілка вгору (^). Мінус визначає діапазон символів, например:

[a-z0−9_] визначає клас символів, що з малих літер літер, цифр, кутових скобок і знака підкреслення. Діапазони можуть задаватися у кожному порядке.

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

[-+0−9] задовольняють всім цифр і знакам плюс і минус.

При визначенні класів оператор ^ має бути першим символом після що відкриває дужки, вказує, що отримана рядок повинна розглядатися як виключення з всього безлічі символів ЕОМ. Таким образом.

[^abc] задовольняє всім символів, крім a, b і з, зокрема всі спеціальні та управляючі символи, а.

[^a-zA-Z] задовольняє кожному символу, котрий є буквою. Зворотний подрібнена риса ж виконує функцію экранирующей послідовності нічого для будь-якого символу на квадратних дужках, який, якщо проти нього стоїть зворотна подрібнена риса, розглядається буквально.

Завдання довільних символов.

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

[40−176] задовольняє всім печатаемым символів коду ASCII, від восьмеричного 40 (прогалину) до 176 (риса сверху).

Задание вариантов.

Знак питання означає варіант в регулярному вираженні. Наприклад ab? c задовольняє або ab чи abc.

Указание повторений.

Повторювані класи вказуються операторами * і +. Наприклад, a* задовольняє кожному кількості (включаючи 0) послідовно які йдуть символів a, тоді, як a+ задовольняє одній або кільком символів. Например,.

[a-z]+ задовольняє всім рядкам з малих літер літер, а.

[A-Za-z][A-Za-z0−9]* задовольняє всім алфавитно-цифровым рядкам, начинающимся з буквы.

Альтернативи і группирование.

Вертикальна риса вказує альтернативи. Например,.

(ab|cd) задовольняє або ab або cd. Для групування застосовуються дужки, хоча верхньому рівні, вони не обов’язкові. Наприклад ab| cd аналогічно попередньому прикладу. Дужки використовується ще складних висловів, например

(ab|cd+)?(ef)* задовольняє таким рядкам, як abefef, efefef, cdef і cddd, але з abc, abcd чи abcdef.

Чутливість до контексту.

Lex розпізнає обмежений обсяг навколишнього контексту. Два найпростіших оператора — ^ і $. Якщо першим символом висловлювання зазначений^, воно буде задовольнятися при розташуванні на початку рядки (після символу перекладу рядки або на початку вхідного потоку). Такий сенс який суперечить значенням цього символу при завданні класів, позаяк у цьому випадку вказується всередині квадратних скобок. Якщо останнім символом висловлювання служить $, вираз буде задовольнятися під час перебування наприкінці рядки. Останній оператор — окреме питання загальнішого оператора /, задає правий контекст. Вислів ab/cd задовольняє рядку ab в тому разі, якщо на ній варто cd. Отже ab$ аналогічно ab/n.

Задание повторюваних выражений.

Фігурні дужки задають або повторення (якщо всередині цифри), або визначення підстановки (якщо всередині ім'я). Например

{digit} шукає заздалегідь визначену рядок безпосередньо з ім'ям digit і вставляє їх у заданої точці. А вираз a{1,5} шукає від однієї до п’яти входжень символу a.

Завдання определений.

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

Завдання действий.

Якщо вираз задовольняє деякому фрагмента який вводимо тексту, lex виконує відповідне дію. У розділі описуються деякі особливості, які допомагають під час написання дій. Існує дія з вмовчанням, що полягає в копіюванні вхідного потоку в вихідний. Копіювання піддаються рядки, не удовлетворившие правилам. Отже, для поглинання всього вхідного потоку потрібно поставити вираз, що задовольнить всім символів. З використанням lex що з yacc це вважається нормальним ситуацією. Можете розглядати копіювання як деяке дію, що можна не указывать.

Один із найпростіших дій — ігнорування вхідного потоку. Це виконується з допомогою порожнього оператора Сі (;).

Ще одна спосіб уникнути завдання дій — символ повторення (|), який би, що дія цього правила аналогічно дії для последующего.

Іноді правила некоректно розпізнають символи межах вхідного потоку. З цією ситуації зручні дві функції. Yymore () вказує, що таке вхідний вираз має поміщатися насамкінець хіба що знайденого. Зазвичай таке вираз затирає поточне вміст yytext. Yyless (n) викликається тоді, як у цей час потрібні в усіх символи, удовлетворившие поточному правилу. Аргумент вказує кількість символів, які повернуться у вхідний потік. Це забезпечує перегляд вперед, але у іншій формі, ніж при $.

Можна користуватися й внутрішніми функціями виводу-введення-висновку. До них относятся:

1. input () наступний символ з потока;

2. output© висновок символу на поток;

3. unput© повернення символу на поток.

За умовчанням цих функцій визначено як макроси, але користувач може, замість них використовувати власні функції. Ці функції визначають взаємозв'язок між зовнішніми файлами та внутрішньою поданням символів, тому їх модифікація мусить бути узгодженої і несуперечливої. Вони можуть перевизначатися для введення та виведення у внутрішнє пам’ять чи інші процеси, але набір символів має бути єдиним, нульової значення, яке input (), має означати кінець файла, взаємозв'язок між input і unput має бути збережена, інакше нічого очікувати працювати перегляд вперед.

Lex не використовує не потрібні перегляд вперед, але його наводять правила, містять /, чи закінчуються однією з таких символов:

+ *? $.

Перегляд вперед також потрібен при обробці висловлювання, службовця префіксом іншого выражения.

Ще один функція, яку іноді переопределяют, — yywrap. Вона викликається під час досягнення кінця файла. Якщо вона повертає 1, виконується нормальне завершення роботи. Іноді буває зручно організувати додатковий введення з іншого джерела. І тут користувач пише свою версію цієї функції, що виконує новий введення і повертає 0. Це призводить до продовження обробки. За умовчанням yywrap завжди повертає 1.

Ця функція — зручний момент в організацію виведення таблиць, підсумкових довідок тощо. після досягнення кінця програми. Зверніть увагу, що написати звичайне правило, распознающее кінець файла, неможливо, єдиний спосіб — функція yywrap. До речі, без переробки функції input () неможливо обробити файл, у якому нулі, оскільки возвращаемый цієї функцією 0 є ознакою кінця файла.

Обробка неоднозначних правил.

Lex може обробляти неоднозначні правила. Коли запроваджувана рядок задовольняє більш, ніж одному вираженню, здійснюється наступний выбор:

* Вибирається найдовша последовательность.

* З усіх підхожих правил вибирається первое.

Вхідний потік зазвичай розбивається на частини отже lex не шукає все можливі входження всіх висловів. Кожен символ вважається сам і лише один раз.

Деколи це неприйнятно. Дія REJECT означає перехід до наступній альтернативі. Воно призводить до виконання правила, який би наступним. Позиція покажчика у вхідному потоці встановлюється відповідним чином. У випадку, дію REJECT корисно, коли завданням служить не розбивка вхідного потоку, а виявлення всіх входжень деякого висловлювання (іноді перекрывающихся) у вхідному потоці. REJECT не здійснює повторного перегляду. Натомість запам’ятовується результат попереднього перегляду. Це означає, що й знайдено правило з правим контекстом і виконано дію REJECT, забороняється використовувати unput для зміни символів, надходили з вхідного потоку. Це єдине обмеження, накладываемое на маніпуляції ще обробленою вхідний информацией.

Чутливість до лівого контексту.

Іноді бажано мати кілька наборів лексичних правил, в час застосовуваних до вхідному потоку. Наприклад, препроцесор компілятора повинен виділяти директиви препроцесора і аналізувати їх інакше, ніж оператори мови. Це чутливості до попередньому контексту. Є кілька способів вирішення цієї проблеми. Оператор ^ розпізнає безпосередньо попередній лівий контекст, як і, як і $ розпізнає безпосередньо наступний правий контекст. Безпосередньо примикає лівий контекст міг бути розширено за аналогією з правим, але навряд це буде корисним, оскільки необхідний лівий контекст часто перебуває трохи раніше, наприклад, на початку строки.

Існує три способу обробки, використовувані у різних условиях:

1. Застосування прапорів (за зміни умов правила змінюються незначительно).

2. Використання початкових состояний.

3. Використання кількох лексичних аналізаторів, працюючих одновременно.

У кожному разі, існують правила, розпізнавальні необхідність зміни умов, у яких буде аналізуватися текст, і встановлюють ряд параметрів для фіксації змінених умов. Це то, можливо, наприклад, прапор, проверяемый в користувальних діях. Це найбільш найпростіший спосіб виконання завдання, оскільки lex тут не бере участь. Може бути зручним запам’ятати прапори як початкових станів правил. З початковим станом може пов’язуватися будь-яке правило. Вона буде застосовуватися лише у тому випадку, коли lex перебуває у цьому стані. Поточне початкова стан то, можливо змінено у час. І, насамкінець, якщо набори правил щодо різноманітних станів дуже відрізняються, більш ясним підходом було б написання кількох окремих аналізаторів, переключаемых при необходимости.

Завдання определений.

Розглянемо загальний формат вхідний спецификации:

{определения}.

{програми пользователя}.

На сьогодні ми описали лише правила. Слід також визначити перемінні як програми, так lex. Це можна зробити як і розділі визначень, і у розділі правил.

Правила перетворюються на програму. Будь-який фрагмент вхідний специфікації, не интерпретируемый lex, копіюється в генерируемую програму. Ці фрагменти можна розділити втричі класса:

1. Будь-яка рядок, яка є частиною правила чи дії, і начинающаяся з прогалини чи табуляції, копіюється в генерируемую програму. Якщо рядки перебувають перед першим символом %%, вони зовнішніми по відношення до будь-який функції. Якщо вони самі перебувають у розділі правил, вони ставитися до згенерованої функції. Рядки повинні скидатися на фрагменти програми розвитку й поміщатися на початок описи правил.

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

2. Весь текст між символами %{ і %} також копіюється. Обмежувачі відкидаються. Цей формат дозволяє вводити оператори препроцесора, що розпочинаються У першій позиції, і навіть рядки, мало схожі на програмний код.

3. Весь текст після третього обмежника %% копіюється в генерируемую программу.

Визначення, призначені для lex, поміщаються перед першим обмежувачем %%. Будь-яка рядок цього розділу, не які перебувають всередині %{ %} і начинающаяся з позиції 1, вважається рядком підстановки. Її формат наступний: ім'я подстановка.

Цепочкам з частини підстановки присвоюється ім'я. Ім'я і підстановка повинні розділятися принаймні одним прогалиною й ім'я має починатися з літери. Підстановка викликається у правилі з допомогою конструкції {имя}.

Згенеровані програми виконують вхід-видобуток символів тільки з допомогою функцій input (), output () і unput (). Що Використовується у тих функціях уявлення символів сприймається lex і передається як яке значення в масиві yytext. При внутрішньому вживанні символ представлений невеликим цілим числом, і за використанні стандартної бібліотеки введеннявиведення його значення одно цілому, відповідному набору бітов при цьому символу на ЕОМ. Зазвичай символ a представлений як і, як і символьна константа:

" a «.

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

{ціле} {символьна строка}.

Рядки пов’язують із символом відповідне значение.

Формат вхідного текста.

Загальний формат вхідного тексту следующий:

{определения}.

{підпрограми пользователя}.

Розділ визначень може містити таку информацию:

1. Визначення як «ім'я прогалину значення » .

2. Включаемый фрагмент як «прогалину фрагмент » .

3. Включаемый фрагмент в виде.

%{ фрагмент.

%}.

4. Початкові стану в виде.

%P.S имя1 имя2 имя3 …

5. Таблиці наборів символів в виде.

%T число прогалину рядок символов.

%T.

6. Модифікація розмірів внутрішніх таблиць в виде.

%x nnn де nnn — десяткове число, відповідне розміру масиву, а x — параметр наступного вида:

Символ Параметр p позиції n стану e вузли дерева a переходи k упаковані символьні класи o розмір вихідного массива.

Рядки розділ правил мають наступний формат: вираз действие.

Дія може тривати досить наступних рядок, його обмежують фігурні скобки.

У регулярних висловлюваннях припустимі такі оператори: x Символ x. x Завжди x, навіть якщо це оператор.

x Завжди x, навіть якщо це оператор

[xy] Символи x чи y.

[x-z] СИмволы x, y чи z.

[^x} Будь-який символ крім x.

. Будь-який символ крім перекладу строки.

^x Символ x на початку рядки. x Символ x, якщо lex перебуває у стані. x$ Символ x наприкінці рядки. x? Необов’язковий x. x* 0, 1, 2 … входжень x. x+ 1, 2, 3 … входжень x. x|y x чи y.

(x) x. x/y x котрого супроводжує y.

{xx} Підстановка xx із розділу визначень. x{m, n} Кількість входжень x — від m до n.

YACC.

Зазвичай вхідні інформація, читаемая програмою, завжди має деякою структурою. І про програму, читаючу вхідний потік ми можемо сказати, що вона ставить певний вхідний мову. Вхідний мову може бути чи складним, як мову програмування, або простим, выглядящим як послідовність чисел. Але, на жаль, звичайні кошти введення обмежені за можливостями, важкі у використанні та найчастіше містять механізмів перевірки корректности.

Yacc (CP) є універсальний інструмент для описи вхідного потоку програм. Це ім'я є скороченням фрази «yet another compiler compiler» («іще одна компілятор компіляторів»). Користувач задає як структуру вхідного потоку, і фрагменти програм, що викликаються при розпізнаванні об'єктів серед. Компілятор компіляторів (чи генератор програм синтаксичного розбору, далі просто генератор) переводить специфікацію в деяку підпрограму, управляючу процесом введення. Часто виявляється зручним здійснювати управління користувальницької завданням з допомогою цієї подпрограммы.

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

Генератор використовують як і розробити компіляторів широко поширених мов (мови Сі, Паскаль тощо.), так нетрадиційних додатків (мову управління фотонаборной установкою, мови настільних калькуляторів, система доступу до документів, отладчик Фортрана).

Генератор надає широкі змогу завдання структури вхідного потоку програми. Користувач yacc задає специфікацію, управляючу процесом введення, до якої належить правила для описи структури потоку, фрагменти програм, викликані при розпізнаванні цих правил, низькорівневі функції до виконання первинного введення. З цієї специфікації генератор будує функцію, управляючу процесом введення. Ця функція, звана синтаксичним аналізатором, викликає низкоуровневую користувальницьку підпрограму (лексичний аналізатор), виділення базових елементів (лексем) з вхідного потоку. Лексеми обробляються в відповідність до правилами, описывающими вхідний потік (граматичними правилами). При розпізнаванні такого правила викликається відповідний фрагмент користувальницької програми. Зверніть увагу, що заодно можна повертати значення, які можуть застосовуватися за іншими фрагментах.

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

Специфікації для синтаксичного аналізатора yacc.

До нетермінальним символів чи лексемам звертаються імена. Yacc вимагає безпосереднього оголошення імен лексем. На додачу, по причин, объясняемым нижче, часто бажано включення лексичного аналізатора як частини файла специфікації. Може бути корисним і включення інших програм. Отже, будь-який файл специфікації складається з трьох часток: оголошень, правив і програм. Частини (чи розділи) поділяються подвійним знаком відсотка (%%). (Символ відсотка часто застосовується у специ-фікаціях як спеціального символа.).

Інакше кажучи, повна специфікація то, можливо записана наступним чином: объявления.

программы.

Розділ оголошень то, можливо порожнім. Понад те, якщо опускається розділ програм, то другий роздільник %% годі й вказувати. Тоді мінімальна специфікація виглядає как.

%% правила.

Прогалини, табуляції і ще переклади рядків ігноруються. Вони теж можуть з’являтися в іменах чи многолитерных зарезервованих символах. Коментарі можуть з’являтися у будь-якій позиції імені, їх синтаксис збігається з синтаксисом коментарів в Си.

Розділ правил складається з однієї чи більш граматичних правил. Граматичне правило записується в формате.

A: BODY ;

A є нетерминальное ім'я, BODY — послідовність імен та литералов (можливо пустую).

Імена може бути довільній довжини й укладаються з літер, точки, підкреслення і цифр. Цифри на початку імені не допускаються. Прописні і рядкові літери вважаються різними. Імена, використовувані у тілі грамматического правила, можуть бути як лексемами, і нетерминальными символами.

Буквальний є символ, укладений у апострофи. Також, як й у Сі, зворотна подрібнена риса служить механізмом екранізування всередині литералов, розпізнаються все спеціальні послідовності мови Си:

n Переклад строки.

r Повернення каретки.

" Апостроф.

Зворотний подрібнена черта.

t Табуляция.

b Крок назад.

f Переклад формата.

xxx Восьмеричне число xxx.