Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
|
Класифікація породжувальних граматик
Пусть дана грамматика G = (N, T, P, S). Тогда если правила грамматики не удовлетворяют никаким ограничениям, то ее называют грамматикой типа 0, или грамматикой без ограничений. Если каждое правило грамматики, кроме S e, имеет вид , где | | | |, и в том случае, когда S e P, символ S не встречается в правых частях правил,то грамматику называют грамматикой типа 1, или неукорачивающей. Если каждое правило грамматики имеет вид A , где A N, (N T)*, то ее называют грамматикой типа 2, или контекстно-свободной (КС-грамматикой). Если каждое правило грамматики имеет вид либо A xB, либо A x, где A, B N, x T* то ее называют грамматикой типа 3, или праволинейной. Язык типа 1 - контекстно-зависимым (КЗ), язык типа 2 - контекстно-свободным (КС), язык типа 3 - праволинейным. K3 K2 K1 K0. Грамматика G называется неоднозначной, если существует цепочка w, для которой имеется два или более различных деревьев вывода в G. Грамматика G называется леворекурсивной, если в ней имеется нетерминал A такой, что существует вывод для некоторой цепочки w. Атрибутной грамматикой называется четверка AG = (G, AS, AI, R), где · G = (N, T, P, S) - приведенная КС-грамматика; · AS - конечное множество синтезируемых атрибутов; · AI - конечное множество наследуемых атрибутов, AS AI = ; · R - конечное множество семантических правил.
Date: 2015-09-24; view: 374; Нарушение авторских прав |