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

Формальная грамматика – это математическая система, определяющая язык посредством порождающих правил.

Определение Формальной грамматикой называется четверка вида:

где V_N - конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);

V_T - множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.), V_T Ç V_N =Æ ;

Р – множество правил вывода грамматики, являющееся конечным подмножеством множества (V_TÈ V_N)⁺´ (V_TÈ V_N)^*; элемент (a, b) множества Р называется правилом вывода и записывается в виде a®b (читается: «из цепочки a выводится цепочка b»);

S - начальный символ грамматики, S Î V_N.

Для записи правил вывода с одинаковыми левыми частями вида используется сокращенная форма записи .

Пример Грамматика G₁=({0, 1}, {A, S}, P₁, S), где множество Р состоит из правил вида: 1) S® 0A1; 2)0A® 00A1; 3) A®e.

Определение Цепочка b Î (V_TÈ V_N)^* непосредственно выводима из цепочки в грамматике (обозначается: aÞ b), если и , где , и правило вывода содержится во множестве Р.

Определение Цепочка b Î (V_TÈ V_N)^* выводима из цепочки в грамматике (обозначается aÞ *b), если существует последовательность цепочек (n³ 0) такая, что .

Пример В грамматике G₁ SÞ *000111, т.к. существует вывод .

Определение Языком, порожденным грамматикой , называется множество всех цепочек в алфавите V_T, которые выводимы из начального символа грамматики S c помощью правил множества Р, т.е. множество .

Пример Для грамматики G₁ язык L(G₁)={0ⁿ1ⁿ | n³ 0}.

Определение Цепочка , для которой существует вывод SÞ *a, называется сентенциальной формой или сентенцией в грамматике .

Определение Языком, порожденным грамматикой G называется множество терминальных сентенциальных форм грамматики.

Классификация языков и грамматик по Хомскому

Классификация грамматик по Хомскому осуществляется по структуре их правил вывода. Выделяется четыре типа грамматик.

Тип 0. Грамматика называется грамматикой типа 0, если на ее правила вывода не наложено никаких ограничений, кроме тех, которые указаны в определении грамматики.

Тип 1. Грамматика называется контекстно-зависимой грамматикой (КЗ-грамматикой), если каждое правило вывода из множества Р имеет вид a®b, где a Î (V_TÈ V_N)⁺, b Î (V_TÈ V_N)^* и |a| £ |b|.

Тип 2. Грамматика называется контекстно-свободной грамматикой (КС-грамматикой), если ее правила вывода имеют вид: , где и

Соотношение типов грамматик и языков представлено на рисунке 1.1.

Р – регулярная грамматика;

КС – контекстно-свободная грамматика;

КЗ – контекстно-зависимая грамматика;

Тип 0 – грамматика типа 0.

Рисунок 1.1 – Соотношение типов формальных языков и грамматик

Тип 3. Грамматика называется регулярной грамматикой (Р-грамматикой) выровненной вправо, если ее правила вывода имеют вид , где .

Грамматика называется регулярной грамматикой (Р-грамматикой) выровненной влево, если ее правила вывода имеют вид , где .

Определение Язык L(G) называется языком типа k, если его можно описать грамматикой типа k, где k – максимально возможный номер типа грамматики.

Пример Примеры различных типов формальных языков и грамматик по классификации Хомского. Терминалы будем обозначать строчными символами, нетерминалы – прописными буквами, начальный символ грамматики – S.

а) Язык типа 0 L(G)= определяется грамматикой с правилами вывода:

1) S ® aaCFD; 2) AD ® D;

3) F ® AFB | AB; 4) Cb ® bC;

5) AB ® bBA; 6) CB ® C;

7) Ab ® bA; 8) bCD ® e.

б) Контекстно-зависимый язык L(G)={aⁿbⁿcⁿ | n³ 1} определяется грамматикой с правилами вывода:

1) S ® aSBC | abc ; 2) bC ® bc;

3) CB ® BC; 4) cC ® cc;

5) BB ® bb.

в) Контекстно-свободный язык L(G)={(ab)ⁿ(cb)ⁿ | n> 0 } определяется грамматикой с правилами вывода:

1) S ® aQb | accb;

2) Q ® cSc.

г) Регулярный язык L(G)={w^ | wÎ {a, b}⁺, где нет двух рядом стоящих а} определяется грамматикой с правилами вывода:

1) S ® A^ | B^;

2) A ® a | Ba;

3) B ® b | Bb | Ab.

Эквивалентность грамматик

Определение Грамматики G₁ и G₂ называются эквивалентными, если они определяют один и тот же язык, т.е. .

Определение Грамматики G₁ и G₂ называются почти эквивалентными, если заданные ими языки различаются не более чем на пустую цепочку символов т.е. .

Пример Для грамматики G₁ эквивалентной будет грамматика G₂ = ({0, 1}, {S}, P₂, S), где множество правил вывода P₂ содержит правила вида S ® 0S1| e.

Почти эквивалентной для грамматики G₁будет грамматика G₃= ({0, 1}, {S}, P₃, S), где множество правил вывода P₃ содержит правила вида S ® 0S1|01.

Формы Бэкуса - Наура

Цепочки языка могут содержать метасимволы, имеющие особое назначение. Метаязык, предложенный Бэкусом и Науром (БНФ) использует следующие обозначения:

- символ «:: =» отделяет левую часть правила от правой (читается: «определяется как»);

- нетерминалы обозначаются произвольной символьной строкой, заключенной в угловые скобки «< » и «> »;

- терминалы - это символы, используемые в описываемом языке;

- правило может определять порождение нескольких альтернативных цепочек, отделяемых друг от друга символом вертикальной черты «|» (читается: «или».

Для повышения удобства и компактности описаний, в расширенных БНФ вводятся следующие дополнительные конструкции (метасимволы):

- квадратные скобки «[» и «]» означают, что заключенная в них синтаксическая конструкция может отсутствовать;

- фигурные скобки «{» и «}» означают повторение заключенной в них синтаксической конструкции ноль или более раз;

- сочетание фигурных скобок и косой черты «{/» и «/}» используется для обозначения повторения один и более раз;

- круглые скобки «(» и «)» используются для ограничения альтернативных конструкций;

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

Пример Правила, определяющие понятие «идентификатор» некоторого языка программирования, будут выглядеть следующим образом:

< буква> :: = a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w |

x | y | z

< цифра> :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

< идентификатор> :: = < буква> { (< буква> | < цифра> ) }

Диаграммы Вирта

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

При построении диаграмм учитывают следующие правила:

- каждый графический элемент, соответствующий терминалу или нетерминалу, имеет по одному входу и выходу, которые обычно изображаются на противоположных сторонах;

- каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг;

- альтернативы в правилах задаются ветвлением дуг, а итерации - их слиянием;

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

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

Пример 1.4.1. Правила, определяющие понятие «идентификатор» некоторого языка программирования, показаны на рисунке 1.3.

Цифра

Буква

Идентификатор

Рисунок 1.3 – Диаграмма Вирта понятия «идентификатор»

⇐ Предыдущая 123 4 5 6 7 8 9 10 Следующая ⇒