Exemple de limbaje de programare formale. Software și suport matematic. Limbaje de programare și medii integrate

Din când în când, pe Habré sunt publicate postări și articole traduse dedicate anumitor aspecte ale teoriei limbajelor formale. Printre astfel de publicații (nu vreau să evidențiez lucrări specifice pentru a nu jigni autorii lor), mai ales printre cele dedicate descrierii diverselor instrumente software de procesare a limbajului, există adesea inexactități și confuzii. Autorul înclină să creadă că unul dintre principalele motive care au condus la această stare de fapt nefericită este nivelul insuficient de înțelegere a ideilor care stau la baza teoriei limbajelor formale.

Acest text este conceput ca o introducere populară în teoria limbilor formale și a gramaticilor. Această teorie este considerată (și, trebuie să spun, pe bună dreptate) destul de complexă și confuză. Studenții se plictisesc de obicei la cursuri, iar examenele, în plus, nu trezesc entuziasm. Prin urmare, în știință nu există atât de mulți cercetători la acest subiect. Este suficient să spunem că tot timpul, de la nașterea teoriei gramaticilor formale la mijlocul anilor 50 ai secolului trecut și până în prezent, au fost publicate doar două teze de doctorat în această direcție științifică. Unul dintre ele a fost scris la sfârșitul anilor 60 de Alexei Vladimirovich Gladkiy, al doilea este deja în pragul noului mileniu - de Mati Pentus.

În plus, în cea mai accesibilă formă, sunt descrise două concepte de bază ale teoriei limbilor formale: limbajul formal și gramatica formală. Dacă testul este interesant pentru public, atunci autorul face o promisiune solemnă de a da naștere a mai multor opuse similare.

Limbi formale

Pe scurt, limbajul formal este model matematic limbaj real. Limbajul real este înțeles aici ca un anumit mod de comunicare (comunicare) a subiecților între ei. Pentru comunicare, subiecții folosesc un set finit de semne (simboluri) care sunt pronunțate (scrise) într-o ordine temporală strictă, i.e. formează secvențe liniare. Astfel de secvențe sunt de obicei numite cuvinte sau propoziții. Astfel, doar așa-numitele. functia comunicativa limbaj, care este studiat folosind metode matematice. Alte funcții ale limbii nu sunt studiate aici și, prin urmare, nu sunt luate în considerare.

Pentru a înțelege mai bine cum se învață limbile formale, este mai întâi necesar să înțelegem care sunt caracteristicile metodelor de învățare matematică. Potrivit lui Kolmogorov et., oricare ar fi aplicat, urmează întotdeauna două principii de bază:

1. Generalizare (abstracție). Obiectele de studiu în matematică sunt entități speciale care există doar în matematică și sunt destinate a fi studiate de matematicieni. Obiectele matematice se formează prin generalizarea obiectelor reale. Studiind orice obiect, matematicianul observă doar câteva dintre proprietățile acestuia și este distras de la restul. Deci, obiectul matematic abstract „număr” poate însemna de fapt numărul de gâște dintr-un iaz sau numărul de molecule dintr-o picătură de apă; principalul lucru este că poți vorbi despre gâște și molecule de apă
   vorbim despre agregate. O proprietate importantă rezultă dintr-o astfel de „idealizare” a obiectelor reale: matematica operează adesea cu colecții infinite, în timp ce în realitate astfel de colecții nu există.
2. Rigiditatea raționamentului. În știință, se obișnuiește să se verifice adevărul unuia sau altuia raționament prin compararea rezultatelor lor cu ceea ce există de fapt, de exemplu. efectua experimente. În matematică, acest criteriu de verificare a raționamentului pentru adevăr nu funcționează. Prin urmare, concluziile nu sunt verificate experimental, dar se obișnuiește să se demonstreze validitatea lor printr-un raționament strict care respectă anumite reguli. Aceste argumente sunt numite dovezi, iar dovezile servesc ca singura modalitate de a fundamenta corectitudinea unei anumite afirmații.

Astfel, pentru a studia limbile folosind metode matematice, este necesar mai întâi să extragem din limbă proprietățile sale care par importante pentru învățare, iar apoi aceste proprietăți sunt strict definite. Abstracția astfel obținută va fi numită limbaj formal – model matematic al unui limbaj real. Conținutul unui anumit model matematic depinde de ce proprietăți sunt importante pentru studiu, i.e. ceea ce este planificat în acest moment să evidențieze și să studieze.

La fel de exemplu celebru O astfel de abstractizare matematică poate fi citată ca un model cunoscut sub denumirea disonantă pentru urechea rusă „o pungă de cuvinte”. În acest model, sunt studiate textele în limbaj natural (adică una dintre acele limbi pe care oamenii le folosesc în procesul comunicării de zi cu zi între ei). Obiectul principal al modelului sac de cuvinte este un cuvânt dotat cu un singur atribut, frecvența de apariție a acestui cuvânt în text original. Modelul nu ține cont de modul în care cuvintele sunt așezate unul lângă altul, ci doar de câte ori apare fiecare cuvânt în text. Punga de cuvinte este folosită în învățarea automată bazată pe text ca unul dintre principalele obiecte de studiu.

Dar în teoria limbajelor formale, pare important să studiem legile aranjare a cuvintelor unul lângă celălalt, adică. proprietățile sintactice ale textelor. Pentru asta, modelul sac de cuvinte arată sărac. Prin urmare, un limbaj formal este definit ca un set de secvențe compuse din elemente ale unui alfabet finit. Să definim asta mai strict.

Alfabetul este un set finit nevid de elemente. Aceste elemente vor fi numite simboluri. Pentru a desemna alfabetul, vom folosi de obicei V-ul latin, iar pentru a desemna simbolurile alfabetului, vom folosi literele mici inițiale ale alfabetului latin. De exemplu, expresia V = (a,b) denotă un alfabet format din două caractere a și b.

Un șir este o secvență finită de caractere. De exemplu, abc este un șir de trei caractere. Adesea, atunci când se desemnează lanțuri în simboluri, sunt utilizați indici. Lanțurile în sine sunt desemnate cu litere mici ale sfârșitului alfabetului grecesc. De exemplu, omega = a1...an este un șir de n caractere. Lanțul poate fi gol, adică nu contine niciun caracter. Astfel de lanțuri vor fi notate cu litera greacă epsilon.

În cele din urmă, un limbaj formal L peste un alfabet V este un set arbitrar de șiruri compuse din simboluri ale alfabetului V. Arbitrarul înseamnă aici faptul că limbajul poate fi gol, adică. nu au un singur lanț, și infinit, adică. alcătuit dintr-un număr infinit de lanţuri. Ultimul fapt este adesea derutant: există limbi reale care conțin un număr infinit de șiruri? În general, totul în natură este finit. Dar aici folosim infinitul ca posibilitate de a forma lanțuri de lungime nelimitată. De exemplu, un limbaj care constă din posibilele nume de variabile ale limbajului de programare C++ este infinit. La urma urmei, numele variabilelor în C++ nu sunt limitate în lungime, așa că poate exista un număr infinit de astfel de nume. În realitate, desigur, numele lungi de variabile nu prea au sens pentru noi. la sfârșitul citirii unui astfel de nume, uiți deja începutul lui. Dar ca posibilitate potențială de a seta variabile de lungime nelimitată, această proprietate pare utilă.

Deci, limbajele formale sunt pur și simplu seturi de șiruri formate din simboluri ale unui alfabet finit. Dar se pune întrebarea: cum se poate defini un limbaj formal? Dacă limbajul este finit, atunci se pot scrie pur și simplu toate lanțurile sale unul după altul (desigur, s-ar putea întreba dacă are sens să scrieți lanțurile unui limbaj care are cel puțin zece mii de elemente și, în general, este are rost să-l scrii?). Ce să faci dacă limbajul este infinit, cum să o definești? Aici intervine gramatica.

Gramaticile formale

Modul de specificare a unei limbi se numește gramatica acelei limbi. Astfel, numim gramatică orice modalitate de a specifica o limbă. De exemplu, gramatica L = (a^nb^n) (aici n este numar natural) definește un limbaj L format din șiruri de caractere de forma ab, aabb, aaabbb etc. Limbajul L este un set infinit de șiruri, dar, cu toate acestea, gramatica (descrierea) sa constă din doar 10 caractere, adică. finit.

