Ayrilash - Parsing

"Tahlil" bu yerga yo'naltiradi. Boshqa maqsadlar uchun qarang Ajratish (ajratish).

Ayrilash, sintaksis tahlili, yoki sintaktik tahlil bu tahlil qilish jarayoni mag'lubiyat ning belgilar, yoki ichida tabiiy til, kompyuter tillari yoki ma'lumotlar tuzilmalari, a qoidalariga muvofiq rasmiy grammatika. Atama tahlil qilish lotin tilidan keladi qismlar (orationis), ma'no qism (nutq).[1]

Ushbu atama turli sohalarda bir oz boshqacha ma'noga ega tilshunoslik va Kompyuter fanlari. An'anaviy hukm ajralish ko'pincha jumla yoki so'zning aniq ma'nosini anglash usuli sifatida, ba'zan kabi vositalar yordamida amalga oshiriladi jumla diagrammalari. Kabi grammatik bo'linmalarning muhimligini odatda ta'kidlaydi Mavzu va predikat.

Ichida hisoblash lingvistikasi bu atama kompyuter tomonidan jumlani yoki boshqa qator so'zlarni tarkibiy qismlariga rasmiy tahlil qilish uchun ishlatilishi uchun ishlatiladi, natijada daraxtni tahlil qilish o'z ichiga olishi mumkin bo'lgan bir-biriga ularning sintaktik munosabatini namoyish etish semantik va boshqa ma'lumotlar (p-qiymatlari ).[iqtibos kerak ] Ayrim tahlil algoritmlari a hosil qilishi mumkin o'rmonni ajratish yoki a uchun ajralish daraxtlari ro'yxati sintaktik jihatdan noaniq kiritish.[2]

Ushbu atama ham ishlatiladi psixolingvistika tilni tushunishni tavsiflashda. Shu nuqtai nazardan, tahlil qilish, odamlarning gapni yoki so'z birikmasini (nutqiy tilda yoki matnda) "grammatik tarkibiy qismlar nuqtai nazaridan, nutq qismlarini aniqlash, sintaktik munosabatlar va boshqalarni" tahlil qilish usulini anglatadi.[1] Ushbu atama ma'ruzachilarni talqin qilishda qanday lingvistik ko'rsatmalar yordam berishini muhokama qilishda ayniqsa keng tarqalgan bog 'yo'lidagi jumlalar.

Informatika doirasida bu atama tahlil qilishda ishlatiladi kompyuter tillari yozishni osonlashtirish uchun kirish kodining tarkibiy qismlariga sintaktik tahlilini nazarda tutadi kompilyatorlar va tarjimonlar. Bu atama, shuningdek, bo'linish yoki ajralishni tavsiflash uchun ham ishlatilishi mumkin.

Inson tillari

Asosiy toifasi: Tabiiy tilni tahlil qilish

An'anaviy usullar

Ayrilishning an'anaviy grammatik mashqlari, ba'zan moddaning tahlili, har bir qismning shakli, vazifasi va sintaktik munosabatlarini tushuntirish bilan matnni nutqning tarkibiy qismlariga ajratishni o'z ichiga oladi.[3] Bu ko'p jihatdan tilni o'rganishdan aniqlanadi kelishiklar va pasayish, bu juda kuchli tillar uchun juda murakkab bo'lishi mumkin. "Odam itni tishlaydi" kabi jumlani tahlil qilish uchun "odam" singari ism gapning sub'ekti ekanligini, "tishlash" fe'lining hozirgi paytdagi "tishlamoq" fe'lining uchinchi shaxs birlik ekanligini va birlik "it" jumla ob'ekti. Kabi usullar jumla diagrammalari ba’zan gapdagi elementlar orasidagi munosabatni ko‘rsatish uchun ishlatiladi.

Ilgari ingliz tilida so'zlashadigan dunyo bo'ylab grammatikani o'qitish uchun ajralish asosiy bo'lgan va yozma tildan foydalanish va tushunish uchun keng tarqalgan hisoblanadi. Biroq, bunday texnikalarni umumiy o'qitish endi dolzarb emas.

Hisoblash usullari

Ba'zilarida mashina tarjimasi va tabiiy tilni qayta ishlash tizimlar, inson tilidagi yozma matnlarni kompyuter dasturlari tahlil qiladi.[4] Inson jumlalarini dasturlar osonlikcha tahlil qila olmaydi, chunki bu erda juda katta ahamiyatga ega noaniqlik ma'nolarni etkazish uchun ishlatilgan inson tili tarkibida (yoki semantik ) potentsial cheksiz imkoniyatlar qatoriga kiradi, ammo ularning ba'zilari faqat ushbu holatga tegishli.[5] Shunday qilib, "Inson itni tishlaydi" va "Itni odamni tishlaydi" degan gaplar bitta tafsilotga aniq, ammo boshqa tilda "ikkalasi it chaqishi" kabi ko'rinishi mumkin, chunki bu ikki imkoniyatni farqlash uchun katta kontekstga asoslanib, agar haqiqatan ham bu farq bo'lsa tashvish. Norasmiy xatti-harakatni tavsiflash uchun rasmiy qoidalarni tayyorlash qiyin, garchi ba'zi qoidalarga amal qilinayotgani aniq bo'lsa.[iqtibos kerak ]

Tabiiy til ma'lumotlarini tahlil qilish uchun tadqiqotchilar birinchi navbatda grammatika foydalanish uchun. Sintaksisni tanlash ikkalasiga ham ta'sir qiladi lingvistik va hisoblash muammolari; masalan, ba'zi bir tahlil tizimlari foydalanadi leksik funktsional grammatika, lekin umuman olganda, ushbu turdagi grammatikalar uchun tahlil qilish ma'lum To'liq emas. Bosh bilan boshqariladigan iboralar tarkibi grammatikasi bu tahliliy jamoada mashhur bo'lgan yana bir lingvistik formalizm, ammo boshqa tadqiqot ishlari Pennda ishlatilgan kabi unchalik murakkab bo'lmagan formalizmlarga qaratilgan. Daraxt banki. Sayoz tahlil qilish faqat asosiy tarkibiy qismlarning chegaralarini topishga qaratilgan, masalan, ot iboralari. Lingvistik tortishuvlardan qochishning yana bir mashhur strategiyasi qaramlik grammatikasi tahlil qilish.

