2.5 Исключение леворекурсивных правил.

Определение. Правило вида <A>  <A> , где A  VA ,  (Vт VA) * , называется праворекурсивным, а правило вида <A>  <A> - леворекурсивным.

Утверждение. Для каждой КС-грамматики Г, содержащей леворекурсивные правила, можно построить эквивалентную грамматику Г', не содержащую леворекурсивных правил.

Способ построения эквивалентной грамматики заключается в следующем. Допустим, что исходная грамматика Г содержит правила: <A>  <A> ₁ | <A> ₂ | ... |<A> _m| , где ни одна цепочка  не начинается с <A> и _ _(Vт V_A) ^* . Введем новый нетерминал <A'> и преобразуем правила так: <A>   ₁ |  ₂ |...|  _n |  ₁<A'> |  ₂<A'>|...|  _n<A'>, <A'>  ₁ |  ₂ |...|  _m|  ₁<A'> | ₂<A'>|...|_m<A'>. Заменяя все правила с левой рекурсией в Г описанным способом, получим грамматику Г', причем L(Г)=L(Г') , поскольку каждая цепочка, выведенная в грамматике Г, может быть построена в грамматике Г'. Рассмотрим построение выводов в Г и Г'. В грамматике Г вывод цепочки имеет вид: < A>  <A> ₁  <A> ₁ ₁  <A> ₁ ₁ ₁   ₁ ₁ ₁ ₁, в грамматике Г' эта же цепочка выводится так: <A>   ₁<A'>   ₁ ₁<A'>   ₁ ₁ ₁<A'>   ₁ ₁ ₁ ₁. Чтобы показать технику преобразования, рассмотрим пример. Требуется преобразовать грамматику Г_{1. 9} (рассмотренную ранее), которая задана схемой: Г_{1. 9}: R={<E>  <E> + <T> | <T>, < T>  <T> * <F> | <F>, <F>  ( <E> ) | a}. Следуя описанному способу, правила <E>  <E> + <T> | <T> преобразуем в правила <E> <T> | <T><E'> и <E'>  +<T> | +<T><E'> , а правила <T>  <T> * <F> | <F> преобразуем в правила <T>  <F> | <F><T'> и <T'>  F> | * <F><T'>. В результате получаем грамматику Г'_{1. 9}, имеющую схему: Г'_{1. 9} : R'= { <E>  < T>, <E>  <T><E'>, < E'> + <T>, <E'>  + <T><E'>, <T>  <F>, <T>  <F><T'>, <T'>  * <F>, <T'>  * <F><T'>, < F>  a, <F>  (<E>) }, не содержащую леворекурсивных правил.

2.6 Исключение цепных правил.

Определение. Правило грамматики вида <A>  <B>, где <A>,<B> VA, называется цепным.

Утверждение. Для КС-грамматики Г, содержащей цепные правила , можно построить эквивалентную ей грамматику Г', не содержащую цепных правил.

