Информатика и выч. техника \ Теория языков программирования и методы трансляции

Контекстно-свободные языки. Свойства и распознаватели КС-языков. Преобразование КС-грамматик. КС-грамматики в нормальной форме, страница 5

10.  Какое множество строится при удалении бесплодных символов?

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

3.3.1  Нормальная форма Хомского

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

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

1.  A®BC, где A, B, CÎVN.

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

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

Никакие другие правила не могут встречаться среди правил грамматики в нормальной форме Хомского.

Грамматика в нормальной форме Хомского называется также грамматикой в бинарной нормальной форме (БНФ), т.к. на каждом шаге нетерминальный символ может быть заменен только на два других нетерминальных символа.

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

Рассмотрим алгоритм преобразования грамматики к БНФ.

Сначала множество нетерминальных символов новой грамматики строится на основе множества нетерминальных символов исходной грамматики: VN¢=VN.

Затем алгоритм работает с правилами P исходной грамматики и в зависимости от их вида строит множество правил P¢ и пополняет множество нетерминальных символов VN¢.

1.  Правила вида A®a, A®BC, S®l, где A, B, CÎVN, aÎVT, переносятся во множество P¢ без изменений.

2.  Если встречается правило вида (A®aB)ÎP, где A, BÎVN, aÎVT, то во множество правил P¢ добавляются правила A®<AaB>B и <AaB>®a, а новый символ <AaB> добавляется во множество нетерминальных символов VN¢.

3.  Если встречается правило вида (A®Ba)ÎP, выполняется аналогичное действие: во множество правил P¢ добавляются правила A®B<ABa> и <ABa>®a, а новый символ <ABa> добавляется во множество нетерминальных символов VN¢.

4.  Если встречается правило вида (A®ab)ÎP, где AÎVN, a, bÎVT, то во множество правил P¢ добавляются правила A®<Aa><Ab> и <Aa>®a, <Ab>®b, а новые символы <Aa>, <Ab> добавляются во множество нетерминальных символов VN¢.

5.  Если встречается правило вида (A®X1X2…Xk)ÎP, где k>2, AÎVN, "i XiÎVTÈVN, то во множество правил P¢ добавляются правила A®X1¢<X2¢…Xk¢>,
<X2¢…Xk¢>®X2¢<X3¢…Xk¢>,
…
<Xk–1¢Xk¢>®Xk–1¢Xk¢,
где все новые нетерминальные символы <…> добавляются во множество нетерминальных символов VN¢. Что касается символов Xi¢, то их вид зависит от того, чем являлся исходный символ Xi. Если для некоторого i XiÎVN, то Xi¢ºXiÎVN¢; если XiÎVT, то Xi¢ – новый нетерминальный символ, т.е. Xi¢ÎVN¢ и в P¢ нужно добавить правило Xi¢®Xi.

Проиллюстрируем данный алгоритм на примере.

Пример: Преобразование КС-грамматики к БНФ.

Дана грамматика G({a,b,c},{A,B,C,S},P,S) в каноническом виде, где P:

S®AaB½Aa½bc

A®AB½a½aC

B®Ba½b

C®AB½c

Первоначально множество нетерминальных символов VN¢={A,B,C,S}, затем оно может пополняться. Последовательно рассматриваем правила P и анализируем каждое из них.

1)  S®AaB – относится к пункту 5 алгоритма. Следовательно, в P¢ включаем S®A<aB>, <aB>®<a>B, <a>®a, а в множество VN¢ добавляем <aB>,<a>.

2)  S®Aa – относится к 3 пункту алгоритма. Следовательно, в P¢ нужно включить S®A<a¢>, <a¢>®a, а в множество VN¢ добавить <a¢>. Но ранее уже появился нетерминал <a>, из которого выводился символ a, поэтому можно использовать его, тогда можно ограничиться правилом S®A<a>.

3)  S®bc – относится к 4 пункту. Следовательно, в P¢ нужно включить S®<b><c>, <b>®b, <c>®c, а в множество VN¢ добавить <b>, <c>.

4)  A®AB  и  A®a – в соответствии с первым пунктом алгоритма включается в P¢ без изменений.

5)  A®aC – относится ко 2 пункту. Следовательно, в P¢ нужно включить A®<a>C, причем замечание из (2) справедливо и в данном случае.

6)  B®Ba – аналогично (2), добавляется правило B®B<a>.

7)  B®b, а также C®AB, C®c соответствуют требуемому виду правил и переносятся в грамматику без изменений.

Таким образом, получаем грамматику G¢({a,b,c},{A,B,C,<aB>,<a>, <b>,<c>,S},P¢,S) в нормальной форме Хомского, где P¢:

S®A<aB>½A<a>½<b><c>

A®AB½a½<a>C

B®B<a>½b

C®AB½c

<aB>®<a>B

<a>®a

<b>®b

<c>®c

Хотя эта грамматика содержит большее количество правил, чем исходная, но построение распознавателя для неё значительно упрощается.

3.3.2  Левая рекурсия. Нормальная форма Грейбах

Символ AÎVN в КС-грамматике G(VT,VN,P,S) называется рекурсивным, если для него существует цепочка вывода вида AÞ+aAb, где a, bÎ(VNÈVT)*.

Виды рекурсии различают в зависимости от цепочек a и b. Если a=l, а b¹l, то рекурсия называется левой, а грамматика – леворекурсивной. Если наоборот: a¹l, а b=l, то рекурсия называется правой, а грамматика – праворекурсивной. Если обе цепочки a=b=l, то рекурсия представляет собой цикл. В дальнейшем будем рассматривать только приведённые грамматики, в которых нет цепных правил и, соответственно, циклов.

Замечание.

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

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

Скачать файл