Formal qrammatika — Vikipediya

Bu məqaləni vikiləşdirmək lazımdır. Lütfən, məqaləni ümumvikipediya və redaktə qaydalarına uyğun şəkildə tərtib edin.

Formal qrammatika — dedikdə elə qaydalar sistemi başa düşülür ki, onun vasitəsilə verilmiş formal dilin(yalnız bu dilin) düzgün sözləri qura bilir. Qrammatika vasitəsilə qurulan formal dilin sözlər çoxluğu sonlu, sonsuz, və ya boş çoxluq ola bilər. Qrammatika sözlər çoxluğunu ixtiyari qaydada qura, yaxud müəyyənləşdirə bilər. Beləliklə, qrammatika sözlərin daxili quruluşunun qanunlarını açıqlayır ki, bunlara sintaksis deyilir. Formal qrammatika— müəyyən sintaksis nəzəriyyə çərçivəsində qurulan qrammatik riyazi modeldir.

Alqoritmik nöqteyi-nəzərdən formal qrammatikaların aşağıdakı növləri var:

1. Tanıyan qrammatikalar: Bu qrammatikalar bir növ elə qurğudur ki, bunun girişinə daxil olan söz verilmiş dilə aiddirsə, "hə", aid deyilsə- "yox" çap olunur.
2. Sadalayan qrammatikalar: Bu qrammatikalar verilmiş dilin bütün sözlərini bir-bir çap etməklə(sadalamaqla) iş görür. Aydındır ki, dilin sözlərinin sayı sonsuz olarsa, qrammatika heç zaman dayanmayacaq. Ancaq qrammatikanı məcburi o zaman dayandırmaq olar ki, lazım olan söz çap olunmuşdur.
3. Doğuran qrammatikalar: Bunlar elə "qurğu"dur ki, dilin lazımlı sözlərini qurur. Doğuran qrammatikaların müxtəlif variantlarını ABŞ riyaziyyatçısı və linqivisti Noam Xomski keçən əsrin 50-ci illərindən etibarən yaratmağa başlamışdır. Bir zamanlar hətta bu qrammatikalar təbii dillərin qurulması üçün istifadə oluna bilən kimi fərz olunurdu, lakin zaman bunların təbii dillər sahəsində tətbiqi imkanlarını sübut etmədi. Hazırda doğuran qrammatikalar, əsasən, formal dillərin(proqramlaşdırma dillərinin) sintaksisinin qurulmasında müvəffəqiyyətlə istifadə olunur.

Tərif: Formal doğuran qrammatika dedikdə 4 obyektdən ibarət bir formal G={V, W, I, P} sistemi başa düşülür ki, burada V={a₁, a₂,…, a_m}- terminal simvollar əlifbası, V={A₁, A₂,…, A_n}- qeyri-terminal simvollar əlifbasıdır. Bunların kəsişmədiyi fərz olunur: ${\displaystyle V\cap W=\{\emptyset \}}$, ${\displaystyle I}$- aksiom, yaxud başlanğıc qeyri-terminal işarə adlanır, ${\displaystyle I\in W}$, ${\displaystyle P}$- çevirmə, yaxud qurulma qaydalarının sonlu çoxluğudur, məsələn, ${\displaystyle (\alpha ,\beta )}$, yaxud ${\displaystyle (\alpha \to \beta )}$ yazılışı onu göstərir ki, ${\displaystyle \alpha }$-dan ${\displaystyle \beta }$ alınır, burada ${\displaystyle \alpha }$, ${\displaystyle \beta }$ terminal və qeyri-terminal işarələrin birləşməsindən ibarət əlifbadan qurulmuş sətirlərdir: ${\displaystyle P=\{\alpha \to \beta \mid \beta \in (V\cup W)^{*},\alpha \in (V\cup W)^{+}\}}$, yəni ${\displaystyle \alpha }$ sətrinin boş olmaması şərti irəli sürülür: ${\displaystyle \alpha \neq e}$. ${\displaystyle V}$ əlifbası qrammatikanın aid olduğu dilin əlifbası ilə eynidir. Qrammatikanın qaydalarına görə ${\displaystyle (\alpha ,\beta )}$ çevrilməsində vergüldən sol tərəfdə olan sözlər yalnız terminal simvollardan ibarət olduqda qrammatika fəaliyyətini dayandırır(terminate). Məqsədə çatana qədər qeyri-terminal simvollar aralıq sözləri qurmaq üçün istifadə olunur. Qeyri-terminalların təyinatı cürbəcür ola bilər və qrammatikanın tipindən asılıdır. Ancaq yeganə qeyri-terminal simvol mövcuddur ki, qrammatikanın tipindən asılı olmayaraq həmişə eyni təyinata malikdir. O, dilin bütün sözlərini işarə etmək üçün istifadə olunur. Bu simvol "doğuran qrammatikanın başlanğıc qeyri-terminal simvolu" adlanır, İ ilə işarə olunur. Hər bir doğuran qrammatikanın elə bir qayda olmalıdır ki, çevirmədə vergülün sol tərəfini yalnız İ olsun. Belə olmasa, bu qrammatika heç bir söz qura bilməz.

