FIRST, FOLLOW और LL(1) predictive parsing
लक्ष्य और notation
Predictive table बनाएँ और उसका trace करें। Uppercase symbols nonterminals हैं, lowercase तथा id terminals हैं; id एक token है। ε empty string है, input token नहीं। $ end marker है। Stack का top बाईं ओर लिखेंगे। LL(1) में input left-to-right, derivation leftmost और lookahead एक token है।
1. Nullable, FIRST और FOLLOW
Nullable(A) का अर्थ A से ε derive होता है। FIRST(α) में α से बने strings के शुरुआती terminals तथा nullable होने पर ε आता है। Sequence XY में पहले FIRST(X) से ε हटाकर लें; X nullable हो तभी Y देखें। FOLLOW(A) में sentential form में A के तुरंत बाद आ सकने वाले terminals हैं; start symbol के लिए end पर $ भी। FOLLOW में ε कभी नहीं आता।
Production X→αAβ के लिए FIRST(β)−{ε}, FOLLOW(A) में डालें। β nullable हो तो FOLLOW(X) भी डालें। Sets स्थिर होने तक दोहराएँ; एक pass पर्याप्त नहीं हो सकता। A→α को हर a∈FIRST(α)−{ε} के M[A,a] में रखें। α nullable हो तो FOLLOW(A) के columns में भी रखें। एक cell में कई productions होना LL(1) conflict है।
2. पूरा छोटा उदाहरण
Grammar S→AB; A→aA | ε; B→bB | c है। इसकी भाषा abc है: शून्य या अधिक a, फिर शून्य या अधिक b, फिर ठीक एक c।
A nullable है, B और S नहीं। FIRST(A)={a,ε}; FIRST(B)={b,c}; FIRST(S)={a,b,c}। FOLLOW(S)={$}; FOLLOW(B)={$}; FOLLOW(A)={b,c}, क्योंकि B nullable नहीं। A→aA केवल FOLLOW(A) को उसी में वापस जोड़ता है।
Table के nonempty cells: M[S,a]=M[S,b]=M[S,c]=S→AB; M[A,a]=A→aA; M[A,b]=M[A,c]=A→ε; M[B,b]=B→bB; M[B,c]=B→c। बाकी सभी errors हैं। खासकर M[A,$] खाली है: पूरे S string में B को c देना जरूरी है, इसलिए A के तुरंत बाद input end नहीं आ सकता।
3. a b c $ का stack trace
S$ stack और abc$ input से शुरू करें। सबसे बाएँ stack symbol को production RHS से बदलें; RHS का पहला symbol top पर रहे।
- S$ → AB$ से S→AB लगाएँ; input abc$ रहता है।
- AB$ → aAB$ से A→aA लगाएँ। a match करने पर stack AB$, input bc$।
- Top A और lookahead b पर A→ε: stack B$, input bc$।
- B$ → bB$; b match होने पर stack B$, input c$।
- B$ → c$; c match होने पर stack $, input $: accept।
ε step कोई input नहीं खाता। ab$ में अंततः B$ के साथ lookahead $ मिलता है; table entry खाली होने से error है। केवल prefix consume होना पूरे input की acceptance नहीं।
4. Transformations और conflicts
Immediate left recursion E→E+t | t को E→tR; R→+tR | ε में बदल सकते हैं। सीधे recursive descent में E→E+t लगाने से input consume किए बिना E फिर call होगा। बदलाव भाषा बचाता है, parse-tree shape बदलता है; translation में इच्छित left associativity अलग से बचानी होगी।
Left factoring A→ab | ac को A→aR; R→b | c बनाता है। Choice distinguishing token आने तक टलती है। केवल factoring या left-recursion removal से LL(1) की guarantee नहीं: nullable alternative और FOLLOW में भी conflict हो सकता है।
उदाहरण S→Aa; A→a | ε में FIRST(a)={a}, FOLLOW(A)={a} है। A→a तथा A→ε दोनों M[A,a] में आते हैं। Grammar LL(1) नहीं है, पर उसकी भाषा {a,aa} की grammar S→aR; R→a | ε LL(1) है। किसी grammar की classification उसकी भाषा की हर grammar की classification नहीं होती।
सावधानियाँ
पूरे RHS का FIRST निकालें, केवल पहले nonterminal का नहीं। ε और $ अलग हैं। खाली cell को अपने-आप ε production न मानें। एक conflicting cell LL(1) दावा खारिज करता है; चुपचाप एक rule को priority न दें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें.
P01. S→AB, A→aA|ε, B→bB|c में FIRST(S) क्या है?
A. {a} B. {a,ε} C. {a,b,c} D. {a,b,c,ε}
उत्तर: C
A: A हटने पर B दिखता है।
B: B नहीं हटता, इसलिए ε नहीं।
C: A से a तथा B से b,c मिलते हैं।
D: B अनिवार्य c देता है, S nullable नहीं।
P02. उसी grammar में FOLLOW(A) क्या है?
A. {b,c} B. {$} C. {a,b,c} D. {ε,b,c}
उत्तर: A
A: बाद वाला nonnullable B, b या c से शुरू होता है।
B: A के बाद B जरूरी है, सीधे $ नहीं।
C: Recursive a, A के पहले है।
D: FOLLOW में ε नहीं आता।
P03. Stack top बाएँ है। Lookahead b पर A B $ का अगला stack क्या है?
A. a A B $ B. B $ C. b $ D. $
उत्तर: B
A: A→aA के लिए lookahead a चाहिए।
B: A→ε केवल A हटाता है, token नहीं।
C: B अभी expand और match नहीं हुआ।
D: B का भाग अभी बनना है।
P04. S→Aa; A→a|ε में conflicting LL(1) cell कौन है?
A. M[S,$] B. M[A,$] C. M[A,a] D. M[S,ε]
उत्तर: C
A: S nullable नहीं।
B: FOLLOW(A)={a} है, {$} नहीं।
C: FIRST(a) और FOLLOW(A) दोनों a column देते हैं।
D: ε lookahead column नहीं।
P05. Immediate left recursion सही तरह हटाने पर क्या बचता है?
A. हर parse-tree shape B. Generated token language C. सभी semantic actions की placement अपने-आप D. Ambiguity हमेशा हटती है
उत्तर: B
A: Tree shape बदलती है।
B: समान transformation terminal strings बचाता है।
C: Actions को सोचकर बदलना होगा।
D: यह हर ambiguity नहीं हटाता।
P06. FOLLOW sets के बारे में कौन-सा कथन हमेशा सही है?
A. Nullable symbols के लिए ε आता है B. केवल nonterminals होते हैं C. सिर्फ एक pass चाहिए D. ε नहीं होता
उत्तर: D
A: Nullability से FOLLOW में ε नहीं आता।
B: FOLLOW में terminals और संभव $ होते हैं।
C: Dependencies में कई passes चाहिए।
D: Empty string following token नहीं है।
स्रोत और सीमा
Official 2026 course के अनुसार विषय का सीमित भाग। 2027 की पूर्णता का दावा नहीं। सभी उदाहरण तथा अभ्यास मौलिक हैं.
प्रगति सहेजने के लिए साइन इन करें। साइन इन