Aksariyat zamonaviy tahlilchilar hech bo'lmaganda qisman statistik; ya'ni ular a ga tayanadi korpus allaqachon izohlangan o'quv ma'lumotlari (qo'l bilan tahlil qilingan). Ushbu yondashuv tizimga muayyan kontekstda turli xil konstruktsiyalar paydo bo'lishi chastotasi haqida ma'lumot to'plash imkonini beradi. (Qarang mashinada o'rganish.) Amaldagi yondashuvlar to'g'ridan-to'g'ri o'z ichiga oladi PCFGlar (ehtimoliy kontekstsiz grammatikalar),[6] maksimal entropiya,[7] va asab tarmoqlari.[8] Ko'proq muvaffaqiyatli tizimlardan foydalaniladi leksik statistika (ya'ni, ular o'z ichiga olgan so'zlarning o'ziga xosligini hisobga oladi) nutqning bir qismi ). Ammo bunday tizimlar himoyasizdir ortiqcha kiyim va biron bir narsani talab qiladi tekislash samarali bo'lish.[iqtibos kerak ]

Tabiiy til uchun algoritmlarni tahlil qilish dasturlash tillari uchun qo'lda ishlab chiqilgan grammatikalarda bo'lgani kabi "yoqimli" xususiyatlarga ega bo'lgan grammatikaga tayanolmaydi. Yuqorida aytib o'tilganidek, ba'zi grammatik rasmiyatchiliklarni hisoblashda tahlil qilish juda qiyin; umuman olganda, kerakli tuzilma bo'lmasa ham kontekstsiz, grammatikaga qandaydir kontekstsiz yaqinlashish birinchi o'tishni amalga oshirish uchun ishlatiladi. Kontekstsiz grammatikalardan foydalanadigan algoritmlar ko'pincha ba'zi bir variantlariga asoslanadi CYK algoritmi, odatda ba'zilari bilan evristik vaqtni tejash uchun mumkin bo'lmagan tahlillarni kesib tashlash. (Qarang diagrammani tahlil qilish.) Ammo ba'zi tizimlar, masalan, ning chiziqli vaqtli versiyalaridan foydalangan holda aniqlik uchun tezlikni almashadilar smenani qisqartirish algoritm. Yaqinda sodir bo'lgan voqea qayta tahlil qilish unda tahlilchi ko'plab tahlillarni taklif qiladi va murakkab tizim eng yaxshi variantni tanlaydi.[iqtibos kerak ] Semantik tahlilchilar matnlarni ularning ma'nolarini ifodalashga aylantirish.[9]

Psixolingvistika

Yilda psixolingvistika, tahlil qilish so'zlarni toifalarga ajratishni (ontologik tushunchalarni shakllantirish) emas, balki jumla tarkibidagi har bir so'zdan qilingan xulosalar asosida tuzilgan sintaksis qoidalariga ko'ra jumla ma'nosini baholashni o'z ichiga oladi ( ma'no ). Odatda bu so'zlarni eshitish yoki o'qish paytida yuz beradi. Binobarin, tahlil qilishning psixolingvistik modellari zarurat hisoblanadi ortib boruvchi, demak, ular odatda qisman sintaktik tuzilish nuqtai nazaridan ifodalangan, jumla qayta ishlanayotganda, ular izohni tuzadilar. Dastlab noto'g'ri tuzilmalarni yaratish talqin qilishda sodir bo'ladi bog 'yo'lidagi jumlalar.

Nutqni tahlil qilish

Nutqni tahlil qilish tildan foydalanish va semiotik hodisalarni tahlil qilish usullarini o'rganadi. Ishonchli til chaqirilishi mumkin ritorika.

Kompyuter tillari

Ayrim

A tahlilchi kirish ma'lumotlarini (tez-tez matnli) qabul qiladigan va a ni yaratadigan dasturiy ta'minot komponentidir ma'lumotlar tuzilishi - ko'pincha qandaydir daraxtni tahlil qilish, mavhum sintaksis daraxti yoki boshqa ierarxik tuzilish, to'g'ri sintaksisni tekshirishda kirishning tarkibiy ko'rinishini beradi. Ajralishdan oldin yoki undan keyin boshqa qadamlar qo'yilishi mumkin yoki ular bitta bosqichga birlashtirilishi mumkin. Ayrıştırıcının oldida ko'pincha alohida bo'ladi leksik analizator, bu kirish belgilarining ketma-ketligidan nishonlarni yaratadi; Shu bilan bir qatorda, ularni birlashtirish mumkin skanersiz tahlil qilish. Ayrıştırıcılar qo'l bilan dasturlashtirilishi yoki a tomonidan avtomatik yoki yarim avtomatik ravishda yaratilishi mumkin ajralish generatori. Ayrıştırma bir-birini to'ldiradi jozibali, formatlangan ishlab chiqaradi chiqish. Ular turli xil domenlarda qo'llanilishi mumkin, lekin ko'pincha birgalikda paydo bo'ladi, masalan skanf /printf juftlik yoki kompilyatorning kirish (oldingi uchini ajratish) va chiqish (orqa kodni yaratish) bosqichlari.

Ayrıştırıcıya kirish, ba'zida ko'pincha matn bo'ladi kompyuter tili, shuningdek, tabiiy tildagi matn yoki kamroq tuzilgan matnli ma'lumotlar bo'lishi mumkin, bu holda odatda matnning ayrim qismlari olinadi, aksincha ajralish daraxti qurilmaydi. Kabi juda oddiy funktsiyalardan ajralib turadi skanf, a frontend kabi murakkab dasturlarga C ++ kompilyatori yoki HTML a veb-brauzer. Oddiy ajralishning muhim klassi yordamida amalga oshiriladi doimiy iboralar, unda doimiy iboralar guruhi a ni belgilaydi oddiy til va odatiy ekspression dvigatel avtomatik ravishda o'sha til uchun ajralish moslamasini yaratadi va bu ruxsat beradi naqshlarni moslashtirish va matnni chiqarish. Boshqa kontekstlarda odatiy iboralar tahlil qilishdan oldin ishlatiladi, chunki natijasi tahlilchi tomonidan ishlatilgan leksing bosqichi sifatida.

Ayrıştırıcıların foydalanish usuli farq qiladi. Ma'lumotlar tillarida, dasturni faylni o'qish vositasi sifatida ajratuvchi ko'pincha topiladi, masalan, HTML yoki XML matn; bu misollar belgilash tillari. Bo'lgan holatda dasturlash tillari, ajraladigan narsa a ning tarkibiy qismidir kompilyator yoki tarjimon, bu manba kodi a kompyuter dasturlash tili ichki vakillikning qandaydir shaklini yaratish; ajralish - bu asosiy qadamdir kompilyator frontend. Dasturlash tillari a nuqtai nazaridan aniqlanadi aniqlanadigan kontekstsiz grammatika chunki ular uchun tezkor va samarali tahlilchilar yozilishi mumkin. Kompilyatorlar uchun ajralishni o'zi bitta o'tish yoki bir nechta o'tish orqali amalga oshirish mumkin - qarang bir martalik kompilyator va ko'p o'tkazuvchan kompilyator.

Bir martalik kompilyatorning nazarda tutilgan kamchiliklarini, asosan, qo'shib qo'yish orqali bartaraf etish mumkin tuzatishlar, bu erda oldinga o'tish paytida kodni boshqa joyga ko'chirish ta'minlanadi va tuzatishlar dasturning amaldagi segmenti bajarilgan deb tan olingandan keyin orqaga qarab qo'llaniladi. Bunday tuzatish mexanizmi foydali bo'lishi mumkin bo'lgan misol, GOTO-ning maqsadi dastur segmenti tugamaguncha noma'lum bo'lgan oldinga yo'naltirilgan GOTO bayonoti bo'lishi mumkin. Bunday holda, tuzatishni qo'llash GOTO maqsadi tan olinmaguncha kechiktiriladi. Aksincha, orqada qolgan GOTO tuzatishni talab qilmaydi, chunki joylashuvi allaqachon ma'lum bo'ladi.

Kontekstsiz grammatikalar tilning barcha talablarini ifoda eta oladigan darajada cheklangan. Norasmiy ravishda, buning sababi shundaki, bunday tilning xotirasi cheklangan. Grammatika o'zboshimchalik bilan uzoq vaqt davomida konstruktsiya mavjudligini eslay olmaydi; bu til uchun zarurdir, unda, masalan, ism havola etilishidan oldin uni e'lon qilish kerak. Ushbu cheklovni ifoda eta oladigan yanada kuchli grammatikalarni samarali tahlil qilib bo'lmaydi. Shunday qilib, kerakli til konstruktsiyalarining yuqori to'plamini qabul qiladigan (ya'ni ba'zi bir yaroqsiz konstruktsiyalarni qabul qiladigan) kontekstsiz grammatika uchun bo'shashtiruvchi tahlilni yaratish odatiy strategiyadir; keyinchalik kiruvchi konstruktsiyalarni filtrlash mumkin semantik tahlil (kontekstli tahlil) bosqichi.

Masalan, ichida Python sintaktik jihatdan to'g'ri kod:

x = 1chop etish(x)

Quyidagi kod, ammo kontekstsiz grammatika nuqtai nazaridan sintaktik ravishda amal qiladi va oldingi tuzilishga ega bo'lgan sintaksis daraxtini beradi, ammo sintaktik jihatdan yaroqsiz kontekstga sezgir grammatika, bu o'zgaruvchini ishlatishdan oldin boshlashni talab qiladi:

x = 1chop etish(y)

Tahlil qilish bosqichida tahlil qilish o'rniga, buni tekshirish orqali ushlanadi qiymatlar sintaksis daraxtida, shuning uchun uning bir qismi sifatida semantik tahlil: kontekstga sezgir sintaksis amalda ko'pincha semantik sifatida osonroq tahlil qilinadi.

Jarayonga umumiy nuqtai

Oddiy ajraluvchida ma'lumotlar oqimi

Quyidagi misol kompyuter tilini grammatikaning ikki darajasi bilan tahlil qilishning keng tarqalgan holatini namoyish etadi: leksik va sintaktik.

Birinchi bosqich - bu nishonlarni yaratish yoki leksik tahlil, bu orqali kirish belgilar oqimi grammatikasi bilan belgilanadigan mazmunli belgilarga bo'linadi doimiy iboralar. Masalan, kalkulyator dasturi "" kabi yozuvni ko'rib chiqadi12 * (3 + 4)^2"va uni jetonlarga ajrating 12, *, (, 3, +, 4, ), ^, 2, ularning har biri arifmetik ifoda kontekstidagi mazmunli belgidir. Lekserda bu belgilarni aytib beradigan qoidalar mavjud edi *, +, ^, ( va ) yangi belgining boshlanishini belgilang, shuning uchun ma'nosiz belgilar "12*"yoki"(3"yaratilmaydi.

Keyingi bosqich - bu ajralish yoki sintaktik tahlil, bu belgilarning ruxsat etilgan ifodani hosil qilishini tekshiradi. Bu odatda a-ga ishora qilish orqali amalga oshiriladi kontekstsiz grammatika ifodani tashkil eta oladigan tarkibiy qismlarni va ular paydo bo'lish tartibini rekursiv ravishda belgilaydi. Biroq, dasturlash tillarini belgilaydigan barcha qoidalar faqatgina kontekstsiz grammatikalar bilan ifodalanishi mumkin emas, masalan, turdagi haqiqiylik va identifikatorlarni to'g'ri deklaratsiya qilish. Ushbu qoidalar rasmiy ravishda ifoda etilishi mumkin atribut grammatikalari.

Oxirgi bosqich semantik tahlil yoki tahlil qilish, bu faqat tasdiqlangan va tegishli choralarni ko'rgan ifodaning natijalarini ishlab chiqadi.[10] Kalkulyator yoki tarjimonga tegishli bo'lsa, harakat ifodani yoki dasturni baholashga qaratilgan; boshqa tomondan, kompilyator qandaydir kod yaratishi mumkin edi. Ushbu amallarni aniqlash uchun atributlar grammatikasidan ham foydalanish mumkin.

Sinov turlari

The vazifa ayrıştırıcının mohiyati, asosan grammatikaning boshlang'ich belgisidan qanday qilib olinishi mumkinligini aniqlash uchun. Bu asosan ikki usulda amalga oshirilishi mumkin:

  • Yuqoridan pastga qarab tahlil qilish - Yuqoridan pastga qarab tahlilni qidirish orqali kirish oqimining chap tomonidagi hosilalarini topishga urinish sifatida ko'rish mumkin. daraxtlarni tahlil qilish berilganning yuqoridan pastga kengayishidan foydalangan holda rasmiy grammatika qoidalar. Jetonlar chapdan o'ngga iste'mol qilinadi. Inklyuziv tanlov joylashtirish uchun ishlatiladi noaniqlik grammatik qoidalarning barcha muqobil o'ng tomonlarini kengaytirish orqali.[11] Bu ibtidoiy sho'rva usuli sifatida tanilgan. Gaplarni diagrammalashga juda o'xshash, ibtidoiy sho'rva jumlalarning tarkibiy qismlarini buzadi.[12]
  • Pastdan yuqoriga qarab tahlil qilish - Tahlilchi kirishdan boshlanishi va uni boshlash belgisiga qayta yozishga urinishi mumkin. Intuitiv ravishda tahlil qiluvchi eng asosiy elementlarni, so'ngra ularning tarkibiga kiradigan elementlarni va boshqalarni topishga harakat qiladi. LR tahlilchilari pastdan yuqoriga qarab tahlil qilishning namunalari. Ushbu turdagi tahlilchi uchun ishlatiladigan yana bir atama Shift-Reduce tahlil qilish.

LL tahlilchilari va rekursiv-nasldan ajratuvchi sig'dira olmaydigan yuqoridan pastga qarab ajratgichlarga misollar chap rekursiv ishlab chiqarish qoidalari. Yuqoridan pastga qarab tahlil qilishning sodda tatbiq etilishi to'g'ridan-to'g'ri va bilvosita chap rekursiyani sig'dira olmaydi va tahlil qilish paytida eksponent vaqt va makon murakkabligini talab qilishi mumkinligiga ishonishgan. noaniq kontekstsiz grammatikalar Frost, Hofiz va Callaghan tomonidan yuqoridan pastga qarab tahlil qilish uchun yanada murakkab algoritmlar yaratilgan.[13][14] joylashadigan noaniqlik va chap rekursiya polinom vaqtida va ajraladigan daraxtlarning potentsial eksponensial sonining polinom kattaligi ko'rinishini yaratadigan. Ularning algoritmi berilganga nisbatan kiritmaning eng chap va eng o'ng tomonlarini keltirib chiqarishga qodir kontekstsiz grammatika.

Tahlilchilarga nisbatan muhim farq - bu ajraluvchi a hosil qiladimi chap tomondagi hosila yoki a o'ng tomondan hosil qilish (qarang kontekstsiz grammatika ). LL tahlilchilari chap tomonni hosil qiladi hosil qilish va LR tahlilchilari to'g'ri derivatsiyani hosil qiladi (garchi odatda teskari bo'lsa ham).[11]

Biroz grafik tahlil qilish algoritmlari ishlab chiqilgan vizual dasturlash tillari.[15][16] Vizual tillar uchun tahlilchilar ba'zida asoslanadi grafik grammatikalar.[17]

Adaptiv tahlil algoritmlar "o'z-o'zini kengaytirish" ni tuzishda ishlatilgan tabiiy til foydalanuvchi interfeyslari.[18]

Dasturiy ta'minotni ishlab chiqish

Shuningdek qarang: ajralish generatorlarini taqqoslash

Ayrim taniqli tahlilchilarni ishlab chiqish vositalariga quyidagilar kiradi:

Qarang

C 2 belgidan pastroq ko'rinish bilan ajratib bo'lmaydigan dastur. Top: C grammatikasi parchasi.[19] Pastki: parser nishonlarni hazm qildi "int v;asosiy(){"va kelib chiqadigan qoidani tanlash haqida Stmt. Faqat birinchi qarashli belgiga qarab "v", ikkala alternativaning qaysi biri uchun qaror qabul qila olmaydi Stmt tanlamoq; ikkinchisi ikkinchi nishonga qarashni talab qiladi.

Lookahead parser qaysi qoidani ishlatishi kerakligini hal qilish uchun foydalanishi mumkin bo'lgan maksimal kiruvchi belgilarni o'rnatadi. Lookahead ayniqsa dolzarbdir LL, LR va LALR tahlilchilari, bu erda LALR (1) kabi qavs ichida algoritm nomiga tashqi ko'rinishini yopish orqali aniq ko'rsatiladi.

Ko'pchilik dasturlash tillari, tahlilchilarning asosiy maqsadi, cheklangan ko'rinishga ega bo'lgan tahlilchi, odatda, ularni ajrata oladigan tarzda diqqat bilan aniqlangan, chunki cheklangan ko'rinishga ega bo'lgan ajraluvchilar ko'pincha samaraliroq. Bir muhim o'zgarish[iqtibos kerak ] ushbu tendentsiya 1990 yilda paydo bo'lgan Terens Parr yaratilgan ANTLR doktorlik dissertatsiyasi uchun tezis, a ajralish generatori samarali LL uchun (k) tahlilchilar, qaerda k har qanday belgilangan qiymatdir.

LR tahlilchilari odatda har bir belgini ko'rgandan keyin faqat bir nechta harakatlarga ega. Ular siljish (keyinchalik qisqartirish uchun ushbu belgini stekka qo'shish), kamaytirish (to'plamdan pop-tokenlarni to'plash va sintaktik konstruktsiyani shakllantirish), tugatish, xato (ma'lum bir qoida qo'llanilmaydi) yoki ziddiyat (siljitish yoki kamaytirish kerakligini bilmaydi) .

Lookaheadning ikkita afzalligi bor.[tushuntirish kerak ]

  • Bu qarama-qarshiliklar yuzaga kelganda tahlilchiga to'g'ri choralarni ko'rishga yordam beradi. Masalan, else bandidagi if ifodasini tahlil qilish.
  • Bu ko'plab takrorlanadigan holatlarni yo'q qiladi va qo'shimcha stackning yukini engillashtiradi. Boshqaruvsiz C tilidagi tahlilchi taxminan 10 ming holatga ega bo'ladi. Tashqi ko'rinishdagi tahlilchi 300 ga yaqin shtatdan iborat bo'ladi.

Misol: ifodani tahlil qilish 1 + 2 * 3[shubhali – muhokama qilish]

Ifodalarni tahlil qilish qoidalari to'plami (grammatika deb ataladi) quyidagicha,
1-qoida:E → E + EIfoda - bu ikkita ifodaning yig'indisi.
2-qoida:E → E * EIfoda ikki iboraning hosilasi.
Qoida3:E → raqamIfoda oddiy raqam
4-qoida:+ ning ustunligi * ga qaraganda kamroq

Ko'pgina dasturlash tillari (APL va Smalltalk kabi ba'zi tillardan tashqari) va algebraik formulalar ko'paytirishga qo'shilishdan yuqori ustunlik beradi, bu holda yuqoridagi misolning to'g'ri talqini 1 + (2 * 3).Yuqoridagi 4-qoida semantik qoidalar ekanligini unutmang. Buni sintaksisga kiritish uchun grammatikani qayta yozish mumkin. Biroq, bunday qoidalarning hammasini ham sintaksisga aylantirish mumkin emas.

