Пред.Страница  След.Страница    Раздел   Содержание

3. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И МАГАЗИННЫЕ АВТОМАТЫ. 

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

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

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

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

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

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

     Рассматривая правила грамматики,  можно сделать  вывод,  что если все символы правой части являются производящими, то производящим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непроизводящих символов в следующем виде:
    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_тÈ V_A  называется недостижимым в КС-грамматике Г, если X не появляется ни в одной выводимой цепочке.

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

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

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

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

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

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

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

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

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

 Г_{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  }.

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

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

Пред.Страница  След.Страница    Раздел   Содержание