LL parser — inputni chapdan o‘ngga o‘qib, uning chapmost derivationini quradigan top-down parserlar oilasidir. Birinchi L left-to-right scanningni, ikkinchisi leftmost derivationni bildiradi. LL(k) parser production tanlash uchun oldindagi k tokenni ko‘radi; amaliy qo‘lda yozilgan recursive-descent parser ko‘pincha LLga yaqin ishlaydi.
Top-down ishlash
Parser start symboldan boshlaydi va joriy nonterminal uchun lookahead token asosida production tanlaydi. Production o‘ng tomonidagi symbol ketma-ket parse qilinadi. Terminal input tokeniga mos kelmasa syntax error yuz beradi.
Recursive descentda har nonterminal alohida funksiya bo‘lishi mumkin. Funksiya token streamdan o‘qib, AST node qaytaradi. Bunday kodni debug va custom diagnostic bilan boyitish oson.
FIRST va FOLLOW
FIRST to‘plami productiondan boshlanishi mumkin bo‘lgan terminallarni, FOLLOW esa nonterminaldan keyin kelishi mumkin bo‘lgan tokenlarni bildiradi. Nullable production bo‘lsa FOLLOW production tanlashda zarur. Predictive parse table shu to‘plamlardan quriladi.
Bir jadval katagiga bir nechta production tushsa grammar berilgan LL(k) uchun conflictga ega. Grammarni left factoring qilish yoki til qoidasini qayta yozish conflictni bartaraf etishi mumkin.
Left recursion
Expr -> Expr + Term kabi direct left recursion recursive-descent parserda cheksiz recursion keltiradi. Grammar Expr -> Term ExprTail va takroriy tail shakliga o‘zgartiriladi. Indirect left recursion bir nechta nonterminal orqali qaytadi va aniqlash qiyinroq.
Left recursionni olib tashlash parse tree shaklini o‘zgartirishi mumkin. Semantic action associativityni to‘g‘ri saqlashi kerak. Parser combinator librarylarining ayrimi memoization yoki maxsus algoritm bilan left recursionni qo‘llashi mumkin.
Precedence
Expression parser precedence darajalarini alohida function bilan yozishi mumkin: primary, unary, multiplicative va additive. Pratt parser top-down bo‘lsa ham binding power orqali operatorlarni ixcham boshqaradi va klassik table-driven LLdan farq qiladi.
Grammar readability va error xabari uchun qavs, postfix va prefix holatlari aniq ajratiladi. Overloaded operatorning semantik tanlovi keyingi type analysisga qoladi.
Error recovery
Predictive parser expected tokenlar to‘plamini yaxshi biladi. Panic mode semicolon yoki closing brace kabi FOLLOW tokenigacha inputni tashlab, keyingi statementdan davom etadi. Bitta missing token uchun insertion recovery ko‘p cascading xatoni kamaytirishi mumkin.
IDE parser incomplete source’da tree yaratishi uchun error node qo‘shadi. Recovery inputni iste’mol qilmasdan bir holatda qolib ketmasligi uchun progress kafolati bo‘ladi.
Afzallik va chegara
LL parserning control flow’i grammar tuzilishiga yaqin, qo‘lda yozish va aniq diagnostic berish qulay. Biroq left-recursive yoki common prefixi katta grammar transformatsiya talab qiladi. LR parser ayrim programming-language grammarlari uchun kengroq sinfni bevosita qabul qiladi.
Packrat va backtracking
Backtracking recursive descent bir production muvaffaqiyatsiz bo‘lsa inputni qaytarib boshqasini sinaydi. Prefixlar uzun bo‘lsa bir token bir necha marta parse qilinib exponential vaqt yuz berishi mumkin. Memoizationli packrat parsing natijani position va rule bo‘yicha cache qilib, ko‘pincha chiziqli vaqt beradi.
Cache xotira sarfini oshiradi va semantic predicate purity talab qiladi. Ordered choice grammarda birinchi mos variantni tanlashi ambiguityni yashirishi mumkin. Grammar yozuvchisi variant tartibining semantikasini tushunadi. Predictive LL table esa conflictni generation vaqtida ko‘rsatib, backtrackingga tayanmaydi. Ikkala yondashuvni “LL” deb bir xil deb qarash noaniqlik tug‘diradi.
Bog‘liq tushunchalar
Recursive descent parser, Predictive parsing, FIRST set, FOLLOW set, Left recursion, LR parser, Grammar