MAI MULTE MATERIALE PE TEMA:
Particularitatea gramaticilor formale de mai sus este faptul că acestea vă permit să definiți un număr infinit de lanțuri de limbaj folosind un set finit de reguli (desigur, multe șiruri de limbi străine poate fi, de asemenea, la sfârșitul anului, dar chiar și pentru limbaj foarte simplu, această condiție nu este de obicei efectuată). Cele de mai sus în exemplul gramaticii pentru intreg zecimal cu semn definește un set infinit de numere întregi cu 15 reguli.
În această formă de scriere gramatică, abilitatea de a utiliza un set finit de reguli se realizează prin reguli recursive. Recurgerea la regulile de gramatică este exprimată prin faptul că unul dintre simbolurile nonterminale este determinat de unul singur. Recurgerea poate fi imediată (explicită) - atunci simbolul este determinat de unul singur într-o singură regulă sau indirect (implicit) - același lucru se întâmplă prin lanțul de reguli.
În gramatica G considerată mai sus, recursiunea directă este prezentă în regula: <чс> ® <чс><цифра>, și în gramatica echivalentă G '- în regula T ® TF.
Pentru a recursie nu a fost infinit, pentru participarea la aceasta gramatica neterminal ar trebui să existe, de asemenea, alte reguli pe care le definesc, trecându-l cel mai mult, și pentru a evita definiția recursiv infinit (altfel acest simbol în gramatica ar fi pur și simplu nu este necesar). Asemenea reguli sunt <чс> ® <цифра> - în gramatica G și T ® F - în gramatica G '.
În teoria limbilor formale, nu se mai poate spune nimic despre recurs. Dar, pentru a înțelege pe deplin semnificația recursului, puteți recurge la semantica limbii - în exemplul de mai sus, aceasta este limba numerelor întregi zecimale cu un semn. Luați în considerare sensul său.
Dacă încercați să definiți ce este un număr, atunci puteți începe cu faptul că orice număr în sine este un număr. Apoi, puteți vedea că orice două cifre - acesta este de asemenea un număr, apoi - trei cifre, etc.
Dacă construiți o definiție a unui număr cu această metodă, atunci nu va fi niciodată finalizată (în matematică, cifrele numărului sunt nelimitate). Cu toate acestea, puteți observa că de fiecare dată, generând un nou număr, pur și simplu adăugăm cifra la dreapta (așa cum scriem de la stânga la dreapta) la numărul deja scris de cifre. Și acest număr de cifre, pornind de la o singură cifră, este, de asemenea, un număr la rândul său. Apoi definiția conceptului de "număr" poate fi construită astfel: "numărul este orice cifră sau alt număr la care orice cifră este adăugată la dreapta". Aceasta este baza regulilor gramatiilor G și G și se reflectă în reguli <чс> ® <цифра> | | <чс><цифра> și T ® P | TF (a doua linie de reguli). Alte reguli din aceste gramatici vă permit să adăugați la număr un semn (primul rând de reguli) și să oferiți o definiție a conceptului de "cifră" (a treia linie de reguli). Ele sunt elementare și nu necesită explicații.
Principiul recursivității (uneori numit "principiul iterației") este un concept important în noțiunea de gramatică formală. Altfel, în mod explicit sau implicit, recursiunea este întotdeauna prezentă în gramatica oricărei limbi de programare reale. Vă permite să construiți un număr infinit de șiruri de limbi și discuția despre generația lor este imposibilă fără a înțelege principiul recursivității. De regulă, gramatica unui limbaj de programare real nu conține una, ci o mulțime de reguli construite folosind recursivitatea.
Trimiteți-le prietenilor: