Существенно неоднозначные языки

Материал из Викиконспекты
Перейти к: навигация, поиск

Неоднозначные грамматики

Неоднозначной грамматикой называется грамматика, по которой для одной цепочки существует более одного дерева разбора..

Пример:

Рассмотрим грамматику [math]E \rightarrow E + E | E * E[/math] и выводимую цепочку[math]E + E * E[/math]. Ее можно вывести двумя способами: [math]E \Rightarrow E + E \Rightarrow E + E * E[/math] [math]E \Rightarrow E * E \Rightarrow E + E * E[/math] Эта граматика неоднозначна.