2-Mavzu. Formal tillar gramatikasi. Kopiliyatorlar. Leksik va semantik tahlil

Til grammatikasi

Grammatika – bu tilni gaplarini tuzish usullaridir.

Grammatika – tilni ta’riflovchi matematik tizimdir.

Grammatika tilni ikkinchi usul bilan ta’riflaydi.

Til grammatikasi qoidalar to‘plami yordamida beriladi.

Formal grammatikada qoidalar tartiblangan zanjirlar juftligi bilan beriladi (α,β). Qoidalarda tartib juda muximdir shuning uchun ko‘pincha qoida α→β yoki α::=β ko‘rinishda yoziladi va bu yoziv quyidagini bildiradi: α zanjir β zanjirni yaratadi , yoki β zanjir ta’rif bo‘yicha α dir. G grammatika bilan berilgan til L(G) ko‘rinishda yoziladi.

Agar ikkita grammatika G va G’ bitta tilni ta’riflasa ular ekvivalentdir. Ikkita grammatika G va G’ qisman ekvivalent agar ular orqali ta’riflangan tillar faqat bo‘sh zanjir bilan farq qilinsa.

Grammatikani formal ta’rifi va uni berish usullari

Grammatikani formal ta’rifi to‘rta narsa bilan aniqlanadi G(VT,VN,P,S)bunda :

VT – terminal belgilar chekli to‘plami;

VN – noterminal belgilar chekli to‘plami shunda VT ∩ VN =Ø; V=VN∪VT belgilar to‘plami G grammatikani to‘liq alfaviti bo‘ladi.

P – α→β;shaklidagi qoidalar to‘plami, bunda /, yani α zanjir terminal va noterminal belgilardan iboratdir( bo‘sh belgisidan tashqari); β zanjir xam terminal va noterminal belgilardan iboratdir va bo‘sh bo‘lishi mumkin;

S – grammatikani boshlang‘ich (mo‘ljal) belgisi S / VN.

Grammatikadagi to‘plamlar quyidagini bildiradi:

VT – bu terminal belgilar to‘plami bo‘lib, shu grammatika bilan tuzilgan tilni alfavitidir. Asosan bu belgilar qoidalarni o‘ng tomonidagi zanjirda uchraydi, agar ular qoidani chap tomonida uchrasa, albatta o‘ng tomondagi zanjirda ham bo‘lishi kerak. Faqat terminallardan tuzilgan zanjirlarni belgilash uchun x,y,z,u,v,w lotin xarflari ko‘pincha ishlatiladi.

VN – bu noterminal belgilar bo‘lib, tilni konstruksiyalarini ta’riflash uchun ishlatiladi. Bu belgilar tilni o‘ziga kirmaydi ular faqat qoidalarda ishlatiladi. Noterminal belgilar qoidani xam chap tomonida , xam o‘ng tomonida uchrashishi mumkin, lekin ular kamida bir marta biror qoidani chap tomonida uchrashishi kerak. Har bir qoidani chap tomonida kamida bitta noterminal bo‘lishi shart. Xech qanday belgi xam terminal xam noterminal bo‘lishi qat’iyan man etiladi.

Boshlang‘ich belgisi doim noterminal belgisi bo‘ladi.

Qoidalarni ta’riflash tili metatil deb nomlanadi. Xar bir qoida aloxida satrda yoziladi. Bunday yozish usuli Xomskiy metatili deb nomlanadi. Xomskiy metatilda noterminal belgilari indeksli A xarf bilan belgilanadi. Masalan butun ishorali sonni grammatikasi Xomskiy metatilda quyidagicha bo‘ladi:

G({0,1,2,3,4,5,6,7,8,9,+,-},{A1,A2,A3},P,A1) P:

A1→A2

A1→+A2

A1→-A2

A2→A3

A2→A2A3

A3→0

A3→1

A3→2

A3→3

A3→4

A3→5

A3→6

A3→7

A3→8

A3→9

Bu misolda terminal belgilar to‘plami VT o‘n ikkita belgidan iboratdir, bu o‘nta raqam va ishora belgilari. Noterminal belgilar to‘plami VN uchta elementdan tashkil qilgan bu A1,A2va A3. Qoidalar to‘plami 15ta qoidadan iborat, va ular 15 satrga yozilgan.Boshlang‘ich belgisi A1.

Bir nechta qoidalarni chap qismi bir xil bo‘lsa α→β1,α→β2, ... ,α→βn ularni bitta qoida bilan yozish mumkin α→β1|β2|...|βn, bunday yozish shakli Bekus-Naur shakli (BNSH) deb nomlanadi bu metatilda :

