|
O’zbekiston respublikasi oliy va o`rta maxsus ta’lim vazirligi
|
| bet | 15/27 | | Sana | 20.11.2023 | | Hajmi | 294 Kb. | | #102034 |
Bog'liq Amaliy matemarika va axborot texnologiyalari” kafedrasi Sadullay
G grammatikada bo’sh bo’lmagan chiqariluvchan satrning chiqarilish jarayonini tasvirlovchi tuzilma – bu chiqaruv daraxti. Gohida chiqaruv daraxtini grammatik tahlil daraxti yoki sintaktik daraxt ham deb ataladi. Chiqaruv daraxtining formal tavsifi quyidagicha :
Agar A noterinal - ichki tugun bo’lib, X1,X2,…,Xn shu tugunning chapdan o’ngga qarab o’g’il tugunlari bo’lsa, u holda berilgan grammatika da A X1X2…Xn qoida mavjud.
Chapdan o’ngga qarab daraxt barglari mos kelgan simvollarni tizib yasalgan satr daraxt uchi deb ataladi. Chiqaruv daraxti uchi bo’sh noterminaldan chiqariladigan (generatsiya qilinadigan, hosil qilinadigan) satrni ifodalaydi.
Chiqaruv daraxti qiyidagi prinsipga asosan tabiiy ravishda o’z barglarini chapdan o’ngga tartiblaydi: agar X va Y bitta ota tugunning o’g’il tugunlari bo’lsa va X tugun Y tugundan chapda joylashgan bo’lsa, u holda X tugunning barcha avlodlari Y tugunning avlodlaridan chapda joylashadi.
KX grammatika tilining yana bir ta’rifini quyidagicha berish mumkin: KX grammatika tili deb uning barcha chiqaruv daraxtlari tomonidan hosil qilinadigan satrlar to’plamiga aytiladi. Berilgan satr uchun uning chiqaruv daraxtini topish sintaktik tahlil (parsing) deb ataladi.
KX grammatika tiliga tegishli terminal satr tuzilmasini qarayatgan vaqtda shuni aniqlash mumkinki, satrga bittadan ko’p chiqaruv daraxti mos kelishi mumkin. Bu holda KX grammatika bir qiymatli emas (ambiguous) deyiladi. KX grammatika bir qiymatli emasligini bittadan ko’p chiqaruv daraxti mavjud bo’lgan ixtiyoriy bitta KX grammatika tiliga tegishli satr mavjudligini ko’rsatish bilan isbotlash mumkin.
Yuqorida aytib o’tilganidek, bir qiymatli KX grammatika da grammatika tiliga tegishli bo’lgan har bir satr uchun yagona chiqarish daraxti mavjud. Satrning har xil chiqarishlari chiqarish jarayonidagi almashtiladigan noterminalni tanlanishiga bog’liq. Shuning uchun bir qiymatli KX grammatika da har bir chiqaruv daraxti uchun yagona bitta chap (o’ng) chiqaruv mavjud.
|
| |
