Определение языка для записи порождающей модели. Пример задания порождающей модели (порождающая грамматика)

Пример задания порождающей модели (порождающая грамматика)

Определение языка для записи порождающей модели

(Порождающей) грамматикой называется четверка G = (N, å, P, S), где

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

(2) å – терминальный словарь - не пересекающееся с N конечное (не пустое) множество терминальных символов, или терминалов;

(3) P – схема грамматики - конечное подмножество множества ((NÈ å)* N (NÈ å)*´ (NÈ å)* - декартово произведение множеств (NÈ å)* N (NÈ å)* и (NÈ å)*)

Элемент (a, b) множества P называется правилом (или продукцией) и записывается в виде a ® b, a называется левой частью правила, а b - правой частью правила);

Заметим, что левая часть правила – это цепочка, составленная из символов объединенного словаря NÈ å, причем эта цепочка обязательно содержит хотя бы один нетерминальный символ (т.е. не является пустой цепочкой); правая часть правила может быть пустой цепочкой.

Структура состояний порождающего процесса

Цепочки w_i = xⁱ₁xxⁱ₂

Т.е. множество состояний – это множество цепочек, допустимых в объединенном словаре

Структура входной информации

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

Структура выходной информации

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

Входная процедура

Тождественное преобразование - цепочка, состоящая из символа S

Выходная процедура

Тождественное преобразование - на выходе язык

Рецепт (правила интерпретации

Определяем правила вывода новой цепочки из предыдущей (есть в лекциях по теории языка)

Правило остановки

Получены терминальные цепочки

Пример задания порождающей модели для языка, основанного на правилах (РЕЛЯП)

Определение языка для записи порождающей модели

.ВСЕ < список переменных> < условие> à

[.ЕСТЬ < список переменных> ] < следствие>

В условие входят - È, &, Ø, (,), арифметические операции, знаки отношения.

В следствии могли использоваться только & и арифметические операции.

P₁(t₁) & P₂(t₂) &... & P_n(t_n) & Ø P¢ ₁(t¢ ₁) & Ø P¢ ₂(t¢ ₂) &... & Ø P¢ _k(t¢ _k) & R, где R – соотношение над переменными, все переменные которые находятся в отрицательных атомарных формулах и все соотношения из R, должны находиться в положительных атомарных формулах.

Исходное правило которое содержит дизъюнкцию или скобки преобразовывается по правилам Де Моргана и по правилам раскрытия скобок.

D₁È D₂È...È D_mà Q

D₁à Q

D₂à Q

...

D_mà Q

D_i: S1& S₂&...& S_mà Q

S₁& S₂à q₁

q₁& S₃à q₂

q_r-1& S_rà Q

Вид результирующего правила:

p₁(v₁) & p₂(v₂) & R(v₁, v₂) à Q(v₁, v₂),

либо

p₁(v₁) & p₂(v₂) & R(v₁, v₂) à ЕСТЬ v₃ Q(v₁, v₂, v₃),

где v₁, v₂, v₃ – вектора переменных, p₁, p₂ – имена отношений, которые определяет пользователь, R – конъюнкция содержащая отрицательные переменные и соотношения над v₁ и v₂, Q – конъюнкция содержащая положительные атомарные формулы.