Oddiy ko'rinmaydigan tahlilchi harakatlari

Dastlab Kiritish = [1, +, 2, *, 3]

  1. "1" qiymatini kirishdan stakka o'tkazing (qoida3 ga binoan). Kiritish = [+, 2, *, 3] Stack = [1]
  2. Qoida3 asosida "1" ni "E" ifodasiga kamaytiradi. Yig'ma = [E]
  3. "+" Tugmachasini kirishdan stakka o'tkazing (qoida1 kutib turib). Kiritish = [2, *, 3] Stack = [E, +]
  4. "2" qiymatini kirishdan stakka o'tkazing (qoida3 ga binoan). Kiritish = [*, 3] Stack = [E, +, 2]
  5. Qoidalar3 asosida "2" to'plam elementini "E" ifodasiga kamaytiring. Stack = [E, +, E]
  6. Qoidalar asosida [E, +, E] va yangi "E" yozuvini "E" ga kamaytiring. Yig'ma = [E]
  7. "*" Tugmachasini kirishdan stakka o'tkazing (qoida2 ni kutib). Kiritish = [3] Stack = [E, *]
  8. "3" qiymatini kirishdan stakka o'tkazing (qoida3 ni kutib). Kiritish = [] (bo'sh) Stack = [E, *, 3]
  9. Stack elementi "3" ni qoidaga asosan "E" ifodasiga kamaytiring. Stack = [E, *, E]
  10. Qoidalar asosida [E, *, E] va yangi "E" yozuvini "E" ga kamaytiring. Yig'ma = [E]

