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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Рекурсивный нетерминал''' (''Recursive nonterminal symbol'') - ''нетерминал'' <math>A</math> ''конт...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 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.

Текущая версия от 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.