Формальные языки, грамматики и основы построения трансляторов. Кревский И.Г - 17 стр.

                                                                          17

      Более сложный синтаксис языка лучше определять с помощью
грамматики. В грамматику входит набор правил для получения предложений
языка. Возьмем синтаксис L и воспользуемся следующими правилами:
      1. S → 0S1                                 2. S → ε
      Чтобы вывести предложение этого языка, поступим следующим
образом. Начнем с символа S и заменим его на 0S1 или ε. Если S опять
появился в полученной строке, его опять можно заменить с помощью одного
из этих правил, и т.д. Полученная таким образом любая строка, не
содержащая S, является предложением этого языка. Например,
      S ⇒ 0S1 ⇒ 00S11 ⇒ 000S111 ⇒ 000111
      Последовательность таких шагов называется выводом строки 000111, а
символ ⇒ служит для разделения шагов вывода. Все предложения данного
языка можно вывести, руководствуясь двумя правилами, любая строка,
которую нельзя вывести с их помощью, не является предложением этого
языка. Грамматику часто называют системой перезаписи.
      Грамматика определяется как четверка (Vt, Vn, P, S), где Vt – алфавит,
символы которого называются терминальными (терминалами), из них
строятся цепочки порождаемые грамматикой. Vn – алфавит, символы
которого называется нетерминальными (нетерминалами), используются
при построении цепочек; они могут входить в промежуточные цепочки, но не
должны входить в результат порождения. Vt и Vn не имеют общих символов,
т.е. Vt ∩Vn = Ø, полный алфавит (словарь) грамматики V определяется как Vt
∪ Vn. P – набор порождающих правил, каждый элемент которых состоит из
пары (α, β), где α находится в V+, а β в V*. α – левая часть правила, а β –
правая, т.е. цепочки, построенные из символов алфавита V. Правило
записывается α → β. S принадлежит Vn и называется начальным символом
(аксиомой). Этот символ – отправная точка в получении любого
предложения языка.
      Грамматикой, генерирующей язык L = { 0n1n | n ≥ 0} является G0 = (
{0,1}, {S}, P, S), где P = { S → 0S1, S → ε }.