Факультет вычислительной математики и кибернетики (стр. 10 из 15)
Несмотря на компактность и удобство регулярных выражений , далеко
не все языки можно определить с помощью регулярных выражений . Существует более универсальный и мощный аппарат описания языка
с помощью грамматик .
Грамматика определяется в виде четверки объектов (AT, AN ,P,S ), где
AT - алфавит терминальных символов , AN - алфавит нетерминальных символов , P - множество продукций ( или правил вывода ) вида a -> b ,
где a - левая часть , а b - правая часть продукции , S - начальный символ ( аксиома или символ предложения ) грамматики , являющийся элементом множества AN ( SÎ AN ) . При этом имеют место следующие соотношения : AT Ç AN = Æ ,a Î A* , b Î A* , A = AT È AN ( A* определяет строки , состоящие из нуль или более повторений символов из A ) . Особенностью начального символа S является то , что с него начинается генерация любой строки языка .
Грамматика используется для генерации строк символов языка начиная с аксиомы грамматики , последовательно применяя правила подстановки ( продукции ) и заменяя нетерминал последователь-
ностью символов правой части соответствующей продукции . Процесс завершается получением строки , не содержащей нетерминальных символов . Язык содержит только те строки символов , которые можно сгенерировать с помощью заданной грамматики .
В дальнейшем для обозначения терминальных символов будем использовать строчные буквы , или , в некоторых случаях слова , состоящие только из строчных букв ( x , y , if , then , else и т.п.). Для обозначения нетерминальных символов будем использовать заглавные буквы ( X ,Y, S и т.п.) . Аксиому грамматики будем обозначать буквой S .
Греческие буквы будут использованы для обозначения строк символов .
Рассмотрим примеры различных грамматик.
Пример 6 . Грамматикой для языка { x n y n | n>0 } , строки которого состоят из одного или более символов x , после чего следует такое же количество символов y , является G1= ( { x , y }, { S }, P , S ) , где множество продукций P определяется как : S -> xSy , S -> xy .
Пример7 . Грамматикой для языка { x m y n |m, n³ 0 } , строки которого состоят из нулевого числа или более символов x , после чего следует нулевое число или более символов y , является
G2= ( { x , y }, { S , B }, P , S ) , где множество продукций P определяется как :
S -> xS
S -> yB
S -> x
S -> y
S -> <>
B -> yB
B -> y .
Например , строка xxyyy может быть сгенерирована грамматикой G2
с помощью серии подстановок S=> xS => xxS => xxyB => xxyyB => xxyyy ,
называемой порождением . Каждая из строк , входящая в порождение ,
называется сентенциальной формой , а последняя сентенциальная форма , состоящая только из терминальных символов , называется
предложением языка . Выражение вида a => b , где a , b - сентенциаль-ные формы означает , что строка b получена из строки a посредством одного порождения . Выражение вида a =*> b означает , что строка b порождается из строки a за нуль или более шагов . Выражение вида
a =+> b означает , что строка b порождается из строки a за один или более шагов . Условимся в дальнейшем обозначать порождения вида
B -> yB , B -> y как B -> yB | y .
Для классификации грамматик и языков было введено понятие иерархии Хомского . Хомский определил четыре класса грамматик , которые были названы грамматиками 0-го , 1-го , 2-го и 3-го типов .
К 0-му типу относятся все грамматики без ограничений на типы продукции . Грамматики 0-го типа называют еще рекурсивно-
- перечислимыми грамматиками .
Грамматики , все продукции которых ограничены соотношением
| a | £ | b | ( то есть длина строки a , исчисляемая количеством входящих символов , не может быть больше длины строки b ) , называ-ются грамматиками 1-го типа , или по другому контекстно-
- зависимыми .
Если контекстно-зависимую грамматику ограничить условием ,
которое предусматривает наличие в левой части каждой продукции только одного единственного нетерминального символа , то мы получаем грамматику 1-го типа , или по другому контекстно-свободную грамматику .
Для определения 3-го типа грамматик , или так называемых регулярных грамматик , введем сначала ряд вспомогательных определений.
Грамматика называется праволинейной , если каждая ее продукция имеет вид A-> a либо A-> bC . Соответственно грамматика называется леволинейной , если каждая ее продукция имеет вид A-> a либо A-> Cb .
Грамматика называется регулярной ( грамматикой 3-го типа ), если она является только праволинейной или только левоволинейной .
Замечание . В контекстно-свободных грамматиках разрешим
использование продукций вида a -> <> , где a -нетерминальный символ ( хотя строго говоря эта продукция не разрешена даже в контекстно-
-зависимых грамматиках ). Это необходимо для включения в соответствующий язык пустой строки в целях более удобного описания синтаксиса языков программирования .
Классификация Хомского является иерархической в том смысле , что
все грамматики 3-го типа являются грамматиками 2-го , все грамматики
2-го типа являются грамматиками 1-го , а все грамматики 1-го типа -
- грамматиками 0-го типа .
Соответственно , мы можем определить иерархию языков
основываясь на порождающих их грамматиках , то есть языки 3-го типа , языки 2-го типа и т.п. . Однако необходимо иметь в виду , что существуют языки , например 3-го типа , которые определяются грамматикой 2-го типа , и в то же время существует эквивалентная грамматика 3-го типа для порождения этого языка (в этом случае она обязательно должна существовать , поскольку речь идет о языке 3-го типа) .
Например язык вида { x m y n |m, n³ 0 } (этот пример уже рассматривался выше) . Этот язык можно сгенерировать следующими продукциями :
S->XY
X->xX
X-> <>
Y->yY
Y-> <>
Очевидно , что грамматика с перечисленными выше продукциями не является грамматикой 3-го типа . Однако этот же язык можно определить
следующими ниже продукциями 3-го типа .
S -> xS
S -> yB
S -> x
S -> y
B -> yB
B -> y
S -> <>
В разработке компиляторов широко используются контекстно-
-свободные и регулярные грамматики . Регулярные грамматики , являющиеся подмножествами контекстно-свободных , являются более простыми. Поэтому всюду , где это возможно имеет смысл использовать в процессе компиляции регулярные грамматики и языки.
В связи с этим возникает необходимость в выявлении способа определения , является ли генерируемый язык регулярным. Такой способ существует и сводится к достаточно простому свойству грамматики , позволяющего определить , является ли генерируемый язык регулярным . Для рассмотрения этого свойства предварительно введем понятие рекурсии в грамматике . Рассмотрим следующие продукции :
A -> Ab
B -> cB
C -> dCf .
Это - примеры так называемой прямой рекурсии , при которой нетерминальный символ из левой части продукции входит и в правую часть . В первом случае имеем левую рекурсию ( нетерминал слева ),
во втором - правую рекурсию (нетерминал справа) , в третьем - среднюю
рекурсию ( нетерминал располагается и не слева и не справа ).Следует
отметить , что кроме прямой рекурсии существует еще понятие
косвенной ( непрямой ) рекурсии . Например : A -> Bc , B -> Cd , C -> Ae . Поскольку существует простой алгоритм преобразования косвенной рекурсии в прямую (этот алгоритм мы здесь не рассматриваем) , далее мы не будем рассматривать косвенную рекурсию .
Теперь мы можем сформулировать важное утверждение , на основе которого можно будет определить , является ли генерируемый язык регулярным : если грамматика не содержит средней рекурсии , то
генерируемый этой грамматикой язык является регулярным . Доказательства этого утверждения мы здесь не приводим .
Введем несколько полезных определений , которые будут использо-ваны в дальнейшем.
Левое порождение определяется как порождение , на каждом шаге которого заменяется крайний левый нетерминал сентенциальной
формы.
Правое порождение определяется как порождение , на каждом шаге которого заменяется крайний правый нетерминал сентенциальной
формы.
Рассмотрим в качестве примера язык вида { x m y n |m, n > 0 } , определяемый следующими продукциями :
S -> XY
X -> xX
X -> x
Y - >yY
Y -> y
Строка xxxyy может быть сгенерирована одним из двух порождений :
1) S => XY => xXY => xxXY => xxxY => xxxyY => xxxyy
2) S => XY => XyY => Xyy => xXyy => xxX yy => xxxyy .
Первое порождение является левым , а второе - правым .
Порождение можно выразить по другому - через синтаксическое дерево ( дерево синтаксического разбора ) .
Например порождение S =>XY=>xXY=>xXyY=>xxXyY=>xxXyy=>xxxyy
можно выразить следующим синтаксическим деревом :
S
 |  |
X Y
 |  |  | |
x X y Y
| | |  |
x X y
x
Рис. 3.1.1-1. Пример синтаксического дерева.
Грамматика называется однозначной , если каждое сгенерированное