Синтаксическая диаграмма

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

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

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

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

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

Синтаксическая диаграмма оператора Case в языке Pascal^[2]

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

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

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

<Оператор_For>

<Тип_Set>

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

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

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

For

Begin

Set

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

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

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

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

Примеры

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

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

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

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

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

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

[";"].

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

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

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

См. также

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

Примечания

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

Литература

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

[1] Глухова, Л.А. Основы алгоритмизации и программирования: учебное пособие. В 2 Ч.. — БГУИР, 2006. — 195 с.

[2] N1ghtF1re/The-syntax-diagram-editor (англ.). http://brakhmen.info. GitHub. Дата обращения: 21 мая 2018. Архивировано 14 декабря 2020 года.

[1]

[2]