Lexical analysis: tokens, automata और longest match
लक्ष्य और conventions
Characters, lexemes, tokens और attributes में अंतर समझें तथा scanner को parser से अलग रखकर trace करें। Token एक category है, जैसे ID या NUM। Lexeme वास्तविक source substring है, जैसे count या 42। Attribute numeric value या symbol-table reference रख सकता है। Whitespace और comments तभी छोड़ते हैं जब भाषा के नियम अनुमति दें। EOF input का अंत है, source character नहीं।
1. Compiler phases और scanner की सीमा
सामान्य front end पहले characters से tokens बनाता है, फिर context-free grammar से parsing और अंत में declaration तथा type consistency जैसे semantic checks करता है। Syntax सही होने पर भी type गलत हो सकता है। Identifier token मिलने से उसका declared होना सिद्ध नहीं होता। Symbol table कई phases साझा कर सकते हैं; पहचानना और scope resolve करना अलग काम हैं।
हमारी छोटी भाषा में letter=[A-Za-z], digit=[0-9], ID=letter(letter|digit)* और NUM=digit+ हैं। Exact if के लिए IF keyword तथा =, ==, +, ++, <, <=, ; operators हैं। यहाँ identifier underscore से शुरू नहीं होता, numeric literal में decimal point नहीं है और अलग से न कहें तो comments नहीं हैं। ये इस उदाहरण के नियम हैं, हर भाषा के नहीं।
2. पहले longest match, फिर priority
वर्तमान position से किसी भी token rule द्वारा स्वीकार किया गया सबसे लंबा prefix चुनें। समान अधिकतम length के दो matches होने पर ही priority लागू करें। IF को ID से पहले रखें: if से IF मिलेगा, लेकिन if2 एक ID होगा। Length जाँचे बिना keyword priority लगाने से if2 गलत टूट जाएगा। कोई nonempty prefix match न हो तो lexical error दें; अनजान character चुपचाप न हटाएँ।
if2<=10++x; का trace:
- i से ID, i फिर if फिर if2 स्वीकार करता है। IF केवल if स्वीकार करता है। सबसे लंबा if2 है: ID(if2)।
- < से < और <= संभव हैं; लंबा <= चुना जाएगा: LE।
- 1 से NUM पहले 1 फिर 10 लेता है, + से पहले रुकता है: NUM(10)।
- + से ++ लंबा है: INC।
- x से ID(x), और ; से SEMI मिलता है।
कुल छह token occurrences हैं। Parser operator arrangement को बाद में reject करे तब भी scanner यह stream बना सकता है। Distinct categories की संख्या और token occurrences की संख्या अलग हैं। Rules से boundaries मिलती हों तो tokens के बीच spaces अनिवार्य नहीं।
3. Automata और last accepting position
Token patterns regular expressions से बताते हैं। एक construction सभी patterns का epsilon-NFA बनाकर accepting states पर token tags रखता है और subset construction से DFA बनाता है। DFA state NFA states का set है। शुरुआत में और हर character transition के बाद epsilon-closure लेना आवश्यक है। एक DFA state में कई accepting tags हों तो तय priority लगाएँ।
Scanner को सबसे हाल का accepting state और input position याद रखना होता है; पहले acceptance पर नहीं रुकना चाहिए। Rules A=ab और B=abcd लें। Input abcx में a और abc के बाद states nonaccepting हैं, ab के बाद A accept होता है और abcd पूरा होता तो B मिलता। x पढ़ना fail होता है। तब ab के बाद वाली position पर लौटकर A(ab) emit करें; अगला scan c से शुरू होगा। c से कोई rule न हो तो वहीं error होगा। असफल lookahead characters A का हिस्सा नहीं बने।
ID rule में पहला letter पढ़ने के बाद state accepting है; आगे letters/digits accepting loop में जाते हैं। Delimiter run को रोकता है लेकिन अगले token के लिए बचता है। Buffer sentinel या retract implementation details हैं, नए tokens नहीं।
4. सीमा और गलतियाँ
Regular token patterns के लिए finite automata पर्याप्त हैं। मनमानी गहराई के balanced nested parentheses सामान्यतः parser सँभालता है, केवल finite-state scanner नहीं। Unrestricted nested comments भी plain finite automaton से आगे की शक्ति चाहते हैं। Comment नाम से regularity न मानें; scanner अतिरिक्त counter या modes उपयोग कर सकता है।
- Maximal munch के tokens syntax में fail हो सकते हैं; scanner पूरी valid program tokenization खोजने नहीं जाता।
- Keyword को priority या पूरे identifier के बाद table lookup से पहचान सकते हैं।
- Empty string को सामान्य token की तरह बार-बार emit करने से input आगे नहीं बढ़ेगा।
- दिए rules में @ lexical error है; सही आकार का undeclared identifier semantic issue है।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें.
P01. IF की priority ID से ऊँची है; maximal munch में if2 क्या है?
A. IF फिर NUM B. एक ID C. तीन ID D. Lexical error
उत्तर: B
A: Priority लंबे match को नहीं हटाती।
B: ID pattern तीनों characters लेता है।
C: Longest match पूरा lexeme लेता है।
D: ID में बाद में digit अनुमत है।
P02. दिए rules में if2<=10++x; में कितने token occurrences हैं?
A. 5 B. 6 C. 7 D. 11
उत्तर: B
A: Semicolon भी token है।
B: ID, LE, NUM, INC, ID, SEMI छह occurrences हैं।
C: <= और ++ अलग-अलग नहीं टूटते।
D: Character और token counts अलग हैं।
P03. Rules ab और abcd में abcx scan करने पर पहला token क्या है?
A. abc B. abcd C. ab D. कुछ नहीं, जबकि ab match हुआ
उत्तर: C
A: abc accepted token नहीं।
B: Input में abcd नहीं।
C: ab के बाद last acceptance पर लौटें।
D: पहला accepted prefix उपलब्ध है।
P04. Token category के बजाय lexeme कौन है?
A. ID B. NUM C. Source substring count D. सभी identifiers का वर्ग
उत्तर: C
A: ID category है।
B: NUM category है।
C: count वास्तविक matched substring है।
D: वर्ग कोई खास occurrence नहीं।
P05. किस काम में token पहचान से आगे semantic जानकारी चाहिए?
A. ++ पहचानना B. अनुमत space छोड़ना C. Digits पहचानना D. x scope में declared है या नहीं जाँचना
उत्तर: D
A: ++ finite pattern है।
B: Space का lexical rule हो सकता है।
C: Digits regular pattern हैं।
D: Declaration और scope इस scanner से आगे की जानकारी चाहते हैं।
P06. केवल plain finite automaton कौन-सी भाषा नहीं पहचान सकता?
A. सभी digit strings B. दिए regex के identifiers C. Finite keyword set D. मनमानी गहराई के balanced parentheses
उत्तर: D
A: Digit strings regular हैं।
B: दिया pattern regular है।
C: हर finite language regular है।
D: Unbounded nesting के लिए finite states से अधिक memory चाहिए।
स्रोत और सीमा
Official 2026 course के अनुसार विषय का सीमित भाग। 2027 की पूर्णता का दावा नहीं। सभी उदाहरण तथा अभ्यास मौलिक हैं.
प्रगति सहेजने के लिए साइन इन करें। साइन इन