spoPresentation2

Классификация грамматик

Автоматные грамматики

Леволинейные: АoВt, Аot, А,В N, t Т

Праволинейные: АotВ, Аot, А,В N, t Т

В отличии от общего вида регулярных грамматик, в правой части правил может присутствовать только один терминальный символ

Регулярные и автоматные грамматики почти эквивалентны

71

Классификация грамматик

В автоматных грамматиках допускается дополнительное правило вида SoO, где S -

аксиома. При этом S не должна встречаться в правых частях других правил грамматики

В этом случае язык, заданный автоматной грамматикой, может включать в себя пустую цепочку, и такая автоматная грамматика полностью эквивалентна регулярной

72

Классификация грамматик

В общем случае одна и та же грамматика может быть отнесена к нескольким классам

Теорема 1. Язык L(G), порождаемый неукорачивающей грамматикой G, легко распознаваем

Теорема 2. Если язык L(G) регулярный, то

он КС. Если язык L(G)	0 1 2	3
КС, то язык L(G)\O

КЗ. Если язык L(G) КЗ,

то он язык класса 0

Классификация грамматик

Для классификации всегда выбирается тип с максимальным номером

Сложность грамматики обратно пропорциональна их типу

Класс 0 допускает самые сложные грамматики, класс 3 – самые простые

74

Классификация грамматик

Пример. G = <N,T,P,S>, N = {F,D,C}, T = {>,<,=,!}, P = {CoD= | F, Do! | = | F, Fo < | >}, S={C}.

CoD= . Для типа 1 (КЗ):

D1АD2oD1ED2, D1, D2 V*, А N, E V+

D1=D2=O V*, тогда A={С} N, E = { D= } V+

Аналогично остальные продукции. Грамматика G соответствует классу 1

Для неукорачивающих

DoE, D, E V+, |E|t|D|

{С} V+,{D=} V+, |D=| =2 > |С| =1

Соответствует. Проверяем все правила

75

Классификация грамматик

Для типа 2 (КС)

АoE, А N, E V+

A={С} N, E={D=} V+

Соответствует. Проверяем все правила

Для типа 3 (регулярные) Леволинейные АoВJ, АoJ, А,В N, J Т*

Праволинейные АoJВ, АoJ, А,В N, J Т* A={С} N, B={D} N, J={=} Т*. Леволинейная

Проверяем все правила

76

Классификация грамматик

Для автоматных АoВa, Аoa, А,В N, a Т

A={С} N, B={D} N, a={=} Т. Соответствует Доходим до продукции СoF

A={С} N, B={F} N, a={O} Т. Не автоматная

77

Иерархия грамматик и языков

Тип Грамматика Язык Распознаватель

Недет., 2-ст.,

0 0 (фр) С фр. стр. неогр. пам.

(машина Тьюринга)

1

1 (КЗ)

КЗ

2

2 (КС)

КС

Недет., 2-ст.,

лин. огр. пам.

Недет., 1-ст.,

магаз. пам.

	3	3 (рег)	Рег.	Недет., 1-ст.,
				без пам.

78

Иерархия грамматик и языков

Тип 0. Для такого языка невозможно построить компилятор, который гарантировано выполнял бы разбор предложений за ограниченное время на основе ограниченных вычислительных ресурсов

Для КЗ языков время распознавания в общем случае экспоненциально зависит от длины исходной цепочки символов

79

Иерархия грамматик и языков

Для КС языков время распознавания в общем случае полиномиально зависит от длины входной цепочки. В зависимости от класса языка это либо кубическая либо

квадратичная зависимость. Для многих языков этого класса зависимость является линейной

80