Преобразования грамматик

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

Определение: символ A Î VN называется бесплодным в грамматике G = (VT, VN, P, S), если множество { a | a Î VT^*, A Þ a} пусто.

Алгоритм удаления бесплодных символов:

Вход: КС-грамматика G = (VT, VN, P, S).

Выход: КС-грамматика G’ = (VT, VN’, P’, S), не содержащая бесплодных символов, для которой L (G) = L (G’).

Метод:

Рекурсивно строим множества N₀, N₁,...

1. N₀ = Æ, i = 1.

2. N_i = {A | (A ® a) Î P и a Î (N_i-1 È VT)^*} È N_i-1.

3. Если N_i ¹ N_i-1, то i = i+1 и переходим к шагу 2, иначе VN’ = N_i; P’ состоит из правил множества P, содержащих только символы из VN’ È VT; G’ = (VT, VN’, P’, S).

Определение: символ x Î (VT È VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.

Алгоритм удаления недостижимых символов:

Вход: КС-грамматика G = (VT, VN, P, S)

Выход: КС-грамматика G’ = (VT’, VN’, P’, S), не содержащая недостижимых символов, для которой L(G) = L(G’).

Метод:

1. V₀ = {S}; i = 1.

2. V_i = {x | x Î (VT È VN), (A ® axb) Î P и A Î V_i-1} È V_i-1.

3. Если V_i ¹ V_i-1, то i = i+1 и переходим к шагу 2, иначе VN’ =
V_i Ç VN; VT’ = V_i Ç VT; P’ состоит из правил множества P, содержащих только символы из Vi; G’ = (VT’, VN’, P’, S).

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

Алгоритм приведения грамматики:

(1) обнаруживаются и удаляются все бесплодные нетерминалы.

(2) обнаруживаются и удаляются все недостижимые символы.

Удаление символов сопровождается удалением правил вывода, содержащих эти символы.

Замечание: е сли в этом алгоритме переставить шаги (1) и (2), то не всегда результатом будет приведенная грамматика.

Для описания синтаксиса языков программирования стараются использовать однозначные приведенные КС-грамматики.

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

Определение. Правило грамматики вида A ® B, где A,B Î VN, называется цепным.

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

Идея доказательства заключается в следующем.

Если грамматика G имеет правила A ® B, B ® C, C ® aX, то такие правила могут быть заменены одним правилом А ® aX, поскольку вывод A Þ B Þ C Þ aX цепочки aX в грамматике G может быть получен в грамматике G' с помощью правила A ® aX.

В общем случае доказательство последнего утверждения можно выполнить так.

Разобьем множество правил P грамматики G на два подмножества P₁ и P₂, включая в P₁ все правила вида A ® B.

Для каждого правила из P₁ найдем множество правил S(A_i), которые строятся так:
если A_i Þ * A_j и в P₂ есть правило A_j ® a, где a - цепочка словаря (VN ÈVT) ^*, то в S(A_i) включим правило A_i ® a.

Построим новое множество правил P’ путем объединения правил P₂ и всех построенных множеств S(A_i). Получим грамматику G' = {VN,VT, P’, S}, которая эквивалентна заданной и не содержит правил вида A ® B.

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

G = ({+,*,(,),a}, {E,T,F}, P={E ® E+T | T, T ® T*F | F, F ® (E) | a}, E).

Вначале разобьем правила грамматики на два подмножества:

P₁ = {E ® T, T ® F},

P₂ = {E ® E+T, T ® T*F, F ® (E) | a }

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

S(E) = { E ® T*F, E ® (E) | a },

S(T) = { T ® (E) | a}

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

P2 U S(E) U S(T) = { E ® T+T | T*F | (E) | a, T ® T*F | (E) | a, F ® (E) | a }

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

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

Определение. Правило вида A ® l называется «пустым» (аннулирующим) правилом.

Определение. Грамматика называется неукорачивающей или грамматикой без «пустых» правил, если либо

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

2)либо схема грамматики содержит только одно правило вида S ® l, где S - начальный символ грамматики, и символ S не встречается в правых частях остальных правил грамматики.

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

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

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

Если же в грамматике есть правило вида S ® l, где S – начальный символ грамматики, и символ S входит в правые части других правил грамматики, то следует ввести новый начальный символ S’ и заменить правило S ® l двумя новыми правилами: S' ® l и S' ® S.

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

G ({a,b}, {S}, P = { S ® aSbS, S ® bSaS, S ® l }, S).

Выполняя все возможные замены символа S в первом правиле грамматики, получаем четыре правила вида:

