WikiSort.ru - Не сортированное

Синтаксическая диаграмма — это направленный граф с одним входным ребром и одним выходным ребром и помеченными вершинами. Синтаксическая диаграмма задаёт язык. Цепочка пометок при вершинах на любом пути от входного ребра к выходному — это цепочка языка, задаваемого синтаксической диаграммой. Поэтому можно считать, что синтаксическая диаграмма — это одна из форм порождающей грамматики автоматных языков. Синтаксические диаграммы и конечные автоматы имеют тесную связь: любой автоматный язык задаётся синтаксической диаграммой и обратно, по любой синтаксической диаграмме можно построить конечный автомат (в общем случае недетерминированный), распознающий тот же язык, который задаёт диаграмма.

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

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

Синтаксические единицы

Синтаксическая диаграмма позволяет графически изобразить структуру синтаксической единицы.^[1]

В метаязыках, описывающих синтаксис языка программирования, используются следующие основные понятия:

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

Примеры записи метапеременных:

<Оператор_For>

<Тип_Set>

<Базовый_скалярный_тип>

Метаконстанты – обозначает лексему языка программирования. В программе метаконстанте соответствует она сама. В синтаксических диаграммах метаконстанты записываются «как есть».

Примеры метаконстант:

For

Begin

Set

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

o  Метасимвол “::=” - используется для отделения имени синтаксической диаграммы.

o  Метасимвол “<>” – используется для обозначения метапеременных

Синтаксическая диаграмма представляет собой ориентированный граф с размеченными ребрами. Для разметки ребер используются метаконстанты и метапеременные.

Примеры

Представление в виде ориентированных графов основных конструкций:

1. Выбор (Альтернатива).

Аналогичная запись в РБНФ:

 <Буква>|<Знак_подчеркивания>.

2. Необязательная часть конструкции (Повторяется либо 1, либо 0 раз).

Аналогичная запись в РБНФ:

[";"].

3. Повторение конструкции

Аналогичная запись в РБНФ:

<Диапазон>{","<Диапазон>}.

См. также

• Эквивалентность детерминированных и недетерминированных конечных автоматов

• Синтаксический анализ
• Расширенная форма Бэкуса — Наура
• Синтаксис языка программирования
• Метаязык

Ссылки

1. ↑ Глухова, Л.А. Основы алгоритмизации и программирования: учебное пособие. В 2 Ч.. — БГУИР, 2006. — 195 с.
2. ↑ N1ghtF1re/The-syntax-diagram-editor (англ.). http://brakhmen.info. GitHub. Проверено 21 мая 2018.

3. Карпов Ю. Г. Теория автоматов. — СПб.: Питер, 2002. С. 224. ISBN 5-318-00537-3