Рекурсия в правилах грамматики
Типы рекурсивных грамматик
1) леворекурсивная : <нетерминал А> ::= <нетерминал А> В
2) правокурсивная : <нетерминал А> ::= В <нетерминал А>
3) с непосредственным восстановлением : <нетерминал А> ::= C <нетерминал А> В
пример:
a) <целое> ::= <знак><целое без знака> | <целое без знака>
b) <ц.б.з> ::= <ц.б.з><цифра> | <цифра>
c) <знак> ::= + | -
d) <целое> ::= 0|1|2|3|4|5|6|7|8|9
Эквивалентная грамматика – грамматика описывающая в точности тот же язык, что и другая грамматика.
Для одного и того же языка можно сконструировать бесконечное мноежство эквивалентных грамматик.
В теории формальных языков для любой левокурсивной грамматики существует эквивалентная правокурсивная грамматика.
Есть другое, формальное, определение для грамматики.
G = (Vт, Vn, S, P)
где Vт – множество терминальных символов.
Vn – множество нетерминальных символов
S – начальный символ грамматики
P – множество правил подстановки вида a::=b
Пример:
Пусть язык L1 = {0^n, 1^2 | n >= 0}, где n – целое число
Допустимая цепочка: E, 01,0011, 000111, 000…0111…1
Тогда для языка L1 будет определена грамматика:
G1 = ({0,1},{S}, S, P)
P: a) <S> ::= 0<S>1
b) <S>::=E
Классификация (или иерархия) грамматик.
Тип 0. Нет ограничений на вид правил подстановки a::=b.
Тип 1. контекста зависимая (неукорачивающая) грамматика.
Здесь имеет место контекстная зависимость в правилах подстановки, которую символически можно изобразить как B <A> C ::= B a C
тип 2. Контекстно-независимые (контекстно-свободные грамматики). Здесь a всегда единичный нетерминал.
Тип 3. Автоматные (регулярные) грамматики.
Здесь кроме ограничений из пункта 3 есть ещё ограничения на вид правой части всех правил, а именно В может иметь только вид: T <N> | <N> T | T | E.
Существует взаимно однозначное соотвествие между типо грамматики и типом необходимого распознающего агрегата.
Для типа 3 – конечный автомат.
Для типа 2 – конечный автомат со стековой (магазинной) памятью.
Для типа 1 – машина Тьюринга с конечной лентой.
Для типа 0 – машина Тьюринга с бесконечной лентой.
Распознающая часть транслятора это программная реализация конечных автоматом.
Даже грамматик типа 0 недосстаточно для описания наших естественных языков.
Классификация языков
Такая же 4-х типовая. НО тип языка должен определятся по типу грамматики наименьшей мощности среди всего множества эквивалентных грамматик для данного языка.
Пример поиска грамматики:
язык L2 = {a^n, b^m | n>=0; m>=0}, где m,n – натуральные числа.
цепочка языка: E, a, a…aa, b, bb…b, a..aab..bb
G2 = ({a,b};{S,A,B};S;P)
P:
a) <S> ::= <A><B>
b) <A>::= a<A>| E
c) <B> ::= b<B> | E
тип грамматики – тип 2 – конечный автомат со стековой памятью.
G’2 = ({a,b};{S};S;P)
P:
a) <S> ::= a<S>
b) <S>::= <S>b
c) <S> ::= E
G’2 – грамматика типа 0 – конечный автомат.
Главные вопросы по теме:
Определение грамматики
Определение эквивалентной грамматики
Типы грамматик по Хомскому
Типы языков
типы распознающих агрегатов их однозначные соответствия типам грамматик.
Вторая итерация рассмотрения фаз компилятора