Scopul gramaticii este sarcina limbajului. Această sarcină trebuie să fie neapărat finală, altfel persoana nu va putea înțelege această gramatică. Dar cum descrie sarcina finală colecții infinite? Acest lucru este posibil numai dacă structura tuturor lanțurilor limbajului se bazează pe principii uniforme, dintre care există un număr finit. În exemplul de mai sus, următorul principiu acționează ca un astfel de principiu: „fiecare șir al limbii începe cu caracterele a, urmate de același număr de caractere b”. Dacă o limbă este o colecție infinită de lanțuri tipizate aleatoriu, a căror structură nu se supune unor principii uniforme, atunci este evident imposibil să inventezi o gramatică pentru o astfel de limbă. Și iată o altă întrebare, dacă o astfel de colecție poate fi considerată sau nu o limbă. În scopul rigurozității matematice și al uniformității abordării, astfel de colecții sunt de obicei considerate un limbaj.

Deci, gramatica unei limbi descrie legile structura interna lanțurile lui. Astfel de legi sunt de obicei numite legi sintactice. Astfel, se poate reformula definiția gramaticii ca modalitate finală de descriere a modelelor sintactice ale unei limbi. Pentru practică, nu doar gramaticile sunt interesante, ci și gramaticile care pot fi stabilite în cadrul unei singure abordări (formalism sau paradigmă). Cu alte cuvinte, pe baza unei singure limbi (metalimbaj) pentru descrierea gramaticilor tuturor limbilor formale. Apoi poți veni cu un algoritm pentru un computer care să ia ca intrare o descriere a gramaticii făcute în acest metalimbaj și să facă ceva cu lanțurile limbajului.

Astfel de paradigme pentru descrierea gramaticilor se numesc teorii sintactice. Gramatica formală este un model matematic de gramatică descris în cadrul unui fel de teorie sintactică. Există destul de multe astfel de teorii. Cel mai cunoscut metalimbaj pentru specificarea gramaticilor este, desigur, gramaticile generative ale lui Chomsky. Dar există și alte formalisme. Una dintre acestea, gramaticile de cartier, va fi descrisă mai jos.

Din punct de vedere algoritmic, gramaticile pot fi subdivizate în funcție de modul în care este specificată limba. Există trei astfel de moduri principale (tipuri de gramatică):

• Recunoașterea gramaticilor. Astfel de gramatici sunt dispozitive (algoritmi) cărora le este dat un lanț de limbi ca intrare, iar la ieșire dispozitivul afișează „Da” dacă lanțul aparține limbii și „Nu” în caz contrar.
• Generarea gramaticilor. Acest tip de dispozitiv este folosit pentru a genera lanțuri de limbi la cerere. Figurat vorbind, atunci când un buton este apăsat, se va genera un lanț de limbi.
• Gramaticile enumerative. Astfel de gramatici imprimă toate lanțurile limbii unul după altul. Evident, dacă o limbă constă dintr-un număr infinit de lanțuri, atunci procesul de enumerare nu se va opri niciodată. Deși, desigur, poate fi oprit forțat la momentul potrivit, de exemplu, atunci când este imprimat lanțul dorit.

O întrebare interesantă este despre transformarea tipurilor gramaticale unele în altele. Este posibil, având o gramatică generativă, să construim, să zicem, una enumerativă? Răspunsul este da, poți. Pentru a face acest lucru, este suficient să generați lanțuri, ordonându-le, să zicem, după lungimea și ordinea caracterelor. Dar în cazul general, este imposibil să transformi o gramatică enumeratoare într-una de recunoaștere. Puteți folosi următoarea metodă. După ce ați primit un lanț ca intrare, începeți procesul de enumerare a lanțurilor și așteptați dacă gramatica de enumerare tipărește acest lanț sau nu. Dacă un astfel de lanț este tipărit, atunci terminăm procesul de enumerare și tipărim „Da”. Dacă șirul aparține unei limbi, atunci cu siguranță va fi tipărit și astfel recunoscut. Dar, dacă lanțul nu aparține limbii, atunci procesul de recunoaștere va continua la nesfârșit. Recunoașterea gramaticală va fi buclă. În acest sens, puterea de a recunoaște gramatici este mai mică decât puterea generatorilor și enumeratorilor. Acest lucru ar trebui să fie reținut atunci când se compară gramaticile generative ale lui Chomsky și mașinile de recunoaștere ale lui Turing.

Gramaticile de vecinătate

La mijlocul anilor '60, matematicianul sovietic Yuliy Anatolyevich Shreider a propus o modalitate simplă de a descrie sintaxa limbilor bazată pe așa-numita. gramaticile de cartier. Pentru fiecare caracter al limbii, este specificat un număr finit al „vecinătăților” sale - lanțuri care conțin acest caracter (centrul cartierului) undeva în interior. Un set de astfel de vecinătăți pentru fiecare caracter al alfabetului unei limbi se numește gramatică de vecinătate. Un lanț este considerat a aparține limbajului definit de gramatica vecinătății dacă fiecare simbol al acestui lanț este inclus în el împreună cu o parte din vecinătatea sa.

Ca exemplu, luăm în considerare limbajul A = (a+a, a+a+a, a+a+a+a,...) . Acest limbaj este cel mai simplu model limbajul expresiilor aritmetice, unde simbolul „a” joacă rolul numerelor, iar simbolul „+” joacă rolul operațiilor. Să compunem o gramatică de vecinătate pentru această limbă. Să setăm vecinătatea pentru simbolul „a”. Caracterul „a” poate apărea în șirurile de limbaj A în trei contexte sintactice: la început, între două caractere „+” și la sfârșit. Pentru a indica începutul și sfârșitul lanțului, introducem pseudo-simbolul „#”. Atunci vecinătățile simbolului „a” vor fi următoarele: #a+, +a+, +a# . De obicei, pentru a evidenția centrul cartierului, acest simbol din lanț este subliniat (la urma urmei, în lanț pot exista și alte astfel de simboluri care să nu fie centrul!), Nu vom face acest lucru aici din lipsa unui simplu tehnic. posibilitate. Caracterul „+” apare doar între două caractere „a”, deci i se dă o singură vecinătate, șirul a+a .

Luați în considerare lanțul a+a+a și verificați dacă aparține limbajului. Primul caracter „a” al lanțului intră în el împreună cu cartierul #a+ . Al doilea caracter „+” intră în lanț împreună cu vecinătatea a+a . O apariție similară poate fi verificată pentru restul caracterelor din șir, de ex. acest lanț aparține limbii, așa cum ne-am aștepta. Dar, de exemplu, șirul a+aa nu aparține limbajului A, deoarece ultimul și penultimul caracter „a” nu au vecinătăți cu care să fie incluse în acest șir.

Nu orice limbă poate fi descrisă de o gramatică de vecinătate. Luați în considerare, de exemplu, limba B, ale cărei șiruri încep fie cu caracterul „0”, fie cu caracterul „1”. În acest din urmă caz, caracterele „a” și „b” pot merge mai departe în lanț. Dacă lanțul începe de la zero, atunci doar caracterele „a” pot merge mai departe. Nu este greu de demonstrat că nu poate fi inventată nicio gramatică de cartier pentru această limbă. Legitimitatea apariției caracterului „b” în lanț se datorează primului său caracter. Pentru orice gramatică de vecinătate care specifică o legătură între caracterele „b” și „1”, se va putea alege un lanț suficient de lung pentru ca orice vecinătate a caracterului „b” să nu ajungă la începutul lanțului. Apoi se va putea substitui caracterul „0” la început și lanțul va aparține limbajului A, care nu corespunde ideilor noastre intuitive despre structura sintactică a lanțurilor acestui limbaj.

Pe de altă parte, este ușor să construiești o mașină de stat care să recunoască acest limbaj. Aceasta înseamnă că clasa de limbi care sunt descrise de gramaticile de vecinătate este mai restrânsă decât clasa de limbi automate. Limbile definite de gramaticile de vecinătate vor fi numite ale lui Schrader. Astfel, în ierarhia limbilor, se poate evidenția clasa limbilor Schrader, care este o subclasă a limbajelor automate.

Putem spune că limbajele lui Schrader definesc o relație sintactică simplă - „a fi aproape” sau relația de prioritate imediată. Relația de precedență îndepărtată (care există evident în limbajul B) nu poate fi specificată de o gramatică de vecinătate. Dar, dacă vizualizăm relațiile sintactice în lanțurile limbii, atunci pentru diagramele de relații în care se transformă astfel de lanțuri, putem veni cu o gramatică de vecinătate.

Secolul 21 este un moment în care deținerea de informații este cel mai important avantaj competitiv în orice domeniu. Cu toate acestea, nu va aduce niciun beneficiu dacă nu este exprimată într-o limbă pe care să o înțeleagă cei cărora le este destinată sau dacă nu există un traducător capabil să transmită sensul său destinatarului.

În prezent, aproximativ 2000 de oameni trăiesc pe pământ. Trăsătura lor distinctivă este, în primul rând, limbajul.

Împreună cu colocvial (natural) omenirea a creat multe limbaje artificiale. Fiecare dintre ele este conceput pentru a rezolva probleme specifice.