Xomski qrammatikasının çevirmələri baxılan sözdə qeyri-terminal simvol yoxa çıxana qədər tətbiq edilir. Bu qrammatika deduktivdir.

Sıfır, yaxud çoxsaylı əvəzləmələr ${\displaystyle \to ^{*}.}$ şəklində təsvir oluna bilər. ${\displaystyle alpha\to ^{*}beta}$ şəklində əvəzləmə onu göstərir ki, beta sözü alpha sözündən sonlu sayda əvəzləmə ilə alınmışdır. Bu halda əgər əvəzləmə heç bir dəfə də tətbiq olunmamışsa, onda alpha və beta sözləri üst-üstə düşür.

Misal1. Fərz edək, ${\displaystyle L}$ dili yeganə ${\displaystyle a}$ simvolundan təşkil olunmuş yeganə ${\displaystyle a}$ sözündən ibarətdir: ${\displaystyle L=\{a\}}$. Bu sözü qurmaq üçün yeganə İ${\displaystyle \to a}$ qaydası kifayət edər. Onu da qeyd edək ki, ${\displaystyle a}$-nın qurulmasını daha mürəkkəb yolla reallaşdırmaq olar, bunun üçün əlavə qeyri-terminal simvoldan, bunu ${\displaystyle A}$ ilə işarə edək, istifadə edilməlidir. Qurma qaydalarını daxil edək:

İ${\displaystyle \to A}$, ${\displaystyle A\to a}$.

Bu halda "a" sözünün yeganə qurulması üsulu: İ ${\displaystyle \to A\to a}$ şəklində təsvir oluna bilər. Qeyri-terminal qrammatikanın əlifbasını ixtiyari qaydada seçmək mümkün olduğu üçün, belə qənaətə gələ bilərik ki, bu dili qurmaq üçün sonsuz sayda doğuran qrammatika təklif oluna bilər.

Misal2. ${\displaystyle L=\{a+a,a+a+a,a+a+a+a,...\}}$ dilinin qurulması üçün doğuran qrammatikanı hazırlayaq. Göründüyü kimi, dilin hər bir sözü ${\displaystyle a}$ simvolu ilə başlayır və bunun davamında bir və daha artıq ${\displaystyle +a}$ fraqmenti iştirak edir. Deməli, əvvəlcə ${\displaystyle a}$ simvolunu qurmaq lazımdır, bundan sonra buna lazım olan qədər ${\displaystyle +a}$ fraqmentini əlavə etmək lazımdır.

Qeyri-terminal ${\displaystyle A}$ simvolunu daxil edək. Qrammatikanın qaydalarını(operatorlarını) daxil edək: İ${\displaystyle \to aA}$, ${\displaystyle A\to +aA}$, ${\displaystyle A\to +a}$.

${\displaystyle a+a+a}$ sözünün qurulması sxemi belə olar: İ${\displaystyle \to aA\to a+aA\to a+a+a}$. Bu qurmada yuxarıdakı operatorlardan hər biri bir dəfə ardıcıl olaraq tətbiq olunmuşdur. ${\displaystyle L}$ dilinin sözlərinin sayı sonsuz olduğu üçün bütün sözləri rekursiv olaraq qurmaq tələb olunur. Rekursiya yaradan səbəb ${\displaystyle A\to +aA}$ operatorudur, çevirmənin solunda və sağında eyni bir simvol—${\displaystyle A}$ simvolu iştirak edir.

Misal3. Simmetrik sətirlər qrammatikasına baxaq, bunu G={V, W, I, P} ilə işarə edək. Burada: ${\displaystyle V=\{a,b\}}$,${\displaystyle W=\{I\}}$,${\displaystyle P=\{I\to aIa,I\to bIb,I\to e\}}$. Bunlar əsasında göstərmək olar ki, ${\displaystyle G}$ simmetrik qrammatikadır.

