Deterministik kontekstsiz grammatika - Deterministic context-free grammar

Yilda rasmiy grammatika nazariya, aniqlanadigan kontekstsiz grammatikalar (DCFGlar) a to'g'ri to'plam ning kontekstsiz grammatikalar. Ular kelib chiqishi mumkin bo'lgan kontekstsiz grammatikalarning pastki qismidir deterministik surish avtomatlari va ular kontekstsiz deterministik tillar. DCFG har doim aniq, va bir so'zsiz CFGlarning muhim subklassi; ammo, deterministik bo'lmagan aniq CFGlar mavjud.

DCFGlar katta amaliy qiziqish uyg'otadi, chunki ularni chiziqli vaqt ichida ajratish mumkin va aslida grammatikadan parser avtomatik ravishda hosil bo'lishi mumkin. ajralish generatori. Shunday qilib, ular kompyuter fanlari davomida keng qo'llaniladi. DCFGlarning har xil cheklangan shakllarini sodda, kam resurs talab qiladigan tahlilchilar tahlil qilishlari mumkin va shuning uchun tez-tez ishlatiladi. Ushbu grammatika darslari ularni tahlil qiladigan tahlilchi turi bilan ataladi va muhim misollar LALR, SLR va LL.

Tarix

1960-yillarda kompyuter fanida nazariy tadqiqotlar doimiy iboralar va cheklangan avtomatlar kashfiyotga olib keldi kontekstsiz grammatikalar nondeterministikka tengdir pastga tushirish avtomatlari.[1][2][3] Ushbu grammatikalar kompyuter dasturlash tillari sintaksisini egallagan deb o'ylashdi. O'sha paytda birinchi kompyuter dasturlash tillari rivojlanayotgan edi (qarang Dasturlash tillari tarixi ) va yozish kompilyatorlar qiyin edi. Ammo foydalanish kontekstsiz grammatikalar kompilyatorning ajraladigan qismini avtomatlashtirishga yordam berish vazifani soddalashtirdi. Deterministik kontekstsiz grammatikalar ayniqsa foydalidir, chunki ular ketma-ketlikda a tomonidan tahlil qilinishi mumkin edi deterministik surish avtomati, bu kompyuter xotirasi cheklanganligi sababli talab edi.[4] 1965 yilda, Donald Knuth ixtiro qilgan LR (k) tahlil qiluvchi va har bir deterministik kontekstsiz til uchun LR (k) grammatikasi mavjudligini isbotladi.[5] Ushbu tahlilchi hali ham juda ko'p xotirani talab qildi. 1969 yilda Frank DeRemer ixtiro qilgan LALR va Oddiy LR LR ajratuvchisiga asoslangan va tilni kamroq tanib olish kuchi evaziga xotira talablarini ancha kamaytirgan ajraluvchilar. LALR tahlilchisi kuchli alternativ edi.[6] Ushbu ikkita tahlilchi shu vaqtdan boshlab ko'plab kompyuter tillarining kompilyatorlarida keng qo'llanila boshlandi. Yaqinda olib borilgan tadqiqotlar natijasida kanonik LR-analizatorlar Knutning jadvallarni yaratish algoritmiga nisbatan jadvalning talablari keskin kamaytirilgan holda amalga oshirilishi mumkin.[7]

Shuningdek qarang

Adabiyotlar

  1. ^ Xomskiy, Noam (1962). "Kontekstsiz grammatikalar va pastga tushirish". Har chorakda amalga oshirilgan ishlar to'g'risida hisobot, MIT elektronika laboratoriyasi. 65: 187–194.
  2. ^ Evey, R.J. (1963). "Pushdown-Store mashinalarini qo'llash". 1963 yil kuzgi qo'shma kompyuter konferentsiyasining AFIPS materiallari: 215–227.
  3. ^ Shuttsenberger, Marsel Pol (1963). "Kontekstsiz tillar va pastga tushirish avtomatlari to'g'risida". Axborot va boshqarish. 6: 246–264. doi:10.1016 / s0019-9958 (63) 90306-1.
  4. ^ Salomaa; D yog'och; S Yu, tahrir. (2001). Yarim asrlik avtomatika nazariyasi. Jahon ilmiy nashriyoti. 38-39 betlar.
  5. ^ Knut, D. E. (1965 yil iyul). "Tillarni chapdan o'ngga tarjima qilish to'g'risida" (PDF). Axborot va boshqarish. 8 (6): 607–639. doi:10.1016 / S0019-9958 (65) 90426-2. Arxivlandi asl nusxasi (PDF) 2012 yil 15 martda. Olingan 29 may 2011.
  6. ^ Franklin L. DeRemer (1969). "LR (k) tillari uchun amaliy tarjimonlar" (PDF). MIT, doktorlik dissertatsiyasi. Arxivlandi asl nusxasi (PDF) 2012-04-05 da.
  7. ^ X. Chen, LR (1) ajralishini o'lchash va kengaytirish, Gavayi universiteti doktorlik dissertatsiyasi, 2009 y.