Parser — tokenlar ketma-ketligini grammar qoidalariga ko‘ra tahlil qilib, ularning tuzilishini aniqlaydigan dasturiy komponent.
Compiler pipeline’da parser lexer bergan tokenlardan parse tree yoki Abstract Syntax Tree hosil qiladi.
Parser faqat dasturlash tillarida emas, configuration, SQL, markup, network protocol va data formatlarda ham ishlatiladi.
Parser inputi
Parser odatda raw belgilar bilan emas, lexer ishlab chiqargan tokenlar bilan ishlaydi.
Misol source:
total = price + tax
Tokenlar:
IDENTIFIER(total)
EQUAL
IDENTIFIER(price)
PLUS
IDENTIFIER(tax)
Parser bu ketma-ketlik assignment va addition tuzilmasi ekanini aniqlaydi.
Grammar
Parser til grammar’siga tayanadi.
Soddalashtirilgan qoida:
assignment → IDENTIFIER "=" expression
expression → term ("+" term)*
term → IDENTIFIER | NUMBER
Grammar qaysi token qayerda kelishi mumkinligini belgilaydi.
Parse tree
Parse tree grammar qoidalarining to‘liq qo‘llanishini ko‘rsatadi.
Unda:
saqlanadi.
Parser generator va grammar debugging uchun foydali.
AST
Compiler ko‘pincha parse tree’dan ixcham AST hosil qiladi.
price + tax uchun:
Add
├── Name(price)
└── Name(tax)
Qavs va ayrim syntax tokenlar ASTda alohida node bo‘lmasligi mumkin.
Top-down parser
Top-down parser eng yuqori grammar qoidasidan boshlanib inputga mos tuzilma quradi.
Turlari:
- recursive descent;
- predictive parser;
- LL parser;
- PEG parser.
U source strukturasini tabiiy functionlar bilan ifodalashi mumkin.
Recursive descent
Har grammar qoidasi alohida function sifatida yoziladi.
Masalan:
parseExpression()
parseTerm()
parsePrimary()
Afzalliklari:
- tushunarli;
- qo‘lda yozish oson;
- yaxshi xato xabari;
- maxsus logic qo‘shish qulay.
Left recursion to‘g‘ridan-to‘g‘ri muammo tug‘diradi va grammar qayta yoziladi.
LL parser
LL parser inputni chapdan o‘ngga o‘qib, leftmost derivation quradi.
LL(k) keyingi k token orqali qaror qiladi.
Grammar:
- left recursion’siz;
- yetarli lookahead;
- factoring
talab qilishi mumkin.
Bottom-up parser
Bottom-up parser tokenlardan boshlanib ularni yuqori grammar konstruktsiyalariga birlashtiradi.
Turlari:
- LR;
- LALR;
- SLR;
- GLR.
U murakkab grammarlarni qabul qilishi mumkin, ammo parse table va conflictlarni tushunish qiyinroq.
Shift-reduce
LR parser ikki asosiy amal bajaradi:
- shift — keyingi tokenni stackka oladi;
- reduce — token yoki node’larni grammar qoidasiga birlashtiradi.
Shift/reduce conflict parser bir holatda tokenni olish yoki reduce qilishni tanlay olmaganda yuz beradi.
Precedence va associativity bilan hal qilinishi mumkin.
Lookahead
Parser qaror qilish uchun keyingi tokenlarni ko‘radi.
Masalan, identifierdan keyin ( bo‘lsa function call, = bo‘lsa assignment bo‘lishi mumkin.
Juda ko‘p lookahead grammarni murakkab va sekin qiladi.
Ambiguity
Bitta token ketma-ketligi bir nechta parse tree bersa grammar ambiguous.
Klassik misol — nested if bilan else qaysi ifga tegishli.
Til specificationi nearest if qoidasi yoki block syntax bilan ambiguity’ni yo‘qotadi.
Operator precedence
Arithmetic grammar noto‘g‘ri yozilsa:
2 + 3 * 4
ikki xil parse bo‘lishi mumkin.
Precedence hierarchy:
expression → addition
addition → multiplication ("+" multiplication)*
multiplication → primary ("*" primary)*
orqali multiplication yuqoriroq qilinadi.
Pratt parser
Pratt parser expressionlarni precedence va associativity asosida ixcham tahlil qiladi.
Har token prefix yoki infix parse functionga ega bo‘lishi mumkin.
Ko‘p operatorli expression grammar uchun qulay.
Parser generator
Grammar specificationdan parser code avtomatik yaratiladi.
Generator:
hosil qiladi.
Generated parser qo‘lda yozilgan lexer, AST builder va error handling bilan integratsiya qilinadi.
Error xabari
Yaxshi parser xatosi:
- aniq joy;
- topilgan token;
- kutilgan konstruksiya;
- qisqa context;
- mumkin bo‘lgan tuzatish
ni ko‘rsatadi.
Faqat “parse error” developerga kam ma’lumot beradi.
Error recovery
Parser bitta xatodan keyin davom etib boshqa xatolarni topishga urinadi.
Usullar:
- semicolon yoki newline’gacha o‘tish;
- yopuvchi qavsni qidirish;
- tokenni tashlash;
- token qo‘shilgan deb taxmin qilish;
- error production.
Recovery noto‘g‘ri bo‘lsa ko‘p yolg‘on xato paydo bo‘ladi.
Incremental parsing
Code editor har tugma bosilganda butun faylni qayta parse qilmasligi mumkin.
Incremental parser faqat o‘zgargan region va ta’sirlangan parent node’larni yangilaydi.
Bu katta faylda syntax highlighting va diagnosticsni tezlashtiradi.
Streaming parser
Katta JSON, XML yoki log faylni to‘liq xotiraga yuklamasdan token va eventlarni ketma-ket qayta ishlaydi.
Streaming parser:
- start element;
- field;
- value;
- end element
hodisalarini beradi.
Random access qiyin, xotira sarfi kichik.
Security
Untrusted input parserga hujum qilishi mumkin.
Xavflar:
- chuqur nesting va stack overflow;
- juda katta token;
- exponential grammar;
- integer overflow;
- malformed length;
- parser differential;
- resource exhaustion.
Depth, size va vaqt limitlari qo‘yiladi.
Parser combinator
Kichik parserlar function sifatida birlashtirilib katta grammar yaratilishi mumkin. sequence, choice, many va optional kabi combinatorlar declarative tuzilma beradi. Backtracking va error message performance’i library dizayniga bog‘liq.
Packrat parsing
PEG parser oldingi rule natijalarini input pozitsiyasi bo‘yicha cache qilsa packrat parsing hosil bo‘ladi. Bu ko‘p backtracking holatini linear vaqtga yaqinlashtiradi, ammo xotira sarfini oshiradi.
Parser differential
Ikki parser bir xil noto‘g‘ri inputni turlicha talqin qilsa security boundary buzilishi mumkin. Proxy va backend, validator va runtime bir xil canonical parsing qoidalariga tayanishi kerak.
Bog‘liq tushunchalar
Grammar, Lexer, Token, Parse tree, AST, Recursive descent, LL parser, LR parser, Error recovery, Incremental parsing