"0-cı sinif" qrammatikalar — Bu zaman ${\displaystyle alpha\to ^{*}beta}$ çevirməsinə heç bir məhdudiyyət qoyulmur, ona görə də bunlara bəzən qeyri-məhdud qrammatika deyilir.

${\displaystyle P=\{\alpha \in (V\cap W)^{+},\beta \in (V\cap W)^{*}\}}$.

Bütün formal qrammatikalar bu sinfə aid edilir. Türinq maşını ilə tanınan bütün dillər bu qrammatikalarla qurula bilir, belə dillərə rekursiv sadalanan dillər deyilir.

Misal. Aşağıda verilmiş qaydalara əsasən ${\displaystyle addd}$ sözünü qurmalı.

Qaydalar:

${\displaystyle I\to aBcc}$

${\displaystyle B\to A}$

${\displaystyle BAA\to d}$

${\displaystyle Ac\to B}$

${\displaystyle A\to AAA\mid dB}$

${\displaystyle I\to aBcc\to aAcc\to aBc\to aAc\to aB\to aA\to adB\to adAAA\to addBAA\to addd}$

"1-ci sinif" qrammatikalar — Bu sinfə mətndən asılı qrammatikalar və qısaltmayan qrammatikalar aid edilir. Birincinin qaydaları aşağıdakı kimi verilir:

${\displaystyle \alpha A\beta \to \alpha \omega \beta }$, burada ${\displaystyle \alpha ,\beta \in (V\cup W)^{*},A\in W,\omega \in (V\cup W)^{+}}$.

Qısaltmayan qrammatikanın qaydaları isə belədir:

${\displaystyle \alpha \to \beta }$, burada ${\displaystyle \alpha ,\beta \in (V\cup W)^{+},1\leq \mid \alpha \mid \leq \mid \beta \mid }$

Bu qrammatikalar ekvivalentdir. Bunlar təbii dilin mətnlərinin analizində istifadə oluna bilir. Bir sıra sahələrdə, məsələn, kompilyatorların qurulmasında istifadəsi, çətinliyə görə, praktiki olaraq mümkün deyil.

Bu sinifdən təbii dillərin və alt dillərin elementlərinin generasiyasında istifadə olunur.

"2-ci sinif" qrammatikalar — Bu qrammatikaların qaydaları ${\displaystyle A\to \alpha }$ şəklində verilir, ${\displaystyle A\in W,\alpha \in (V\cup W)^{*}}$, yəni bu qrammatika sol tərəfdə yalnız bir qeyri-terminal simvolun olmasını tələb edir. Buna mətndən asılı olmayan qrammatika deyilir. Bu qrammatikalar vasitəsilə qurulan dillər maqazin yaddaşlı avtomatlar tərəfindən tanınır.

"3-cü sinif" qrammatikalar(requlyar) — Bu qrammatikaların qaydaları ${\displaystyle A\to \alpha B(A\to B\alpha )}$ və ya ${\displaystyle A\to \alpha }$ şəklində verilir, burada ${\displaystyle A,B\in W,\alpha \in V}$.

Bu cür qrammatikaya avtomat, yaxud requlyar qrammatika deyilir. Bu qrammatikalar mətndən asılı deyil, məhdud imkanlara malikdir. Bunlar formal qrammatikalardan requlyar dilləri qura bilən ən sadə qrammatikalardır. Bu qrammatikaları iki ekvivalent sinfə ayırmaq olar:

• Sol tərəfli qrammatika
• Sağ tərəfli qrammatika

Sol tərəfli qrammatikanın operatorları:

${\displaystyle A\to B\alpha }$

${\displaystyle A\to \alpha }$

Sağ tərəfli qrammatikanın operatorları:

${\displaystyle A\to \alpha B}$

${\displaystyle A\to \alpha }$

Sol tərəfli və sağ tərəfli qrammatikalar bir-birinə ekvivalentdir, bunlar eyni dil qurur. Ancaq onu da qeyd edək ki, sol tərəfli və sağ tərəfli qrammatikaların operatorlarını birləşdirsək, alınan dil requlyar olmaya bilər. Bundan başqa sağ tərəfli qrammatika ilə qurulan dillər çoxluğu sonlu avtomatlarla qurulan dillər çoxluğu ilə eynidir.

Əgər hər hansı ${\displaystyle L}$ dil ${\displaystyle i}$-ci sinif qrammatika ilə qurulmuşsa, onda deyirlər ki, bu dil ${\displaystyle i}$ sinfinə aiddir. ${\displaystyle i}$ sinfinə aid olan bütün qrammatikalar ${\displaystyle G_{i}}$ ilə işarə etsək, onda formal qrammatikalar arasındakı əlaqəni aşağıdakı kimi təsvir etmək olar:

