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