O’zbekiston respublikasi oliy va o`rta maxsus ta’lim vazirligi

Chiqaruv daraxti

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 :

• 
  Daraxt ildizi boshlang’ich simvol bilan belgilanadi
  
• 
  Har bir barg terminal simvol yoki е bilan belgilanadi
  
• 
  Har bir ichki tugun noterminal simvol orqali belgilanadi
  

Agar A noterinal - ichki tugun bo’lib, X₁,X₂,…,X_n shu tugunning chapdan o’ngga qarab o’g’il tugunlari bo’lsa, u holda berilgan grammatika da A  X₁X₂…X_n 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.

Bir qiymatli KX grammatika

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.