2.6 Резюме

• Грамматики типа 3 называют автоматными, поскольку в качестве распознавателей цепочек, порождаемых этими грамматиками, используются конечные автоматы без выходов.

• Построение распознавателя для заданной автоматной грамматики выполняется достаточно просто путем построения диаграммы или таблицы переходов по схеме грамматики.

• Если заданная грамматика не содержит правил с одинаковой левой частью, правая часть которых начинается одинаковыми терминальными с символами, то такой грамматике соответствует детерминированный распознаватель.

• Интересным свойством А-распознавателей является то, что для любого недетерминированного распознавателя можно построить эквивалентный ему детерминированный распознаватель. Это означает, что все автоматные языки могут распознаваться с помощью детерминированных устройств.

• Одним из практических применений автоматных грамматик является построение распознавателей для конечных языков.

• Во многих случаях число состояний распознавателей конечных языков удается сократить за счет объединения эквивалентных состояний.

3. Контекстно-свободные грамматики и магазинные автоматы.

3.1 Приведенные грамматики.

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

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

Вначале рассмотрим алгоритм выявления символов, из которых нельзя вывести конечные цепочки.

  Определение непроизводящих символов.

Определение. Символ <X> ÎVA называется непроизводящим, если из него не может быть выведена конечная терминальная цепочка.

     Рассматривая правила грамматики,  можно сделать  вывод,  что если все символы правой части являются производящими, то производящим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непроизводящих символов в следующем виде:     1. Составить список нетерминалов,  для которых найдется хотя  бы одно правило, правая часть которого не содержит нетерминалов.     2. Если найдено такое правило,  что все нетерминалы, стоящие  в его правой части уже занесены в список,  то добавить  в  список  нетерминал, стоящий в его левой части.     3. Если на шаге 2 список больше не пополняется,  то  получен  список всех производящих нетерминалов грамматики,  а все нетерминалы не попавшие в него являются непроизводящими. Анализируя в соответствии с приведенными правилами следующую грамматику : Г_{3. 0}: R = {<I>®a<I>a, <I>®b<A>d, <I>®c, <A>®c<B>d, <A>®a<A>d, <B>®d<A>f  }, находим, что здесь непроизводящими являются символы <А> и <В>. После удаления правил, содержащих непроизводящии символы, получаем:   R' = {<I> ®a<I>a, <I>® c}.

Определения недостижимых символов.

Определение.  Символ X  Î VтÈ VA  называется недостижимым в КС-грамматике Г, если X не появляется ни в одной выводимой цепочке.

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

1. Образовать одноэлементный список, состоящий из начального символа

2. Если найдено правило, левая часть которого уже имеется в списке, то включить в  список все символы, содержащиеся в его правой части.

3.  Если на шаге 2 новые нетерминалы в список больше  не  добавляются,  то получен список всех достижимых нетерминалов, а нетерминалы, не попавшие в список, являются недостижимыми.

Например, применяя приведенные правила к следующей грамматике:

Г_{3. 1} :      R = { <I> ®a<I>b, <I> ®c, <A> ®b<I>, <A> ®a   },

находим, что A является недостижимым символом.

  Определения бесполезных символов.

Бесполезный символ грамматики можно определить следующим образом:

Определение. Символ X, который принадлежит VтU Va называется бесполезным в  КС-грамматике Г, если он является недостижимым или непроизводящим.

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

 Г_{3. 2} : R = {<I>®ac,

<I>® b<A>, <A>® c<B><C>, <B>® a<I><A>, <C>® bc, <C>® d  }.

Вначале находим, что <А> и <В> являются непроизводящими символами и, исключая правила с непроизводящими символами , получаем:

R' = {<I>®ac,          <C>® bc,          <C>® d  }.

В полученной схеме символ <C>  является недостижимым символом. Исключая правила, содержащие этот символ, получаем:

R" = {<I>®ac  }.

Определение. КС-грамматика называется приведенной, если она  не содержит бесполезных символов.

В дальнейшем изложении рассматриваются только приведенные КС-грамматики. Другие виды преобразований грамматик, описываемые ниже, предназначены для  исключения правил определенного вида из схемы грамматики.