Рекурсивный нетерминал: различия между версиями

Перейти к навигации Перейти к поиску
нет описания правки
Нет описания правки
Нет описания правки
 
Строка 1: Строка 1:
'''Рекурсивный нетерминал''' (''[[Recursive nonterminal symbol]]'') -
'''Рекурсивный нетерминал''' (''[[Recursive nonterminal symbol]]'')
''[[нетерминал]]'' <math>A</math> ''[[контекстно-свободная грамматика|контекстно-свободной грамматики]]''
''[[нетерминал]]'' <math>\,A</math> ''[[контекстно-свободная грамматика|контекстно-свободной грамматики]]''
<math>G=(N,\Sigma,P,S)</math>, если <math>A\Longrightarrow^+\alpha A\beta</math>
<math>\,G=(N,\Sigma,P,S)</math>, если <math>A\Longrightarrow^+\alpha A\beta</math>
для некоторых <math>\alpha</math> и <math>\beta</math>. Если <math>\alpha =e</math>, то <math>A</math>
для некоторых <math>\,\alpha</math> и <math>\,\beta</math>. Если <math>\,\alpha =e</math>, то <math>\,A</math>
называется ''леворекурсивным''. Аналогично, если <math>\beta
называется ''леворекурсивным''. Аналогично, если <math>\,\beta
=e</math>, то <math>A</math> называется ''праворекурсивным''.
=e</math>, то <math>\,A</math> называется ''праворекурсивным''.


[[Грамматика]] <math>G</math> называется ''леворекурсивной''
[[Грамматика]] <math>\,G</math> называется ''леворекурсивной''
(соответственно ''праворекурсивной''), если в <math>G</math> имеется
(соответственно ''праворекурсивной''), если в <math>\,G</math> имеется
хотя бы один леворекурсивный (соответственно
хотя бы один леворекурсивный (соответственно
праворекурсивный) нетерминал. Грамматика, в которой
праворекурсивный) нетерминал. Грамматика, в которой
Строка 13: Строка 13:
символа, называется ''рекурсивной''.
символа, называется ''рекурсивной''.
==Литература==
==Литература==
[Ахо-Ульман],  
* Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — Т. 1,2.
 
[Касьянов/95]
* Касьянов В.Н.  Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995.

Навигация