Идея доказательства заключается в следующем. Если схема грамматики имеет вид R = {...,<A>  <B>,...,<B>  <C>, ... , <C> a<X> },то такая грамматика эквивалентна грамматике со схемой R' = {...,<A>  a<X>,...},поскольку вывод в грамматике со схемой R цепочки a<X> : <A>  B>  <C> a<X> может быть получен в грамматике со схемой R' с помощью правила <A>  a<X>. В общем случае доказательство последнего утверждения можно выполнить так. Разобьем R на два подмножества R₁ и R₂, включая в R₁ все правила вида <A>  B>. Для каждого правила из R₁ найдем множество правил S(<A_i>), которые строятся так: если <A_i>  * <A_j> и в R₂ есть правило <A_j>   , где  - цепочка словаря (V_т V_A)^* , то в S(<A_i>) включим правило <A_i>   . Построим новую схему R' путем объединения правил R₂ и всех построенных множеств S(<A_i>). Получим грамматику Г' = {V_т ,V_a , I , R'}, которая эквивалентна заданной и не содержит правил вида <A>  <B>. В качестве примера выполним исключение цепных правил из грамматики Г_{1. 9} со схемой : Г_{1. 9}: R={<E>  <E> + <T> | <T>, < T>  T> * <F> | <F>, <F>  ( <E> ) | a}. Вначале разобьем правила грамматики на два подмножества: R₁ = { <E>  <T>,<T>  <F> } , R₂ = { <E>  <E>+<T>, <T>  <T>*<F>, <F>(<E>) | a }. Для каждого правила из R1 построим соответствующее подмножество. S(<E>) = { <E>  T>*<F>, <E> (<E>) | a }, S(<T>) = { <T>  (<E>) | a}. В результате получаем искомую схему грамматики без цепных правил в виде: R2 U S(<E>) U S(<T>) = { <E>  --> <T>+<T> | <T>*<F> | (<E>) | a, <T>  <T>*<F> | (<E>) | a, <F>  (<E>) | a }.Последний вид рассматриваемых преобразований связан с удалением из грамматики правил с пустой правой частью.

Определение. Правило вида <A>  $ называется аннулирующим правилом.

2.7 Преобразование неукорачивающих грамматик.

Определение. Грамматика называется неукорачивающей или грамматикой без аннулирующих правил, если либо 1)схема грамматики не содержит аннулирующих правил, 2)либо схема грамматики содержит только одно правило вида <I>  $, где <I> - начальный символ грамматики, и символ I не встречается в правых частях остальных правил грамматики.

Для грамматик, содержащих аннулирующие правила, справедливо следующее утверждение.

Утверждение. Для каждой КС-грамматики Г', содержащей аннулирующие правила, можно построить эквивалентную ей неукорачивающую грамматику Г, такую что L(Г')=L(Г).

Построение неукорачивающей грамматики предполагает увеличение числа правил заданной грамматики путем построения дополнительных правил, получаемых в результате исключения нетерминалов аннулирующих правил. Чтобы построить дополнительные правила необходимо выполнить все возможные подстановки пустой цепочки вместо аннулирующего нетерминала во все правила грамматики. Если же в грамматике есть правило вида <I>  $ и символ <I> входит в правые части других правил грамматики, то следует ввести новый начальный символ <I'> и заменить правило <I>  $ двумя новыми правилами: <I'>  $ и <I'> <I> . В качестве иллюстрации способа построения неукорачивающих грамматик, исключим аннулирующие правила из следующей грамматики: Г_{2. 3} : R = { <I>  a<I>b<I>, <I>  b<I>a<I>, <I>  $ } Выполняя все возможные замены символа I в первом правиле грамматики, получаем четыре правила вида: <I>  a<I>b<I>, <I>  ab<I>, <I> a<I>b, <I> ab .

Поступая аналогично со вторым правилом, имеем: <I> b<I>a<I>, <I> ba<I>, <I>  b<I>a, <I>  ba. Учитывая, что начальный символ, образующий аннулирующее правило, входит в правые части других правил грамматики, заменим правило <I>  $ правилами вида <I'> $ и <I'> <I> . Построенная совокупность правил образует схему искомой неукорачивающей грамматики. Все приведенные выше преобразования грамматик могут быть использованы и оказаться полезными при построении как конечных, так и магазинных автоматов.

6.Построение распознавателя для конечного языка.

3.3 Построение детерминированного нисходящего распознавателя.

