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

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

Вход
Выход

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

Обязательные элементы
Необязательный элемент
Игнорируемый элемент
Повторение элемента
Повторение через разделитель

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

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

Пример: диаграмма для

идент::= A..Z [(A..Z | 0..9)*]

имеет вид

Пример: описанная выше грамматика для арифметических выражений задаётся совокупностью диаграмм:

выр
прост-выр
слаг
множ

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