Рекурсивная грамматика - Recursive grammar

В Информатика, а грамматика неофициально называется рекурсивная грамматика если он содержит правила производства которые рекурсивный, что означает, что расширение нетерминала в соответствии с этими правилами может в конечном итоге привести к строке, которая снова включает тот же нетерминал. В противном случае это называется нерекурсивная грамматика.[1]

Например, грамматика для контекстно-свободный язык является леворекурсивный если существует нетерминальный символ А которые можно пропустить через производственные правила, чтобы получить строку с А (как крайний левый символ).[2][3]Все типы грамматик в Иерархия Хомского может быть рекурсивным, и именно рекурсия позволяет создавать бесконечные наборы слов.[1]

Характеристики

Безрекурсивная грамматика может создать только конечный язык; и каждый конечный язык может быть произведен с помощью нерекурсивной грамматики.[1]Например, прямолинейная грамматика производит всего одно слово.

Рекурсивная контекстно-свободная грамматика, не содержащая бесполезные правила обязательно производит бесконечный язык. Это свойство составляет основу алгоритм который может эффективно проверить, дает ли контекстно-свободная грамматика конечный или бесконечный язык.[4]

Рекомендации

  1. ^ а б c Недерхоф, Марк-Ян; Сатта, Джорджио (2002), «Анализ нерекурсивных контекстно-свободных грамматик», Труды 40-го ежегодного собрания Ассоциации компьютерной лингвистики (ACL '02), Страудсбург, Пенсильвания, США: Ассоциация компьютерной лингвистики, стр. 112–119, Дои:10.3115/1073083.1073104.
  2. ^ Примечания по теории формального языка и синтаксическому анализу Джеймс Пауэр, факультет компьютерных наук Ирландского национального университета, Мейнут Мейнут, графство Килдэр, Ирландия.
  3. ^ Мур, Роберт С. (2000), «Удаление левой рекурсии из контекстно-свободных грамматик», Труды 1-го Североамериканского отделения конференции Ассоциации компьютерной лингвистики (NAACL 2000), Страудсбург, Пенсильвания, США: Ассоциация компьютерной лингвистики, стр. 249–255..
  4. ^ Флек, Артур Чарльз (2001), Формальные модели вычислений: крайние пределы вычислений, Серия AMAST в вычислительной технике, 7, World Scientific, теорема 6.3.1, с. 309, г. ISBN  9789810245009.