Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Лабы по 2 RKG с нета / ТВПС / Ответы на экзамен (ТВПС).doc
Скачиваний:
8
Добавлен:
13.02.2016
Размер:
912.9 Кб
Скачать

1. Грамматики

Грамматики образуют наиболее важный класс генераторов языка. Грамматика – это математическая система, определяющая вид языка. Одновременно она является устройством, которое придаёт цепочкам (предложениям) языка полезную структуру. Мы будем пользоваться формализмом грамматик Хомского.

В грамматике, определяющей язык L, используются два конечных непересекающихся множества символов – множество нетерминальных символов, которое обычно обозначается буквой , и множество терминальных символов, обозначаемое . Из терминальных символов образуются слова (цепочки) определяемого языка. Нетерминальные символы служат для порождения слов языка L определённым способом.

Сердцевину грамматики составляет конечное множество Р правил образования, которое описывает процесс порождения цепочек языка. Правило это просто пара цепочек или элемент множества, иначе говоря, ()*  ()*  (). Первой компонентой правила является любая цепочка, содержащая хотя бы один нетерминал, а второй компонентой – любая цепочка.

Пример.

Например, правилом может быть пара (AB, CDE). Если уже установлено, что некоторая цепочка порождается грамматикой и содержит AB, т.е. левую часть этого правила, в качестве своей подцепочки, то можно образовать новую цепочку , заменив одно вхождение AB в на CDE.

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

Соглашение. Правило (, ) будем записывать .

Определение.

Грамматикой называется четвёрка G=(N, Σ, P, S),

где

N – конечное множество нетерминальных символов или нетерминалов (иногда называемых вспомогательными символами, синтаксическими переменными или понятиями);

 - непересекающееся с N конечное множество терминальных символов (терминалов);

P – конечное подмножество множества ()*()*() , элемент (, ) множества P называется правилом (или продукцией) и записывается ;

S – выделенный символ из N, называемый начальным (исходным) символом.

Примером грамматики служит четвёрка G1 = ({A, S}, {0, 1}, P, S), где P состоит из правил

S→0A1

0A→00A1

A→C.

Нетерминальными символами являются А и S, а терминальными - 1 и 0.

Грамматика определяет язык рекурсивным образом. Рекурсивность проявляется в задании особого рода цепочек, называемых вводимыми цепочками грамматики G=(N,Σ,P,S), где

  1. S - вводимая цепочка;

  2. если αβγ – выводимая цепочка и β→ содержится в Р, то  – тоже выводимая цепочка.

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

Терминология.

Пусть G=(N, Σ, P, S) – грамматика. Отношение G на множестве ()* (φGΨ означает Ψ, непосредственно выводимая из φ ) и практикуется: если αβγ – цепочка из ()* и βδ – правило из Р, то αβγ G αδγ.

Транзитивное замыкание отношения G обозначим через G+ и трактуется – Ψ, выводимая из φ нетривиальным образом.

Рефлексивное и транзитивное замыкание отношения G (G*) φG* Ψ, Ψ, выводимая из φ.

Далее, если ясно, о какой грамматике идёт речь, то индекс G будет опускаться.

Таким образом, L(G) = {w | w,Sw} через будем обозначатьk-ю степень отношения . Иначе говоря , если существует, состоящая изk+1 цепочек, для которых при 1iк и =. Эта последовательность цепочек называется выводом длиныk цепочки  из цепочки  в грамматике G.

Отметим, что * тогда и только тогда, когда  для некоторогоi≥0, и + тогда и только тогда, когда  для некоторогоi≥1.

Пример.

Рассмотрим грамматику G1 из ранее приведённого примера

S.

На первом шаге S заменяется на А01 в соответствии с правилом S→A01.

На втором шаге 0A заменяется на 00A1.

На третьем шаге A заменяется на e.

Можно сказать, что S3

S+

S*,

и что 0011 принадлежит языку L(G1).

Соглашение: 1

2

…….

n

обозначим 1 2 ….n .

Кроме того, примем ещё следующие соглашения относительно символов и цепочек, связанных с грамматикой:

  1. a, b ,c, d и цифры 0,1,2,..,9 обозначают терминальные символы;

  2. A, B, C, D, S обозначают нетерминалы, S – начальный символ;

  3. U, V,...,Z обозначают либо нетерминалы, либо терминалы;

  4.   обозначают цепочки, которые могут содержать как терминалы, так и нетерминалы;

  5. u, v,...,z обозначают цепочки, состоящие только из терминалов.

Пример.

Пусть G0 = ({E, T, F},{a, +, * (, )}, P, E), где P состоит из правил:

E→E+T | T

T→T*F | F

F→(E) | a.

Пример вывода в этой грамматике:

EE+T

T+T

F+T

a+T

a+T*F

a+F*F

a+a*F

a+a*a,

т.е. язык G0 представляет собой множество арифметических выражений, построенных из символов a, +, *, (и).