S ® aSbS, S ® abS, S ® aSb, S ® ab.

Поступая аналогично со вторым правилом, имеем:

S ® bSaS, S ® baS, S ® bSa, S ® ba.

Учитывая, что начальный символ, образующий аннулирующее правило, входит в правые части других правил грамматики, заменим правило S ® l правилами вида S' ® l и S' ® S.

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

S' ® S | l

S ® aSbS | abS | aSb | ab | bSaS | baS | bSa | ba

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

КС-грамматики в нормальной форме

Грамматики в нормальной форме Хомского

Нормальная форма Хомского или бинарная нормальная форма (БНФ) — это одна из предопределенных форм для правил КС-грамматики. В нормальную форму Хомского можно преобразовать любую произвольную КС-грамматику. Для пре­образования в нормальную форму Хомского предварительно грамматику надо преобразовать в приведенный вид.

Определение нормальной формы Хомского

КС-грамматика G(VT,VN,P,S) называется грамматикой в нормальной форме Хомского, если в ее множестве правил Р присутствуют только правила следую­щего вида:

1. А ® ВС, где A,B,CÎVN.

2. А ® а, где AÎVN и aÎVT.

3. S ® l, если lÎL(G), причем S не должно встречаться в правых частях других правил.

Никакие другие формы правил не должны встречаться среди правил граммати­ки в нормальной форме Хомского [6, т. 1, 26].

КС-грамматика в нормальной форме Хомского называется также грамматикой в бинарной нормальной форме (БНФ). Название «бинарная» происходит от того, что на каждом шаге вывода в такой грамматике один нетерминальный символ может быть заменен только на два других нетерминальных символа. Поэтому в дереве вывода грамматики в нормальной форме Хомского каждая вершина либо распадается на две другие вершины (в соответствии с первым видом правил), либо содержит один последующий лист с терминальным символом (в соответст­вии со вторым видом правил) Третий вид правил введен для того, чтобы к нор­мальной форме Хомского можно было преобразовывать грамматики КС-языков, содержащих пустые цепочки символов.

Алгоритм преобразования грамматики в нормальную форму Хомского

Алгоритм позволяет преобразовать произвольную исходную КС-грамматику в эквивалентную грамматику в нормальной форме Хомского.

Условие: дана КС-грамматика G(VT,VN,P,S), необходимо построить эквивалентную ей грамматику G'(VT,VN',P',S') в нормальной форме Хомского: L(G) = L(G').

На первом шаге исходную грамматику надо преобразовать к приведенному виду. Поскольку алгоритм преобразования КС-грамматик к приведенному виду был рассмотрен выше, можно считать, что исходная грамматика уже является приве­денной (не содержит бесполезных и недостижимых символов, цепных правил и l-правил).

В начале работы алгоритма преобразования приведенной КС-грамматики в нор­мальную форму Хомского множество нетерминальных символов VN' результи­рующей грамматики G' строится на основе множества нетерминальных симво­лов VN исходной грамматики G: VN’ = VN.

Затем алгоритм преобразования работает с множеством правил Р исходной грам­матики G. Он просматривает все правила из множества Р и в зависимости от вида каждого правила строит множество правил Р' результирующей граммати­ки G' и дополняет множество нетерминальных символов этой грамматики VN'.

1. Если встречается правило вида А®а, где AÎ VN и aÎ VT, то оно переносится во множество Р' без изменений.

2. Если встречается правило вида А®ВС, где A,B,CÎ VN, то оно переносится во множество Р' без изменений.

3. Если встречается правило вида S®l, где S — целевой символ грамматики G, то оно переносится во множество Р' без изменений.

4. Если встречается правило вида А®аВ, где A,BÎ VN и aÎ VT, то во множест­во правил Р' включаются правила А®<АаВ>В и <АаВ>®а и новый символ <АаВ > добавляется во множество нетерминальных символов VN' граммати­ки G'.

5. Если встречается правило вида А®Ва, где A.BÎ VN и aÎ VT, то во множество правил Р' включаются правила А®В<АВа> и <АВа>®а, и новый символ <АВа> добавляется во множество нетерминальных символов VN' граммати­ки G'.

6. Если встречается правило вида А®аЬ, где A Î VN и a,bÎ VT, то во множество правил Р' включаются правила А®<Аа><АЬ>, <Аа>®а и <Ab>®b, новые символы <Аа> и <АЬ> добавляются во множество нетерминальных симво­лов VN' грамматики G'.

7. Если встречается правило вида A®X₁...X_k, k>2, где AÎ VN и "i: X_iÎ VT È VN, то во множество правил Р' включается цепочка правил:

А ® <X₁’><X₂...X_k>

<X₂...X_k> ® <X₂’><X₃...X_k>

<X_k-1X_k> ® <X_k-1’><X_k>

новые нетерминальные символы <Х₂...Х_k>, <Х₃...Х_k);>,..., <X_k-1,X_k> включают­ся во множество нетерминальных символов VN' грамматики G', кроме того, "i: если X_iÎ VN, то <Х_i'>ºХ_i иначе (если X_iÎ VT) <X_i'> — это новый нетер­минальный символ, он добавляется во множество VN', а во множество пра­вил Р' грамматики G' добавляется правило <Х_i'> ® X_i.

