Реферат: Программное обеспечение удалённого доступа к технической документации

TOC o «1-3» Введение.… PAGEREF _Toc468060139 h 3

1. Постановка задачи.… PAGEREF _Toc468060140 h 8

1.1 Требования, предъявляемые к транслятору.… PAGEREF _Toc468060141 h

1.2 Оценка достоинств и недостатков существующих трансляторов.… PAGEREF _Toc468060143 h

Заключение.… PAGEREF _Toc468060144 h

2. Проектированиетранслятора… PAGEREF _Toc468060145 h 16

2.1 Схема разработки транслятора.… PAGEREF _Toc468060146 h

2.2 Принципы построения лексических анализаторов.… PAGEREF _Toc468060147 h

2.3 Грамматики. Принципы построения грамматическиханализаторов.… PAGEREF _Toc468060148 h

Заключение.… PAGEREF _Toc468060149 h

3. Технология реализациитранслятора с помощью генераторовпрограмм Lex и Yacc. PAGEREF _Toc468060150 h 35

3.1 Определение лексем, встречающихся в формате nroff… PAGEREF _Toc468060151 h

3.2 Описание грамматических правил преобразования из форматаnroff в формат HTML. PAGEREF _Toc468060152 h

3.3 Соответствие между командами форматов nroff и HTML.… PAGEREF _Toc468060153 h

3.4 Отладка лексического и грамматического анализаторов.… PAGEREF _Toc468060154 h

Заключение.… PAGEREF _Toc468060155 h

4. Экономическое обоснованиеразработки НИОКР.… PAGEREF _Toc468060156 h 50

4.1 Расчет затрат времени на разработку транслятора.… PAGEREF _Toc468060157 h

4.2 Расчет стоимости основных фондов, используемых дляразработки транслятора. PAGEREF _Toc468060158 h

4.3 Расчет затрат на разработку транслятора.… PAGEREF _Toc468060159 h

4.4 Формирование расчетной (остаточной) прибыли предприятия иопределение эффективности произведенных затрат на разработку транслятора.… PAGEREF _Toc468060160 h

4.5 Оценка значимости разработки транслятора.… PAGEREF _Toc468060161 h

Заключение.… PAGEREF _Toc468060162 h

5. Обеспечение комфортныхусловий труда при работе на ПЭВМ.. PAGEREF _Toc468060163 h 69

5.1 Характеристика условий труда оператора ЭВМ… PAGEREF _Toc468060164 h

5.2 Требования к защите от шума и вибраций.… PAGEREF _Toc468060165 h

5.3 Требования к микроклимату, содержанию аэроионов и вредныххимических веществ в воздухе помещений эксплуатации ПЭВМ… PAGEREF _Toc468060166 h

5.4 Требования к интенсивности электромагнитных полей, рентге-
новского, видимого, ультрафиолетового и инфракрасного излучений.PAGEREF _Toc468060167 h

5.5 Требования к освещению помещений и рабочих мест с ПЭВМ.… PAGEREF _Toc468060168 h

5.6 Расчет освещенности рабочего места программиста.… PAGEREF _Toc468060169 h

Заключение.… PAGEREF _Toc468060170 h

Список литературы:… PAGEREF _Toc468060175 h 85

Приложения.… PAGEREF _Toc468060171 h 86

Фрагмент кода лексического анализатора.… PAGEREF _Toc468060172 h

Фрагмент кода грамматического анализатора.… PAGEREF _Toc468060173 h

Код головной программы.… PAGEREF _Toc468060174 h

Введение.

Одним из основополагающих моментоворганизации САПР является выбор архитектуры вычислительного комплекса итехнологии доступа к прикладным программным средствам. В настоящее времянаиболее распространенным является подход, получивший наименование «технологииклиент-сервер». Этот подход состоит в сосредоточении вычислительных иприкладных ресурсов на выделенных компьютерах — серверах и организации доступак ним с рабочих мест — клиентов.

Так как обязательным компонентомСАПР является информационное обеспечение (различные базы данных, проектныебиблиотеки и все виды документации), то при использовании технологииклиент-сервер целесообразно разместить эти составляющие на выделенных серверах.

Главным препятствием при созданиитаких информационных серверов оказывается большое количество форматов текста, вкоторых хранится техническая информация и различная документация, способов исредств доступа к данным, их разнородность, различие требований к аппаратнымсредствам и системной среде.

Например, документация о системеUNIX и функциях языка «c++» (или его аналога «g++») представлена в виде такназываемых «manual pages». Она просматривается с помощью команды системы UNIX«man» либо с помощью утилиты просмотра «Xman». Справочные файлы САПР «Compass»используют формат «Iview», просматриваемый с помощью специальных утилитпросмотра. А САПР «Cadence» предоставляет информацию пользователю в формате«Open Book», также требующем специальных средств просмотра.

Кроме того, при использовании вкачестве рабочего места X‑терминала, доступ к некоторым документамстановится невозможен в принципе, так как, например, программе просмотра«Iview» требуется для работы графический клиент X‑Window версии 6, амногие из находящихся в эксплуатации Х‑терминалов имеют аппаратно‑реализованнуюверсию X‑Window 5.

Для выхода из создавшейсяситуации можно предложить следующее:необходимо привести всю документацию к единому формату данных и сосредоточитьее в одном месте, удобном для доступа всех пользователей. Это даст возможность оснастить всехпользователей унифицированными средствами доступа ко всем информационным ресурсам.

Единый формат для документациидолжен отвечать следующим требованиям:

·

Тексты,записанные в выбранном формате, должны быть доступны для чтения как наперсональном компьютере под управлением операционной системыWindows 95(NT), так и на сервере, работающим под управлением UNIX, а такжена Х‑терминале.

·

Текстыдолжны сохранять исходное форматирование.

Учитывая,что часто документация содержит перекрестные ссылки, важной чертой, влияющей навыбор формата, становится возможность создания в тексте таких ссылок.

Крометого, требуется, чтобы твердые копии документации изготавливались бы однимметодом и выглядели бы одинаково вне зависимости от метода доступа к удаленномусерверу технической документации.

Представляется оптимальным выборформата HTML. Этот формат просматривается с помощью программ, версии которыхработают как под управлением Windows, так и под управлением UNIX. Формат HTMLподдерживает широкие возможности форматирования. Кроме того, этот форматявляется стандартным форматом для текстов в технологиях Internet, и егоиспользование позволяет легко решить проблему общедоступности документации припомощи использовании этих технологий. Используя формат HTML, можно сделатьдокументацию, преобразованную из того или иного формата, общедоступной,поместив ее в один из узлов сети. Следует заметить, что в настоящее времябольшинство локальных сетей строятся на тех же принципах и с использованиемтого же инструментария, что и сети Internet. Формат HTML удобен еще и тем, чтоформатирование текста в нем, как и в формате nroff (наиболее распространенном всреде UNIX), осуществляется простыми текстовыми командами, что позволяет еголегко редактировать в случае надобности с помощью любого текстового редактора.

Проект посвящен разработке методасоздания программ‑трансляторов различных форматов текста. Рассмотренысуществующие программы‑трансляторы, оценены их достоинства и недостатки.Выбран унифицированный подход к разработке программ‑трансляторов,разработан маршрут разработки таких программ.

Рассмотрены экономические аспектыразработки программы‑транслятора, произведена оценка значимостиразработки транслятора.

1. Постановка задачи.

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

1.1 Требования,предъявляемые к транслятору.

Согласно условиям техническогозадания программа должна функционировать в вычислительных системах подуправлением ОС «Unix» и совместимых с ней (“SunOS”, “Linux”, “FreeBSD”,и др.). Проблема состоит в том, что исполняемые файлы ОС “UNIX” могут бытьнеработоспособны в среде “Linux”. В то же время, многие из UNIX-подобных системпоставляются пользователю в виде исходных файлов, предназначенных длякомпилирования. Так же и в данном случае можно передавать программу в видеисходных текстов, снабженных программой компиляции. Это, с одной стороны,повысит переносимость программы, а с другой — позволит вносить достаточноопытному пользователю необходимые поправки и корректировки, расширяявозможности транслятора в соответствии с потребностями пользователя. При этомнеобходимым условием становится написание программы при помощи таких средств,которые присутствовали бы в любой UNIX-подобной операционной системе.

