Языки и трансляции. Мартыненко Б.К. - 18 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

17
§ 2.3. Типы грамматик
Грамматику, определенную в предыдущем параграфе, вслед за Н.Хомским
назовем
грамматикой типа 0. Им введено ещё три типа грамматик, различа-
ющихся ограничениями, накладываемыми на вид правил.
Определение 2.7. Грамматика G = (V
N
, V
T
, P, S) является грамматикой типа 1
или
контекстно-зависимой грамматикой, если для каждого её правила α → β∈ P
выполняется условие
| β | ≥ | α |.
Часто вместо термина “контекстно-зависимая грамматика” используют
аббревиатуру csg (
context-sensitive grammar). Очевидно, что грамматики,
приведённые в примерах 2.1. и 2.2, являются контекстно-зависимыми грам-
матиками, поскольку правые части их правил не короче левых частей.
Замечание 2.1. Некоторые авторы требуют, чтобы правила контекстно-
зависимой грамматики имели вид:
α
1
Aα
2
→α
1
βα
2
, где α
1
,α
2
,β∈V
*
, причём
β≠ε, а A∈V
N
. Это мотивирует название “контекстно-зависимая” тем, что
правило
α
1
Aα
2
→ α
1
βα
2
позволяет заменять A на β только, если A появляется в
сентенциальной форме в контексте
α
1
и α
2
. В отечественной литературе для
таких грамматик чаще используется термин НС-грамматики или
грамматики
непосредственных составляющих, а грамматики типа 1 называются неукорачи-
вающими грамматиками.
Можно показать, что это требование относительно контекстной замены не
изменяет класса порождаемых языков. Действительно, любая НС-грамматика
является неукорачивающей. Однако любое правило неукорачивающей грам-
матики может быть преобразовано так, чтобы все символы, его составляющие,
были нетерминалами. Для этого достаточно каждое вхождение терминала
a∈ V
T
заменить на новый нетерминал Z, пополнить словарь нетерминалов этим
символом и включить правило
Z → a в множество правил грамматики.
Правила вида
Z → a допустимы для НС-грамматик.
Правило же вида
X
1
X
2
… X
m
→ Y
1
Y
2
…Y
m + q
, где m > 0, q ≥ 0, X
i
,Y
j
∈V
N
, 1 ≤ i ≤ m, 1 ≤ j ≤ m + q
эквивалентно группе правил:
X
1
X
2
… X
m
→ A
1
X
2
… X
m
,
A
1
X
2
… X
m
→ A
1
A
2
… X
m
,
…
A
1
A
2
… X
m
→ A
1
A
2
… A
m
,
A
1
A
2
… A
m
→ Y
1
A
2
… A
m
,
Y
1
A
2
… A
m
→ Y
1
Y
2
… A
m
,
…
Y
1
Y
2
… A
m –1
A
m
→ Y
1
Y
2
…Y
m –1
A
m
,
Y
1
Y
2
…
A
m –1
A
m
→ Y
1
Y
2
…Y
m –1
Y
m
Y
m +1
…Y
m + q
,
где A
1
, A
2
,…, A
m
— дополнительные нетерминалы. Каждое из этих правил имеет
требуемый НС-грамматикой вид: α
1
Aα
2
→α
1
βα
2
.

Страницы