ОЩЕ Материали:
Особеността на посочените по-горе формални граматики е, че те ви позволяват да определите безкраен брой вериги език с помощта на ограничен набор от правила (разбира се, много езикови струни могат да бъдат и в края, но дори и за по-лесно недвижими език, това състояние обикновено не се извършва). Най-горе в Пример граматика за знак число със знак определя безкраен набор от числа с 15 правила.
В тази бройна система граматиката може да използва ограничен набор от правила, се постига чрез рекурсивни правила. Рекурсия в граматични правила, изразени в това, че един от символите nonterminal определят чрез себе си. Рекурсия може да бъде директен (изрично) - тогава символът се определя чрез себе си в едно правило, или непряка (косвена) - същото се случва чрез верига от правила.
Граматиката G обсъдено по-горе директно рекурсия присъства в правило: <чс> ® <чс><цифра>, и равностоен граматика G "- в T®TF правило.
За да рекурсия не е безкрайна, за участие в него nonterminal граматика също трябва да съществуват други правила, които го определят, то най-преминаване, и да се избегне безкрайното рекурсивно определение (в противен случай този символ в граматиката би просто не е необходимо). са правилата <чс> ® <цифра> - в граматика G и Т ® F - в граматика G '.
В официалната теория език, какво повече да кажа за рекурсия невъзможно. Но за да се разбере напълно смисъла на рекурсия, можете да прибегнете до езикови семантика - в горния пример е езикът на десетичната число със знак. Помислете за неговото значение.
Ако се опитаме да се дефинира какво е число, а след това можете да започнете с това, че всяко число по себе си е цяло число. Освен това, може да се види, че всеки две числа - също известен брой, а след това - три цифри, и така нататък ..
Ако сте изграждане на определението за такава metodchom, че никога няма да бъде завършен (по математика малко брой не е ограничен). Въпреки това, можете да забележите, че всеки път, когато създавате нов номер, ние просто добавя фигурата вдясно (както се използва да се напише от ляво на дясно), за да са писали поредица от числа. И тази поредица от номера от един номер, също от своя страна, е число. След определението за "множество" концепции могат да бъдат изградени по такъв начин: "броя - е всяка цифра или друг номер, към който всяка фигура десен недовършен". Това е, което е в основата на правилата на граматиката G и G 'е отразено в правилата <чс> ® <цифра> | <чс><цифра> и T ® P | TF (втори ред на правилата). Други правила в тези граматики ви позволи да добавите в броя на знаците (на първия ред на правилата) и да даде определение на понятието "число" (трети ред на правилата). Те са елементарни и не изискват обяснение.
принцип рекурсия (понякога се нарича "принцип на повторение") - важна концепция в представянето на формални граматики. Така iliinache, явно или неявно, рекурсия винаги присъства в някакви реални граматики на езици за програмиране. Това дава възможност да се изгради един безкраен брой на веригите на езика, както и да се говори за тяхното поколение е невъзможно, без да разбират принципа на рекурсия. Като правило, граматиката на един истински език за програмиране не съдържа един, а цял набор от правила, изграден с помощта на рекурсия.