1.2.2. Примеры, иллюстрирующие первичные понятия

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

а) Задана грамматика Г_{1. 0} и требуется определить язык, порождаемый этой грамматикой:

Г_{1. 0}:      V_т = {a, b, c}, V_a = {<I>}, R = {<I> ® abc}.

Схема грамматики содержит одно правило, поэтому Г_{1. 0} порождает язык из одного слова

L(Г_{1. 0}) = {abc}.

 b) Задана грамматика Г_{1. 1} и требуется определить язык, порождаемый этой грамматикой .

Г_{1. 1} :      V_т = {a, b, c}, V_a = {<I>, <B>, <C>}

R =  { <I> ® a<B>,

<B> ® <C>d, <B> ® dc, <C> ® $}.

Построим все выводы в этой грамматике:

<I>  Þ a<B> Þ  a<C>d  Þ ad, <I>  Þ a<B> Þ  adc.

Следовательно язык L(Г_{1. 1}) = {adc, ad}. в) Задана грамматика Г_{1. 2} и требуется определить язык, порождаемый этой грамматикой .

Г_{1. 2} :   V_a = {<I>, <A>}, V_т = {0, 1},

R = {<I> ® 0<A>1,

0<A> ® 00<A>1, <A> ® $}.

Рассмотрим несколько выводов с помощью правил грамматики Г_{1. 2}. Применяя первое и третье правила, получаем:

<I> Þ 0<A>1 Þ 01.

Применяя два раза первое правило и третье, имеем

<I> Þ 0<A>1 Þ 00<A>11 Þ 0011.

В общем случае, применяя K раз первое правило, получим в результате цепочку, содержащую K нулей и K единиц. Следовательно, язык, порождаемый грамматикой Г_{1. 2}, содержит всевозможные цепочки, в которых число нулей равно числу единиц. г) Задана грамматика Г_{1. 3} и требуется построить язык, порождаемый этой грамматикой.

Г_{1. 3} :       V_т = {a, b}, V_a = {<I>, <A>},

R = { <I> ® a<A>,         <A> ® b<A>}.

Попытка построения вывода в этой грамматике приводит нас к цепочке:

<I> Þ a<A> Þ ab<A> Þ abb<A> Þ... ,

которая оказывается бесконечной. Другими словами, Г_{1. 3} порождает пустой язык.

1.2.3. Пустой язык

Определение.  Если язык, порождаемый грамматикой Г, не содержит ни одной конечной цепочки (конечного слова), то он называется пустым.   Утверждение.  Для того, чтобы язык L( Г ) не был пустым, в множестве R должно быть хотя бы одно правило вида r = c ® y, где y Î Vт* и должен существовать вывод  <I> Þ* c.

1.2.4. Резюме

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

1.3. Типы формальных языков и грамматик

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

1.3.1. Грамматики типа 0

Грамматики типа 0, которые называют грамматиками общего вида, не имеют никаких ограничений на правила порождения. Любое правило

r = h ® y

может быть построено с использованием произвольных цепочек  h, y Î (V_т È V_a)*. Например,  

<T><W> ® <W><T>  или  x<A>b<C><D> ® x<H><D>.