“→” yoki “::=” belgilar qoidani chap qismini o‘ng qismidan ajratish uchun ishlatiladi; noterminallar ixtiyoriy satr ko‘rinishda yozilib “<” va “>” burchak qavslar ichiga olinadi;

alternativ qoidalar “ | ” belgisi bilan ajratiladi. Yuqorida berilgan grammatika BNShda quyidagicha ta’riflanadi:

G({0,1,2,3,4,5,6,7,8,9,+,-}, {,,}, P,

) P:

→ | + | -

→ |

→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Shuni aytib o‘tish kerakki noterminal so‘zlar nomlari qoidalarni tushinarli bo‘lish uchun shunday qo‘yilgan, vaholanki ularni boshqacha xam belgilash mumkin , natijadagi grammatika bari bir butun sonni ta’riflaydi. Lekin terminal belgilarni o‘zgartirib bo‘lmaydi, aks xolda butunlay boshqa til bo‘ladi. Masalan yuqoridagi grammatikani quyidagicha berish mumkin:

G’({0,1,2,3,4,5,6,7,8,9,+,-}, {S,T,F}, P, S) P:

S→T | +T | -T

T→F | TF

F→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Bu grammatikada noterminallar sifatida katta lotin xariflar ishlatildi, yani VN={S,T,F}.G’ va G grammatikalar ekvivalentdir.

Formal grammatikalar chekli qoidalar orqali cheksiz zanjirlar to‘plamini ta’riflaydi. Bunday imkoniyatni rekursiv qoidalar beradi. Rekursiyali qoidada noterminal belgisi o‘zi orqali ta’riflanadi bu bevositali rekursiya deb nomlanadi, agar noterminal bir nechta qoidadan so‘ng o‘zi orqali ta’riflansa buni vositali rekursiya deb nomlanadi.

Bizni misolda → bevositali rekursiv qoida. Rekursiv qoida cheksiz bo‘lib qolmasligi uchun shu noterminal uchun albatta rekursiv bo‘lmagan qoida xam bo`lishi kerak, bizda bu:→.

Grammatika qoidalarini yanada tushinarli bo‘lish uchun boshqa usullar xam mavjud. Shunday usullarda ikkitasini keltiramiz bu metabelgilar usuli va grafik usuli.

Meta belgilar usulida, boshqacha aytganda kengaytirilgan Bekus-Naur shakli (KBNSH)da qo‘shimcha metabelgilar kiritilgan bu:

(),[],{} ,”,”, “”

() qavs ichida turgan zanjirlar ro‘yxatidan faqat bittasi shu o‘rinda turishi mumkin;

[] qavs ichida turgan zanjir bo‘lmasligi xam mumkin;

{} qavs ichida turgan zanjir bo‘lmasligi mumkin,yoki bir marta bo‘lishi mumkin , yoki ber necha marta bo‘lishi mumkin;

“,” vergul belgisi ro‘yxatdagi zanjirlarni ajratish uchun ishlatiladi; “” qo‘shtirnoq belgisi ichidagi metabelgini terminal sifatida yozish uchun ishlatiladi. KBNShda yozilgan yuqoridagi grammatikamiz quydagicha bo‘ladi: G({0,1,2,3,4,5,6,7,8,9,+,-},{,},P,) P:

→[(+,-)]{}

→0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Bu grammatika qoidalaridan ko‘rinib turibdiki birinchidan noterminal soni kamaydi, ikkinchida rekursiya yo‘qoldi.

Grafik usulida xar bir noterminal belgi uchun diagramma chiziladi bu diagrammada grammatika qoidasini beradi. Bunday grafika Virt diagrammasi deb nomlanadi. Uning yozish qoidalari kuyidagicha:

1. terminal belgilar va ulardan tuzilgan o‘zgarmas so‘zlar (leksemalar) aylanani yoki egrilgan yon tomonli to‘g‘ri to‘rtburchak ichiga olinadi;

2. noterminal belgilar to‘g‘ri to‘rtburchak ichiga olinadi;

3. xar bir grafik element bitta kiruvchi va bitta chiquvchi chiziqqa ega;

4. xar bir qoida uchun alohida diagramma chiziladi va unda terminal va noterminal elementlar bir biri bilan yoylar orqali ulanadilar;

5.variantlar bir nechta yoylar bilan, iteratsiya(rekursiya, qaytarishlar) yoyni qayta ulanishi bilan beriladi;

6.Qoidani boshlanishini bildiruvchi bitta noterminal bilan belgilangan kiruvchi yoy (chapda va ustida) va qoidani yakunlovchi bitta chiquvchi yoy (o‘ngda va ostida) bo‘lishi kerak ;

Misol taraqasida bir nechta elementar konstruqsiyalarni diagrammalarinikeltiramiz: