AST

AST — source code yoki formal ifodaning grammatik tuzilishini abstrakt daraxt ko‘rinishida ifodalovchi ma’lumotlar tuzilmasi. Uning to‘liq nomi Abstract Syntax Tree hisoblanadi.

AST parser natijasida yaratiladi va compiler, interpreter, linter, formatter, IDE hamda code transformation vositalari uchun asosiy ichki model vazifasini bajaradi.

Abstraktlik

AST concrete syntaxdagi barcha belgilarni saqlamaydi.

Masalan:

a + b * c

AST:

Add
├── Name(a)
└── Multiply
    ├── Name(b)
    └── Name(c)

Qavs yoki operator precedence alohida qoida sifatida emas, daraxt tuzilmasining o‘zida aks etadi.

Parse tree bilan farqi

Parse tree grammar qoidalarining barcha bosqichlarini saqlaydi.

AST esa compiler uchun muhim semantik tuzilmani qoldiradi.

Parse tree’da:

expression;
term;
factor;
punctuation;
yordamchi non-terminal

ko‘p bo‘lishi mumkin.

ASTda ular Add, Multiply, Literal kabi aniq node’larga qisqaradi.

Node

Har AST node ma’lum konstruksiyani ifodalaydi.

Misollar:

Program;
FunctionDeclaration;
VariableDeclaration;
IfStatement;
Loop;
CallExpression;
BinaryExpression;
Identifier;
Literal;
ReturnStatement.

Node child node’lar va metadata saqlaydi.

Source location

AST node original source joyini saqlashi mumkin:

file;
boshlanish qatori;
tugash qatori;
ustun;
byte offset.

Bu error message, debugger, formatter va source map uchun kerak.

Generated node source locationga ega bo‘lmasligi yoki synthetic belgi olishi mumkin.

Expression AST

Misol:

result = 2 + 3 * 4

Daraxt:

Assignment
├── Target: Name(result)
└── Value: Add
    ├── Literal(2)
    └── Multiply
        ├── Literal(3)
        └── Literal(4)

Operator precedence parser tomonidan to‘g‘ri tuzilma sifatida joylashtirilgan.

Statement AST

Control flow konstruksiyasi childlar orqali ifodalanadi.

IfStatement
├── Condition
├── ThenBlock
└── ElseBlock

Compiler keyin control-flow graph yaratishi mumkin.

Semantic analysis

Parser AST yaratgach, semantic bosqich:

symbol resolution;
scope;
type checking;
overload;
access;
definite assignment;
constant evaluation

bajaradi.

Node’larga inferred type yoki symbol reference biriktirilishi mumkin.

Symbol table

Identifier node faqat "count" matnini saqlaydi.

Semantic analysis uning qaysi declarationga tegishli ekanini symbol table orqali topadi.

Bir xil nom:

local variable;
field;
global;
imported symbol

bo‘lishi mumkin.

Resolved AST aniq symbol identityga ega bo‘ladi.

AST traversal

Daraxtni yurish usullari:

depth-first;
pre-order;
post-order;
visitor;
recursive function;
iterative stack.

Har node turi uchun alohida handler bo‘lishi mumkin.

Linter AST traversal orqali patternlarni topadi.

Visitor pattern

Visitor node classlarini o‘zgartirmasdan yangi operation qo‘shadi.

Masalan:

type checker;
pretty printer;
code generator;
dependency collector.

Visitor hierarchy yangi node turi qo‘shilganda barcha visitorlarni yangilashni talab qilishi mumkin.

AST transformatsiyasi

Transpiler va compiler optimization ASTni o‘zgartiradi.

Misollar:

constant folding;
syntactic sugarni ochish;
optional chainingni shartlarga aylantirish;
async/await transformatsiyasi;
macro expansion;
instrumentation;
import rewrite.

Transformatsiya source semanticsni saqlashi kerak.

Constant folding

2 + 3

compile vaqtida:

literaliga aylantirilishi mumkin.

Side effect yoki overflow semantics mavjud bo‘lsa, folding til qoidalariga aynan mos bajariladi.

AST va IR

AST source til tuzilmasiga yaqin.

Compiler keyinchalik pastroq darajadagi Intermediate Representation yaratadi.

IR:

explicit control flow;
temporary variable;
SSA;
machinega yaqin operation

bilan optimization uchun qulay.

AST va IR chegarasi compiler dizayniga bog‘liq.

Concrete syntax tree

Formatter comment, whitespace va original quote uslubini saqlashi kerak.

Oddiy AST bu detallarni yo‘qotadi.

Shu sababli formatter:

CST;
lossless syntax tree;
token stream;
trivia

dan foydalanishi mumkin.

Linter

Linter AST orqali:

ishlatilmagan variable;
unreachable code;
xavfli API;
murakkab expression;
naming;
deprecated method

ni aniqlaydi.

Faqat text regex bilan bunday tahlil ko‘p false positive beradi.

IDE

IDE AST yoki incremental syntax tree asosida:

syntax highlighting;
outline;
code folding;
navigation;
refactoring;
completion;
diagnostics

beradi.

Fayl hali syntactically noto‘g‘ri bo‘lsa ham partial tree yaratish kerak.

Serialization

AST JSON yoki binary formatga serialize qilinishi mumkin.

Qo‘llanishlar:

compiler processlari orasida uzatish;
cache;
tool integration;
remote analysis.

AST schema compiler versiyasiga bog‘liq. Public format sifatida chiqarilsa versioning talab qilinadi.

Macro

AST macro raw text emas, syntax node’lar bilan ishlashi mumkin.

Bu identifier capture va quotingni xavfsizroq boshqaradi.

Hygienic macro scope va yangi identifierlarni nazorat qiladi.

Security

Untrusted source juda chuqur AST yaratib recursion yoki memory exhaustionga sabab bo‘lishi mumkin.

Parser va analysis:

depth limit;
node count;
input size;
timeout

qo‘llaydi.

Code transformation yangi source yaratganda escaping va source mapping to‘g‘ri bo‘lishi kerak.

Diagnostika

AST muammosida:

parser output;
node turi;
source location;
symbol resolution;
transform tartibi;
synthetic node;
parent-child bog‘lanish;
schema versiyasi

tekshiriladi.

AST dump source qanday talqin qilinganini aniq ko‘rsatadi.

Parent reference

Ba’zi AST node faqat childlarni saqlaydi, parent pointer yo‘q. Parent kerak bo‘lsa traversal stack yoki alohida index ishlatiladi. Parent pointer transformatsiyada yangilanmasa daraxt nomuvofiq holatga kelishi mumkin.

Immutable AST

Immutable node o‘zgartirilmaydi; transformatsiya yangi node va o‘zgargan parent yo‘lini yaratadi. Bu parallel analysis va cache uchun qulay. Mutable tree esa in-place transformatsiyada kam allocation talab qilishi mumkin.

AST equivalence

Ikki source boshqa formatting va qavsga ega bo‘lib, bir xil AST hosil qilishi mumkin. Semantic refactoringda daraxtlar yoki keyingi IR solishtiriladi, ammo comment va formatting alohida saqlanadi.

Bog‘liq tushunchalar

Abstract Syntax Tree, Parse tree, Parser, Lexer, Node, Visitor pattern, Semantic analysis, Symbol table, Intermediate Representation, Compiler