Способ построения распознавателя предусматривает сопоставление каждому правилу грамматики команды распознавателя . Согласно общему способу построения распознавателей для КС-грамматик, описанному в предыдущем разделе, каждому правилу разделенной грамматики, которые имеют вид: <A> a  , где  - цепочка символов полного словаря и a принадлежит терминальному словарю, нужно поставить в соответствие команду (*) f ⁰( s₀ ,  , <A> ) = ( s₀ ,  ' a) , которая задает такт работы без сдвига входной головки и в которой  ' представляет собой зеркальное отображение цепочки  . Отметим, что в результате выполнения этой команды, в вершине магазина окажется терминал a. Общий способ построения редусматривает также построение для каждого a символа грамматики команды: (**) f ( s₀ , a , a ) = ( s₀ , $ ) которая удаляет этот терминал из магазина и сдвигает входную головку. Учитывая, что в разделенной грамматике каждое правило начинается с терминального символа, и что эти терминалы не повторяются, можно сделать вывод о том , что команда (*) должна выполняться только в том случае, когда под входной головкой находится терминал a, и после нее всегда должна выполняться команда (**). Чтобы исключить неопределенность правил вида (*) и уменьшить число тактов работы распознавателя, объединим команды вида (*) и (**) в одну команду. Построение такой команды должно выполняться следующим образом: каждому правилу разделенной грамматики <A>  a  поставим в соответствие команду f ( s₀ , a , <A>) = ( s₀ ,  ') , которая определяет такт работы распознавателя со сдвигом входной головки. Кроме того, следует учесть, что терминальные символы могут быть расположены в правых частях правил не только на самой левой позиции. Для таких терминалов необходимо построить команды вида : f ( s₀ , b , b ) = ( s₀ , $ ) Для перехода в заключительное состояние добавим правило: f ( s₀ , $ ,h₀ ) = ( s₁ , $ ) , а в качестве начальной конфигурации распознавателя примем, как обычно, следующее выражение: ( s₀ ,  , h₀<I> ) , где <I> - начальный символ грамматики, а  - заданная входная цепочка. Применяя приведенные выше правила, построим распознаватель для разделенной грамматики Г_{3. 0} . В результате получаем: М ₄ : P = { a , b }, H = { a , b ,<I> , <B> , h₀ }, S = {s₀}, F= {s₀},f ( s₀ , a , <I>) = ( s₀ , <B>b ) f ( s₀ , a , <B>) = ( s₀ , $ ) f ( s₀ , b , <I> ) = ( s₀ , <I> b <B> ) f ( s₀ , b , <B> ) = ( s₀ , <B> ) f ( s₀ , b , b ) = ( s₀ , $ ) f ( s₀ ,  , h₀ ) = ( s₀ , $ ) Работу построенного автомата покажем на примере анализа цепочки bbabab.

( s₀ , bbababa , h₀<I> )  ( s₀ , bababa , h₀<I>b<B> ) 

( s₀ , ababa , h₀<I>b<B> )  ( s₀ , baba , h₀<I>b ) 

( s₀ , aba , h₀<I> )  ( s₀ , ba , h₀<B>b )  ( s₀ , a , h₀<B> )

 ( s₀ , $ , h₀ )  ( s₀ , $ , $ ) . Приведенная последовательность конфигураций показывает, что в каждой конфигурации может быть применена единственная команда детерминированного распознавателя.

7.КС-грамматики. Неукорачивающиеся грамматики. Исключение леворекурсивных правил. Приведенные грамматики.

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

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

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

Рассматривая правила грамматики, можно сделать вывод, что если все символы правой части являются производящими, то производящим является и символ, стоящий в левой части. Последнее утверждение позволяет написать процедуру обнаружения непроизводящих символов в следующем виде: 1. Составить список нетерминалов, для которых найдется хотя бы одно правило, правая часть которого не содержит нетерминалов. 2. Если найдено такое правило, что все нетерминалы, стоящие в его правой части уже занесены в список, то добавить в список нетерминал, стоящий в его левой части. 3. Если на шаге 2 список больше не пополняется, то получен список всех производящих нетерминалов грамматики, а все нетерминалы не попавшие в него являются непроизводящими. Анализируя в соответствии с приведенными правилами следующую грамматику : Г_{2. 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}.

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

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

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

Образовать одноэлементный список, состоящий из начального символа. Если найдено правило, левая часть которого уже имеется в списке, то включить в список все символы, содержащиеся в его правой части. Если на шаге 2 новые нетерминалы в список больше не добавляются, то получен список всех достижимых нетерминалов, а нетерминалы, не попавшие в список, являются недостижимыми. Например, применяя приведенные правила к следующей грамматике: Г_{2. 1} : R = { <I> a<I>b, <I> c, <A> b<I>, <A> a },

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

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

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

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

Исключить бесполезные символы из грамматики можно удаляя правила, содержащие вначале непроизводящие, а затем недостижимые символы. В качестве иллюстрации применения приведенных правил выполним преобразование следующей грамматики: Г_{2. 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 }. 

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

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

2.5 Исключение леворекурсивных правил.

Определение. Правило вида <A>  <A> , где A  VA ,  (Vт VA) * , называется праворекурсивным, а правило вида <A>  <A> - леворекурсивным.

Утверждение. Для каждой КС-грамматики Г, содержащей леворекурсивные правила, можно построить эквивалентную грамматику Г', не содержащую леворекурсивных правил.

Способ построения эквивалентной грамматики заключается в следующем. Допустим, что исходная грамматика Г содержит правила: <A>  <A> ₁ | <A> ₂ | ... |<A> _m| , где ни одна цепочка  не начинается с <A> и _ _(Vт V_A) ^* . Введем новый нетерминал <A'> и преобразуем правила так: <A>   ₁ |  ₂ |...|  _n |  ₁<A'> |  ₂<A'>|...|  _n<A'>, <A'>  ₁ |  ₂ |...|  _m|  ₁<A'> | ₂<A'>|...| _m<A'>. Заменяя все правила с левой рекурсией в Г описанным способом, получим грамматику Г', причем L(Г)=L(Г') , поскольку каждая цепочка, выведенная в грамматике Г, может быть построена в грамматике Г'. Рассмотрим построение выводов в Г и Г'. В грамматике Г вывод цепочки имеет вид: < A>  <A> ₁  <A> ₁ ₁  <A> ₁ ₁ ₁   ₁ ₁ ₁ ₁, в грамматике Г' эта же цепочка выводится так: <A>   ₁<A'>   ₁ ₁<A'>   ₁ ₁ ₁<A'>   ₁ ₁ ₁ ₁.

Чтобы показать технику преобразования, рассмотрим пример. Требуется преобразовать грамматику Г_{1. 9} (рассмотренную ранее), которая задана схемой: Г_{1. 9}: R={<E>  <E> + <T> | <T>, < T>  <T> * <F> | <F>, <F>  ( <E> ) | a}.Следуя описанному способу, правила <E>  <E> + <T> | <T> преобразуем в правила <E> <T> | <T><E'> и <E'>  +<T> | +<T><E'> , а правила <T>  <T> * <F> | <F> преобразуем в правила <T>  <F> | <F><T'> и <T'>  F> | * <F><T'>. В результате получаем грамматику Г'_{1. 9}, имеющую схему: Г'_{1. 9} : R'= { <E>  < T>, <E>  <T><E'>, < E'> + <T>, <E'>  + <T><E'>, <T>  <F>, <T>  <F><T'>, <T'>  * <F>, <T'>  * <F><T'>, < F>  a, <F>  (<E>) }, не содержащую леворекурсивных правил.

2.6 Исключение цепных правил.

Определение. Правило грамматики вида <A>  <B>, где <A>,<B> VA, называется цепным.

Утверждение. Для КС-грамматики Г, содержащей цепные правила , можно построить эквивалентную ей грамматику Г', не содержащую цепных правил.

Идея доказательства заключается в следующем. Если схема грамматики имеет вид R = {...,<A>  <B>,...,<B>  <C>, ... , <C> a<X> }, то такая грамматика эквивалентна грамматике со схемой

R' = {...,<A>  a<X>,...}, поскольку вывод в грамматике со схемой R цепочки a<X> : <A>  B>  <C> a<X> может быть получен в грамматике со схемой R' с помощью правила <A>  a<X>. В общем случае доказательство последнего утверждения можно выполнить так. Разобьем R на два подмножества R₁ и R₂, включая в R₁ все правила вида <A>  B>. Для каждого правила из R₁ найдем множество правил S(<A_i>), которые строятся так: если <A_i>  * <A_j> и в R₂ есть правило <A_j>   , где  - цепочка словаря (V_т V_A)^* , то в S(<A_i>) включим правило <A_i>   . Построим новую схему R' путем объединения правил R₂ и всех построенных множеств S(<A_i>). Получим грамматику Г' = {V_т ,V_a , I , R'}, которая эквивалентна заданной и не содержит правил вида <A>  <B>. В качестве примера выполним исключение цепных правил из грамматики Г_{1. 9} со схемой : Г_{1. 9}: R={<E>  <E> + <T> | <T>, < T>  T> * <F> | <F>, <F>  ( <E> ) | a}.

Вначале разобьем правила грамматики на два подмножества: R₁ = { <E>  <T>,<T>  <F> } , R₂ = { <E>  <E>+<T>, <T>  <T>*<F>, <F>(<E>) | a }Для каждого правила из R1 построим соответствующее подмножество. S(<E>) = { <E>  T>*<F>, <E> (<E>) | a }, S(<T>) = { <T>  (<E>) | a}

В результате получаем искомую схему грамматики без цепных правил в виде:

R2 U S(<E>) U S(<T>) = { <E>  --> <T>+<T> | <T>*<F> | (<E>) | a, <T>  <T>*<F> | (<E>) | a, <F>  (<E>) | a }

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

Определение. Правило вида <A>  $ называется аннулирующим правилом.

2.7 Преобразование неукорачивающих грамматик.

Определение. Грамматика называется неукорачивающей или грамматикой без аннулирующих правил, если либо 1)схема грамматики не содержит аннулирующих правил, 2)либо схема грамматики содержит только одно правило вида <I>  $, где <I> - начальный символ грамматики, и символ I не встречается в правых частях остальных правил грамматики.

Для грамматик, содержащих аннулирующие правила, справедливо следующее утверждение.

Утверждение. Для каждой КС-грамматики Г', содержащей аннулирующие правила, можно построить эквивалентную ей неукорачивающую грамматику Г, такую что L(Г')=L(Г).

Построение неукорачивающей грамматики предполагает увеличение числа правил заданной грамматики путем построения дополнительных правил, получаемых в результате исключения нетерминалов аннулирующих правил. Чтобы построить дополнительные правила необходимо выполнить все возможные подстановки пустой цепочки вместо аннулирующего нетерминала во все правила грамматики. Если же в грамматике есть правило вида <I>  $ и символ <I> входит в правые части других правил грамматики, то следует ввести новый начальный символ <I'> и заменить правило <I>  $ двумя новыми правилами: <I'>  $ и <I'> <I> . В качестве иллюстрации способа построения неукорачивающих грамматик, исключим аннулирующие правила из следующей грамматики: Г_{2. 3} : R = { <I>  a<I>b<I>, <I>  b<I>a<I>, <I>  $ } Выполняя все возможные замены символа I в первом правиле грамматики, получаем четыре правила вида:

<I>  a<I>b<I>, <I>  ab<I>, <I> a<I>b, <I> ab . Поступая аналогично со вторым правилом, имеем: <I> b<I>a<I>, <I> ba<I>, <I>  b<I>a, <I>  ba. Учитывая, что начальный символ, образующий аннулирующее правило, входит в правые части других правил грамматики, заменим правило <I>  $ правилами вида <I'> $ и <I'> <I> . Построенная совокупность правил образует схему искомой неукорачивающей грамматики. Все приведенные выше преобразования грамматик могут быть использованы и оказаться полезными при построении как конечных, так и магазинных автоматов.

8.Определение и правила вычисления функции ПЕРВ. Использование функции.

3.4 Множество выбора.

Другой класс грамматик, порождающих детерминированные языки, называется слаборазделенными грамматиками. Этот класс отличается от класса разделенных грамматик тем, что он допускает использование аннулирующих правил в схеме грамматики. Однако, не всякая разделенная грамматика с аннулирующими правилами относится к классу слаборазделенных грамматик. Чтобы сформулировать определение, позволяющее опознавать слаборазделенные и LL(1) грамматики, нам потребуются новые понятия: множество ВЫБОР, функции ПЕРВ и СЛЕД .