Классификация грамматик и языков по Хомскому
Московский государственный университет им. М.В.Ломоносова
Факультет вычислительной математики и кибернетики
Волкова И.А., Руденко Т.В.
Формальные грамматики и языки.
Элементы теории трансляции.
(издание второе, переработанное и дополненное)
1999
УДК 519.682.1+681.142.2
Приводятся основные определения, понятия и алгоритмы теории формальных грамматик и языков, некоторые методы трансляции, а также наборы задач по каждой из рассматриваемых тем. Излагаемые методы трансляции проиллюстрированы на примере модельного языка.
Во втором издании исправлены неточности и ошибки первого издания, расширен набор задач: номера первого издания сохранены, но появились дополнительные пункты, отмеченные малыми латинскими буквами. Все новые или измененные задачи отмечены звездочкой.
Для студентов факультета ВМК в поддержку основного лекционного курса “Системное программное обеспечение” и для преподавателей, ведущих практические занятия по этому курсу.
Авторы выражают благодарность Пильщикову В.Н. за предоставленные материалы по курсу “Системное программное обеспечение”, ценные советы и замечания при подготовке пособия, а также благодарят Баландина К.А. за большую помощь в оформлении работы.
Рецензенты:
проф. Жоголев Е.А.
доц. Корухова Л.С.
Волкова И.А., Руденко Т.В. “Формальные грамматики и языки. Элементы теории трансляции. (учебное пособие для студентов II курса)” - издание второе
(переработанное и дополненное)
|
|
Издательский отдел факультета ВМиК МГУ
(лицензия ЛР №040777 от 23.07.96), 1998.-62 с.
Печатается по решению Редакционно-издательского Совета факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова
ISBN 5-89407-032-5
Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова, 1999
ЭЛЕМЕНТЫ ТЕОРИИ
ФОРМАЛЬНЫХ ЯЗЫКОВ И ГРАММАТИК
Введение.
В этом разделе изложены некоторые аспекты теории формальных языков, существенные с точки зрения трансляции. Здесь введены базовые понятия и даны определения, связанные с одним из основных механизмов определения языков - грамматиками, приведена наиболее распространенная классификация грамматик (по Хомскому). Особое внимание уделяется контекстно-свободным грамматикам и, в частности, их важному подклассу - регулярным грамматикам. Грамматики этих классов широко используются при трансляции языков программирования. Здесь не приводятся доказательства сформулированных фактов, свойств, теорем, доказательства правильности алгоритмов; их можно найти в книгах, указанных в списке литературы.
|
|
Основные понятия и определения
Определение: алфавит - это конечное множество символов.
Предполагается, что термин "символ" имеет достаточно ясный интуитивный смысл и не нуждается в дальнейшем уточнении.
Определение: цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита.
Определение: цепочка, которая не содержит ни одного символа, называется пустой цепочкой. Для ее обозначения будем использовать символ e.
Более формально цепочка символов в алфавите V определяется следующим образом:
(1) e - цепочка в алфавите V;
(2) если a - цепочка в алфавите V и a - символ этого алфавита, то aa - цепочка в алфавите V;
(3) b - цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).
Определение: если a и b - цепочки, то цепочка ab называется конкатенацией (или сцеплением) цепочек a и b.
Например, если a = ab и b = cd, то ab = abcd.
Для любой цепочки a всегда ae = ea = a.
Определение: обращением (или реверсом) цепочки a называется цепочка, символы которой записаны в обратном порядке.
Обращение цепочки a будем обозначать aR.
Например, если a = abcdef, то aR = fedcba.
|
|
Для пустой цепочки: e = eR.
Определение: n-ой степенью цепочки a (будем обозначать an) называется конкатенация n цепочек a.
a0 = e; an = aan-1 = an-1a.
Определение: длина цепочки - это число составляющих ее символов.
Например, если a = abcdefg, то длина a равна 7.
Длину цепочки a будем обозначать | a |. Длина e равна 0.
Определение: язык в алфавите V - это подмножество цепочек конечной длины в этом алфавите.
Определение: обозначим через V* множество, содержащее все цепочки в алфавите V, включая пустую цепочку e.
Например, если V={0,1}, то V* = {e, 0, 1, 00, 11, 01, 10, 000, 001, 011, ...}.
Определение: обозначим через V+ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку e.
Следовательно, V* = V+ È {e}.
Ясно, что каждый язык в алфавите 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)*; элемент (a, b) множества P называется правилом вывода и записывается в виде a ® b,
S - начальный символ (цель) грамматики, S Î VN.
Для записи правил вывода с одинаковыми левыми частями
a ® b1 a ® b2 ... a ® bn
будем пользоваться сокращенной записью
a ® b1 | b2 |...| bn.
Каждое bi , i = 1, 2, ... ,n , будем называть альтернативой правила вывода из цепочки a.
Пример грамматики: G1 = ({0,1}, {A,S}, P, S), где P состоит из правил
S ® 0A1
0A ® 00A1
A ® e
Определение: цепочка b Î (VT È VN)* непосредственно выводима из цепочки a Î (VT È VN)+ в грамматике G = (VT, VN, P, S) (обозначим a ® b), если a = x1gx2, b = x1dx2, где x1, x2, d Î (VT È VN)*, g Î (VT È VN)+ и правило вывода
g ® d содержится в P.
Например, цепочка 00A11 непосредственно выводима из 0A1 в грамматике G1.
Определение: цепочка b Î (VT È VN)* выводима из цепочки
a Î (VT È VN)+ в грамматике G = (VT, VN, P, S) (обозначим a Þ b), если существуют цепочки g0, g1, ... , gn (n>=0), такие, что a = g0 ® g1 ® ... ® gn= b.
Определение: последовательность g0, g1, ... , gn называется выводом длины n.
Например, S Þ 000A111 в грамматике G1 (см. пример выше), т.к. существует вывод S ® 0A1 ® 00A11 ® 000A111. Длина вывода равна 3.
Определение: языком, порождаемым грамматикой G = (VT, VN, P, S), называется множество L(G) = {a Î VT* | S Þ a}.
Другими словами, L(G) - это все цепочки в алфавите VT, которые выводимы из S с помощью P.
Например, L(G1) = {0n1n | n>0}.
Определение: цепочка a Î (VT È VN)*, для которой S Þ a, называется сентенциальной формой в грамматике 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 ® 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) не входит.
Классификация грамматик и языков по Хомскому
(грамматики классифицируются по виду их правил вывода)
ТИП 0:
Грамматика G = (VT, VN, P, S) называется грамматикой типа 0, если на правила вывода не накладывается никаких ограничений (кроме тех, которые указаны в определении грамматики).
ТИП 1:
Грамматика G = (VT, VN, P, S) называется неукорачивающей грамматикой, если каждое правило из P имеет вид a ® b, где a Î (VT È VN)+, b Î (VT È VN)+ и
| a | <= | b |.
Грамматика G = (VT, VN, P, S) называется контекстно-зависимой ( КЗ ), если каждое правило из P имеет вид a ® b, где a = x1Ax2; b = x1gx2; A Î VN;
g Î (VT È VN)+; x1,x2 Î (VT È VN)*.
Грамматику типа 1 можно определить как неукорачивающую либо как контекстно-зависимую.
Выбор определения не влияет на множество языков, порождаемых грамматиками этого класса, поскольку доказано, что множество языков, порождаемых неукорачивающими грамматиками, совпадает с множеством языков, порождаемых КЗ-грамматиками.
ТИП 2:
Грамматика G = (VT, VN, P, S) называется контекстно-свободной ( КС ), если каждое правило из Р имеет вид A ® b, где A Î VN, b Î (VT È VN)+.
Грамматика G = (VT, VN, P, S) называется укорачивающей контекстно-свободной ( УКС ), если каждое правило из Р имеет вид A ® b, где A Î VN,
b Î (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.
(1) любая неукорачивающая грамматика является грамматикой типа 0.
Замечание: УКС-грамматика, содержащая правила вида A ® e, не является КЗ-грамматикой и не является неукорачивающей грамматикой.
Определение: язык L(G) является языком типа k, если его можно описать грамматикой типа k.
Соотношения между типами языков:
(1) каждый регулярный язык является КС-языком, но существуют КС-языки, которые не являются регулярными ( например, L = {anbn | n>0}).
(2) каждый КС-язык является КЗ-языком, но существуют КЗ-языки, которые не являются КС-языками ( например, L = {anbncn | n>0}).
(2) каждый КЗ-язык является языком типа 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 ® e
описывают один и тот же язык L = L(G1) = L(G2) = { 0n1n | n>0}. Язык L называют КС-языком, т.к. существует КС-грамматика, его описывающая. Но он не является регулярным языком, т.к. не существует регулярной грамматики, описывающей этот язык [3].
Примеры грамматик и языков.
Замечание: если при описании грамматики указаны только правила вывода Р, то будем считать, что большие латинские буквы обозначают нетерминальные символы, S - цель грамматики, все остальные символы - терминальные.
1) Язык типа 0: L(G) = {a2 | n >= 1}
G: S ® aaCFD
F ® AFB | AB
AB ® bBA
Ab ® bA
AD ® D
Cb ® bC
CB ® C
bCD ® e
2) Язык типа 1: L(G) = { an bn cn, n >= 1}
G: S ® aSBC | abC
CB ® BC
bB ® bb
bC ® bc
cC ® cc
3) Язык типа 2: L(G) = {(ac)n (cb)n | n > 0}
G: S ® aQb | accb
Q ® cSc
4) Язык типа 3: L(G) = {w ^ | w Î {a,b}+, где нет двух рядом стоящих а}
G: S ® A^ | B^
A ® a | Ba
B ® b | Bb | Ab
Разбор цепочек
Цепочка принадлежит языку, порождаемому грамматикой, только в том случае, если существует ее вывод из цели этой грамматики. Процесс построения такого вывода ( а, следовательно, и определения принадлежности цепочки языку) называется разбором.
С практической точки зрения наибольший интерес представляет разбор по контекстно-свободным (КС и УКС) грамматикам. Их порождающей мощности достаточно для описания большей части синтаксической структуры языков программирования, для различных подклассов КС-грамматик имеются хорошо разработанные практически приемлемые способы решения задачи разбора.
Рассмотрим основные понятия и определения, связанные с разбором по КС-грамматике.
Определение: вывод цепочки b Î (VT)* из S Î VN в КС-грамматике
G = (VT, VN, P, S), называется левым (левосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого левого нетерминала.
Определение: вывод цепочки b Î (VT)* из S Î VN в КС-грамматике
G = (VT, VN, P, S), называется правым (правосторонним), если в этом выводе каждая очередная сентенциальная форма получается из предыдущей заменой самого правого нетерминала.
В грамматике для одной и той же цепочки может быть несколько выводов, эквивалентных в том смысле, что в них в одних и тех же местах применяются одни и те же правила вывода, но в различном порядке.
Например, для цепочки a+b+a в грамматике
G = ({a,b,+}, {S,T}, {S ® T | T+S; T ® a | b}, S)
можно построить выводы:
(1) S®T+S®T+T+S®T+T+T®a+T+T®a+b+T®a+b+a
(2) S®T+S®a+S®a+T+S®a+b+S®a+b+T®a+b+a
(3) S®T+S®T+T+S®T+T+T®T+T+a®T+b+a®a+b+a
Здесь (2) - левосторонний вывод, (3) - правосторонний, а (1) не является ни левосторонним, ни правосторонним, но все эти выводы являются эквивалентными в указанном выше смысле.
Для КС-грамматик можно ввести удобное графическое представление вывода, называемое деревом вывода, причем для всех эквивалентных выводов деревья вывода совпадают.
Определение: дерево называется деревом вывода (или деревом разбора) в КС-грамматике G = {VT, VN, P, S), если выполнены следующие условия:
(1) каждая вершина дерева помечена символом из множества (VN È VT È e ) , при этом корень дерева помечен символом S; листья - символами из (VT È e);
(2) если вершина дерева помечена символом A Î VN, а ее непосредственные потомки - символами a1, a2, ... , an, где каждое ai Î (VT È VN), то A ® a1a2...an - правило вывода в этой грамматике;
(3) если вершина дерева помечена символом A Î VN, а ее единственный непосредственный потомок помечен символом e, то A ® e - правило вывода в этой грамматике.
Пример дерева вывода для цепочки a+b+a в грамматике G:
Определение: КС-грамматика G называется неоднозначной, если существует хотя бы одна цепочка a Î L(G), для которой может быть построено два или более различных деревьев вывода.
Это утверждение эквивалентно тому, что цепочка a имеет два или более разных левосторонних (или правосторонних) выводов.
Определение: в противном случае грамматика называется однозначной.
Определение: язык, порождаемый грамматикой, называется неоднозначным, если он не может быть порожден никакой однозначной грамматикой.
Пример неоднозначной грамматики:
G = ({if, then, else, a, b}, {S}, P, S),
где P = {S ® if b then S else S | if b then S | a}.
В этой грамматике для цепочки if b then if b then a else a можно построить два различных дерева вывода.
Однако это не означает, что язык L(G) обязательно неоднозначный. Определенная нами неоднозначность - это свойство грамматики, а не языка, т.е. для некоторых неоднозначных грамматик существуют эквивалентные им однозначные грамматики.
Если грамматика используется для определения языка программирования, то она должна быть однозначной.
В приведенном выше примере разные деревья вывода предполагают соответствие else разным then. Если договориться, что else должно соответствовать ближайшему к нему then, и подправить грамматику G, то неоднозначность будет устранена:
S ® if b then S | if b then S’ else S | a
S’ ® if b then S’ else S’ | a
Проблема, порождает ли данная КС-грамматика однозначный язык (т.е. существует ли эквивалентная ей однозначная грамматика), является алгоритмически неразрешимой.
Однако можно указать некоторые виды правил вывода, которые приводят к неоднозначности:
(3) A ® AA | a
(4) A ® AaA | b
1. A ® aA | Ab | g
2. A ® aA | aAbA | g
Пример неоднозначного КС-языка:
L = {ai bj ck | i = j или j = k}.
Интуитивно это объясняется тем, что цепочки с i = j должны порождаться группой правил вывода, отличных от правил, порождающих цепочки с j = k. Но тогда, по крайней мере, некоторые из цепочек с i = j = k будут порождаться обеими группами правил и, следовательно, будут иметь по два разных дерева вывода. Доказательство того, что КС-язык L неоднозначный, приведен в [3, стр. 235-236].
Одна из грамматик, порождающих L, такова:
S ® AB | DC
A ® aA | e
B ® bBc | e
C ® cC | e
D ® aDb | e
Очевидно, что она неоднозначна.
Дерево вывода можно строить нисходящим либо восходящим способом.
При нисходящем разборе дерево вывода формируется от корня к листьям; на каждом шаге для вершины, помеченной нетерминальным символом, пытаются найти такое правило вывода, чтобы имеющиеся в нем терминальные символы “проектировались” на символы исходной цепочки.
Метод восходящего разбора заключается в том, что исходную цепочку пытаются “свернуть” к начальному символу S; на каждом шаге ищут подцепочку, которая совпадает с правой частью какого-либо правила вывода; если такая подцепочка находится, то она заменяется нетерминалом из левой части этого правила.
Если грамматика однозначная, то при любом способе построения будет получено одно и то же дерево разбора.
Преобразования грамматик
В некоторых случаях КС-грамматика может содержать недостижимые и бесплодные символы, которые не участвуют в порождении цепочек языка и поэтому могут быть удалены из грамматики.
Определение: символ x Î (VT È VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.
Дата добавления: 2018-10-27; просмотров: 436; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!