Полученный же в результате работыпрограммы должен поддерживаться как в операционной системе UNIX, так и воперационной системе Windows‑95 (NT). Программа, предназначенная дляпросмотра текста в конечном формате должна быть распространенной иобщедоступной. Оптимальным вариантом было бы, если бы программа являласьнеотъемлемой частью операционных систем или же в любой системе существовалиспособы просмотра текста в данном формате.

Важным условием являетсясохранение в конечном формате текста всего форматирования, имевшегося в исходномформате и, возможно, добавление элементов форматирования, облегчающих работупользователя с документом.

Следует учитывать, что большинствоимеющихся форматов используют при выводе текста различные шрифты. При этом вразных операционных системах шрифты различны и, в большинстве случаев, несовместимы. При преобразовании текста следует провести адекватную замену используемыхв исходном тексте шрифтов.

1.2 Оценкадостоинств и недостатков существующих трансляторов.

Прежде всего, следует выяснить,имеет ли смысл создавать новую программу, так как в настоящее время ужесуществуют различные программы-трансляторы из формата nroff в формат HTML.Рассмотрим характеристики этих программ, выясняя их преимущества и ихнедостатки.

Наиболее известными и распространеннымипрограммами в настоящее время являются следующие:

1.

Программа “nroff2HTML”(автор Р. Ричи).

Программанаписана на языке “C”, работает под управлением ОС “UNIX”.

Работаетс исходными текстами в формате nroff. При конвертировании вставляет в текстконечного файла обязательные теги формата HTML (такие, как, ,) и затем копирует исходный текст, уничтожая всекоманды nroff, предварительно отформатировав его с помощью тега. В результате получается сплошной текст.

2.

Программа“gnome-man2html”, входящая в графический интерфейс пользователя “GNOME”.

Программанаписана на языке «C», работает под управлением операционной системы«Linux», тесно интегрирована с графическим интерфейсом пользователя«GNOME».

Даннаяпрограмма работает не с реальными файлами, а выступает как фильтр при выводетекста с помощью программы “man” на экран компьютера, перенаправляя вывод вокно HTML-броузера и снабжая его при этом всеми командами, необходимыми дляформатирования. Полученный на экране текст выглядит наилучшим образом, т.к. внем сохраняются все необходимые виды форматирования и поддерживаютсяперекрестные ссылки. Но данная программа не может работать без пакета “GNOME”,для работы которого, в свою очередь, необходима ОС “Linux”.

3.

Программа “hypernroff”(автор К. Садовски).

Программанаписана на языке “C”, работает под управлением ОС “UNIX”.

Вкачестве входного и выходного потоков используется стандартный поток ввода‑вывода.Позволяет принимать информацию из файлов и выводить ее в файл посредствомперенаправления потоков, доступном в среде UNIX. Вставляет в текст конечногофайла обязательные теги формата HTML. Поддерживает некоторые виды управлениятекстом, такие, как выравнивание (по левому и правому краям, по центру). Всеформатирование осуществляется заменой пробелов, при помощи которыхформатируется текст в формате nroff, на символ формата HTML “nbsp” -неразрывный пробел. Изменение шрифтов, подчеркивание, курсив не поддерживаются.

4.

Программа “man2html”(автор Р. Верховен).

Программанаписана на языке “C”, работает под управлением ОС “FreeBSD”. Под управлениемдругих разновидностей ОС “UNIX” не полностью работоспособна. Существуетcgi-скрипт “vh-man2html” (автор М. Гамильтон), обеспечивающий вызов программы ивыдачу результатов ее работы в html-броузере.

