Формальные грамматики позволяют задавать языки, представляющие множества цепочек, построенных по определенным правилам. Используемый способ задания позволяет построить любую цепочку, принадлежащую языку. Чтобы сделать процесс построения, называемый выводом, наглядным, его изображают в виде графа, точнее, в виде дерева, которое называют синтаксическим деревом или деревом вывода. Учитывая, что вывод любой цепочки языка, принадлежащей языку, порождаемому заданной грамматикой, должен начинаться с начального символа, правила построения дерева можно сформулировать так:
1) В качестве начальной вершины или корня дерева возьмем вершину, которую обозначим начальным символом грамматики <I>; эта вершина образует нулевой ярус дерева,
2) Если при выводе цепочки на очередном шаге используется правило грамматики <A> ® a и вершина, помеченная нетерминалом <A>, расположена на ярусе с номером k-1, то к построенному дереву нужно добавить столько вершин, сколько содержится символов в цепочке a, расположить эти вершины на ярусе k, обозначить их символами цепочки a и соединить эти вершины дугами с вершиной <A>. Результатом вывода является множество конечных узлов - листьев, которые выписываются при обходе дерева слева - вниз - направо - вверх. Рассмотрим, например, грамматикy Г1. 8:
Г1. 8:
Vт = {a, b}, Va = {<I>},
R = {<I> ® a<I>b,
<I> ® ab },
которая порождает язык L(Г8) = {aa...abb...b}, где а и b повторяются по n раз, n=1,2,...
Вывод цепочки с помощью правил этой грамматики имеет вид: (см. рис.)
Вывод цепочки с помощью правил грамматики может быть задан не только в виде синтаксического дерева. Если пронумеровать правила грамматики, то последовательность номеров используемых правил также задает вывод.
Последовательность номеров правил грамматики Г, применение которых позволяет построить вывод рассматриваемой цепочки s из начального символа грамматики, называется синтаксическим разбором s.
Например, в следующей грамматике
Г1. 9:
Vт = { i, +, *, (,) }, Va = {<E>, <T>, <P>}
R ={ (1) <E> ®<E> +<T>,
(2) <E> ®<T>,
(3) <T> ®<T> *<P>,
(4) <T> ®<P>,
(5) <P> ®(E),
(6) <P> ® i }, правила которой пронумерованы, вывод
<E> Ю <E> +<T> Ю <T> +<T> Ю <T> *<P> +<T> Ю
<P> *<P> +<T> Ю i * <P> +<T> Ю i * i +<T> Ю
i * i +<P> Ю i * i + i имеет синтаксический разбор [1,2,3,4,6,6,4,6].
Если в процессе построения вывода появляются промежуточные цепочки, содержащие несколько нетерминальных символов, то можно продолжать вывод, заменяя любой из них. Таким образом, одни и те же правила могут быть использованы при выводе цепочки в разном порядке.
Например, вывод цепочки i + i в грамматике Г1. 9 может быть получен десятью различными способами.
Схема грамматики содержит правила вывода, определяющие синтаксис языка, или, другими словами, возможные компоненты и конструкции цепочек порождаемого языка. Для задания правил используются различные формы описания: символическая, форма Наура-Бэкуса, итерационная форма и синтаксические диаграммы.
В работах, связанных с рассмотрением общих свойств грамматик, обычно применяют символическую форму задания правил. Эта форма была рассмотрена в предыдущем параграфе. Она предусматривает использование в качестве элементов нетерминального словаря отдельных символов и стрелки в качестве разделителя правой и левой частей правила.
При описании синтаксиса конкретных языков программирования приходится вводить большое число нетерминальных символов, и символическая форма записи теряет свою наглядность. В этом случае применяют форму Наура-Бэкуса (ФНБ), которая предполагает использование в качестве нетерминальных символов комбинаций слов естественного языка, заключенных в угловые скобки, а в качестве разделителя - специального знака, состоящего из двух двоеточий и равенства. Например, если правила <L> ® <L> и <L> ® <E> записаны в символической форме, и символ <L> соответствует синтаксическому понятию "список", а символ <E> - "элемент списка", то их можно представить в форме Наура-Бэкуса так:
<список>::= <элемент списка><список>,
<список>::= <элемент списка>.
Чтобы сократить описание схемы грамматики, в ФБН разрешается объединять правила c одинаковой левой частью в одно правило, правая часть которого должна включать правые части объединяемых правил, разделенные вертикальной чертой. Используя объединение правил, для рассматриваемого примера получаем:
<список>::=<элемент списка><список>|<элемент списка>.