Пример 1.1.

<предложение>::=<подлежащее><группа сказуемого>

<подлежащее>::=мать½отец

<группа сказуемого>::=<сказуемое><дополнение>

<сказуемое>::=любит½обожает½боготворит

<дополнение>::=сына½дочь ™

Если имеется множество правил, то ими можно воспользоваться для того, чтобы вывести или породить цепочку (предложение) по следующей схеме. Начнем с начального символа грамматики - <предложение>, найдем правило, в котором <предложение> слева от ::= , и подставим вместо <предложение> цепочку, которая расположена справа от ::=, то есть

<предложение> Þ <подлежащее> <группа сказуемого>.

Таким образом, мы заменяем синтаксическое понятие на одну из цепочек, из которых оно может состоять. Повторим процесс. Возьмем один из нетерминалов в цепочке <подлежащее> <группа сказуемого>, например <подлежащее>; найдем правило, где <подлежащее> находится слева от ::=, и заменим <подлежащее> в исходной цепочке на соответствующую цепочку, которая находится справа от ::=. Это дает

<подлежащее> < группа сказуемого > Þ мать < группа сказуемого > .

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

<предложение> Þ <подлежащее> <группа сказуемого>

Þ мать < группа сказуемого >

Þ мать <сказуемое> <дополнение>

Þ мать любит <дополнение>

Þ мать любит сына.

Этот вывод предложения запишем сокращенно, используя новый символ Þ⁺<предложение> Þ⁺ мать любит сына.

На каждом шаге можно заменить любой нетерминал. В приведенном выше выводе всегда заменялся самый левый из них.

Вывод, на каждом шаге которого заменяется самый левый нетерминал сентенциальной формы, называется левым (левосторонним) выводом. Существует и часто используется также правый (правосторонний) вывод, который получается, если в сентенциальной форме заменять всегда самый правый нетерминал.

Обратите внимание на то, что предложенная грамматика используется для описания многих предложений. Девять правил грамматики, если считать каждую альтернативу за отдельное правило, а так оно и есть, определяют двенадцать предложений (цепочек) языка:

мать любит сына мать обожает сына мать боготворит сына

мать любит дочь мать обожает дочь мать боготворит дочь

отец любит сына отец обожает сына отец боготворит сына

отец любит дочь отец обожает дочь отец боготворит дочь

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

Рассмотрим еще один пример полезной грамматики

Пример 1.2.Грамматики целого числа без знака содержат следующие 13 правил

(1) <число>::=<чс> S ® A

(2) <чс>::=<цифра><чс> A ® AB

(3) <чс>::=<цифра> A ® B

(4) <цифра>::=0 B ® 0

(5) <цифра>::=1 B ® 1

(6) <цифра>::=2 B ® 2

(7) <цифра>::=3 B ® 3

(8) <цифра>::=4 B ® 4

(9) <цифра>::=5 B ® 5

(10) <цифра>::=6 B ® 6

(11) <цифра>::=7 B ® 7

(12) <цифра>::=8 B ® 8

(13) <цифра>::=9 B ® 9.

Заметим, что грамматики G(<число>) и G(S) определяют один и тот же язык и отличаются только именами нетерминалов и вторым правилом ™

А теперь продолжим наши определения.

Пусть G - грамматика. Будем говорить, что цепочка a непосредственно порождает цепочку b, и обозначим a Þ b, если для некоторых цепочекj и y можно написать a = jUy, b = jgy, где U::= g правило грамматики G. Будем также говорить, что b непосредственно выводима из a или что b непосредственно приводится (редуцируется, сворачивается) к a .

Цепочки j и y, конечно, могут быть пустыми. Следовательно, для любого правила A®aграмматики G имеет место A Þ a . На рис. 1.1 даны некоторые примеры непосредственных выводов для грамматики G(<число>) из примера 1.2 и обозначений предыдущего определения.

Будем говорить, что a порождает b или b приводится к a и записывать a Þ⁺ b, если существует последовательность непосредственных выводов a = g₀ Þ g₁ Þ g₂ Þ ... Þ g_n = b, где n>0. Эта последовательность называется выводом длины n. Будем писать a Þ^* b, если a Þ⁺ b или a = b.

Если просмотреть все строки на рисунке 1.1, то мы получим

<число> Þ <чс> Þ <цифра> <чс> Þ 2 <чс> Þ 2 <цифра> Þ 25.

Таким образом, <число> Þ⁺ 22 и длина вывода равна 5. (Если длина вывода известна можно, записывать в явном виде <число> Þ⁵ 22 )

Заметим, что пока в цепочке есть хотя бы один нетерминал, из нее можно вывести новую цепочку, однако если нетерминальные символы отсутствуют, то вывод завершен. Неслучайно "терминалом" (terminal - заключительный, конечный) называют символ, который не встречается в левой части ни одного из правил. Исключение составляют нетерминалы-тупики, которые будут рассмотрены позже.

Цепочка a называется сентенциальной формой, если a выводима из начального символа S, то есть, если SÞ^*a.

Цепочка языка - это сентенциальная форма, состоящая только из терминалов.

Язык L(G(S)) - это множество цепочек: L(G)={ a çSÞ^*a и aÎV_T ^*},

то есть язык - это подмножество множества всех терминальных цепочек V_T ^*.

Структура цепочек языка задается грамматикой и, как видно из примера 1.2, несколько грамматик могут определять один и тот же язык. Такие грамматики называются эквивалентными.

Пусть G(S) - грамматика. И пусть w =abg - сентенциальная форма. Тогда b называется фразой сентенциальной формы w для нетерминального символа U, если SÞ^* aUg и UÞ⁺ b; и далее, b называется простой фразой, если SÞ^* aUg и UÞ g.

Тот факт, что U Þ⁺ b, вовсе не означает, что b является фразой сентенциальной формы abg; необходимо также иметь S Þ^* aUg. Значит ли в примере 1.2, что <чс> является фразой сентенциальной формы 1 <чс>, если существует правило <число>::=<чс> ? Конечно, нет, поскольку невозможен вывод цепочки 1 <число> из начального символа грамматики <число>. Каковы же фразы сентенциальной формы 1 <чс> ? Имеет место вывод

<число> Þ <чс> Þ <цифра><чс> Þ 1<чс>.

Таким образом,

(1) <число> Þ^* <чс> и <чс> Þ⁺1<чс>

(2) <число> Þ^* <цифра><чс> и <цифра> Þ⁺1.

Следовательно, 1<чс> и 1 - фразы, простой же фразой будет только 1.

В дальнейшем мы часто будем говорить о самой левой простой фразе сентенциальной формы, которая называется основой.

Грамматики G(<число>) и G(S) из примера 1.2 описывают бесконечный язык, то есть язык, состоящий из бесконечного числа цепочек. Это обусловлено тем, что правило <чс>::=<цифра><чс> (A®AB) содержит <чс> (A) и в левой, и в правой частях, то есть в некотором смысле символ <чс> (A) сам себя определяет.

В общем случае, еслиUÞ⁺...U..., то говорят, что грамматика рекурсивна по отношению к U. Если UÞ⁺ U..., то имеет место левая рекурсия, а если UÞ⁺...U, то - правая рекурсия. Соответствующие правила называют лево- (право)рекурсивными. Если язык бесконечен, то определяющая его грамматика должна быть рекурсивной.