Работаетс исходными текстами в формате nroff. Поддерживает макросы man-1.4 и форматBSD-mandoc (разновидность nroff). Вставляет в текст конечного файлаобязательные теги формата HTML. Поддерживает различные виды управления текстом,в том числе таблицы. Замена шрифтов не производится. Не вставляютсяперекрестные ссылки, хотя скрипт “vh-man2html” сильно облегчает поискнеобходимых файлов.

Ни одна из этих программ неудовлетворяет нашим требованиям, так как нам необходимо сохранять максимальнополный объем форматирования (что дает нам программа “gnome-man2htmnl”),добившись переносимости программы и максимальной ее независимости от наполненияоперационной среды (программа “gnome-man2htmnl” является непереносимой, она функционируеттолько под управлением системы Linux). Главным недостатком всех рассмотренныхпрограмм является их ориентация на работу непосредственно на одном рабочемместе, без использования сетевых технологий. Этим объясняется, например то, чтони одно из программ не поддерживает замену шрифтов X‑Window System нашрифты операционной системы Windows.

При создании проекта в первуюочередь следует решить второй вопрос (независимость от наполнения операционнойсреды), и, затем, выбрав принципы реализации проекта, приступить к созданиюпрограммы, способной адекватно обработать, как минимум, весь объем стандартныхкоманд и операций формата nroff.

1.3Выбор способа реализации транслятора.

Первым очевидным элементом,присутствующим во всех таких ОС, является компилятор языка “С”, на котором,собственно, и написана операционная система “UNIX”. Но язык “С” являетсядостаточно сложным языком и не все пользователи знакомы с ним. В тоже время, вОС “UNIX” существуют другие средства написания программ: это генераторыпрограмм LEX и YACC. Описание их команд настолько просто и логично, что позволяетвносить коррективы в существующую программу не имея специальной подготовки, и,возможно, даже не будучи знакомым с описанием этих средств, имея только текстисходной программы.

Заключение.

Выявлена необходимость созданияпрограммы‑транслятора, так как существующие на данный момент программы неудовлетворяет предъявляемым требованиям. В качестве конечного формата выбрангипертекстовый формат HTML, как наиболее полно соответствующий нашим целям, широкораспространенный и простой в использовании. В качестве средства созданияпрограмм выбраны генераторы программ Lex и Yacc благодаря легкости освоения иполной переносимости программ, написанных на их основе, в среде UNIX.

2. Проектирование транслятора

Проектирование программы‑трансляторас использованием генераторов программ Lex и Yacc имеет свои особенности,независящие от конкретных форматов, с которыми будет работать разрабатываемыйтранслятор.

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

2.1 Схемаразработки транслятора.

Сначала с помощью генераторапрограмм Lex строится лексический анализатор. В задачу лексического анализаторавходит полное поглощение входного файла (потока) и передача в синтаксическийанализатор найденных лексем, а также некоторых необходимых данных. Например,может быть найдена некоторая лексема NUMBER, а в качестве данных будет переданочисловое значение найденного числа или цифры, либо возможна ситуация прикоторой в качестве лексемы выбирается команда, а данные, сопутствующие этой команде,передаются не как лексемы, а каким-либо другим путем.

Затем строится синтаксическийанализатор с помощью генератора программ YACC. В синтаксическом анализатореописываются правила, с помощью которых будет происходить преобразование текста.Правила опираются на полученные из лексического анализатора лексемы.

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

Компиляция модулей (лексическогоанализатора, синтаксического анализатора и головной программы) происходит вследующем порядке:

1.

Спецификация синтаксическогоанализатора с помощью генератора программ Yacc преобразуется в программу наязыке C. При этом создается файл с описанием лексем, обрабатываемых синтаксическиманализатором.

2.

Спецификация лексическогоанализатора с помощью генератора программ Lex преобразуется в программу на языкеC. Имена лексем определяются в подключаемом файле, полученном на предыдущемэтапе.

3.

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

2.2 Принципыпостроения лексических анализаторов.

