Завдання.
Розробити транслятор документів з формату nroff у формат HTML.
1. Транслятор повинен бути реалізований засобами програм lex та yacc.
2. Трансляції підлягає відокремлений документ. (Один файл-одиндокумент).
3. В якості тестових прикладів використовувати документи з керівництва
ОС UNIX (man-файли).
4. Як середовище розробки використовувати ОС UNIX.
Введення.
В даний час все більше поширення знаходить використаннядля доступу до RISC-серверів, на яких працюють найбільш потужні системи
САПР, замість X-терміналів більш дешевих і при цьому більш універсальнихперсональних комп'ютерів.
Для зв'язку між персональними комп'ютерами і RISC-серверіввикористовуються програми, емулює на персональному комп'ютері роботу X -терміналів. При цьому на персональному комп'ютері, що працює під управлінням
Windows, запускається UNIX-сесія з графічним інтерфейсом користувача
(GUI). В якості графічного інтерфейсу може використовуватися як будь-якийз доступних на сервері графічний інтерфейс, так і інтерфейс Windows.
Обсяг даних, якими обмінюються при цьому персональний комп'ютер і
RISC-сервер, досить великий. Тому нерідко виникає необхідність утому, щоб виконувати частину завдань не на віддаленому сервері, а безпосередньона персональному комп'ютері. Особливо велике значення це має в ситуації,яка виникає в останні часом все частіше - коли сервер і персональнийкомп'ютер знаходяться на великій відстані один від одного і об'єднуються міжсобою не за допомогою прямого з'єднання, як це було у випадку з X -терміналом, і навіть не за допомогою локальних мереж, а за допомогоюміжнародної мережі Internet.
Разом з тим, слід визначитися з тим, які завдання має сенспереносити на персональний комп'ютер, а які необхідно вирішувати на сервері,щоб підвищити віддачу від системи в цілому. Видається, що однією ззавдань, перенесення якої на персональний комп'ютер полегшить роботукористувача і зробить її більш зручною, може бути робота з документацією,існуючої в системі UNIX.
Документація в системі UNIX представлена у вигляді так званих 'manualpages '. Вона проглядається за допомогою команди системи 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" (автор - Р. Річі).
Програма написана на мові "C ", працює під управлінням ОС" UNIX ".
При конвертації вставляє в текст кінцевого файлу обов'язкові теги формату
HTML (такі, як,,) і потімкопіює попередньо відформотований за допомогою програми nroff текст,уклавши його в пару тегів.
2. Програма "man2html", що входить в GUI * "Gnome".
Програма написана на мові "C", працює під управлінням ОС
"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 імя_шріфта - встановлює шрифт
. ps n - встановлює розмір символу
Команди управління сторінками:
. bp - почати нову сторінку
. pl - встановити довжину сторінки
. pn - встановити номер сторінки
. rt - вертикальний повернення для стовпців < p> Команди управління текстом:
. 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 - поточний рядок
. c - поточний рядок від введення
. f - поточний шрифт
. i - поточний відступ
. j - поточна регулювання (adjustment) тексту
. l - довжина рядка
Використання числових змінних:
. nr R v [i] - привласнити числової змінної R значення v знеобов'язковим інкремент i
. af R c - встановити формат числової змінної (1,01, i, I, a, A)
nx-використовувати регістр x
n (xy - використовувати регістр xy - дві букви < br> n + x - додати інкремент, а потім використовувати
n-(xy - відняти інкремент, а потім використовувати
Використання строкових змінних:
. ds R str - привласнити змінної R вміст str
. as R str - дописати str в кінець рядковий змінної R
* x - використовувати регістр x
* (xy - використовувати регістр xy - дві букви
w'string '- довжиною строки
Коментарі:
"коментар
Макроси:
. de xx"-початок визначення макросу
Today is the $ 1 $ 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 (c, 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) ac
(3) acb
(4) acbc
(5) acbca
(6) acbc
. a
(7) a c b a c
. a
Остаточний варіант дерева називається деревом виведення термінальноїланцюжка acabac.
Коли один ланцюжок може мати кілька дерев виводу, говорять, щовідповідна граматика неоднозначна.
Таким чином, резюмуючи вищесказане, можна підсумувати:
1. Кожній ланцюжку, що виводиться в цiй контекстно-вільної граматики,відповідає одне або кілька дерев виводу.
2. Кожному дереву відповідає один або більше висновків.
3. Кожному дереву відповідає єдиний правий і єдинийлівий висновки.
4. Якщо кожній ланцюжку, що виводиться в цiй контекстно-вільноїграматики, відповідає єдине дерево виводу, ця граматиканазивається однозначною, інакше її називають неоднозначною.
Для будь-якого контекстно-вільного мови існує нескінченне числограматик, що породжують цю мову. Хоча більшість цих граматик занадтоскладні, на практиці часом буває корисно мати для опису деякогомови кілька різних граматик.
Якщо права частина кожного правила граматики містить не більше одногонетермінала, причому цей нетермінал є самим правим символом правоючастини, граматика називається праволінейной.
Нетермінали, які не породжують ні однієї термінальної ланцюжка,називаються безплідними або мертвими. Вони можуть бути виключені з граматикиз усіма правилами, в які входять.
Нетермінали, які не з'являються ні в одному ланцюжку, що виводиться зпочаткового символу, називаються недосяжними нетерміналамі.
Нетермінали, які безплідні або недосяжні називаютьсямарними. При складанні граматик велика ймовірність появимарних нетерміналов і захаращення граматик зайвими правилами. Дляпошуку подібних нетерміналов існує конкретна процедура, розбита надві частини: виявлення безплідних нетерміналов і виявлення недосяжнихнетерміналов. Спочатку потрібно виконати процедуру для безпліднихнетерміналов, тому що при їх видаленні з граматик інші нетермінали можутьстати недосяжними.
Термінальний символ називається продуктивним (або живим), якщо з ньоговиводиться яка-небудь термінальна ланцюжок, тобто якщо він не єбезплідним нетерміналом. Процедура виявлення безплідних нетерміналовзаснована на наступному властивості продуктивних символів:
Якщо всі символи правій частині правила продуктивні, то продуктивний ісимвол, що стоїть в її лівій частині.
Символ називається досяжним у граматиці, якщо він може з'явитися вякий-небудь ланцюжку, що виводиться з початкового нетермінала, тобто якщо вінне є недосяжним. Процедура виявлення недосяжних символівграматики заснована на наступному властивості досяжних символів:
Якщо нетермінал в лівій частині правила є досяжним, тодосяжні і всі символи правій частині цього правила.
Параметри мови, які в керівництві описуються граматикою, прийнятоназивати синтаксичними або граматичними властивостями, а властивості,які граматикою не описуються - семантичними властивостями. Укерівництві з мови семантичні властивості описуються звичайно наприродною мовою.
Створення програми-транслятора.
Для написання програми-транслятора файлів з формату 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 (c) і unput (c), тому що вони використовуються аналізатором та їхперевизначення може призвести до помилки.
Правила синтаксичного аналізатора будуються так, щоб вони виявилисявкладеними одна в одну. Найбільш зовнішнє правило повинно повністюописувати будь-який можливий файл, який може бути оброблений данимианалізатором. У правилах допускається рекурсія, тобто правило може міститиелементи, при розкритті яких буде викликано воно саме. У нашому випадкунайбільш загальним правилом є опис вхідного файлу як списку списківрядків. Строки можуть бути двох типів - команди і текст. Команди можуть матиаргумент або не мати аргументу. Текст може бути текстовим рядком інового рядка. Такі елементи, як команди, аргументи, текстові та пустірядки являють собою лексеми - мінімальний об'єкт, яким оперуєаналізатор при синтаксичному аналізі.
1. Якщо синтаксичний аналізатор отримує від лексичного аналізаторалексему "текст", то він виводить у вихідний потік вміст буфера yytext.
2. Якщо отримана лексема "порожній рядок", то в вихідний потік виводиться тег
HTML.
3. Якщо отримана лексема, що відповідає однієї з команд, то, можливо,запитується лексема аргументу і виконуються необхідні операції.
Так як у всіх командах аргумент є другим елементом правила,то для доступу до його значенням завжди використовується псевдопеременная $ 2.
Обробка більшості команд призводить до того, що у вихідний потікзаписується відкриває ТЕ