Astfel de sisteme de semne includ limbaje formale, dintre care exemple sunt prezentate mai jos.

Definiții

În primul rând, să definim ce este o limbă. Acest cuvânt este înțeles în mod obișnuit ca un sistem de semne care este folosit pentru a stabili comunicații între oameni și cunoștințe.

Baza majorității limbilor artificiale și naturale este alfabetul.

Este un set de caractere folosit pentru a forma cuvinte și fraze.

Limbajul se caracterizează prin:

• setul de caractere folosit;
• reguli pentru alcătuirea „cuvintelor”, „expozițiilor” și „textelor” din acestea;
• un set de reguli (sintactice, pragmatice și semantice) pentru utilizarea constructelor construite.

Caracteristicile limbajelor naturale

După cum am menționat deja, toate limbile sunt împărțite condiționat în artificiale și naturale. Există multe diferențe între ele.

Limbile vorbite sunt naturale. Caracteristicile lor includ, printre altele:

• ambiguitatea majorității cuvintelor;
• existența sinonimelor și a omonimelor;
• prezența mai multor nume pentru același subiect;
• existența excepțiilor de la aproape toate regulile.

Toate aceste caracteristici sunt principalele diferențe dintre sistemele naturale de semne și limbajele formale. Exemple de cuvinte și afirmații ambigue sunt cunoscute tuturor. Deci, cuvântul „eter”, în funcție de context, poate însemna atât substanță, cât și transmisie radio sau televiziune.

Principalele funcții ale limbilor vorbite sunt:

• comunicare;
• activitate cognitivă;
• exprimarea emoțiilor;
• impact asupra interlocutorului (corespondent, dacă vorbim despre corespondență).

Caracteristicile limbajelor artificiale

Limbile artificiale sunt create de oameni în scopuri speciale sau pentru grupuri specifice de oameni.

Una dintre principalele caracteristici ale limbilor artificiale este definirea fără ambiguitate a vocabularului lor, precum și regulile pentru a le da semnificații și a forma expresii.

Limbi și gramatici formale

Un limbaj, fie el natural sau artificial, poate exista doar dacă există un set de reguli specifice. În același timp, ar trebui furnizată o afișare consistentă, compactă și precisă a relațiilor și proprietăților domeniului studiat. Dacă sunt strict formulate, atunci ei spun că limbajul. Limbajele de programare sunt exemple de astfel de sisteme de semne, deși, strict vorbind, ele ocupă mai degrabă o poziție intermediară (vezi mai jos).

Schema de construire a sistemelor de semne formale este următoarea:

• este selectat un alfabet (un set de simboluri inițiale);
• sunt specificate regulile de construire a expresiilor (sintaxei) limbajului.

Scopul aplicatiei

Logice formale, programare etc.) sunt folosite în procesul cercetării științifice. Sunt mai bune decât cele naturale pentru a reprezenta cunoștințele și sunt un mijloc de schimb de informații mai obiectiv și mai precis.

Limbile formale includ toate sistemele cunoscute de matematică și simboluri chimice, cod Morse, notație muzicală etc.

În plus, limbajele formale de programare sunt utilizate pe scară largă. Dezvoltarea lor rapidă a început la mijlocul secolului al XX-lea, în legătură cu apariția tehnologiei informatice.

Limbajul logic formal

În centrul oricărui limbaj de programare se află matematica. Ea, la rândul său, se bazează pe sistemul de semne al logicii formale.

Ca știință, logica a fost creată de Aristotel. De asemenea, a elaborat reguli de transformare a afirmațiilor care păstrează valoarea lor de adevăr, indiferent de conținutul conceptelor incluse în aceste afirmații.

Logica formală se luptă cu „deficiențele” limbajelor naturale asociate cu ambiguitatea unor enunțuri etc. În acest scop, operațiunile cu gânduri sunt înlocuite cu acțiuni cu semne ale unui limbaj formal. Acest lucru elimină orice incertitudine și vă permite să stabiliți cu exactitate adevărul afirmației.

Caracteristicile limbajelor de programare

După cum sa menționat deja, cu unele rezerve pot fi clasificate ca formale.

Ele sunt unite cu acestea din urmă prin multe reguli sintactice, iar cu cele naturale prin câteva cuvinte cheie și construcții.

Pentru a crea un limbaj de programare, este necesar să se determine setul de simboluri valide și programele corecte ale limbajului și semnificația fiecărui program corect. Dacă prima sarcină poate fi rezolvată prin intermediul formalizării, în cazul celei de-a doua, aceste abordări nu funcționează.

Setul de caractere valide în limbaje de programare sunt caractere care pot fi tastate de la tastatură. Sunt prima parte a tabelului de codificare ASCII.

gramaticile

Limbajul de programare, ca oricare altul, are o gramatică. Acest termen este înțeles ca o descriere a metodei de compilare a propunerilor. Gramaticile sunt descrise în diferite moduri. În cazul limbajelor de programare, acestea sunt reguli care sunt specificate prin perechi ordonate de șiruri de caractere de două tipuri: construcții sintactice definitorii și restricții semantice. La stabilirea gramaticilor, mai întâi ei stabilesc formal regulile de construire a construcțiilor sintactice, iar apoi le stabilesc pe cele semantice într-una dintre limbile naturale.

Regulile sunt scrise în formă grafică prin intermediul unor diagrame speciale. Inițial, această abordare a fost aplicată la crearea limbajului Pascal. Cu toate acestea, apoi a început să fie utilizat pe scară largă în altele.

Clasificarea limbajelor de programare

În acest moment, există câteva mii de ele, împreună cu „dialecte”. Ele sunt clasificate ca procesuale și declarative. În limbile de primul tip, transformarea datelor este specificată prin descrierea secvenței de acțiuni efectuate asupra lor, a doua - prin relații. Există și alte clasificări. De exemplu, limbajele de programare sunt împărțite în funcționale, procedurale, orientate pe obiecte și logice. Dacă abordăm problema cu strictețe, atunci nicio clasificare nu poate fi obiectivă. La urma urmei, o parte semnificativă a limbajelor de programare are capabilitățile sistemelor formale de mai multe tipuri simultan. În timp, marginile se vor estompa și mai mult.

Acum veți putea răspunde la întrebarea: „Ce limbi formale cunoașteți?”. Oamenii de știință continuă să le îmbunătățească, pentru a le face soluție posibilă diverse probleme practice şi teoretice care sunt considerate în prezent de nerezolvat.

LIMBAJE FORMALIZATE (FORTALE).

A INTELEGE

Limbajul formalizat (formal) este un limbaj artificial caracterizat prin reguli precise pentru construirea expresiilor și înțelegerea lor.

Limbajul formal este construit în conformitate cu reguli clare, oferind o afișare consistentă, precisă și compactă a proprietăților și relațiilor domeniului studiat (obiecte modelate).

Spre deosebire de limbajele naturale, limbile formale au reguli clar definite pentru interpretarea semantică și transformarea sintactică a semnelor utilizate, precum și faptul că semnificația și semnificația semnelor nu se schimbă în funcție de circumstanțe pragmatice (de exemplu, pe contextul).

Limbile formale sunt adesea construite pe baza limbajului matematicii.

De-a lungul istoriei dezvoltării matematicii, desemnările simbolice pentru diferite obiecte și concepte au fost utilizate pe scară largă în aceasta. Cu toate acestea, împreună cu desemnările simbolice, matematicienii au folosit liber limbajul natural. Dar, la un anumit stadiu al dezvoltării științei (secolul al XVII-lea), a apărut necesitatea unei analize logice riguroase a judecăților matematice, precum și a clarificării conceptului de „dovadă”, care este important pentru matematică. S-a dovedit că este imposibil să rezolvi aceste probleme fără o formalizare strictă a teoriilor matematice. Era nevoie de a prezenta aceste teorii într-un limbaj formal. Secolul XX poate fi considerat un secol de dezvoltare rapidă a diferitelor limbi formale.

Din punctul de vedere al informaticii, limbajele formale joacă cel mai important rol dintre limbajele formale. limbajul logicii (limbajul algebrei logicii) și limbaje de programare . Ele au, de asemenea, o mare importanță practică.

Toate limbajele formale sunt constructe create de cineva. Cele mai multe dintre ele sunt construite după următoarea schemă.

În primul rând, alege alfabet , sau un set de caractere sursă din care vor fi construite toate expresiile limbajului. Apoi este descris sintaxă limbajul, adică regulile de construire a expresiilor cu sens.

Deoarece conceptul de „simbol” are o încărcătură semantică cu mai multe valori pentru semnele alfabetului, termenul „litera” este mai des folosit. Dar trebuie amintit că literele din alfabetul unei limbi formale pot fi litere ale alfabetului limbilor naturale, paranteze și caractere speciale etc.