Лексический анализатор выполняетпервую стадию трансляции — читает строки транслируемого текста, выделяетлексемы и передает их на дальнейшие стадии трансляции (грамматический разбор,синтаксический анализ).

Основным элементом лексическогоанализатора являются правила. Правила – это расширенные регулярные выражения идействия. Действия могут быть записаны как с помощью команд «языка» Lex, так ина языке C. Регулярные выражения – это описания возможных наборов символов извходного потока, называемые в дальнейшем лексемами.

Лексический анализатор распознаеттип каждой лексемы и соответствующим образом помечает ее. Лексический анализатор должен не только выделитьлексему, но и выполнить некоторые преобразования. Например, если лексема — число,то его необходимо перевести во внутреннюю форму записи.

Хотя лексический анализ по своей идеепрост, тем не менее эта фаза работы транслятора часто занимает больше времени,чем любая другая. Частично это происходит из-за необходимости просматривать ианализировать исходный текст символ за символом. Иногда даже бывает необходимовернуть прочитанный символ во входнойпоток с тем, чтобы повторить просмотр и анализ. Происходит это потому, чточасто бывает трудно определить, где проходят границы лексемы. Например, могутсуществовать две лексемы: “make” и “makefile”. При анализе входного потока символовможет быть выделена лексема “make”, хотя правильно было бы выделить лексему“makefile”. Единственный способ преодолеть это затруднение — просмотр полученной цепочки символов назад и вперед. В нашем примере при выделениилексемы “make” мы должны просмотреть следующий поступающий символ и, если он будет символом«f», то вполне возможно, что поступает лексема “makefile”.

Вообще говоря, в общем случаепрограммы лексического анализа, построенные с помощью генератора программ Lex,всегда просматривают входной поток вперед. При этом из входного потокавыбирается лексема, соответствующая правилам, с наибольшей длиной. Этонесколько замедляет работу, но помогает избежать ошибок.

Также в общем случаепредполагается, что лексема может находиться в любом месте входного потока. Нопри этом предусмотрены способы учитывать контекст. Во‑первых, для этогоприменяются так называемые «состояния» лексического анализатора. Переход всостояние осуществляется при срабатывании какого‑либо правила поспециальной команде. Исходным состоянием анализатора является состояние «0».Возможна ситуация, когда одно и тоже правило может выполняться в несколькихсостояниях. Во‑вторых, существует оператор определения контекста: «/».Например, выражение «ab/cd» удовлетворяет строке ab только в том случае, еслиза ней следует cd.

Кроме того, в Lex существуютинструменты, использующие просмотр вперед и назад: в правиле при определениилексемы могут использоваться спецсимволы «^» и «$», говорящие, что лексемадолжна находится в начале строки или в конце. Последний, на самом деле,является частным случаем оператора «/», так как для определения конца строкииспользуется выражение

”n”

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

Для передачи данных излексического анализатора в синтаксический существует несколько путей. Наиболеепростым является метод передачи данных при помощи глобальных переменных –текстовой yytext и числовой yylval.

Для упрощения написанияспецификаций можно применять так называемые «подстановки». Какой-либо частоиспользуемый шаблон описывается и сопоставляется с некоторым именем. В дальнейшемэто имя можно использовать в правилах вместо данного шаблона. При этом, есливозникнет необходимость изменения шаблона, не надо будет искать вхожденияшаблона на протяжении всей спецификации – достаточно будет изменить шаблон вопределении подстановки.

2.3 Грамматики.
Принципы построения грамматических анализаторов.

Спецификация Yacc (грамматика)описывается как набор правил в виде, близком к форме Бэкуса‑Наура (БНФ).Каждое правило описывает грамматическую конструкцию, называемую нетерминальнымсимволом, и сопоставляет ей имя. С точки зрения грамматического разбора правила рассматриваются как правила вывода(подстановки). Грамматические правила описываются в терминах некоторых исходных конструкций, которые называются лексическими единицами, илилексемами. Как правило, имена сопоставляются лексемам, соответствующим классамобъектов, конкретное значение которых не существенно для целей грамматического анализа.

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

