spoPresentation2

Однозначность грамматики

Грамматика неоднозначна, если в ней имеются правила вида:

SoSS | D

SoSDS | E

SoDS | SE | J

SoDS | DSES | J

Это необходимое, но не достаточное условие однозначности

Отсутствие правил такого вида еще не гарантирует однозначности

191

Рекурсивность грамматики

Рекурсия может быть явной, когда символ определяется сам через себя A o D1A D2

неявной (косвенной), когда символ определяется через цепочку правил

A* D1A D2

Грамматика называется леворекурсивной, если в ней имеются выводы вида: A N: A *AD, DV+

Праворекурсивной: A N: A *DА, DV+

Самовставляющей (самовложенной) A N: A * DAE, D,EV+.

192

Приведеная грамматика

В грамматике G(N,T,P,S) символ A N

называется бесполезным (бесплодным), если не существует вывода вида:

S * DAE DbE, D,b,E T*

Из него нельзя вывести ни одной цепочки терминальных символов

Символ A называется недостижимым, если AzS и не существует вывода вида:

S *DAE, D,E V*

При любом выводе этот символ не может

появиться в цепочке

193

Приведеная грамматика

Грамматика G(N,T,P,S) называется грамматикой без O-правил, (O-свободной) если AoO Р, A N, либо есть ровно одно правило SoO, и аксиома S не встречается в

правых частях других правил

КС грамматика G(N,T,P,S) называется грамматикой без циклов, если в ней нет выводов вида A *A, A N

Циклы возможны только если в грамматике присутствуют цепные правила вида AoB, A,B N

194

Приведеная грамматика

Упрощение грамматики:

Устранение недостижимых символов

Устранение бесполезных символов

Максимальное упрощение построения СА:

Устранение цепных правил (как следствие циклов)

Устранение O-правил

Грамматика называется приведенной, если она не имеет бесполезных и недостижимых символов, O-правил, цепных правил

195

Приведеная грамматика

Любая приведенная КС-грамматика, не содержащая самовложений, эквивалентна регулярной грамматике

Алгоритмы приведения выполняются в следующем порядке

удаление бесполезных символов

удаление недостижимых символов

удаление O-правил

удаление цепных правил

196

Нормальная форма Хомского

Для КС грамматик существует несколько стандартных способов задания, т.н. нормальных форм

Каждая КС грамматика G (N,T,P,S) эквивалентна КС грамматике G’ (N’,T,P’,S) в НФ Хомского, все порождающие правила из множества P’ имеют вид

AoBC | Aoa, A,B,C N’, a T; либо SoO,

если O L(G) и S не встречается в правых

частях правил

197

Нормальная форма Грейбах

Другой формой представления G (N,T,P,S) является НФ Грейбах, все порождающие правила из множества P имеют вид

Ao bD, A N, b T, D N* либо SoO, если

O L(G) и S не встречается в правых частях

правил

198

Перевод КС грамматики в НФ Хомского

Дано: КС грамматика G(T,N,P,S)

Получить: эквивалентную ей КС грамматику в НФ Хомского G’(T’,N’,P’,S’), задающую тот же язык L(G) = L(G’)

Дополнительные условия: грамматика G

должна быть приведенной

199

Перевод КС грамматики в НФ Хомского

1. T’ = T, N’ = N, S’ = S

2. P’ ={p|AoBC;Aoa;SoO;A,B,C N, a T; p P}

3. P’ = P’ { p | AoBA’, A’oa; причем AoBaP; A,B N, a T }; N’=N’ {A’}

4. P’ = P’ { p | AoA’B, A’oa; причем AoaB P; A,B N, a T }; N’=N’ {A’}

5. P’ = P’ { p | Bi-1oAi’Bi ; i=1,2,…,k-1; B0=A;

Bk-1 =Ak’ , причем AoA1A2…Ak P, k>2; где

Ai’=Ai , если Ai N , и P’ = P’ { p’ | Ai’ o Ai } если Ai Т }; N’ = N’ {B1, B2,…,Bk-2, A1’, A2’,…Ak’}

200