Парадигма развития науки (стр. 25 )

2. Контекстно-свободные или бесконтекстные грамматики (КС-грам­матики) имеют продукции вида ψ→z, где ψ— нетерминальный символ, а z — произвольная непустая цепочка над VT VH.

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

3. Линейные грамматики (ЛН-грамматики) имеют продукции вида ψ→z, где ψ VH, а z = F (VT) либо z = uτv, где z, u,v F (VT),

τVH. Ины­ми словами правые части продукции ЛН-грамматик являются терминаль­ными цепочками либо содержат лишь один терминальный символ.

Продукция ψ→z — называется праволинейной (леволинейной), если z(VT) либо z = uτ, (z =τu), т. е. если единственный нетерминал τ входит в правые части линейных продукций, то он всегда крайний справа (слева). Соответственно грамматики называются праволинейной, леволи­нейной, а языки праволинейным, леволинейным.

4. Автоматные грамматики (А-грамматики) имеют продукции вида ψ→bτ, где ψ,τVH, bVT и порождают автоматные языки (А-языки).

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

Некоторые языки исследования можно полностью описать А-грамматикой Gа — (VT, VH, a, P); может быть ассоциирован конечный автомат А = (VT, S, σ, φ, Г), где VT — входной алфавит автомата А, совпадающий с терминальным алфавитом грамматики Ga;

S = VH {φ} (φ VH) — мно­жество состояний автомата; σ и φ — соответственно начальное и конечные состояния; Г — граф переходов, определяющий функционирование авто­мата (рис. 21.1).

Рис. 21.1. Граф функционирования конечного автомата

Каждому нетерминалу ψVH грамматики Gа соответствует вершина графа Г, помеченная символом ψ. В графе есть еще одна вершина, поме­ченная символом заключительного состояния φ. Единственному началь­ному состоянию σ автомата А соответствует вершина, помеченная аксио­мой σ. Каждой продукции ψ→аτ соответствует ребро на графе из вершины ψ в вершину τ, помеченное терминальным символом аVT. При подаче на вход такого автомата цепочки терминальных символов осуществляется смена состояний в соответствии с движением по ребрам графа от вершины σ до φ. Причем в каждом состоянии автомат воспринимает очередной тер­минальный символ и переход осуществляется по ребру, помеченному этим символом.

К отдельному виду формальных грамматик порождающего типа, ко­торые описывают класс контекстно-свободных языков, относятся Бекуса нормальные формы (БНФ) или металингвистические формулы. Такие фор­мулы или такие языки предназначены для описания свойств других язы­ков и называются метаязыками. БНФ предложил американский матема­тик Бекус для синтаксиса языка АЛГОЛ-60. Они широко применяются для формального описания различных КС-языков. Основными классами объектов, которые используются в БНФ, являются основные символы и имена конструкций описываемого языка в виде металингвистических пе­ременных. Значения металингвистических переменных — это цепочки ос­новных символов описываемого языка.

Каждая металингвистическая формула описывает правила построе­ния некоторой конструкции языка и состоит из двух частей. В левой части находится металингвистическая переменная, которая обозначает соот­ветствующую конструкцию. Затем следует так называемая металингвисти­ческая связка ::=, имеющая смысл глагола «быть». Она соединяет ле­вую и правую части формулы. В правой части формулы указывается один или несколько вариантов построения конструкции, определенной в левой части. Варианты разделяются металингвистической связкой | (вертикаль­ная черта), имеющей значение «или». Металингвистические переменные обозначаются словами, которые заключаются в угловые скобки < >. Эти слова поясняют смысл описываемой конструкции.

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

Примером БНФ может служить задание синтаксиса целого числа в описании языка:

<целое> :: = <целое без знака> | — <целое без

знака> | + <целое без знака>

<целое без знака> :: = <цифра> | <целое без

знака> <цифра>

<цифра> :: = 0|1|2|3|4|5|6|7|8|9

Здесь <целое>, <целое без знака>, <цифра> — суть метапеременные, а цифры от 0 до 9 — основные терминальные символы языка.

Определение целого числа без знака является рекурсивным, так как любая цифра — это целое без знака, или любое целое без знака, к кото­рому справа приписана цифра, также есть целое без знака.

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

Рис. 21.2. Вариант синтаксической диаграммы для распознавания описания целого числа

21.3. Входные языки

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

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

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

Структурно-символический способ предусматривает предварительное выделение и описание типовых или базовых графических элементов (БГЭ), создание библиотеки БГЭ и дальнейшее ее использование для составления из базовых элементов форм и чертежей объекта исследуемой проблемы.

Аналитический способ основан на описании графического изображения в виде математических соотношений, например уравнений поверхностей и линий.

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

Операторы символических ВГ-языков задаются в виде текстовых строк или вводятся в ЭВМ с терминалов с помощью алфавитно-цифровой и (или) функциональной клавиатуры, устройств управления маркером или устройства указания и считывания координат на планшете ввода (кодографе).

Терминология ВГ-языков должна быть близка к обычной терминологии, чтобы облегчить процесс освоения языка и ввода графиче­ских данных непосредственно специалистами прикладной области без посредника-специалиста в области программирования. ВГ-языки могут быть ориентированы на описание объекта и на ввод изображения. Особен­ность ВГ-языков первого типа состоит в том, что в результате трансляции описания в ЭВМ формируется модель геометрии объекта в трехмерном пространстве, которая может быть представлена на устройствах отображе­ния в виде изображения произвольных проекций, сечений, разрезов. Ре­зультатом трансляции описания на языках второго типа является лишь то изображение, которое введено. Эти языки могут использоваться в АСНИ для ввода типовых графических элементов чертежей (ТЭЧ). ВГ-языки для опи­сания изображений основаны на использовании некоторых общих под­множеств команд, которые обеспечивают: построение графических прими­тивов; задание атрибутов графических примитивов; построение графиче­ских изображений произвольной конфигурации; построение изображения из ограниченного множества элементов, имеющих типовую конфигурацию; сокращение избыточности описания на основе использования принципа умолчания и признаков повторения; преобразование изображения (афинные и другие преобразования); документирование информации в графиче­ском, текстовом виде или запись на машинные носители; прием и передачу информации; управление устройствами вывода. Подмножества этих команд могут быть расширены или сокращены в зависимости от области и условий использования конкретного языка.