Прежде всего стоит отметить, чторазличают два основных типа грамматик: контекстно-зависимые иконтекстно-независимые.

Если порождающее правило имеетследующий вид:

a

Ab::= axb,

где A – нетерминальный символ, а x

— терминальный или нетерминальный, то порождающееправило называется контекстно-зависимым, то есть замена нетерминального символаA на последовательность xможет иметь место только в контекстах aи b. Соответственно, и грамматика, содержащая подобноеправило, называется контекстно-зависимой.

Если порождающее правило имеетвид:

A ::= x

то есть, если левая частьпорождающего правила состоит из одного нетерминального символа, который в итоге(через ряд промежуточных шагов) может заменяться на последовательность x

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

Контекстно‑независимыеграмматики более универсальны. Для разработки универсальных принциповпроектирования трансляторов следует использовать их, так как они позволяютобработать практически любой входной язык.

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

Существует несколькоосновополагающих терминов в теории грамматик. Нетерминальный символ(нетерминал) – описываемые элементы. Например, при определении языковпрограммирования нетерминалами служат <оператор>, <арифметическоевыражение> и т.п. В контекстно-свободной грамматике может быть любоеконечное число нетерминалов.

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

Правила грамматики иногданазываются продукциями и в общем виде выглядят так:

Один_нетерминал à

любая конечная цепочка из терминалов инетерминалов.

При этом цепочка справа от стрелкиможет быть и пустой. Например,

àx

Иногда подобные правила называютэпсилон‑правилами. Контекстно-свободная грамматика может содержать любоеконечное множество продукций. В качестве иллюстрации опять приведем пример изописания языка программирования. Продукция тогда выглядит так:

<оператор> à

IF <логическое_выражение> THEN<оператор>

Один из нетерминалов выделен какначальный нетерминал или начальный символ, с которого должны начинаться выводыцепочек языка. Для языков программирования таким нетерминалом может быть,например, <программа>. Обычно начальный символ обозначают .

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

1)

конечным множествомнетерминалов;

2)

конечным множествомтерминалов, которое не пересекается с множеством нетерминалов;

3)

конечным множествомправил вида à a, где A – нетерминал, а a — цепочка терминалов и нетерминалов(возможно, пустая); нетерминал называется левой частью правила, а a — правой частью;

4)

одним нетерминальнымсимволом, выделенным в качестве начального.

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

Для описания грамматик очень частоиспользуют способ записи, получивший название формы Бэкуса-Науэра или БНФ.Здесь символ à

заменяется символом ::=, за которым может следоватьлюбое число правых частей, разделенных вертикальной чертой |. Здесь такженетерминалы заключаются в угловые скобки.

Правила грамматики используют длятого, чтобы задавать способы подстановки или замены цепочек. Подстановкаосуществляется путем замены некоторого нетерминала в какой-нибудь заданнойцепочке терминалов и нетерминалов на правую часть правила, левой частьюкоторого является этот нетерминал. Иногда говорят, что в таком случае правилоприменяется к нетерминалу цепочки.

Последовательность некоторыхподстановок называется выводом. Каждая цепочка, встречающаяся в выводе,называется промежуточной цепочкой этого вывода.

Множество терминальных цепочек,которые можно вывести из начального символа грамматики, называется языком.Говорят, что язык определяется, грамматикой, порождается ею или выводится вней. Язык, порождаемый контекстно-свободной грамматикой, также называется контекстно-свободнымязыком.

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

Описать дерево вывода цепочкиконтекстно-свободного языка проще на примере.

Пусть дана следующая грамматика (начальный нетерминал ):

1. àac

2. àx

3. àc

4. àb

5. àb

6. àa

Пусть дана цепочка: ac, тогда вывод будет выглядеть следующим образом:

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

Теперь для каждой из семи пронумерованных цепочек можно построить дерево.

<span Courier New";mso-fareast-font-family:«Times New Roman»;mso-bidi-font-family: «T