КС-грамматика называется однозначной если для некоторой цепочки w приналежит (N U T)* существует только одно дерево вывода . В противном случае грамматика называется неоднозначной.

Необходимо отметить , что однозначность или неоднозначность - это свойства грамматики, а не языка. Язык может быть описан несколькими грамматиками. Имеет же смысл рассматривать только однозначные грамматики.

 

КС язык называется существенно неоднозначным если каждая КС-грамматика пораждающая этот язык является неоднозначной.

 

ТЕОРЕМА) Каждый праволинейный язык, пораждается некоторой праволинейной грамматкикой. Другими словами: ни один праволинейный язык не является существенно неоднозначным.

ОПР) КС-грамматика G называется

1) левокурсивной, если в ней имеются выводы вида х::=X*АЛФА, где x принадлежит N, АЛФА приналежит (N U T)*

2) правокурсивной, если в ней имеются выводы вида X::=АЛФА*Х, где x принадлежит N, АЛФА приналежит (N U T)*

3)самовставляющей, если она имеет вывод вида вида X::=АЛФА*Х*БЕТА, где x принадлежит N, АЛФА и БЕТА приналежит (N U T)*

 

КС-грамматика G называется рекурскией, если имеется хотя бы один из описанных случаев.

В общем случае любая КС-грамматика описывающая язык программирования, является рекурсивной.

Важной является выявление того или иного метода синтаксического разбора. Различные методы построения дерева синтаксического разбора допускает в грамматике один вид рекурсии.