Целевым символом результирующей грамматики G' является целевой символ исходной грамматики G.

Пример преобразования грамматики в нормальную форму Хомского

Рассмотрим в качестве примера грамматику G({a,b.c}.{A,B,C,S}, P,S)

Р:

S ® АаВ | Аа | be

А ® АВ | а | аС

В ® Ва | b

С ® АВ | с

Эта грамматика уже находится в приведенной форме. Построим эквивалентную ей грамматику G'(VT,VN',P',S) в нормальной форме Хомского. Начнем построе­ние с множества нетерминальных символов новой грамматики: VN' = {A,B,C,S}. Множество еще будет дополняться в процессе работы алгоритма.

Начнем разбирать правила этой грамматики.

Первое правило исходной грамматики S®AaB подпадает под 7-й вариант рабо­ты алгоритма. В соответствии с требованиями алгоритма заменяем его на после­довательность:

S ® <A'><aB>

<aB> ® <а'><В'>

Поскольку А и В — нетерминальные символы, а «а» — терминальный символ, то получаем, что <А'>ºА и <В'>ºВ, а новое правило <а'>->а должно быть добав­лено во множество правил Р' новой грамматики. Получаем последовательность правил:

S ® А <аВ>

<аВ> ® <а'>В

<а'> ® а

Во множество нетерминальных символов VN' новой грамматики необходимо до­бавить новые символы <аВ> и <а'>. Получаем VN' = {A,B,C,S,<aB>,<a'>}.

Второе правило исходной грамматики S ® Aa подпадает под 5-й вариант работы алгоритма. Заменяем его на два правила:

S ® A<SAa>

<SAa> ® а

Новый символ <SAa> добавляется во множество нетерминальных символов но­вой грамматики. Получаем VN' = {A,B,C,S,<aB>,<a'>,<SAa>}.

Третье правило исходной грамматики S ® bc подпадает под 6-й вариант работы алгоритма. Заменяем его на три правила:

S ® <Sb><Sc>

<Sb> ® b

<Sc> ® с

Новые символы <Sb> и <Sc> добавляются во множество нетерминальных сим­волов новой грамматики. Получаем VN' = {A,B>C,S,<aB>,<a'>,<SAa>,<Sb>,<Sc>}.

Четвертое правило исходной грамматики А ® АВ подпадает под 2-й вариант рабо­ты алгоритма. Переносим его во множество правил новой грамматики без изме­нений.

Пятое правило исходной грамматики А ® а подпадает под 1-й вариант работы ал­горитма. Переносим его во множество правил новой грамматики без изменений.

Шестое правило исходной грамматики А ® аС подпадает под 4-й вариант работы алгоритма. Заменяем его на два правила:

А ® <АаС>С

<АаС> ® а

Новый символ <АаС> добавляется во множество нетерминальных символов но­вой грамматики. Получаем VN' = {A,B,C,S,<aB>,<a'>,<SAa>,<Sb>,<Sc>,<AaC>}.

Седьмое правило исходной грамматики В ® Ва подпадает под 5-й вариант работы алгоритма. Заменяем его на два правила:

В ® В<ВВа>

<ВВа> ®а

Новый символ <ВВа> добавляется во множество нетерминальных символов но­вой грамматики. Получаем VN' = {A,B,C,S,<aB>,<a'>,<SAa>,<Sb>,<Sc>,<AaC>, <ВВа>}.

Восьмое правило исходной грамматики B ® b подпадает под 1-й вариант работы алгоритма. Переносим его во множество правил новой грамматики без изменений.

Девятое правило исходной грамматики С->АВ подпадает под 2-й вариант работы алгоритма. Переносим его во множество правил новой грамматики без изменений.