Din scrisori, după anumite reguli, poți face cuvinte si expresii .

Cea mai simplă regulă este că orice succesiune finită de litere poate fi considerată un cuvânt. De fapt cuvântul este cel mai simplu model de informare(și este, desigur, un obiect constructiv).

EXEMPLUL 1

Una dintre cele mai importante din punctul de vedere al informaticii este alfabetul, format din două litere „0”, „1”. Orice succesiune finită de zerouri și unu este un cuvânt în acest alfabet.

În limbajele logico-matematice, printre expresii există termeni Și formule .

Terme sunt un analog al numelor de obiecte, scopul lor principal este de a desemna un obiect.

Termenii includ în primul rând variabilele subiectului și constantele - expresii care servesc la desemnarea unor obiecte specifice.

Termenii mai complecși sunt construiți din variabile și constante ale subiectului în conformitate cu anumite reguli. De obicei, funcțiile permise în limbă sunt folosite pentru aceasta.

EXEMPLUL 2

În logică, astfel de funcții sunt inversiunea (), conjuncția (), disjuncția (), implicația () etc.

Exemple de termeni în algebră logică:

DAR; AB A; (AC).

În limbaje de programare, operații aritmetice, operații relaționale (,

Exemple de termeni în limbajul de programare Pascal:

DAR; prog_1; ((A1+25)3*B) și (B0)); 2+sqrt(z*sin(b)).

Formule

EXEMPLUL 3

Exemple de formule logice:

(АС)  АС = 1; x((x)(x))

Instrucțiunile programului pot fi numite formule într-un limbaj de programare.

Exemple de „formule” ale limbajului de programare Pascal:

A:= 2+sqrt(Z*sin(B)); dacă F3 atunci scrieți(R) altfel R:=sqr(F);

Expresiile semnificative sunt obținute într-un limbaj formal doar dacă sunt sigure reguli formarea, transformarea și „înțelegerea” termenilor și formulelor. Aceste reguli includ:

regulile de construcție termeni și formule;

reguli de interpretare termeni și formule (aspectul semantic al limbajului);

reguli de inferență

Pentru fiecare limbă formală, setul acestor reguli trebuie definit cu strictețe, iar modificarea oricăreia dintre ele duce cel mai adesea la apariția unei noi varietati (dialect) a acestei limbi.

EXEMPLUL 4

operator Pascal

dacă F3 atunci scrieți(R) altfel R:=sqr(F);

interpretate după următoarele reguli:

variabila F poate fi doar de tip întreg sau real, iar variabila R poate fi doar de tip real. Dacă nu este cazul, atunci instrucțiunea este considerată incorectă din punct de vedere sintactic și nu va fi executată (va fi emis un mesaj de eroare de sintaxă);

variabilele (cei mai simpli termeni) F și R trebuie definite anterior, adică celulele cu aceste nume trebuie să conțină niște valori de tipul corespunzător (pentru unele versiuni de Pascal, această regulă nu este inclusă în sintaxa limbajului. În acest caz, se selectează acea secvență de zerouri și unu, care este conținută în celule cu adrese date și este interpretată ca un număr zecimal);

dacă valoarea expresiei (termen complex „F3”) care urmează cuvântului cheie (rezervat) dacă este „adevărat”, atunci se execută instrucțiunea care urmează cuvântului cheie atunci (valoarea variabilei F este afișată pe ecran); dacă valoarea sa este „falsă”, atunci se execută instrucțiunea de după cuvântul cheie else (se calculează pătratul valorii variabilei F și rezultatul este plasat într-o celulă numită R).

Prezența în sintaxa limbajului formal a regulilor de derivare a termenilor și formulelor vă permite să efectuați transformări izomorfe modele construite pe baza acestui limbaj. Astfel, limbajele formale nu numai că reflectă (reprezintă) unul sau altul set de cunoștințe deja existente, ci sunt mijloace de formalizare aceste cunoştinţe, permiţând prin transformări formale obţinerea de noi cunoştinţe. Mai mult decât atât, întrucât transformările pot avea loc numai după reguli formale stricte, construirea unor modele izomorfe celui dat, dar care oferă noi cunoștințe, poate fi automatizate. Această caracteristică este utilizată pe scară largă în bazele de cunoștințe informatice, în sistem expert, în sistemele de sprijinire a deciziei.

Limbile formale sunt utilizate pe scară largă în știință și tehnologie. În curs cercetare științificăȘi activitati practice limbajele formale sunt de obicei folosite în strânsă asociere cu limbajul natural, deoarece acesta din urmă are o putere expresivă mult mai mare. În același timp, un limbaj formal este un mijloc de reprezentare mai exactă a cunoștințelor decât un limbaj natural și, în consecință, un mijloc de schimb de informații mai precis și mai obiectiv între oameni.

CUNOAȘTE

Limbajul formalizat (formal) este un limbaj artificial caracterizat prin reguli precise pentru construirea expresiilor și interpretarea (înțelegerea) a acestora.

Când construim un limbaj formal, se alege alfabet , și este descris sintaxă limba.

Alfabet- un set de caractere inițiale din care vor fi construite toate expresiile limbajului.

Expresii limbajul formal sunt termeni și formule.

Scop principal terma - desemnează un obiect.

Cei mai simpli termeni sunt variabilele și constantele subiectului - expresii care servesc la desemnarea unor obiecte specifice.

Termenii compuși sunt construiți după anumite reguli prin aplicarea funcțiilor permise în limbaj la termeni simpli.

Formule sunt formate din termeni cărora li se aplică operatorii admiși în limbă.

Sintaxă limbajul - un set de reguli pentru construirea de expresii semnificative - include:

regulile de construcție termeni și formule;

reguli de interpretare termeni și formule;

reguli de inferență unele formule și termeni din alte formule și termeni.

Limbi formale precum limbajul logicii Și limbaje de programare .

Limbile formale sunt utilizate pe scară largă în știință și tehnologie. Ele sunt un mijloc de schimb de informații mai precis și mai obiectiv între oameni decât limbajul natural.

Limbile formale nu numai că reflectă (reprezintă) unul sau altul set de cunoștințe deja existente, ci sunt un mijloc de oficializare a acestor cunoștințe, ceea ce face posibilă obținerea de noi cunoștințe prin transformări formale. Această posibilitate este utilizată pe scară largă în bazele de cunoștințe informatice, în sistemele expert, în sistemele de suport decizional.

A FI CAPABIL SĂ

EXERCITIUL 1

Enumerați din ce litere este format alfabetul limbajului de programare pe care îl cunoașteți și ce reguli există pentru formarea termenilor simpli în acest limbaj.

Dacă există cuvinte rezervate în acest limbaj de programare? Dacă da, vă rugăm să furnizați exemple de cuvinte rezervate și nerezervate.

Ce în limbajele de programare poate fi considerat termeni și formule?

RĂSPUNS. Alfabetul unui limbaj de programare include toate simbolurile care pot fi folosite la scrierea programelor.

Termenii limbajului de programare sunt identificatori, precum și expresii construite din identificatori, constante, semne ale operațiilor aritmetice și logice, funcții matematice și alte (definite în limbaj), paranteze.

Formulele unui limbaj de programare sunt operatorii admiși în acesta: intrare, ieșire, atribuire, condițional, buclă etc.

SARCINA 2

Dacă ați studiat elementele de bază ale logicii formale, atunci:

dați exemple când transformarea formală a formulelor logice vă permite să obțineți noi cunoștințe despre obiectele studiate;

interpretați formula: x ((x)  (x)) sau  (A  A) = 1

RĂSPUNS. 2) este legea necontradicției, a cărei esență este: nicio afirmație nu poate fi adevărată și falsă în același timp.

SARCINA 3

Care este alfabetul sistemului numeric zecimal?

Care este regula de bază pentru formarea (înregistrarea) numerelor în acest sistem de numere pozițional?

RĂSPUNS. Alfabet: cifre zecimale, virgulă (sau virgulă) și semne plus și minus. Regula: greutatea unei cifre într-un număr depinde de poziția sa în notația numărului.

SARCINA 4

Cum poate fi interpretat cuvântul din alfabet binar „0100 1001 0100 0110” într-un sistem de programare cunoscut de dvs. (se introduc spații pentru lizibilitate)?

RĂSPUNS. În Pascal, acești doi octeți pot fi interpretați ca un șir de caractere „IF”, ca două numere de tip octet - 73 și 70, ca un număr de tip întreg - 20758 (18758 ???).

SARCINA 5

Interfața grafică a sistemului Windows conține elemente precum pictograme sau pictograme. Putem presupune că acestea sunt incluse în alfabetul limbii interfeței cu utilizatorul a acestui sistem? Justificați răspunsul.

