Рекурсивный нетерминал

Рекурсивный нетерминал (Recursive nonterminal symbol) — нетерминал [math]\displaystyle{ \,A }[/math] контекстно-свободной грамматики [math]\displaystyle{ \,G=(N,\Sigma,P,S) }[/math], если [math]\displaystyle{ A\Longrightarrow^+\alpha A\beta }[/math] для некоторых [math]\displaystyle{ \,\alpha }[/math] и [math]\displaystyle{ \,\beta }[/math]. Если [math]\displaystyle{ \,\alpha =e }[/math], то [math]\displaystyle{ \,A }[/math] называется леворекурсивным. Аналогично, если [math]\displaystyle{ \,\beta =e }[/math], то [math]\displaystyle{ \,A }[/math] называется праворекурсивным.

Грамматика [math]\displaystyle{ \,G }[/math] называется леворекурсивной (соответственно праворекурсивной), если в [math]\displaystyle{ \,G }[/math] имеется хотя бы один леворекурсивный (соответственно праворекурсивный) нетерминал. Грамматика, в которой рекурсивны все нетерминалы, кроме, быть может, начального символа, называется рекурсивной.

Литература

• Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.

• Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.