Рекурсивный нетерминал: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Рекурсивный нетерминал''' (''Recursive nonterminal symbol'') - ''нетерминал'' <math>A</math> ''конт...) |
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> | ||
| Строка 6: | Строка 6: | ||
=e</math>, то <math>A</math> называется ''праворекурсивным''. | =e</math>, то <math>A</math> называется ''праворекурсивным''. | ||
Грамматика <math>G</math> называется ''леворекурсивной'' | [[Грамматика]] <math>G</math> называется ''леворекурсивной'' | ||
(соответственно ''праворекурсивной''), если в <math>G</math> имеется | (соответственно ''праворекурсивной''), если в <math>G</math> имеется | ||
хотя бы один леворекурсивный (соответственно | хотя бы один леворекурсивный (соответственно | ||
Версия от 13:15, 25 января 2010
Рекурсивный нетерминал (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] имеется хотя бы один леворекурсивный (соответственно праворекурсивный) нетерминал. Грамматика, в которой рекурсивны все нетерминалы, кроме, быть может, начального символа, называется рекурсивной.
Литература
[Ахо-Ульман],
[Касьянов/95]