Til semantikasi bo'yicha tahlil daraxti va undan olingan kod to'g'ri emas.

Ko'zsiz to'g'ri tahlil qilish uchun uchta echim mavjud:

  • Foydalanuvchi iboralarni qavs ichiga kiritishi kerak. Bu ko'pincha foydali echim emas.
  • Tahlilchi qoida buzilgan yoki to'liq bo'lmaganda orqaga qaytish va qaytadan urinish uchun ko'proq mantiqqa ega bo'lishi kerak. Shunga o'xshash usul LL tahlilchilarida qo'llaniladi.
  • Shu bilan bir qatorda, tahlilchi yoki grammatika kamaytirishni kechiktirish va kamaytirish uchun qo'shimcha mantiqqa ega bo'lishi kerak, faqat avval qaysi qoidani kamaytirish kerakligiga ishonch hosil bo'lganda. Ushbu usul LR tahlilchilarida qo'llaniladi. Bu iborani to'g'ri tahlil qiladi, lekin yana ko'p holatlarda va chuqurlik chuqurligini oshiradi.
Qarashni tahlil qiluvchi harakatlar[tushuntirish kerak ]
  1. Qoida3 ni kutib, 1 kirishidagi stackga 1 ni almashtiring. Bu darhol kamaymaydi.
  2. Stack 1-elementni input3-ga oddiy ifodaga kamaytiring + qoida asosida. Tashqi ko'rinish +, shuning uchun biz E + ga boramiz, shuning uchun biz stakani E ga kamaytiramiz.
  3. Shift + qoida1 ga binoan kirish + ustiga stakka.
  4. Qoida3 ni kutib, 2-kirishdagi stekka 2-ni siljiting.
  5. Stack 2-bandni qoida bo'yicha ifodaga kamaytiring * qoida3 asosida. Tashqi ko'rinish * undan oldin faqat E kutadi.
  6. Endi stack E + E ga ega va hali ham kirish *. Endi qoida2 asosida siljish yoki qoidalar asosida qisqartirish uchun ikkita tanlov mavjud. * Qoida4 ga asoslangan + ustunligi yuqori bo'lganligi sababli, qoida2 ni kutib * stackga o'tamiz.
  7. 3-qoidani kutib, 3-sonli kirishni stakka 3 ga o'tkazing.
  8. Qoidalar 3 asosida kiritishni oxirini ko'rgandan keyin stack 3-elementni Expression-ga kamaytiring.
  9. Qoidalar asosida E * E dan E gacha bo'lgan stack elementlarini kamaytiring.
  10. Qoida1 asosida E + E dan E gacha bo'lgan stack elementlarini kamaytiring.