EXTINDEȚI-VĂ PERSPECTIVA

În limbajele formale, ca în nicio alta, rolul semnului, înțeles în sensul larg al cuvântului, este mare. Unele aspecte ale utilizării semnelor au fost luate în considerare de noi mai devreme, dar este logic să vorbim despre asta mai detaliat.

Motivul apariției semnelor este destul de evident: majoritatea obiectelor de cunoaștere și activitate nu sunt disponibile pentru percepție directă în procesul de cunoaștere și prezentare în procesul de comunicare.

Semn(gr.  - semn, lat. transcriere - semeion) este un obiect material care acționează ca reprezentant al unui alt obiect, proprietate sau relație și este folosit pentru a dobândi, stoca, procesa și transmite mesaje (informații). , cunoștințe).

NOTĂ 1. În locul cuvântului „semn”, se folosesc alte concepte în sens similar: „nume”, „termen”, „desemnare”.

Conform definiției unuia dintre creatorii teoriei semnelor (semioticii) C.P. Pierce, semn- acesta este un astfel de element x, care înlocuiește pentru subiect un element y (denotație) după un anumit atribut.

Respectiv, denotație- asta înseamnă acest semn într-o anumită situație.

Denotație oarecare unitate lingvistică abstractă (din latină denoto - desemnez) - un set de obiecte care pot fi numite printr-un semn dat.

NOTA 2. În locul cuvântului „denotație” în logică, se folosesc alte nume (identice, sinonime): cel mai adesea „sens”, „notat”.

La rândul său, fiecare semn definește unele proprietăți ale obiectului pe care îl denotă. Informația pe care o poartă un semn despre ceea ce denotă se numește concept semn (din lat. conceptus - concept).

NOTA 3. Termenul „concept” are sinonime: „sens”, „semnificație semn”.

DE EXEMPLU, în cuvântul „animal” găsim sensul străvechi al cuvântului „stomac” – viață. Animalele diferă nu prin prezența unui stomac, ci prin faptul că sunt în viață, au o viață stomacală. Astfel, conceptul de semn „animal” este conceptul de ființă vie, detonație este orice ființă vie specifică care este înțeleasă într-o situație de semn dată.

Potrivit lui Peirce, toate semnele sunt împărțite în index , simbolic Și simbolic natura relaţiei dintre semnificant şi semnificat.

Raportul indiceluiîntre semnificant și semnificat în semn se bazează pe asemănarea lor actuală, existentă. Această clasă include, de exemplu, cuvinte onomatopeice sau formule structurale compuși chimici. Semnele index sunt asociate cu relația cauzală desemnată (de exemplu, prezența acoperișurilor umede este un semn că a plouat).

Atitudine iconicăîntre semnificant și semnificat este, după C. Pierce, „o simplă generalitate în termenii unei proprietăți”. Semne de copiere (semne iconice) - reproduceri, reproduceri similare cu cea desemnată (de exemplu, fotografii, amprente digitale).

ÎN semn simbolic semnificantul și semnificatul sunt legate „fără a ține seama de vreo legătură reală” (de exemplu, unui obiect i se atribuie o anumită combinație de sunete, litere, cifre, culori, mișcări etc.).

Pentru construcția limbajelor formale, acest tip de semne este important (a se vedea paragraful din primul capitol despre teza principală a formalizării).

NOTA 4 Caracterele simbolice sunt uneori denumite simboluri . Conform ideii remarcabilului filozof rus P.A. Florensky, un simbol este „o ființă care este mai mare decât ea însăși. Simbol- acesta este ceva care este ceva care nu este el însuși, mai mare decât el și totuși se manifestă în esență prin el. De exemplu, creatura mitică grifon, care combină un leu și un vultur, este unul dintre simbolurile lui Isus Hristos.

Se întâmplă adesea ca un semn care a apărut mai întâi ca semn iconic să devină ulterior un semn-simbol.

DE EXEMPLU, litera  din alfabetul fenician se numea „aleph” – un taur (seamănă cu un cap de taur). Atunci ea a fost un semn emblematic. În limba greacă, această literă nu este asociată cu un taur și devine un semn-simbol.

Pe măsură ce simbolismul matematic se dezvoltă, semnele iconice sunt, de asemenea, înlocuite cu simboluri. De exemplu, cifra romană V semăna cu o mână deschisă (cinci degete), în timp ce 5 modern este un simbol.

Semnele denotă respectiv planeta Venus și Marte în astronomie, iar în biologie - feminin și masculin. Aceste semne sunt de origine iconică. Prima dintre ele este o imagine stilizată a unei oglinzi antice, al doilea este un scut cu o suliță.

Denotațiile nu sunt în niciun caz întotdeauna obiecte din viața reală și colecții de astfel de obiecte. Multe exemple de denotații care nu sunt obiecte ale realității sunt cuprinse în cunoscutul basm al lui L. Carol „Alice în Țara Minunilor”. De asemenea, formulează în mod figurat principiul apariției unor astfel de denotații:

„A trăit pentru a trăi (Iepurele de martie – nota autorului), dar pentru a fi ceva ce nu era.” În acest sens, proverbul rus „el a trăit și a fost” nu pare a fi deloc o tautologie.

Structura semnului este descrisă de așa-numitul „triunghi Frege” (după numele remarcabilului logician german, care a făcut multe pentru dezvoltarea teoriei limbajelor formale). În altă terminologie, se numește „triunghi semantic” sau triunghiul lui Ogden și Richards. Ea stabilește o legătură între semn, denotația semnului și conceptul de semn.

Orez. 4.3.1. Triunghi Frege

Cu ajutorul acestui triunghi se pot clarifica o serie de efecte de limbaj cunoscute (situații de semne).

1) Sinonimie- o situație constând în coincidența totală sau parțială a semnificațiilor diferitelor semne:

Orez. 4.3.2. Schema de sinonimie

2) semnele pot avea aceeași denotație, dar au semnificații diferite (identitate denotativă). De exemplu, semnele „păcat 30 °” și „1/2” au aceeași denotație, adică numesc același număr real, dar semnificația acestor semne este diferită:

Orez. 4.3.3. Schema identităţii denotative

3) Polisemie(polisemie) - semnul are mai multe semnificații:

Orez. 4.3.4. Diagrama polisemiei

FAPT INTERESANT

Referință istorică

Primii pași către crearea unui limbaj formal al logicii au fost făcuți în antichitate. Aristotel (384-322 î.Hr.) a introdus variabile cu litere pentru subiecte și predicate ale enunțurilor categorice simple, iar conducătorul școlii stoice Chrysippus (c. 281-208 î.Hr.) și elevii săi - variabile pentru enunțuri în general. În secolul al XVI-lea, R. Descartes (1596-1659) a creat baza limbajului formal modern al matematicii - algebra literelor, iar G. W. Leibniz (1646-1716) a transferat simbolismul lui Descartes în logică. Principalul limbaj al logicii la acea vreme era limbajul natural. Dându-și seama de neajunsurile sintactice și semantice semnificative ale unui limbaj natural (îngreunarea, ambiguitatea și inexactitatea expresiilor, regulile sintactice neclare etc.), Leibniz a formulat teza că, fără crearea unui limbaj artificial special - „calcul universal” - dezvoltarea ulterioară. a logicii este imposibil. Dar numai în sfârşitul XIX-lea secolul, ideea lui Leibniz a fost dezvoltată în studiile lui J. Boole (1815-1864), S. Jevons (1835-1882), E. Schroeder (1841-1902) și alții - a apărut algebra logicii.

Dezvoltarea ulterioară a limbajului logicii este asociată cu numele lui J. Peano (1858-1932) și G. Frege (1848-1925). Peano a introdus o serie de simboluri acceptate în matematica modernă, în special „”, „”, „”, pentru a desemna, respectiv, relațiile de apartenență, unire și intersecție a mulțimilor. Frege a construit un calcul axiomatic de propoziții și predicate, care conținea toate elementele de bază ale calculului logic modern.

Pe baza rezultatelor obținute de Frege și folosind simbolismul Peano modificat, B. Russell (1872-1970) și AN Whitehead (1861-1947) în lucrarea lor comună „Principles of Mathematics” (1913) au formulat principalele prevederi ale limbajul logicii.

În prezent, limbajul logicii își găsește o aplicație importantă în informatică, în dezvoltarea limbajelor de programare, a software-ului de calculator și a diverselor sisteme tehnice.

Apariția limbajelor de programare cade la începutul anilor 50 ai secolului XX. Inițial, programele erau create în limbajul instrucțiunilor mașinii și erau secvențe de coduri binare care erau introduse din consolă într-un computer pentru execuție.

