Задача распознавания цепочек языка

Пусть задана грамматика G(L) = {Σ, N, S, P} и цепочка γ терминальных символов алфавита Σ. Задача распознавания состоит в том, чтобы ответить на вопрос, принадлежит ли цепочка γ языку, порождаемому грамматикой G(L). Эту задачу можно решить следующим образом: попробовать построить последовательность применений правил грамматики, порождающих цепочку γ. Если удается найти такую последовательность, то ответом будет «да», в противном случае – «нет». Построенную при ответе «да» последовательность применений правил называют грамматическим разбором цепочки. Грамматический разбор необходим, если требуется произвести трансляцию цепочки, т.е. ее перевод в некоторую другую форму.

Сложность задачи распознавания зависит от сложности грамматики. Доказано, что для грамматики класса 0 в общем случае эта задача алгоритмически неразрешима, т.е. не существует универсального алгоритма, который для любой грамматики класса 0 и любой входной цепочки после конечного числа шагов выдаст ответ «да» или «нет». Алгоритмы распознавания построены для грамматик классов 1, 2 и 3, причем как для однозначных, так и для неоднозначных грамматик. Сложность алгоритмов распознавания тем меньше, чем проще грамматика. Самый простой и эффективный алгоритм существует для распознавания однозначных грамматик класса 3 (А-грамматик).

Порождающие грамматики применяются для решения задач распознавания самых различных языков. Для естественных языков (английского, русского и др.) их применение ограниченно: в настоящее время удалось построить грамматики (КЗ-грамматики) только для упрощенных подмножеств естественных языков. В то же время для большинства языков программирования (языков высокого уровня) однозначные КС-грамматики явились мощным инструментом для создания трансляторов. Что же касается машинных языков, а также автокодов, ассемблеров, командных языков, то для их описания оказалось достаточным применение однозначных А-грамматик.

Дата добавления: 2015-07-26; просмотров: 137; Нарушение авторских прав

Мы поможем в написании ваших работ!