Принцип рекурсии в правилах грамматики

Особенности формальных грамматик в том, что они позволяют определить бесконечное множество цепочек языка с помощью конечного набора правил. Приведенная выше в примере грамматика для целых десятичных чисел со знаком определяет бесконечное множество целых чисел с помощью 15 правил.

Возможность пользоваться конечным набором правил достигается в такой форме записи грамматики за счет рекурсивных правил. Рекурсия в правилах грамматики выражается в том, что один из нетерминальных символов определяется сам через себя. Рекурсия может быть явной (непосредственной) - тогда символ определяется сам через себя в одном правиле, либо неявной (косвенной) – тогда то же самое происходит через цепочку правил.

В рассмотренной выше грамматике G непосредственная рекурсия присутствует в правиле: <ч>→<ч><ц>, а в эквивалентной ей грамматике G’- в правиле: T→TF.

Чтобы рекурсия не была бесконечной, для участвующего в ней нетерминального символа грамматики должны существовать также и другие правила, которые определяют его, не через самого себя, и позволяют избежать бесконечного рекурсивного определения (в противном случае этот символ в грамматике был бы просто не нужен). Такими правилами являются <ч>→<ц> - в грамматике G и T→F - в грамматике G’.

Смысл рекурсии можно пояснить, обращаясь к семантике языка, – в рассмотренном выше примере это язык целых десятичных чисел со знаком. Число – это любая цифра сама по себе. Любые две цифры – это тоже число, затем – три цифры и т. д. Если строить определение числа таким методом, то оно никогда не будет закончено (в математике разрядность числа ничем не ограничена). Однако можно заметить, что каждый раз, порождая новое число, мы просто дописываем цифру справа к уже написанному ряду цифр. А этот ряд цифр, начиная от одной цифры, тоже в свою очередь является числом. Тогда определение для понятия “число” можно построить таким образом: “число – это любая цифра, либо другое число, к которому справа дописана любая цифра”. Именно это и составляет основу правил грамматик G и G’ и отражено во второй строке правил в правилах < ч>®< ц>|< ч>< ц> и T ® F | TF. Другие правила в этих грамматиках позволяют добавить к числу знак (первая строка правил) и дают определение понятию “цифра” (третья строка правил).

Принцип рекурсии – важное понятие в представлении о формальных грамматиках. Явно или не явно рекурсия всегда присутствует в грамматиках любых реальных языков программирования. Именно она позволяет строить бесконечное множество цепочек языка, и говорить об их порождении невозможно без понимания принципов рекурсии. Как правило, в грамматике реального языка программирования содержится не одно, а целое множество правил, построенных с помощью рекурсии.

Дата добавления: 2014-12-27