Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Порождающие грамматики
|
|
Классическая теория формальных языков изучает синтаксис (словосочетания) языка.
Вводится математическая модель синтаксиса, которая описывает механизмы порождения и распознавания «правильно построенных» слов языка.
Задача: описать процедуру, позволяющую породить произвольную цепочку слов языка, согласно конечному множеству правил.
Классическим способом определения языков является определение их с помощью порождающих грамматик (грамматик Холмского).
Порождающая грамматика позволяет порождать цепочки языка из некоторой начальной цепочки с помощью определенных правил замены.
Порождение есть пошаговый процесс, в котором на каждом шаге из цепочки, уже полученной на предыдущем шаге, путем применения правил замены получаем новую цепочку.
Пример. Выполняя дифференцирование сложной функции, переходим от одной формулы к другой с помощью таблицы производных.
Терминал (терминальный символ) — объект, непосредственно присутствующий в словах языка, и имеющий конкретное, неизменяемое значение (обобщение понятия «буквы»).
В формальных языках, используемых на компьютере, в качестве терминалов обычно берут все или часть стандартных символов ASCII — латинские буквы, цифры и спец. символы.
Нетерминал (нетерминальный символ) — объект, обозначающий какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющий конкретного символьного значения.
Словами языка, заданного грамматикой, являются все последовательности терминалов, выводимые (порождаемые) из начального нетерминала по правилам вывода.
Чтобы задать грамматику, требуется:
¾ задать алфавиты терминалов и нетерминалов,
¾ набор правил вывода,
¾ выделить в множестве нетерминалов начальный.
Порождающая грамматика задается упорядоченным набором из четырех компонент:
G =(T, N, P, S,), где
· T — алфавит, содержащий множество терминалов;
· N — алфавит, содержащий множество нетерминалов, причем N ∩ T =Æ;
· S — стартовый (начальный) символ из набора нетерминалов S Î N. Он называется аксиомой.
· P — конечное множество правил выводаили продукций. Каждое правило вывода имеет вид:
«левая часть» ®«правая часть»,
«Левая часть» 
продукции — это непустая последовательность терминальных инетерминальных символов, содержащая хотя бы один нетерминал.
«Правая часть» 
— это любая (в том числе и пустая) последовательность терминальных и нетерминальных символов.
Для записи правил вывода с одинаковыми левыми частями
a ® b 1 a ® b 2... a ® b n
будем пользоваться сокращенной записью
a ® b 1| b 2|...| b n.
Каждое b i, i = 1, 2,..., n, будем называть альтернативой правила вывода из цепочки a.
Алфавит 
называется объединенным алфавитом грамматики.
P ⊂ (Т∪ N)+ × (Т∪ N) ∗
Будем обозначать:
элементы множества T строчными буквами из начала латинского алфавита,
элементы множества N — заглавными латинскими буквами.
Пример. Пусть даны множества
T = {a, b, c}, N = {S},
P = {S → acSbcS, cS → ε }.
Тогда ( T, N, P, S) является порождающей грамматикой.
Пример. Пусть даны множества
T = {0, 1 }, N = {А, S},
P = {S → 0А1, 0А → 00А1, А → ε }.
Тогда G1 = ( T, N, Р, S) является порождающей грамматикой., а слово (цепочка) 
непосредственно выводимо из 
в грамматике G1, так как существует соответствующее правило в Р.
Цепочка b Î (TÈ N)* выводима из цепочки a Î (TÈ N)+в грамматике G = ( T, N, Р, S), если существуют цепочки g0, g1,..., gn (n> =0), такие, что
a = g0® g1®... ® g n = b.
Обозначаем:
Последовательность g0, g1,..., gn называется выводом длины n.
В последнем примере
т.к. существует вывод
S ® 0A1 ® 00A11 ® 000A111.
(S → 0А1, 0А → 00А1)
Длина вывода равна 3.
Пример. Пусть
G = ({a, b, c}, {S}, {S → acSbcS, cS → ε }, S).
Тогда 
.
Языком, порождаемым грамматикой G = ( T, N, Р, S)
называется множество L (G) = { a Î T * | 
}.
Другими словами, L (G) - это все цепочки в алфавите T, которые выводимы из S с помощью P.
Например, L(G1) = {0n1n | n> 0}.
Пример. Пусть G = á { a, b }, { S }, { S a bb, S a aSa }, S ñ. Последовательно применяем правила вывода и находим слова языка в терминальном алфавите:
S a bb,
S a aSa a abba,
S a aSa a aaSaa a aabbaa,
S a aSa a aaSaa ….a anbban
Язык, порождаемый этой грамматикой, имеет вид
L (G)={ anbban | n ³ 0}.
Грамматики G1 и G2 называются эквивалентными, если L (G1) = L (G2).
Пример.
G1 = ({0, 1}, {A, S}, P1, S) и G2 = ({0, 1}, {S}, P2, S)
P1: S ® 0A1 P2: S ® 0S1 | 01
0A ® 00A1
A ®e
эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = {0n1n | n> 0}.
Грамматики G1 и G2 почти эквивалентны, если
L (G1) È {e} = L (G2) È {e}.
Другими словами, грамматики почти эквивалентны, если языки, ими порождаемые, отличаются не более, чем на e.
Пример.
G1 = ({0, 1}, {A, S}, P1, S) и G2 = ({0, 1}, {S}, P2, S)
P1: S ® 0A1 P2: S ® 0S1 | e
0A ®00A1
A ®e
почти эквивалентны, т.к.
L(G1)={0n1n | n> 0}, а L(G2)={0n1n | n> =0},
т.е. L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.
Наиболее распространенным способом задания (и распознавания) языка является использование автоматов.
|
|