Primul pas în dezvoltarea limbajelor de programare a fost introducerea desemnărilor mnemonice (mnemonice - memorie) pentru comenzi și date și crearea unui program de mașină care traduce aceste denumiri mnemonice în coduri de mașină. Un astfel de program, și odată cu el sistemul de notație, a fost numit asamblator .

Fiecare tip de mașină avea propriul său asamblator, iar transferul programelor de la mașină la mașină era o procedură foarte laborioasă. Prin urmare, a apărut ideea de a crea un limbaj independent de mașină. Astfel de limbi au început să apară la mijlocul anilor 1950, iar programul care a tradus propozițiile acestei limbi în limbajul mașinii a devenit cunoscut sub numele de traducător .

Există câteva mii de limbaje de programare și dialectele lor (soiurile). Ele pot fi clasificate în diferite moduri. Unii autori împart întreaga varietate de limbaje de programare în limbaje procedurale și declarative. În limbajele procedurale, transformarea datelor este specificată prin descrierea secvenței de acțiuni asupra acestora. În limbajele declarative, transformarea datelor este specificată în primul rând prin descrierea relației dintre datele în sine. Conform unei alte clasificări, limbajele de programare pot fi împărțite în procedurale, funcționale, logice, orientate pe obiecte. Cu toate acestea, orice clasificare este oarecum arbitrară, deoarece, de regulă, majoritatea limbajelor de programare includ caracteristicile limbilor tipuri diferite.

Un loc aparte printre limbajele de programare îl ocupă limbajele care asigură funcționarea sistemelor de management al bazelor de date (DBMS). Adesea, în ele se disting două subsisteme: un limbaj de descriere a datelor și un limbaj de manipulare a datelor (un alt nume este limbajul de interogare).

Programarea este o întreagă știință care vă permite să creați programe de calculator. Include un număr mare de operații și algoritmi diferiți care formează un singur limbaj de programare. Deci, ce este și care sunt limbajele de programare? Articolul oferă răspunsuri, precum și o listă generală a limbajelor de programare.

Istoria apariției și schimbării limbajelor de programare ar trebui studiată împreună cu istoria dezvoltării tehnologiei computerelor, deoarece aceste concepte sunt direct legate. Fără limbaje de programare, ar fi imposibil să se creeze vreun program pentru funcționarea unui computer, ceea ce înseamnă că crearea computerelor ar deveni un exercițiu fără sens.

Primul limbaj de mașină a fost inventat în 1941 de Konrad Zuse, care este inventatorul motorului analitic. Puțin mai târziu, în 1943, Howard Aiken a creat mașina Mark-1, capabilă să citească instrucțiuni la nivelul codului mașinii.

În anii 1950, a existat o cerere activă pentru dezvoltarea de software, iar limbajul mașinii nu putea rezista la cantități mari de cod, așa că a fost creat un nou mod de a comunica cu computerele. „Assembler” este primul limbaj mnemonic care înlocuiește instrucțiunile mașinii. De-a lungul anilor, lista limbajelor de programare este doar în creștere, deoarece domeniul de aplicare al tehnologiei computerelor devine din ce în ce mai extins.

Clasificarea limbajelor de programare

În acest moment există peste 300 de limbaje de programare. Fiecare dintre ele are propriile caracteristici și este potrivit pentru o anumită sarcină. Toate limbajele de programare pot fi împărțite în mai multe grupuri:

• Orientat pe aspect (ideea principală este separarea funcționalității pentru a crește eficiența modulelor de program).
• Structural (pe baza ideii de a crea o structură ierarhică a blocurilor individuale ale programului).
• Logic (bazat pe teoria aparatului logicii matematice și a regulilor de rezoluție).
• Orientat pe obiecte (în astfel de programare nu se mai folosesc algoritmi, ci obiecte care aparțin unei anumite clase).
• Multi-paradigmă (combină mai multe paradigme, iar programatorul însuși decide ce limbaj să folosească în acest sau acel caz).
• Funcțional (elementele principale sunt funcții care își schimbă valoarea în funcție de rezultatele calculelor datelor inițiale).

Programare pentru incepatori

Mulți oameni se întreabă ce este programarea? Practic, este o modalitate de a comunica cu un computer. Datorită limbajelor de programare, putem seta sarcini specifice pentru diverse dispozitive prin crearea de aplicații sau programe speciale. Când studiezi această știință pe stadiul inițial cel mai important lucru este să alegi limbaje de programare potrivite (interesante pentru tine). Lista pentru începători este mai jos:

• Basic a fost inventat în 1964, aparține familiei de limbaje de nivel înalt și este folosit pentru a scrie programe de aplicație.
• Python („Python”) este destul de ușor de învățat datorită sintaxei sale simple și lizibile, dar avantajul este că poate fi folosit atât pentru a crea programe obișnuite desktop, cât și aplicații web.
• Pascal ("Pascal") - una dintre cele mai vechi limbi (1969) creată pentru predarea studenților. Modificarea sa modernă are o tastare și o structură stricte, dar „Pascal” este un limbaj complet logic, care este de înțeles la nivel intuitiv.

Nu este lista plina limbaje de programare pentru începători. Există un număr mare de sintaxe care sunt ușor de înțeles și cu siguranță vor fi solicitate în următorii ani. Fiecare are dreptul să aleagă independent direcția care va fi interesantă pentru el.

Începătorii au ocazia să accelereze învățarea programării și a elementelor sale de bază datorită instrumentelor speciale. Asistentul principal este mediul de dezvoltare integrat Visual Basic pentru programe și aplicații („Visual Basic” este, de asemenea, un limbaj de programare care a moștenit stilul limbajului Basic din anii 1970).

Nivelurile limbajului de programare

Toate limbajele formalizate concepute pentru a crea, descrie programe și algoritmi pentru rezolvarea problemelor pe computere sunt împărțite în două categorii principale: limbaje de programare de nivel scăzut (lista este prezentată mai jos) și cele de nivel înalt. Să vorbim despre fiecare dintre ele separat.

Limbile de nivel scăzut sunt concepute pentru a crea instrucțiuni de mașină pentru procesoare. Principalul lor avantaj este că folosesc notația mnemonică, adică în loc de o secvență de zerouri și unu (din sistemul de numere binar), computerul își amintește un cuvânt abreviat semnificativ din în limba engleză. Cele mai cunoscute limbi de nivel scăzut sunt „Assembler” (există mai multe subspecii ale acestui limbaj, fiecare dintre ele având multe în comun, dar diferă doar printr-un set de directive și macrocomenzi suplimentare), CIL (disponibil în .Net platformă) și JAVA Bytecode.

Limbaje de programare la nivel înalt: listă

Limbile de nivel înalt sunt concepute pentru confortul și eficiența aplicațiilor, sunt exact opusul limbilor de nivel scăzut. Trăsătura lor distinctivă este prezența construcțiilor semantice care descriu concis și pe scurt structurile și algoritmii programelor. În limbile de nivel scăzut, descrierea lor în codul mașinii ar fi prea lungă și de neînțeles. Limbile de nivel înalt, pe de altă parte, sunt independente de platformă. În schimb, compilatorii îndeplinesc funcția de traducător: traduc textul programului în instrucțiuni elementare ale mașinii.

Următoarea listă de limbaje de programare: C ("C"), C # ("C-sharp"), "Fortran", "Pascal", Java ("Java") - se numără printre cele mai utilizate sintaxe de nivel înalt. Are următoarele proprietăți: aceste limbaje funcționează cu structuri complexe, acceptă tipuri de date șir și operațiuni de I/O pe fișiere și au, de asemenea, avantajul de a fi mult mai ușor de lucrat datorită lizibilității și sintaxei inteligibile.

Cele mai utilizate limbaje de programare

În principiu, puteți scrie un program în orice limbă. Întrebarea este, va funcționa eficient și fără greșeală? De aceea ar trebui alese cele mai potrivite limbaje de programare pentru rezolvarea diferitelor probleme. Lista de popularitate poate fi rezumată după cum urmează:

• Limbaje OOP: Java, C++, Python, PHP, VisualBasic și JavaScript;
• grup de limbaje structurale: Basic, Fortran și Pascal;
• multi-paradigmă: C#, Delphi, Curry și Scala.

Domeniul de aplicare al programelor și aplicațiilor

Alegerea limbii în care este scris acest sau acel program depinde în mare măsură de domeniul de aplicare al acestuia. Deci, de exemplu, pentru a lucra cu hardware-ul computerului în sine (drivere de scriere și programe de suport), cea mai bună opțiune ar fi C ("C") sau C ++, care sunt incluse în principalele limbaje de programare (vezi lista de mai sus). Și pentru dezvoltarea de aplicații mobile, inclusiv jocuri, ar trebui să alegeți Java sau C # ("C-sharp").

