Бильгаева Н.Ц. - Теория алгоритмов, формальных языков, грамматик и автоматов, страница 8

Так, правила вывода изприведенного примера можно записать следующим образом: S → aSb | ab.4.3. Классификация грамматикПравила порождающих грамматик позволяют осуществлять преобразования строк.Ограничения же на виды правил позволяют выделить классы грамматик. Рассмотримклассификацию, которую предложил Н. Хомский.Грамматики типа 0 - это грамматики, на правила вывода которых нет ограничений.Грамматики типа 1, или контекcтные грамматики -это грамматики, все правила которыхимеют следующий вид: хАу → хϕу, где A ∈ VN, x, y, ϕ ∈ (VN ∪ VT)+.Грамматики типа 2 - это бесконтекстные, или контекстно-свободные грамматики (КСграмматики).

Правила вывода для этих грамматик имеют следующий вид: А → ϕ, где А ∈VN, ϕ ∈ (VN ∪ VT)*.Грамматики типа 3 - это автоматные грамматики, которые делятся на два типа:а) леволинейные (леворекурсивные), правила вывода для которых имеют следующийвид: А → Аа | a, где А ∈ VN;б) праволинейные (праворекурсивные), правила вывода для которых имеют следующийвид: А → Aа | a.Язык L называется языком типа i, если существует грамматика типа i, порождающаяязык L.4.3.1. Методика решения задачПример 1. Дана порождающая грамматика G = (VT, VN, Р, S), в которой VT = {a, d, е}, VN= {В, С, S}, Р = {S → аВ, В → Cd | dC, С → е}. Выписать терминальные цепочки,порожденные данной грамматикой, и определить длину их вывода.Решение.

Получим следующие терминальные цепочки:S → аВ → aCd → aed,S → аВ → adC → ade,длина вывода которых равна 3.Пример 2. Дана грамматика G = (VT, VN, Р, C), в которой VT = {a, b, c, d, е}, VN = {A, В,С, D, E}, Р = {A → ed, В → Ab, С → Bc, С → dD, D → Ae, E → bc}. Определить,принадлежит ли языку L(G) цепочка eadabcb.Решение. Выведем возможные терминальные цепочки из аксиомы с помощью заданныхправил вывода:С → Bc → Abc → edbc,С → dD → dAe → dede.Так как первые же терминальные символы полученных цепочек не совпадают сзаданной, можно сделать вывод о том, что цепочка eadabcb не принадлежит языку L(G).Пример 3. Построить КС-грамматику (грамматику типа 2), порождающую цепочки из 0и 1 с одинаковым числом тех и других символов.Решение.

Определим множества, задающие грамматику: VT = {0, 1}; VN = {S}; Р ={S → 0S1, S → 1S0, S → ε, S → S01, S → S10}.Пример 4. Описать язык, порождаемый следующими правилами: S → bSS | а.Решение. Построим несколько терминальных цепочек, применяя заданные правилавывода:S → a;S → bSS → baa;S → bSS → bbSSS → bbaaa;S → bSS → bbSSbSS → bbaabaa;S → bSS → bbSSbSS → bbbSSbSSbbSSbSS → ...Из полученных цепочек видно, что:а) цепочки всегда начинаются с терминала b, кроме аксиомы, и заканчиваютсятерминалом а;б) количество терминалов а в любой цепочке всегда на 1 больше, чем b.Исходя из этих выводов, определим язык, порождаемый заданными правилами,следующим образом:L(G) = {α | α ∈ {a, b}*}, |a| = |b| + 1, причем цепочки начинаются с терминала b изаканчиваются терминалом а.4.4.

Грамматический разборВ КС-грамматике может быть несколько выводов, эквивалентных в том смысле, что вних применяются одни и те же правила к одинаковым в промежуточном выводе цепочкам,но в различном порядке. Например, для грамматики G с правилами вывода S → ScS|b|aвозможны следующие эквивалентные выводы терминальной цепочки acb: S → ScS →Scb → acb и S → ScS → acS → acb.Деревом вывода цепочки х в КС-грамматике G = (VT, VN, Р, S) называетсяупорядоченное дерево, каждая вершина которого помечена символом из множества V ∪ VN∪ {ε} так, что каждому правилу А → b1b2b3 ... bk, использующемуся при выводе цепочки х, вдереве вывода соответствует поддерево с корнем А и прямыми потомками b1, b2, b3, ..., bk,которое приведено на рисунке:Ab1 b2…bkВ силу того, что цепочка х ∈ L(G) выводится из аксиомы S, корнем вывода всегдаявляется аксиома.

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

Одной цепочке языка может соответствовать больше одногодерева, так как эта цепочка может иметь разные выводы, порождающие разные деревья.КС-грамматика G == (VT, VN, Р, S) называется неоднозначной (неопределенной), еслисуществует цепочка х ∈ L(G), имеющая два или более дерева вывода.Рассмотрим пример.Пусть даны две КС-грамматики:G1 = (VT, VN, Р1, S), VN = {S},P1={S → S+S | S | S⋅S | (S) | a};G2= (VT, VN, Р2, S), VN = {S, A, B},P2 = {S → S + A | A | A, A → A⋅B | A / B | B, B → a| (S)}, содержащие в множестветерминальных символов знаки операций, круглые скобки и символ а.

Определить, являютсяли грамматики однозначными. Если какая-либо из них неоднозначна, привести примерцепочки, для которой существует два различных дерева вывода.Решение: Грамматика G1 является неоднозначной, так как она имеет правила с правойчастью, содержащей два вхождения нетерминала S и знак арифметической операции.Построим два дерева вывода для простейшей цепочки а + а + а:Грамматика G2 является однозначной, так как не содержит правил с двойнымвхождением нетерминального символа. Так, для цепочки а + а + а она имеет только однодерево вывода.В некоторых случаях неоднозначность в грамматиках может устраняться путемэквивалентных преобразований. Однако в общем случае проблема устранениянеоднозначности неразрешима.

На практике от неоднозначности избавляются путемзадания словесных ограничений, называемых контекстными условиями языка, которыевключаются в его семантику.Различают две стратегии грамматического разбора: восходящую и нисходящую, которыесоответствуют способу построения синтаксических деревьев. При нисходящей стратегииразбора дерево строится от корня аксиомы вниз, к терминальным вершинам. Главнойзадачей при нисходящем разборе является выбор того правила, которое следует применитьна рассматриваемом шаге. При восходящем разборе дерево строится от терминальныхвершин к корню дерева (аксиоме).Преобразование цепочки, обратное порождению, называется редукцией.4.4.1. Представление грамматики в виде графаДерево грамматического разбора не следует путать с представлением грамматики в видеграфа.

Граф грамматики в качестве вершин содержит сентенциальные формы (любыецепочки, выводимые из аксиомы).Рассмотрим представление грамматики G в виде графа: G = (VT, VN, Р, S), в которой VT ={a, b, с}, VN = {S}, P={S → aSa | bSb | c}.4.5. Преобразования КС-грамматикЧасто требуется изменить грамматику таким образом, чтобы она удовлетворялаопределенным требованиям, не изменяя при этом порождаемый грамматикой язык. Дляэтого используются эквивалентные преобразования КС-грамматик, некоторые из которыхрассмотрены ниже.4.5.1.

Удаление правил вида А → ВПреобразование первого типа состоит в удалении правил А → В, или <нетерминал> →<нетерминал>.Покажем, что для любой КС-грамматики можно построить эквивалентную грамматику,не содержащую правил вида: А → В, где А и В - нетерминальные символы.Пусть имеется КС-грамматика G=(VT, VN, P, S), где множество нетерминалов VN={A1,A2, . . .

, An}. Разобьем Р на два непересекающихся множества: P = P1 ∪ P2. В P1 включенывсе правила вида Аi → Ak, в P2 включены все остальные правила, т.е. P2 = P \ P1. Затем длякаждого Аi определим множество правил P(Аi), включив в него все такие правила Аi→ϕ, чтоАi →* Aj и Аj → ϕ, где Аj → ϕ ∈ P2.

Построим эквивалентную КС-грамматику Gэ = (VT, VN,Pэ, S), в которой множества терминальных и нетерминальных символов, а также аксиомасовпадают с теми же объектами исходной грамматики G, а множество правил Pэ полученообъединением правил множества P2 и правил P(Аi) для всех 1≤ i ≤n:Pэ =nUi=1P ( A i ) ∪ P2 .Пример.

Пусть задана грамматика G со следующими правилами вывода S → aFb | А; А→ аА | В; В → aSb | S; F → bc | bFc.Построим множества правил Р2, P(S), P(A), P(B), P(F).Определим правила для Р2: Р2 = {S → aFb; А → аА; В → aSb; F → bc | bFc}.Определим правила для P(S): S => A => B или S =>*А; S=>В, где =>* обозначаетнепосредственную выводимость. P(S) = {S → аА; S → aSb).Определим правила для Р(А): А => В => S или А =>* В; А => S.

Р(А) = {А → aSb; А →aFb}.Определим правила для Р(В): В => S => А или В =>* S; В =>*А. Р(В) = {В → aFb; В →аА}.Определим правила для P(F): так как непосредственно выводимых нетерминалов несуществует, то P(F) = 0.Объединив полученные правила, можно записать грамматику Gэ, эквивалентнуюисходной:S → aFb | aSb | аА;А → аА | aSb | aFb;В → аА | aSb | aFb;F → bc | bFc.Графическая модификация методаАналитическое преобразование по рассмотренному алгоритму оказывается довольносложным.