Parse tree — tokenlar ketma-ketligining formal grammar qoidalariga qanday mos kelganini iyerarxik ko‘rsatadigan daraxtdir. Daraxt ildizi start symbolni, ichki node’lar nonterminal grammar kategoriyalarini, barglar esa token yoki terminallarni ifodalaydi. U parserning source tuzilishini tanlaganini aniq ko‘rsatadi va keyingi semantic analysis uchun asos yaratadi.
Grammar bilan qurilish
Masalan, expression grammar addition va multiplication uchun alohida qoidaga ega bo‘lsa, 2 + 3 * 4 daraxti multiplicationni additionning o‘ng qismida joylashtiradi. Shu tuzilma operator precedence’ni ifodalaydi. Qavslar boshqa production tanlatib, daraxtni o‘zgartiradi.
Har derivation step nonterminalni productionning o‘ng tomoni bilan almashtiradi. Leftmost va rightmost derivation turli tartibda ishlasa ham unambiguous grammar bir xil parse tree beradi.
Concrete va abstract tree
Concrete syntax tree punctuation, keyword va grammar qatlamlarini to‘liq saqlaydi. Abstract Syntax Tree esa qavs va yordamchi nonterminal kabi semantikaga keraksiz elementlarni olib tashlab, operation hamda operandni ixcham ifodalaydi. Compiler ko‘pincha AST bilan ishlaydi.
Formatter yoki source-to-source refactoring whitespace va commentni saqlashi kerak bo‘lsa concrete yoki lossless syntax tree foydali. AST original formattingni qayta tiklash uchun yetarli bo‘lmasligi mumkin.
Ambiguity
Ambiguous grammar bitta token ketma-ketligi uchun bir nechta parse tree beradi. Dangling else va precedence berilmagan expression bunga klassik misol. Parser generator conflict ko‘rsatishi yoki precedence declaration orqali bittasini tanlashi mumkin.
Til spetsifikatsiyasi ambiguityni grammar yoki alohida disambiguation qoidasi bilan bartaraf etadi. Parserning tasodifiy default tanloviga tayanish portability va tushunishni yomonlashtiradi.
Parser turlari
LL parser leftmost derivationni top-down quradi va lookahead bilan production tanlaydi. LR parser bottom-up ishlaydi, handlelarni reduce qilib rightmost derivationning teskarisini hosil qiladi. Ikkalasi tree yoki semantic action natijasini yaratishi mumkin.
Generalized parser ambiguous yoki keng grammar uchun parse forest yaratishi mumkin. Parse forest umumiy subtree’larni bo‘lishib, barcha variantni ixcham saqlaydi. Keyingi semantic yoki precedence qoidasi kerakli variantni tanlaydi.
Amaliy ishlatish
Syntax highlighting, code navigation, linter, refactoring va query language parse treega tayanadi. Node source span bilan bog‘langan bo‘lsa diagnostic aniq qator va ustunni ko‘rsatadi. Incremental parser kichik editdan keyin o‘zgarmagan subtree’larni qayta ishlatadi.
Untrusted source juda chuqur nesting bilan parser stackini to‘ldirishi mumkin. Depth, token soni va recovery limitlari qo‘llanadi. Tree node’larida raw user textni keyin HTMLga chiqarishda escaping zarur.
Tree traversal
Visitor pattern node turlarini aylanib, symbol yig‘ish, lint yoki code generationni bajaradi. Recursive traversal chuqur tree’da stack overflow qilishi mumkin; iterative stack yoki depth limit ishlatiladi. Parent pointer qulay, ammo ownership cycle va memory sarfini oshirishi mumkin.
Tree transform immutable node bilan yangi subtree qaytarishi yoki mutable node’ni joyida o‘zgartirishi mumkin. Source span va comment association transformdan keyin saqlanishi kerak. Structural sharing incremental compilerda o‘zgarmagan subtree’larni reuse qiladi. Node ID faqat process ichida barqaror bo‘lsa uni persistent cache yoki cross-run reference sifatida ishlatish mumkin emas.
Parse tree’ni serialize qilishda grammar versiyasi metadata sifatida yoziladi. Eski grammar bilan yaratilgan node turlari yangi consumerga noma’lum bo‘lishi mumkin; migration yoki qayta parsing bu nomuvofiqlikni boshqaradi.
Bog‘liq tushunchalar
Grammar, Parser, Abstract Syntax Tree, Concrete syntax tree, LL parser, LR parser, Derivation