Lexer

Lexer — belgilar oqimini tilning ma’noli eng kichik birliklari bo‘lgan tokenlarga ajratadigan komponent. U lexical analyzer yoki scanner deb ham ataladi.

Compiler pipeline’da lexer source code’ni o‘qib, parser uchun tokenlar ketma-ketligini yaratadi.

Belgidan tokenga

Source:

count = value + 10

Lexer natijasi:

IDENTIFIER("count")
EQUAL
IDENTIFIER("value")
PLUS
NUMBER("10")
EOF

Parser raw harflar bilan emas, shu token turlari bilan ishlaydi.

Token tarkibi

Token quyidagi ma’lumotlarga ega bo‘lishi mumkin:

• type;
• asl matn — lexeme;
• qiymat;
• qator;
• ustun;
• byte offset;
• file;
• leading yoki trailing trivia.

Masalan, 123 tokeni text sifatida "123", qiymat sifatida integer 123 bo‘lishi mumkin.

Lexeme

Lexeme source’dagi tokenga mos aniq belgilar ketma-ketligi.

Misollar:

• while — keyword lexeme;
• user_name — identifier lexeme;
• 42 — number lexeme;
• >= — operator lexeme.

Token type umumiy kategoriya, lexeme esa original matn.

Token qoidalari

Lexer qoidalari regular expression yoki state machine bilan ifodalanishi mumkin.

Masalan:

IDENTIFIER = harf (harf | raqam | "_")*
NUMBER = raqam+
WHITESPACE = space | tab | newline

Keywordlar identifier sifatida o‘qilib, keyin reserved word jadvalidan tekshirilishi mumkin.

Longest match

Bir nechta qoida mos bo‘lsa, lexer odatda eng uzun lexeme’ni tanlaydi.

Masalan:

>=

bitta GREATER_EQUAL tokeni, > va = ikkita token emas.

Bu maximal munch tamoyili.

Teng uzunlikda qoida prioritysi ishlatilishi mumkin.

Whitespace

Ko‘p tillarda whitespace tokenlar orasini ajratadi, ammo parserga yuborilmaydi.

Python kabi indentation-sensitive tilda lexer:

• INDENT;
• DEDENT;
• NEWLINE

tokenlarini hosil qiladi.

Shu sababli whitespace har doim “keraksiz” emas.

Comment

Comment lexer tomonidan taniladi.

Compiler parserga yubormasligi mumkin.

Formatter va documentation vositasi commentni saqlashi kerak, shuning uchun u trivia yoki alohida token sifatida qoladi.

Nested comment va string ichidagi comment belgisi state talab qiladi.

String literal

String lexing murakkab bo‘lishi mumkin.

Lexer quyidagilarni boshqaradi:

• quote turi;
• escape sequence;
• newline;
• raw string;
• interpolation;
• Unicode escape;
• yopilmagan string.

Masalan, comment belgisi string ichida comment boshlamaydi.

Number literal

Number formatlari:

• decimal;
• hexadecimal;
• binary;
• octal;
• floating point;
• exponent;
• underscore separator;
• suffix.

Lexer 1.5e-3ni bitta number tokeni sifatida tanishi kerak.

Minus belgisi ko‘pincha alohida operator bo‘lib, negative son parser yoki semantic bosqichda hosil qilinadi.

Mode va state

Bitta token qoidasi barcha holatda bir xil emas.

Masalan, template ichida:

• oddiy text;
• expression;
• string;
• comment

rejimlari bo‘lishi mumkin.

Lexer mode stack orqali qoidalar to‘plamini almashtiradi.

Regular language

Ko‘p lexical qoidalar regular language bo‘lib, finite automaton bilan taniladi.

Regex:

1. NFAga;
2. DFAga;
3. transition tablega

aylantirilishi mumkin.

Bu har belgini samarali qayta ishlashga yordam beradi.

Hand-written lexer

Qo‘lda yozilgan lexer pointer yoki indeks bilan source bo‘ylab yuradi.

Afzalliklari:

• aniq error;
• maxsus syntax;
• performance nazorati;
• dependency kam.

Kamchiligi — barcha edge case va Unicode qoidalarini to‘g‘ri yozish zarur.

Lexer generator

Token qoidalaridan avtomatik lexer code yaratiladi.

Generator:

• regex;
• priority;
• action;
• mode

asosida scanner hosil qiladi.

Conflict va unreachable rule haqida ogohlantirishi mumkin.

Keyword

Keyword til tomonidan rezerv qilingan so‘z.

Lexer identifierni o‘qigach jadvaldan tekshiradi:

if → IF
while → WHILE
user → IDENTIFIER

Contextual keyword faqat ma’lum grammar joyida keyword bo‘ladi. Uni parser yoki semantic bosqich aniqlashi mumkin.

Unicode identifier

Zamonaviy tillar identifierda Unicode harflariga ruxsat berishi mumkin.

Qoidalar:

• boshlang‘ich kategoriya;
• davom etuvchi kategoriya;
• normalization;
• confusable belgilar;
• bidirectional control.

Ko‘rinishi o‘xshash turli belgilar security xavfi tug‘diradi.

Position tracking

Lexer har tokenning source joyini saqlaydi.

UTF-8da byte offset, Unicode code point va ekrandagi ustun bir xil emas.

Tab kengligi va combining character error ustunini murakkablashtiradi.

Lexical error

Misollar:

• noma’lum belgi;
• yopilmagan string;
• noto‘g‘ri escape;
• yaroqsiz number;
• yopilmagan comment;
• invalid encoding.

Lexer xato joyi va lexeme contextini qaytaradi.

Incremental lexing

Editor faylning kichik qismini o‘zgartirganda lexer o‘sha joydan qayta ishlashi mumkin.

Ammo multiline string yoki comment holati keyingi qatorlarga ta’sir qiladi.

Incremental algoritm oldingi barqaror state’dan boshlaydi.

Lexer va tokenizer

Atamalar ko‘pincha bir xil ishlatiladi.

Compiler nazariyasida lexer grammar parseri uchun formal tokenlar yaratadi.

NLP yoki qidiruvda tokenizer matnni so‘z, subword yoki sentence birliklariga bo‘ladi.

Kontekst farqni belgilaydi.

Trivia

Whitespace va comment parser semantikasi uchun kerak bo‘lmasa ham formatter va source-to-source vosita uchun saqlanadi. Bunday elementlar ko‘pincha trivia deb ataladi va yaqin tokenning leading yoki trailing qismiga biriktiriladi.

Lexical ambiguity

>> bitta shift operatori yoki ikki yopuvchi generic qavs sifatida talqin qilinishi mumkin. Til versiyasi va parser contexti lexer tokenini bo‘lishi yoki qayta talqin qilishi mumkin.

Streaming lexer

Katta input bo‘laklarda o‘qilganda token ikki buffer chegarasiga bo‘linishi mumkin. Lexer tugallanmagan string yoki number qismini keyingi chunk kelguncha saqlaydi.

Bog‘liq tushunchalar

Lexical analysis, Token, Lexeme, Scanner, Regex, Finite automaton, Parser, Keyword, Trivia, Source position