Dacă nu v-ați decis încă în ce direcție să lucrați, vă recomandăm să începeți să învățați cu C sau C++. Au o sintaxă foarte clară, o împărțire structurală clară în clase și funcții. În plus, cunoscând C sau C++, puteți învăța cu ușurință orice alt limbaj de programare.

Primul lucru care distinge un limbaj de programare de altul este sintaxa lor. Scopul principal al sintaxei este de a oferi o notație pentru schimbul de informații între programator și traducător. Cu toate acestea, atunci când se dezvoltă detaliile sintaxei, acestea pornesc adesea de la criterii secundare, al căror scop este de a face programul ușor de citit, scris și tradus și, de asemenea, să îl facă fără ambiguitate. Dacă comoditatea citirii și scrierii programelor este necesară pentru utilizatorul unui limbaj de programare, atunci ușurința traducerii și absența discrepanțelor în limbă sunt relevante pentru nevoile traducătorului. Aceste obiective, în general, sunt contradictorii, iar găsirea unui compromis acceptabil în soluționarea lor este una dintre sarcinile centrale în dezvoltarea unui limbaj de programare.

Dezvoltarea unui nou limbaj de programare începe cu definirea sintaxei acestuia. Pentru a descrie sintaxa unui limbaj de programare, la rândul său, este necesară și o anumită clasă. Un limbaj destinat să descrie o altă limbă se numește metalimbaj. Limbajul folosit pentru a descrie sintaxa unei limbi se numește limbaj metasintactic. În limbajele metasintactice se folosește un set special de semne convenționale, care formează notația acestui limbaj.

Din punct de vedere istoric, primul limbaj metasintactic care a fost folosit în practică pentru a descrie sintaxa limbajelor de programare (în special, Algol-60) sunt formele normale Backus, prescurtate ca BNF - forma normală Backus sau forma Backus-Naur. Scopul principal al formularelor Backus este de a prezenta într-o formă concisă și compactă reguli strict formale și lipsite de ambiguitate pentru scrierea principalelor structuri ale limbajului de programare descris.

Definiția formală a sintaxei unui limbaj de programare este de obicei numită gramatică.

Limbi și gramatici formale

Inițial, știința limbilor - lingvistica - s-a redus la studiul limbilor naturale specifice, clasificarea lor, elucidarea asemănărilor și diferențelor dintre ele. Apariția și dezvoltarea metamatematicii, care studiază limbajul matematicii, lucrările privind studiul mijloacelor de comunicare cu animalele și alte cercetări au condus în anii 30 la o înțelegere semnificativ mai largă a limbii, în care limbajul este înțeles ca orice mijloc de comunicare. , constând din:

sistem de semne, adică seturi de secvențe de caractere admisibile;

multe semnificații ale acestui sistem;

corespondența dintre secvențe de caractere și semnificații, ceea ce face posibile secvențe de caractere „înțeles”.

Semnele pot fi litere ale alfabetului, simboluri matematice, sunete etc. Lingvistica matematică ia în considerare numai astfel de sisteme de semne în care semnele sunt simboluri ale unui alfabet, iar secvențele de semne sunt texte, adică. limbile sunt privite ca secvențe arbitrare de texte semnificative. În același timp, regulile care definesc setul de texte formează sintaxa limbii, iar descrierea setului de semnificații și corespondența dintre semnificații și texte formează semantica limbii. Semantica unei limbi depinde de natura obiectelor descrise de limbaj, iar mijloacele de studiu sunt diferite pentru tipuri variate limbi. Sintaxa limbii, după cum sa dovedit, depinde într-o măsură mai mică de scopul limbii și poate fi studiată prin metode care nu depind de conținutul și scopul limbii. Aparatul matematic pentru studierea sintaxei limbilor se numește teoria gramaticilor formale. Din punct de vedere al sintaxei, limbajul nu mai este înțeles ca un mijloc de comunicare, ci ca un ansamblu de obiecte formale - secvențe de caractere alfabetice. Termenul „formal” subliniază faptul că obiectele și operațiunile asupra lor sunt considerate pur formal, fără interpretări semnificative ale obiectelor. Să reproducem principalii termeni și definiții ale acestei teorii.

O literă (sau simbol) este un simplu semn indivizibil; multe litere formează un alfabet. Alfabetele sunt mulțimi și, prin urmare, li se poate aplica notația teoretică a mulțimilor. Un șir este o succesiune ordonată de litere din alfabet. Lanțurile vor fi numite și cuvinte. Setul tuturor lanțurilor (cuvintelor) posibile peste alfabetul A se numește închiderea lui A și este notat cu A*.

Mulțimea A* se numește o iterație a alfabetului A.

Dacă șirurile constau din litere repetate, atunci notația abreviată este folosită pentru a arăta că șirul trebuie considerat ca un produs al literelor alfabetului.

La conversia unor lanțuri în altele, se folosește conceptul de sublanț.

Un set alternativ de termeni pentru o literă, alfabet sau șir (cuvânt) este setul: cuvânt, dicționar și, respectiv, propoziție. Setul de lanțuri (sau propoziții) se numește limbaj. Formal, limba L peste alfabetul A.

Astfel, folosind terminologia de mai sus, limbajul de programare pentru un anumit alfabet A este un astfel de subset al multimii A* care include doar acele propozitii care, datorita informatiilor externe despre semantica lor, sunt considerate semnificative, i.e. satisface sintaxa limbajului de programare.

Definiția de mai sus a unui limbaj formal ca orice subset de A* este generală: nu permite cuiva să evidențieze printre multitudinea de limbi clasele lor individuale care sunt utilizate în practică.

Utilizarea sistematică a metodelor matematice pentru a descrie limbaje de programare începe în anii 1960. Apoi s-a constatat că formele Backus care au fost folosite pentru a descrie sintaxa limbajului ALGOL-60 au o justificare formală strictă folosind mijloacele lingvisticii matematice. Din acel moment, istoria dezvoltării și aplicării aparatului matematic formal - teoria limbajelor și gramaticilor formale - a început pentru proiectarea și construcția traducătorilor.

Forma Backus descrie două clase de obiecte: în primul rând, acestea sunt principalele simboluri ale limbajului de programare și, în al doilea rând, denumirile structurilor limbajului descris, sau așa-numitele variabile metalingvistice.

Definiția formală a gramaticii

Forma Backus-Naur

Gramatica este definită după cum urmează:

VT - set de simboluri terminale (set de simboluri ale alfabetului);

