LR parser — inputni chapdan o‘ngga o‘qib, rightmost derivationning teskarisini bottom-up usulda quradigan deterministic parserlar oilasidir. U shift va reduce amallari orqali tokenlardan katta grammar konstruksiyalarini hosil qiladi. LR grammarlari ko‘plab programming-language syntaxlarini left recursionni olib tashlamasdan ifodalay oladi.
Shift-reduce mexanizmi
Parser stackda state va grammar symbollarini saqlaydi. shift keyingi tokenni stackka olib, yangi statega o‘tadi. reduce stack tepasidagi production o‘ng tomonini nonterminal chap tomoni bilan almashtiradi. accept start production tugaganini bildiradi.
Action table joriy state va lookahead uchun shift, reduce, accept yoki errorni tanlaydi. Goto table reductiondan keyingi nonterminal uchun yangi state beradi. Table parser generator tomonidan grammar itemlari automatonidan quriladi.
LR variantlari
LR(0) lookaheadsiz ishlaydi va grammarlari cheklangan. SLR FOLLOW to‘plami bilan reductionni toraytiradi. Canonical LR(1) har itemga lookahead qo‘shib kuchliroq, ammo table katta bo‘lishi mumkin. LALR(1) o‘xshash state’larni birlashtirib table hajmini kamaytiradi va ko‘p klassik parser generatorlarda ishlatiladi.
State birlashtirish ayrim LR(1) grammarni LALR conflictga aylantirishi mumkin. Zamonaviy generatorlar canonical yoki IELR kabi variantni taklif qilishi mumkin. Qaysi algoritm ishlatilgani diagnostic va grammar imkoniga ta’sir qiladi.
Conflict
Shift/reduce conflict parser tokenni olish yoki productionni reduce qilish orasida ikkilanayotganini bildiradi. Expression grammarida precedence va associativity deklaratsiyasi konfliktni hal qilishi mumkin. Reduce/reduce conflict ikki production bir xil joyda yakunlanishi mumkinligini ko‘rsatadi va ko‘pincha grammar ambiguity yoki ortiqcha qoidani bildiradi.
Generator default shift tanlashi mumkin, lekin warningni ko‘r-ko‘rona bostirish xavfli. Expected conflict, masalan dangling else, hujjatlashtiriladi va test bilan mustahkamlanadi.
Semantic action
Reduction paytida o‘ng tomondagi qiymatlardan AST node yoki boshqa semantic value quriladi. Action ichida ko‘p business logic yozish parserni testlashni qiyinlashtiradi; tree qurish va semantic analysisni ajratish ma’qul.
Source span birinchi va oxirgi token pozitsiyasidan olinadi. Empty production uchun location policy aniq bo‘ladi. Memory ownership va error yo‘lida stackdagi semantic value’larni tozalash C/C++ generatorlarda muhim.
Error recovery
Maxsus error symbol grammar’da recovery nuqtasini belgilashi mumkin. Parser stackdan state chiqarib, error tokenni qabul qiladigan holat topadi va synchronizationgacha token tashlaydi. Recovery tree’da error node saqlab, keyingi analizni davom ettiradi.
LR table expected tokenlarni chiqarishi mumkin, ammo ro‘yxat foydalanuvchi uchun juda katta bo‘lishi mumkin. Custom context va eng ehtimoliy fix diagnosticni yaxshilaydi.
Table va runtime
Parse table generated source, compact binary yoki runtime structure sifatida saqlanishi mumkin. Compression default action va sparse row orqali hajmni kamaytiradi, lekin diagnostic uchun full transition ma’lumoti kerak bo‘lishi mumkin. Generator va runtime versioni mos keladi.
Parser stack input uzunligi bilan o‘sishi mumkin; chuqur nesting va malicious token stream uchun limit zarur. Incremental LR parsing editdan ta’sirlangan regionni qayta parse qilishga urinadi, ammo stack state va contextni tiklash murakkab. Generalized LR conflict paytida bir nechta stackni parallel yuritib ambiguous grammarni qabul qiladi, keyin parse forestni disambiguation qiladi.
Bog‘liq tushunchalar
Shift-reduce parser, LALR parser, Parser generator, Grammar conflict, Parse table, LL parser, Bottom-up parsing