Fərqli qrammatikaların bir-birinə çevrilməsi maraqlı məsələdir. Məsələn, doğuran qrammatika əsasında sadalayan qrammatika qurmaq olarmı? Olar. Bunun üçün doğuran qrammatika ilə sözləri generasiya etmək, onları uzunluğuna və simvollarının düzülüşünə görə nizamlamaq kifayətdir. Ancaq bunun əksinə, ümumi halda, hökm etmək olmaz, yəni hər bir sadalayan qrammatika əsasında doğuran qrammatika qurmaq olmaz. Sadalayan qrammatikadan tanıyan qrammatikanın qurulması da, ümumi halda, mümkün olmayan məsələdir. Ancaq birincinin əsasında ikincinin işini aşağıdakı kimi şərh etmık olar:

Sadalayan qrammatikanın çıxış sözlərini ardıcıl olaraq tanıyan qrammatikaya təqdim edək. Tanıyan qrammatikaya lazım olan söz çap olunduqda tanıyan qrammatika "hə" cavabı verir və biz sadalayan qrammatikanın işini məcburən dayandırırıq. Ancaq sadalayan qrammatikanın çıxışındakı heç bir söz verilmiş dilə aid olmasa, tanıma prosesi sonsuz olaraq davam edəcək, tanıyan qrammatikanın işi düyünə düşəcək. Bu mənada tanıyan qrammatikaların gücü doğuran və sadalayan qrammatikaların gücündən kiçikdir. Xomskinin doğuran qrammatikası ilə Türinqin tanıyan maşınlarını müqayisə etdikdə bu məsələni nəzərə almaq lazımdır.

Daha əlverişli qrammatika induktiv olan qrammatikadır.

Teorem 1: Hər bir təbii dilin sonlu sayda cümlələrindən ibarət çoxluq formal qrammatikadır.

Teorem 2: Hər bir formal dilə uyğun bir induktiv qrammatika qurmaq mümkündür.

Mətndən asılı olmayan ilk qrammatika kimi C. Bekusun yaratdığı ALQOL-60 dilini qeyd etmək olar.

Tezaurus formal qrammatikanın tətbiqinə aid bir nümunə kimi göstərilə bilər. Tezaurus cədvəl şəklində verilən modeldir(cədvələ baxın). Bu model baza sözlərinin əsasında cümlə qurmağa imkan verir.

Bu tezaurusun "*" işarəsi mətndə verilən sözə yeni söz əlavə etmək imkanı yaradır. Belə ki, cümləni "məmulat" sözü ilə başlasaq, "məmulatın keyfiyyəti" cümləsi alınar.

Tezaurusdan kompüterdə informasiya bazası yaradan zaman verilənlər bazasının idarə edilməsi zamanı və s. müxtəlif sahələrdə istifadə olunur.

Formal qrammatikalardan biri də Bekus-Naur qrammatikasıdır. Bunun vasitəsilə "identifikator" anlayışının izahı aşağıdakı kimi verilir:

<identifikator> :: = <hərf> | <hərf> <davam>

<davam> :: = <simvol> | <simvol> <davam>

<simvol> :: = <hərf> | <rəqəm>

<hərf> :: = A | B | … | Z

<rəqəm> :: = 0| 1| 2| …| 9

Bekus-Naur qrammatikası əsasında başqa konstruksiyaları da yaratmaq olar, məsələn:

<isim> :: = <kök><şəkilçi>

<şəkilçi> :: = <tək halın şəkilçisi> | <cəm halın şəkilçisi>

Şərti işarələrin açıqlaması:

<… > —izahı tələb olunan hər hansı anlayış soldan və sağdan müvafiq olaraq bu işarələrlə əhatə olunur

${\displaystyle ::=}$ —bu işarədən solda izah olunan anlayış, sağda onun izahı yazılır

| —bu işarə "və ya" mənasını bildirir

Göründüyü kimi, Bekus-Naur qrammatikasında hər hansı anlayış özünə istinad etməklə izah oluna bilir, yəni bu qrammatikada rekursivlikdən istifadə olunur.^[1]

• Alqoritmlər

• Vaqif Əsəd oğlu Kərimov. Alqoritmlər nəzəriyyəsi. Dərs vəsaiti. Bakı. ADNSU-nun nəşri, 2017, 116 səh.