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

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

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

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

Синтаксические единицы[править | править код]

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

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

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

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

<Оператор_For>  <Тип_Set>  <Базовый_скалярный_тип>

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

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

For  Begin  Set

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

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

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

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

Примеры[править | править код]

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

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

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

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

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

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

[";"]. 

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

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

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

См. также[править | править код]

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

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

Примечания[править | править код]

Литература[править | править код]

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