Рекурсивный нетерминал: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||
* Касьянов В.Н. Лекции по теории формальных языков, автоматов и сложности вычислений. — Новосибирск: НГУ, 1995. | |||
Текущая версия от 12:05, 1 сентября 2011
Рекурсивный нетерминал (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.