Основы теории формальных языков
В этом
разделе изложены некоторые аспекты теории формальных языков, существенные с
точки зрения трансляции. Здесь введены базовые понятия и даны определения,
связанные с одним из основных механизмов определения языков - грамматиками,
приведена наиболее распространенная классификация грамматик (по Хомскому).
Особое внимание уделяется контекстно-свободным грамматикам и, в частности, их
важному подклассу - регулярным грамматикам. Грамматики этих классов широко используются
при описании и трансляции языков программирования. Здесь не приводятся
доказательства сформулированных фактов, свойств, теорем, доказательства
правильности алгоритмов; их можно найти в книгах, указанных в списке
литературы.
Определение: алфавит
- это конечное множество символов. (Термин "символ" имеет достаточно
ясный интуитивный смысл и не нуждается в дальнейшем уточнении.)
Например,
алфавит A = {a, b, c, +, !} содержит 5 букв, а алфавит B = {00,
01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.
Определение:
цепочкой символов в алфавите V
называется любая конечная последовательность символов этого алфавита.
Определение:
цепочка, которая не содержит ни одного символа, называется пустой цепочкой.
Для ее обозначения будем использовать символ l.
Более
формально цепочка символов в алфавите V определяется следующим образом:
(1) l -
цепочка в алфавите V;
(2) если
a
- цепочка в алфавите V и a - символ
этого алфавита, то aa или аa - цепочка в алфавите V;
(3) b -
цепочка в алфавите V тогда и только тогда, когда она является
таковой в силу (1) и (2).
Определение:
если a и b - цепочки, то цепочка ab называется конкатенацией (или
сцеплением) цепочек a и b.
Например,
если a = ab и b = cd, то ab = abcd.
Для любой
цепочки a всегда al = la = a.
Определение: обращением
(или реверсом) цепочки a называется цепочка, символы
которой записаны в обратном порядке.
Обращение
цепочки a будем обозначать aR.
Например,
если a = abcdef, то aR
= fedcba.
Для
пустой цепочки: l = lR.
Определение:
n-ой степенью цепочки a (будем обозначать an)
называется конкатенация n цепочек a.
a0
= l;
an
= aan-1
= an-1a.
Определение: длина
цепочки - это число составляющих ее символов.
Например,
если a = abcdefg, то длина a равна 7.
Длину
цепочки a будем обозначать |a|. Длина l равна 0.
Определение: язык
в алфавите V - это подмножество цепочек конечной длины в этом алфавите.
Определение:
обозначим через V* множество, содержащее все цепочки в
алфавите V, включая пустую цепочку l.
Например,
если V={0,1}, то V* = {l, 0, 1,
00, 11, 01, 10, 000, 001, 011, ...}.
Определение:
обозначим через V+ множество, содержащее все цепочки в
алфавите V,
исключая пустую цепочку l.
Следовательно,
V* = V+ È {l}.
Ясно, что
каждый язык в алфавите 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 ® l
Определение: цепочка
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 ® l
эквивалентны, т.к. обе порождают
язык
L(G1)
= L(G2) = {0n1n | n>0}.
Определение:
грамматики G1 и G2 почти эквивалентны, если
L(G1)
È
{l}
= L(G2) È {l}.
Другими
словами, грамматики почти эквивалентны, если языки, ими порождаемые, отличаются
не более, чем на l.
Например,
G1 = ({0,1}, {A,S}, P1, S) и G2 = ({0,1}, {S}, P2, S), где
P1: S ® 0A1 P2: S ® 0S1
| l
0A ® 00A1
A ® l
почти эквивалентны, т.к. L(G1)={0n1n
| n>0}, а L(G2)={0n1n
| n³0}, т.е. L(G2)
состоит из всех цепочек языка L(G1)
и пустой цепочки, которая в L(G1)
не входит.
Способы задания схем
грамматик
Схема
грамматики содержит правила вывода, определяющие синтаксис языка, или, другими
словами, структуру цепочек порождаемого языка. Для задания правил используются
различные формы описания: символическая, форма Бэкуса-Наура, итерационная форма
и синтаксические диаграммы.
При
рассмотрении общих свойств грамматик обычно применяют символическую форму
задания правил. Эта форма была рассмотрена в предыдущем параграфе.
В
практических применениях вместо символического представления схем грамматик
обычно используют форму Бэкуса-Наура, или синтаксические диаграммы.
