Nevoia de a crea limbi oficiale este asociată cu anumite deficiențe ale limbajului natural, care au apărut atunci când sunt folosite în teoria algoritmilor. Să luăm în considerare unele dintre ele:
1. Dependența modurilor de a construi propozițiile (sintaxa) din semnificația lor (semantică). De exemplu, este necesar să se utilizeze propoziția "Medicul examinat pacientul" sau "Medicul examinat pacientul", în funcție de apartenența medicului la sexul respectiv;
2. Ambiguitatea semantică a propozițiilor. De exemplu, propunerea: "Păstrați bani în bancă", poate însemna stocarea de numerar într-o instituție financiară sau într-o anumită capacitate;
3. Inexactitatea semantică a sentințelor. De exemplu, la propunerea "Ieri era vreme caldă" este imposibil să se determine temperatura aerului, deoarece la diferite momente ale anului temperaturile diferite pot corespunde cu vremea caldă;
4. existența paradoxurilor considerate în secțiunea anterioară.
Un limbaj formal, convenabil pentru teoria algoritmilor, nu ar trebui să aibă aceste dezavantaje. În acest caz, vom folosi o altă limbă (metalimbaj) pentru a descrie o limbă formală (obiect lingvistic), de exemplu, limba rusă.
Regulile pentru construirea cuvintelor din litere și propoziții din cuvintele unui limbaj formal vor fi numite gramatică formală. Pentru a descrie sintaxa unui limbaj formal, folosiți formularul standard propus de lingvistul american și matematicianul Chomsky, care poate fi reprezentat ca:
unde X este alfabetul simbolurilor terminale ale limbii formale;
Y - alfabet auxiliar al simbolurilor nonterminale;
R este setul final de reguli sintactice;
S - simbol auxiliar inițial dintr-un set de simboluri nonterminale (simbolul terminal este cel mai mic element semnificativ al limbii formale).
Fiecare dintre sintactic regula R reprezintă substituția A → B, în care A și B - câteva cuvinte derivate din simbolurile X și Y. alfabetelor Propunerile limbaj formal începe să primească, dacă este cazul simbolului neterminal S permutarea O astfel de substituție R., stânga o parte din care corespunde simbolului neterminal al S, ar trebui să fie în R. Dacă rezultatul conține numai simboluri terminale, aceasta înseamnă că limba de propunere a fost primită. Dacă sunt prezente în rezultate simboluri neterminal cu lanț, atunci vom începe din nou aplicate lanțului de una dintre substituții R, în care oricare dintre ele. Dacă șirul rezultat are mai multe apariții ale lui A, atunci substituția corespunzătoare permite înlocuirea oricăruia dintre aceste apariții ale lui A în B.
Luați în considerare un exemplu de gramatică formală în care X =, Y =, iar sistemul de substituții are forma:
O astfel de gramatică generează un limbaj formal care conține numere binare citite de la stânga la dreapta în același mod ca și de la dreapta la stânga. De exemplu, utilizarea permutărilor 3, 4, 1 va avea ca rezultat numărul 01010; substituții 4, 3, 3, 2 - pentru a obține numărul 1001001, etc.
Forma normală a lui Backus-Naur.
Forma normală a lui Backus-Naur (BNF) este un alt mod de a descrie un limbaj formal.
Pentru a descrie un limbaj formal cu ajutorul BNF vom folosi reguli sintactice (produse) în care vom folosi următoarele simboluri:
1. = este un simbol care separă partea stângă a unui produs care este un simbol nonterminal din partea dreaptă, care este un lanț terminal non-gol al simbolurilor terminal și nonterminal. Simbolul. = citit așa cum este definit prin definiție sau poate conține;
2. | este un separator care se află între diferite forme ale aceluiași concept nonterminal. Caracterul este citit ca sau;
3. <> - S-au folosit unghiulare pentru extragerea unui simbol nonterminal, adică un concept care nu poate apărea în propozițiile limbii descrise și este folosit pentru a descrie aceste propoziții.
Luați în considerare exemple de descriere a cifrelor zecimale și a constantelor unui tip întreg cu ajutorul BNF.
Faptul că 1 este o cifră este exprimat folosind BNF după cum urmează:
Parantezele unghiulare <> sunt folosite pentru a selecta un simbol nonterminal care nu poate apărea în propozițiile limbii formale descrise și este destinat să descrie regula sintactică. Simbolul 1 poate apărea în propozițiile limbii oficiale descrise și este un simbol terminal.
Pentru a arăta simbolul neterminal <цифра> poate fi 0 sau 1, puteți utiliza următoarea regulă de sintaxă:
Astfel, pentru a descrie cifrele zecimale, puteți scrie o regulă:
<цифра>:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.
Constantele de tip întreg pot fi definite recursiv după cum urmează:
- <константа>:: =<цифра>;
- <константа>:: =<константа> <цифра>;
- <цифра>:: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.
Prima dintre reguli citește: <константа> poate consta din <цифры>. A doua regulă prevede: <константа> poate fi alta <константы>, urmat de <цифра>.
Regulile sintactice rezultate formează o gramatică pentru limbă <констант>. Propozițiile acestei limbi sunt secvențe ale simbolurilor terminale care pot fi derivate dintr-un simbol nonterminal <константа>. Să luăm în considerare un exemplu de obținere a unei constante 673 prin utilizarea regulilor sintactice scrise cu ajutorul BNF:
- utilizăm a doua regulă: simbolul nonterminal <константа> înlocuiți cu un lanț <константа> <цифра>;
- folosim a treia regulă: simbolul nonterminal <цифра> înlocuiți cu simbolul terminalului 3;
- noi folosim din nou regula a doua și obținem <константа> <цифра>3;
- utilizăm a treia regulă și obținem <константа> 73;
- folosim prima regulă: simbolul nonterminal <константа> înlocuiți cu simbolul nonterminal <цифра>, rezultatul este un lanț <цифра> 73;
- utilizăm a treia regulă și obținem 673.
BNF și modificările sale sunt în prezent mijloacele standard de descriere a sintaxei limbajelor de programare.
Articole similare
Trimiteți-le prietenilor: