Формальные грамматики и языки. Элементы теории трансляции. - страница №1/5
Московский государственный университет им. М.В.Ломоносова
Факультет вычислительной математики и кибернетики
Волкова И.А., Руденко Т.В.
Формальные грамматики и языки.
Элементы теории трансляции.
(издание второе, переработанное и дополненное)
1999
УДК 519.682.1+681.142.2
Приводятся основные определения, понятия и алгоритмы теории формальных грамматик и языков, некоторые методы трансляции, а также наборы задач по каждой из рассматриваемых тем. Излагаемые методы трансляции проиллюстрированы на примере модельного языка.
Во втором издании исправлены неточности и ошибки первого издания, расширен набор задач: номера первого издания сохранены, но появились дополнительные пункты, отмеченные малыми латинскими буквами. Все новые или измененные задачи отмечены звездочкой.
Для студентов факультета ВМК в поддержку основного лекционного курса “Системное программное обеспечение” и для преподавателей, ведущих практические занятия по этому курсу.
Авторы выражают благодарность Пильщикову В.Н. за предоставленные материалы по курсу “Системное программное обеспечение”, ценные советы и замечания при подготовке пособия, а также благодарят Баландина К.А. за большую помощь в оформлении работы.
Рецензенты:
проф. Жоголев Е.А.
доц. Корухова Л.С.
Волкова И.А., Руденко Т.В. “Формальные грамматики и языки. Элементы теории трансляции. (учебное пособие для студентов II курса)” - издание второе
(переработанное и дополненное)
Издательский отдел факультета ВМиК МГУ
(лицензия ЛР №040777 от 23.07.96), 1998.-62 с.
Печатается по решению Редакционно-издательского Совета факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова
ISBN 5-89407-032-5
-
Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова, 1999
ЭЛЕМЕНТЫ ТЕОРИИ
ФОРМАЛЬНЫХ ЯЗЫКОВ И ГРАММАТИК
Введение.
В этом разделе изложены некоторые аспекты теории формальных языков, существенные с точки зрения трансляции. Здесь введены базовые понятия и даны определения, связанные с одним из основных механизмов определения языков - грамматиками, приведена наиболее распространенная классификация грамматик (по Хомскому). Особое внимание уделяется контекстно-свободным грамматикам и, в частности, их важному подклассу - регулярным грамматикам. Грамматики этих классов широко используются при трансляции языков программирования. Здесь не приводятся доказательства сформулированных фактов, свойств, теорем, доказательства правильности алгоритмов; их можно найти в книгах, указанных в списке литературы.
Основные понятия и определения
Определение: алфавит - это конечное множество символов.
Предполагается, что термин "символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.
Определение: цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита.
Определение: цепочка, которая не содержит ни одного символа, называется
пустой цепочкой. Для ее обозначения будем использовать символ .
Более формально цепочка символов в алфавите V определяется следующим образом:
(1) - цепочка в алфавите V;
(2) если - цепочка в алфавите V и a - символ этого алфавита, то a - цепочка в алфавите V;
(3) - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).
Определение: если и - цепочки, то цепочка называется
конкатенацией (или
сцеплением) цепочек и .
Например, если = ab и = cd, то = abcd.
Для любой цепочки всегда = = .
Определение: обращением (или реверсом) цепочки называется цепочка, символы которой записаны в обратном порядке.
Обращение цепочки будем обозначать R.
Например, если = abcdef, то R = fedcba.
Для пустой цепочки: = R.
Определение: n-ой степенью цепочки (будем обозначать
n) называется конкатенация n цепочек .
0 = ; n = n-1 = n-1.
Определение: длина цепочки - это число составляющих ее символов.
Например, если = abcdefg, то длина равна 7.
Длину цепочки будем обозначать | |. Длина равна 0.
Определение: язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.
Определение: обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку .
Например, если V={0,1}, то V* = {, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}.
Определение: обозначим через V
+ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку .
Следовательно, V* = V+ {}.
Ясно, что каждый язык в алфавите V является подмножеством множества V
*.
Известно несколько различных способов описания языков [3]. Один из них использует порождающие грамматики. Именно этот способ описания языков чаще всего будет использоваться нами в дальнейшем.
Определение: декартовым произведением A B множеств A и B называется множество { (a,b) | a A, b B}.
Определение: порождающая грамматика G - это четверка (VT, VN, P, S), где
VT - алфавит терминальных символов ( терминалов ),
VN - алфавит нетерминальных символов (нетерминалов), не пересекаю-
щийся с VT,
P - конечное подмножество множества (VT VN)+ (VT VN)*; элемент (, ) множества P называется правилом вывода и записывается в виде ,
S - начальный символ (цель) грамматики, S VN.
Для записи правил вывода с одинаковыми левыми частями
1 2 ... n
будем пользоваться сокращенной записью
1 | 2 |...| n.
Каждое i , i = 1, 2, ... ,n , будем называть альтернативой правила вывода из цепочки .
Пример грамматики: G1 = ({0,1}, {A,S}, P, S), где P состоит из правил
S 0A1
0A 00A1
A
Определение: цепочка (VT VN)* непосредственно выводима из цепочки (VT VN)+ в грамматике G = (VT, VN, P, S) (обозначим ), если = 12, = 12, где 1, 2, (VT VN)*, (VT VN)+ и правило вывода
содержится в P.
Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике G1.
Определение: цепочка (VT VN)
* выводима из цепочки
(VT VN)
+ в грамматике G = (VT, VN, P, S) (обозначим ), если существуют цепочки
0,
1, ... ,
n (n>=0), такие, что =
0
1 ...
n= .
Определение: последовательность
0,
1, ... ,
n называется
выводом длины n.
Например, S 000A111 в грамматике G1 (см. пример выше), т.к. существует вывод S 0A1 00A11 000A111. Длина вывода равна 3.
Определение: языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G) = { VT
* | S }.
Другими словами, L(G) - это все цепочки в алфавите VT, которые выводимы из S с помощью P.
Например, L(G1) = {0n1n | n>0}.
Определение: цепочка (VT VN)*, для которой S , называется сентенциальной формой в грамматике G = (VT, VN, P, S).
Таким образом, язык, порождаемый грамматикой, можно определить как множество терминальных сентенциальных форм.
Определение: грамматики 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
эквивалентны, т.к. обе порождают язык L(G1) = L(G2) = {0
n1
n | 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 |
0A 00A1
A
почти эквивалентны, т.к. L(G1)={0n1n | n>0}, а L(G2)={0n1n | n>=0}, т.е. L(G2) состоит из всех цепочек языка L(G1) и пустой цепочки, которая в L(G1) не входит.
Классификация грамматик и языков по Хомскому
(грамматики классифицируются по виду их правил вывода)
ТИП 0:
Грамматика G = (VT, VN, P, S) называется грамматикой типа 0, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики).
ТИП 1:
Грамматика G = (VT, VN, P, S) называется неукорачивающей грамматикой, если каждое правило из P имеет вид , где (VT VN)+, (VT VN)+ и
| | <= | |.
Грамматика G = (VT, VN, P, S) называется
контекстно-зависимой ( КЗ ), если каждое правило из P имеет вид , где =
1A
2; =
1
2; A VN;
(VT VN)
+;
1,
2 (VT VN)
*.
Грамматику типа 1 можно определить как неукорачивающую либо как контекстно-зависимую.
Выбор определения не влияет на множество языков, порождаемых грамматиками этого класса, поскольку доказано, что множество языков, порождаемых неукорачивающими грамматиками, совпадает с множеством языков, порождаемых КЗ-грамматиками.
ТИП 2:
Грамматика G = (VT, VN, P, S) называется контекстно-свободной ( КС ), если каждое правило из Р имеет вид A , где A VN, (VT VN)+.
Грамматика G = (VT, VN, P, S) называется
укорачивающей контекстно-свободной ( УКС ), если каждое правило из Р имеет вид A , где A VN,
(VT VN)
*.
Грамматику типа 2 можно определить как контекстно-свободную либо как укорачивающую контекстно-свободную.
Возможность выбора обусловлена тем, что для каждой УКС-грамматики существует почти эквивалентная КС-грамматика.
ТИП 3:
Грамматика G = (VT, VN, P, S) называется праволинейной, если каждое правило из Р имеет вид A tB либо A t, где A VN, B VN, t VT.
Грамматика G = (VT, VN, P, S) называется
леволинейной, если каждое правило из Р имеет вид A Bt либо A t, где A VN, B VN, t VT.
Грамматику типа 3 (регулярную, Р-грамматику) можно определить как праволинейную либо как леволинейную.
Выбор определения не влияет на множество языков, порождаемых грамматиками этого класса, поскольку доказано, что множество языков, порождаемых праволинейными грамматиками, совпадает с множеством языков, порождаемых леволинейными грамматиками.
Соотношения между типами грамматик:
(1) любая регулярная грамматика является КС-грамматикой;
(2) любая регулярная грамматика является УКС-грамматикой;
(3) любая КС-грамматика является КЗ-грамматикой;
(4) любая КС-грамматика является неукорачивающей грамматикой;
(5) любая КЗ-грамматика является грамматикой типа 0.
-
любая неукорачивающая грамматика является грамматикой типа 0.
Замечание: УКС-грамматика, содержащая правила вида A , не является КЗ-грамматикой и не является неукорачивающей грамматикой.
Определение: язык L(G) является
языком типа k, если его можно описать грамматикой типа k.
Соотношения между типами языков:
(1) каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными ( например, L = {a
nb
n | n>0}).
(2) каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками ( например, L = {anbncn | n>0}).
-
каждый КЗ-язык является языком типа 0.
Замечание: УКС-язык, содержащий пустую цепочку, не является КЗ-языком.
Замечание: следует подчеркнуть, что если язык задан грамматикой типа k, то это не значит, что не существует грамматики типа k’ (k’>k), описывающей тот же язык. Поэтому, когда говорят о языке типа k, обычно имеют в виду максимально возможный номер k.
Например, КЗ-грамматика G1 = ({0,1}, {A,S}, P1, S) и
КС-грамматика G2 = ({0,1}, {S}, P2, S), где
P1: S 0A1 P2: S 0S1 | 01
0A 00A1
A
описывают один и тот же язык L = L(G1) = L(G2) = { 0n1n | n>0}. Язык L называют КС-языком, т.к. существует КС-грамматика, его описывающая. Но он не является регулярным языком, т.к. не существует регулярной грамматики, описывающей этот язык [3].
следующая страница >>