Yaratilgan daraxt daraxti to'g'ri va sodda yanada samarali[oydinlashtirish ][iqtibos kerak ] tashqi ko'rinishga ega bo'lmagan tahlilchilarga qaraganda. Bu ta'qib qilingan strategiya LALR tahlilchilari.

Shuningdek qarang

Adabiyotlar

  1. ^ a b "Ajratish". dictionary.reference.com. Olingan 27 noyabr 2010.
  2. ^ Masaru Tomita (2012 yil 6-dekabr). Umumiy LR tahlil qilish. Springer Science & Business Media. ISBN  978-1-4615-4034-2.
  3. ^ "Grammatika va kompozitsiya".
  4. ^ Kristofer D .. Manning; Kristofer D. Manning; Xinrix Shutze (1999). Statistik tabiiy tilni qayta ishlash asoslari. MIT Press. ISBN  978-0-262-13360-9.
  5. ^ Jurafskiy, Daniel (1996). "Leksik va sintaktik kirish va nomutanosiblikning taxminiy modeli". Kognitiv fan. 20 (2): 137–194. CiteSeerX  10.1.1.150.5711. doi:10.1207 / s15516709cog2002_1.
  6. ^ Klein, Dan va Kristofer D. Manning. "To'g'ri aniqlanmagan tahlil. "Kompyuter lingvistikasi assotsiatsiyasi bo'yicha 41-yillik yig'ilish materiallari. 1-jild. Kompyuter lingvistikasi assotsiatsiyasi, 2003 yil.
  7. ^ Charniak, Evgeniya. "Maksimal entropiya ilhomlantiruvchi tahlilchi. "Hisoblash lingvistik assotsiatsiyasi konferentsiyasining 1-Shimoliy Amerika bo'limining materiallari. Hisoblash lingvistikasi assotsiatsiyasi, 2000 yil.
  8. ^ Chen, Danqi va Kristofer Manning. "Neyron tarmoqlaridan foydalangan holda tez va aniq bog'liqlikni tahlil qiluvchi. "Tabiiy tilni qayta ishlashda empirik usullar bo'yicha 2014 yilgi konferentsiya materiallari (EMNLP). 2014 yil.
  9. ^ Jia, Robin; Liang, Persi (2016-06-11). "Neyronal semantik tahlil qilish uchun ma'lumotlarning rekombinatsiyasi". arXiv:1606.03622 [cs.CL ].
  10. ^ Berant, Jonatan va Persi Liang. "Parafrazing orqali semantik tahlil. "Hisoblash lingvistikasi assotsiatsiyasining 52-yillik yig'ilishi materiallari (1-jild: Uzoq hujjatlar). 2014 yil.
  11. ^ a b Aho, A.V., Seti, R. va Ullman, JD (1986) "Tuzuvchilar: printsiplar, metodlar va vositalar". Addison-Uesli Longman Publishing Co., Inc. Boston, MA, AQSh.
  12. ^ Sikkel, Klaas, 1954- (1997). Sxemalarni tahlil qilish: algoritmlarni tahlil qilish va tahlil qilish uchun asos. Berlin: Springer. ISBN  9783642605413. OCLC  606012644.CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)
  13. ^ Frost, R., Hofiz, R. va Kallagan, P. (2007) " Ikki tomonlama chap-rekursiv grammatikalar uchun yuqoridan pastga modulli va samarali tahlil qilish ." Ayrilish texnologiyalari bo'yicha 10-Xalqaro seminar (IWPT), ACL-SIGPARSE , Sahifalar: 109 - 120, 2007 yil iyun, Praga.
  14. ^ Frost, R., Hofiz, R. va Kallagan, P. (2008) " Aniq bo'lmagan chap-rekursiv grammatikalar uchun tahlil qiluvchi kombinatorlar." Deklarativ tillarning amaliy jihatlari bo'yicha 10-Xalqaro simpozium (PADL), ACM-SIGPLAN , Jild 4902/2008, Sahifalar: 167 - 181, 2008 yil yanvar, San-Frantsisko.
  15. ^ Rekers, Jan va Endi Shyurr. "Vizual tillarni qatlamli grafik grammatikalari bilan aniqlash va tahlil qilish. "Vizual tillar va hisoblash jurnali 8.1 (1997): 27-55.
  16. ^ Rekers, Jan va A. Schurr. "Grafik tahlil qilish uchun grafik grammatik yondashuv. "Vizual tillar, ma'lumotlar. IEEE 11-Xalqaro simpoziumi. IEEE, 1995 y.
  17. ^ Chjan, Da-Tsian, Kang Chjan va Tszyannong Cao. "Vizual tillarni spetsifikatsiyasi uchun kontekstga sezgir grafik grammatikasi formalizmi. "Computer Journal 44.3 (2001): 186-200.
  18. ^ Jil Fayn Lehman (2012 yil 6-dekabr). Adaptiv ajralish: O'z-o'zidan kengayadigan tabiiy til interfeyslari. Springer Science & Business Media. ISBN  978-1-4615-3622-2.
  19. ^ olingan Brayan V. Kernigan va Dennis M. Ritchi (1988 yil aprel). C dasturlash tili. Prentice Hall dasturiy ta'minot seriyasi (2-nashr). Englewood Cliffs / NJ: Prentice Hall. ISBN  0131103628. (Qo'shimcha A.13 "Grammatika", p.193 ff)

Qo'shimcha o'qish

Tashqi havolalar