VN - un set de simboluri non-terminale (simboluri care definesc conceptele limbajului

P - set de reguli;

S este simbolul țintă al gramaticii, o axiomă.

Luați în considerare o descriere formală a gramaticii Backus pentru numere zecimale întregi.

G((0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -), (<число>, <цифра>), P,<число>)

P - regulă pentru generarea lexemelor de limbă:

<число> -> [(+,-)]<цифра>[<цифра>]

<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9.

Un element opțional dintr-o regulă este inclus între paranteze drepte [...].

Elementele alternative sunt indicate printr-o listă verticală de opțiuni cuprinse între paranteze (...).

Alternativele opționale sunt indicate printr-o listă verticală de opțiuni cuprinsă între paranteze drepte [...].

Un element care se repetă este indicat de o listă cu un element (închis, dacă este necesar, între paranteze ondulate sau pătrate) urmată de punctele de suspensie obișnuite....

Cuvintele cheie obligatorii sunt subliniate, dar cuvintele opționale nu sunt.

Formele Backus reprezintă o descriere formală a limbajului și ele, în esență, i-au determinat pe cercetători să introducă instrumente matematice pentru descrierea sistemică și cercetarea limbajelor de programare, utilizarea aparatului matematic ca bază pentru analizarea în traducător, care a fost dezvoltat ulterior în diverse metode de analiză bazate pe definiții sintactice formale.

Trebuie remarcat faptul că BNF nu permite descrierea dependențelor de context într-un limbaj de programare. De exemplu, o astfel de limitare a programelor Pascal ca „un identificator nu poate fi declarat de două ori în același bloc” nu poate fi descrisă folosind BNF. Restricțiile de acest fel sunt mai aproape de o altă caracteristică a limbajului - semantica. Prin urmare, aici sunt folosite alte mijloace, numite în general limbaje metasemantice. Cu toate acestea, de regulă, același BNF este nucleul acestor limbi.

O caracteristică a multor formule metalingvistice este prezența recursiunilor în ele, adică. utilizarea structurilor descrise în sine pentru a descrie structurile. Recursiunea poate fi explicită sau implicită. Recursiunea explicită are loc, de exemplu, în regula 2 din lista de mai sus a regulilor de descriere numar decimal. Recursiunea implicită este prezentă în cazul în care o variabilă metallingvistică este utilizată pentru a construi o construcție la un anumit pas, denotând această construcție însăși.

Prezența recursiunilor face dificilă citirea și înțelegerea formulelor metalingvistice, dar aceasta este poate singura modalitate care permite utilizarea unui număr finit de reguli pentru a descrie un limbaj care poate conține un număr infinit de lanțuri de caractere de bază. Limbajele de programare sunt infinite - un număr infinit de programe corecte pot fi scrise pe ele, iar atunci când descrieți sintaxa lor folosind BNF, vor exista întotdeauna recursiuni explicite sau implicite.

În practică, alte limbaje metalingvistice sunt, de asemenea, folosite pentru a descrie sintaxa limbajelor de programare. Unul dintre scopurile utilizării lor este acela de a elimina unele nefirești în reprezentarea BNF a construcțiilor sintactice comune pentru elementele de regulă opționale, alternative și repetate.

Teoria gramaticilor formale se ocupă de descrierea, recunoașterea și prelucrarea limbilor. Vă permite să răspundeți la o serie de întrebări aplicate. De exemplu, pot fi recunoscute rapid și ușor limbile dintr-o anumită clasă Z; dacă limba dată aparține clasei Z; Există algoritmi care să răspundă la întrebări precum: „Aparține șirul a limbii L sau nu?” etc.

În general, există două moduri principale de a descrie clase individuale de limbi:

utilizarea unei proceduri de generare;

folosind o procedură de recunoaștere.

Prima dintre acestea este dată de un set finit de reguli, numite gramatici, care generează exact acele lanțuri care aparțin limbajului L.

Al doilea este cu ajutorul unui dispozitiv abstract de recunoaștere (automat).

La construirea traducătorilor, se folosesc ambele metode: gramatica ca mijloc de descriere a sintaxei limbajului de programare și automatul ca model al algoritmului de recunoaștere a propozițiilor limbajului, care este folosit ca bază pentru construirea limbajului. traducător. În același timp, o gramatică se construiește metodic (și tehnologic), iar apoi, pe baza ei, ca sursă, se construiește un algoritm de recunoaștere.

De remarcat că, deși gramatica generativă descrie procesul de generare a lanțurilor în limbajul L(G), această descriere nu este algoritmică - una dintre principalele proprietăți ale algoritmului lipsește în gramatică - determinism, i.e. ordinea specifică de aplicare a regulilor de substituție gramaticală nu este fixă. Acest lucru asigură compactitatea descrierii limbii. În cazul general, un astfel de algoritm de enumerare poate fi fixat în diferite moduri, dar acest lucru nu este necesar pentru o definire precisă a limbajului.

Astfel, gramatica formală G poate defini un set de algoritmi de generare a limbajului.

Aplicarea practică a gramaticilor este legată de rezolvarea problemei recunoașterii. Problema recunoașterii este rezolvabilă dacă există un algoritm care, într-un număr finit de pași, dă un răspuns la întrebarea dacă un șir arbitrar peste vocabularul principal al gramaticii aparține limbajului generat de această gramatică. Dacă un astfel de algoritm există, atunci limbajul se numește recognoscibil. Dacă, în plus, numărul de pași ai algoritmului de recunoaștere depinde de lungimea lanțului și poate fi estimat, se spune că limbajul este ușor de recunoscut. Altfel, nu are sens să vorbim despre construirea unui traducător pentru un limbaj de programare nerecunoscut. Prin urmare, în practică, astfel de clase particulare de gramatici generative sunt considerate care corespund limbilor recunoscute și, în majoritatea cazurilor, ușor de recunoscut. Cele mai importante clase de astfel de limbi pot fi definite în cadrul clasificării limbilor propusă în 1959 de lingvistul american N. Chomsky (clasificarea Chomsky). El a propus să clasifice limbajele formale în funcție de tipul de reguli ale gramaticilor care le generează:

Clasa 0. Gramatici cu structura sintagmetica. Ele pot servi ca model de limbi naturale. Sunt cele mai complexe, nu au nicio aplicație practică pentru construirea de traducători.

Clasa 1. Gramatici sensibile la context. La construirea propozițiilor, un simbol non-terminal poate fi înlocuit cu altul, ținând cont de context. Pe baza unor astfel de gramatici, se poate realiza traducerea automată dintr-o limbă naturală în alta.

Clasa 2. Gramatici fără context. Înlocuirea unui non-terminal are loc indiferent de context. Gramaticile CS joacă un rol major în studiul formal al sintaxei limbajelor de programare și în construirea unei unități de analiză pentru un traducător.

Clasa 3. Gramatici obișnuite. Limbile din clasa 3 se numesc limbi cu un număr finit de stări sau limbaje automate (regulate), iar gramaticile care le generează se numesc gramaticile automate (A-gramatici). Gramaticile A sunt folosite în principal în stadiul analizei lexicale.

Clasele principale de limbi pot fi definite prin clase de recunoaștere abstracte (automate), care formează și ierarhia corespunzătoare.

Dintre cele patru clase de gramatici, gramaticile fără context sunt cele mai importante atunci când sunt aplicate limbajelor de programare. Cu ajutorul lor, puteți defini o parte mare, deși nu toată, a structurii sintactice a unui limbaj de programare.

În funcție de tipurile de gramatică, limbile sunt împărțite în 4 tipuri:

<тип 0>- limbi cu structură de frază. Toate limbile naturale aparțin acestui tip.

<тип 1>- limbaje sensibile la context. Limbile și gramaticile sunt folosite în analiza și traducerea textelor în limbile naturale. Pe baza unor astfel de gramatici, se poate realiza traducerea automată dintr-o limbă naturală în alta.

<тип 2>- limbi fără context. Limbajele fără context stau la baza construcțiilor sintactice limbile moderne programare.

<тип 3>- limbi obișnuite. Sunt cele mai comune și utilizate pe scară largă în domeniul proiectării sistemelor informatice. Pentru a lucra cu ele, se folosesc seturi regulate, expresii regulate și automate finite.

Concluzie: depinde de tipul de clasificare al limbii, cu ajutorul cărei gramatică se poate construi o propoziție a limbii, cum se recunoaște propoziția.

Pentru multe limbaje de programare, există instrucțiuni special formulate care vă permit să verificați dacă limbajul aparține tipului specificat. Astfel de afirmații se numesc leme.

Automatele finite folosesc memoria și procesează o secvență de caractere de intrare care aparțineau unui set finit. Matematic, mașina de stări este descrisă după cum urmează:

unde V=() - alfabet de intrare;

Q=() - alfabetul stărilor;

funcția de tranziție;

Starea inițială a automatului;

F este starea finală a automatului;

Automatul finit poate fi reprezentat condiționat prin următoarea diagramă (Figura 2.1).

Figura 2.1 - Schema simplificată a mașinii de stări

Unitatea de control (CU) poate citi secvențial caractere, deplasându-se de la stânga la dreapta. Dispozitivul de control poate fi în diferite stări: începerea lucrului: ; la sfârşitul lui F. Trecerea de la stare la stare se realizează în conformitate cu funcţia de tranziţie. În acest sens, mașina cu stări finite poate fi reprezentată după cum urmează:

Această comandă înseamnă că mașina de stări este într-o stare, citește un caracter și intră în stare.

Deci mașina de stat este un recunoaștetor de limbă.

Sarcina analizei este, pe baza gramaticii existente (este cunoscut limbajul de programare), de a construi un dispozitiv de recunoaștere pentru acest limbaj.

Recunoaștetorii pot fi clasificați în funcție de tipul componentelor lor constitutive:

Cititor;

Dispozitive de gestionare a memoriei.

În funcție de tipurile de cititor, dispozitivele de recunoaștere pot fi unilaterale și cu două fețe. Recunoașterea unidirecțională permite cititorului să se miște atunci când citește caracterele introduse într-o singură direcție. Dispozitivele de recunoaștere cu două fețe permit mișcarea în ambele direcții.

În funcție de tipul dispozitivelor de control, recunoașterii sunt:

determinat;

Nedeterminist.

Recunoașterea este deterministă dacă la fiecare pas al activității sale există o configurație unică la care recunoașterea va merge la pasul următor.

În funcție de tipurile de memorie, recunoaștetorii sunt:

1) fără memorie;

2) cu memorie limitată;

3) cu memorie nelimitată.

O modalitate de a descrie un algoritm de recunoaștere a limbii este de a specifica un dispozitiv de recunoaștere.

Pentru dispozitivele fără context, aceste dispozitive sunt automate push-pull.

Memoria push-pull este organizată pe baza primului intrat, ultimul ieșit.

Procesul de traducere a unui program sursă într-un program obiect este de obicei împărțit în mai multe subprocese (faze). Principalele etape ale traducerii sunt:

1) analiza lexicală;

2) analizarea;

3) analiza semantică;

4) sinteza unui program obiect.