Десятое правило исходной грамматики С-»с подпадает под 1-й вариант работы алгоритма. Переносим его во множество правил новой грамматики без изменений.

Рассмотрение множества правил исходной грамматики закончено. Множество правил Р' новой грамматики G' и множество нетерминальных символов VN' этой грамматики окончательно построены. Целевым символом новой грамматики является символ S.

Получаем новую грамматику в нормальной форме Хомского, эквивалентную исходной: G'({a,b,c},{A,B,C,S,<aB>,<a'>,<SAa>,<Sb>,<Sc>,<AaC>,<BBa>}, P', S):

Р':

S ® А<аВ> | A<SAa> | <Sb><Sc>

<аВ> ® <а'>В

<а'> ® а

<SAa> ® a

<Sb> ® b

<Sc> ® с

А ® АВ | а | <АаC>C

<АаC> ® а

В ® В<ВВа> | b

<ВВа> ® а

С ® АВ | с

Видно, что при приведении грамматики к нормальной форме Хомского количество правил и нетерминальных символов в грамматике увеличивается. При этом врастет объем грамматики и несколько затрудняется ее восприятие человеком. Од­нако цель преобразования — не упрощение грамматики, а упрощение построе­ния распознавателя языка на ее основе. Именно этой цели и служит нормальная форма Хомского. Далее будут рассмотрены методы построения распознавателей, в основе которых лежит именно эта форма представления грамматики КС-языка.

Левая рекурсия в КС-грамматиках. Алгоритм устранения левой рекурсии из правил грамматики.

Определение. Правило вида A ® a A, где A Î VN, a Î(VT ÈVN) ^*, называется праворекурсивным, а правило вида A ® Aa - леворекурсивным.

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

Способ построения эквивалентной грамматики заключается в следующем. Допустим, что исходная грамматика G содержит правила:

A ® Aa₁ | Aa₂ |... |Aa_m| b₁ | b₂ | … | b_n,

где ни одна цепочка b не начинается с A и a_i, b_i Î (VT ÈVN)^*.

Введем новый нетерминал <A'> и преобразуем правила так:

A ® b₁ | b₂ |...| b_n | b₁<A'> | b₂<A'>|...| b_n<A'>,

<A'> ® a₁ | a₂ |...| a_m| a₁<A'> |a₂<A'>|...|a_m<A'>.

Заменяя все правила с левой рекурсией в G описанным способом, получим грамматику G', причем L(G)=L(G'), поскольку каждая цепочка, выведенная в грамматике G, может быть построена в грамматике G'.

Рассмотрим построение выводов в G и G'.

В грамматике G вывод цепочки имеет вид:

A Þ Aa₁ Þ Aa₁a₁ Þ Aa₁a₁a₁ Þ b₁a₁a₁a₁,

в грамматике G' эта же цепочка выводится так:

A Þ b₁<A'> Þ b₁a₁<A'> Þ b₁a₁a₁<A'> Þ b₁a₁a₁a₁.

Чтобы показать технику преобразования, рассмотрим пример. Требуется преобразовать грамматику G (рассмотренную ранее), с правилами:

P:

E ® E + T | T

T ® T * F | F

F ® (E) | a

Следуя описанному способу, правила E ® E + T | T преобразуем в правила E ® T | TE' и E' ® +T | +TE', а правила T ® T * F | F преобразуем в правила T ® F | FT' и T' ® * F | * FT'.

В результате получаем грамматику G' с правилами:

P':

E ® T

E ® TE'

E' ® + T

E' ® + TE'

T ® F

T ® FT' T' ® * F

T' ® * FT' F ® a

F ® (E)

не содержащую леворекурсивных правил.

Грамматики в нормальной форме Грейбах

На основании грамматики, в которой исключена левая рекурсия, можно построить грамматику в нормальной форме Грейбах.

КС-грамматика G(VT,VN,P,S) называется грамматикой в нормальной форме Грейбах, если она не является леворекурсивной и в ее множестве правил Р присутствуют только правила следующего вида:

1. А ® аa, где aÎ VT и aÎ VN*.

2. S ® l, если lÎL(G), причем S не должно встречаться в правых частях других правил.

Никакие другие формы правил не должны встречаться среди правил грамматики в нормальной форме Грейбах.

Нормальная форма Грейбах является удобной формой представления грамматик для построения нисходящих левосторонних распознавателей (в тех случаях, когда присутствие левой рекурсии в правилах грамматики недопустимо). Подробнее с нею можно познакомиться в [6, т. 1, 26].

Поиск по сайту: