LR items, shift–reduce parsing और conflicts
लक्ष्य और conventions
छोटा LR automaton बनाएँ, LR(0), SLR(1), canonical LR(1), LALR(1) अलग करें और reductions trace करें। LR input बाएँ से दाएँ पढ़कर rightmost derivation को उलटे क्रम में बनाता है। यहाँ stack top दाईं ओर है। A→α·β में α पहचाना जा चुका है, β बाकी है। Fresh start rule S′→S जोड़ें। केवल S′→S· और lookahead $ पर accept करें, हर completed item पर नहीं।
1. Closure और goto
Dot के बाद nonterminal B हो तो LR(0) closure हर B production के लिए B→·γ जोड़ता है और यह प्रक्रिया दोहराता है। goto(I,X) में matching items का dot X के आगे करके closure लेते हैं। Terminal transition shift देता है; nonterminal transition reduction के बाद का goto देता है।
Grammar S′→S, S→CC, C→cC | d के पूरे states:
- I0: S′→·S; S→·CC; C→·cC; C→·d।
- I1=goto(I0,S): S′→S·।
- I2=goto(I0,C): S→C·C; C→·cC; C→·d।
- I3=goto(I0,c): C→c·C; C→·cC; C→·d।
- I4=goto(I0,d): C→d·।
- I5=goto(I2,C): S→CC·।
- I6=goto(I3,C): C→cC·।
बाकी transitions: I2 में c→I3, d→I4; I3 में c→I3, d→I4। I4, I5, I6 में एक-एक ordinary completed item है और कोई terminal shift नहीं। I1 केवल accept करता है। इसलिए grammar में LR(0) conflict नहीं है। State numbers मनमाने हैं; item sets और transitions महत्वपूर्ण हैं।
2. c d d $ का पूरा trace
States और grammar symbols को बारी-बारी लिखें, शुरुआत [0]।
- c पर shift: [0 c 3], बाकी dd$।
- d पर shift: [0 c 3 d 4], बाकी d$।
- C→d reduce: d और state 4 pop हों, 3 खुले। goto(3,C)=6 से [0 c 3 C 6]। Input d$ ही है।
- C→cC reduce: दो symbols और उनके states हटें, 0 खुले। goto(0,C)=2 से [0 C 2]। Input d$ ही है।
- d shift: [0 C 2 d 4], बाकी $।
- C→d reduce: state 2 खुले; goto(2,C)=5 से [0 C 2 C 5]।
- S→CC reduce: 0 खुले; goto(0,S)=1 से [0 S 1]। $ पर accept।
Reduction input consume नहीं करता। A→ε में शून्य grammar symbols pop करें, फिर A पर goto लें। Handle reverse-rightmost derivation में घटने वाला substring है; केवल RHS जैसा दिखने वाला कोई भी substring नहीं।
3. Reduction कहाँ लगाएँ
LR(0) में completed A→α· reduction हर terminal/end-marker column पर आता है। SLR इसे FOLLOW(A) तक सीमित करता है। Canonical LR(1) item में अपना lookahead है: [A→α·β,a]। [A→α·Bβ,a] के closure में हर b∈FIRST(βa) के लिए [B→·γ,b] जोड़ते हैं। Completed item केवल अपने lookahead पर reduce करता है।
S→Aa | b; A→b लें। b के बाद state में S→b· और A→b· दोनों आते हैं: LR(0) reduce/reduce conflict। मगर FOLLOW(S)={$}, FOLLOW(A)={a}; SLR में दोनों reductions अलग columns में पड़ते हैं। इसलिए यह grammar SLR(1) है। केवल दो completed items देखकर SLR conflict न कहें; lookahead columns का overlap जाँचें।
Shift/reduce conflict में एक cell shift और reduction दोनों देता है। Reduce/reduce में एक cell दो अलग reductions देता है। Precedence declarations कुछ conflicts सुलझा सकती हैं, लेकिन मूल grammar अपने-आप conflict-free नहीं बन जाती।
4. LALR merge और सीमाएँ
LALR उन canonical LR(1) states को मिलाता है जिनका LR(0) core समान है; matching items के lookaheads का union होता है। States कम होते हैं, लेकिन नए reduce/reduce conflicts आ सकते हैं। Conflict-free canonical LR(1) automaton में केवल equal-core merging से नया shift/reduce conflict नहीं आ सकता: shift सभी merged states के समान core में है, इसलिए conflicting reduction lookahead अपने source state में ही conflict देता।
Fixed grammar के लिए LR(0) ⊆ SLR(1) ⊆ LALR(1) ⊆ canonical LR(1) है। Deterministic LR grammar unambiguous होती है। हर unambiguous grammar LR(1) नहीं होती और कमजोर construction का conflict ambiguity का प्रमाण नहीं। किस grammar और किस construction की जाँच है, स्पष्ट करें।
मौलिक अभ्यास: छह single-correct MCQ
ये मौलिक शिक्षण प्रश्न हैं, पिछले वर्षों के प्रश्न नहीं। ठीक एक उत्तर चुनें.
P01. LR parser कौन-सी derivation बनाता है?
A. Leftmost सीधे क्रम में B. Rightmost उलटे क्रम में C. Rightmost सीधे क्रम में D. बिना क्रम कोई भी derivation
उत्तर: B
A: यह top-down से जुड़ा है।
B: Bottom-up reductions rightmost derivation उलटते हैं।
C: Reductions उलटी दिशा में हैं।
D: Handle sequence का निश्चित अर्थ है।
P02. उदाहरण में [0 c 3 C 6] पर C→cC reduce करने के बाद stack?
A. [0 C 2] B. [0 c 3] C. [0 C 6] D. [0 S 1]
उत्तर: A
A: दो symbols हटाकर goto(0,C)=2 लें।
B: दोनों RHS symbols हटेंगे।
C: खुला state 0 है, उसका C goto 2 है।
D: इस reduction का LHS C है, S नहीं।
P03. SLR में A→α reduction किन columns पर होता है?
A. FIRST(A) B. FOLLOW से अलग हर terminal C. FOLLOW(A) D. केवल dot के बाद वाला symbol
उत्तर: C
A: FIRST शुरुआत बताता है, A के बाद का context नहीं।
B: यह LR(0) नियम है।
C: FOLLOW completed reduction सीमित करता है।
D: Completed item में dot के बाद symbol नहीं।
P04. S→Aa|b; A→b में b के बाद दोनों reductions कैसे हैं?
A. अनिवार्य SLR conflict B. कोई LR(0) conflict नहीं C. LR(0) conflict, SLR lookaheads से अलग D. भाषा ambiguous होने का प्रमाण
उत्तर: C
A: FOLLOW sets अलग हैं।
B: LR(0) दोनों को सभी columns देता है।
C: S, $ पर और A, a पर reduce करता है।
D: यह ambiguity सिद्ध नहीं करता।
P05. Conflict-free canonical LR(1) के equal-core merge से नया क्या आ सकता है?
A. केवल नया shift action B. Reduce/reduce conflict C. Grammar में नया terminal D. निश्चित shift/reduce conflict
उत्तर: B
A: Core shifts तय करता है।
B: Lookahead union अलग reductions को overlap करा सकता है।
C: Merge states बदलता है, alphabet नहीं।
D: केवल इस merge से नया shift/reduce conflict नहीं आता।
P06. A→ε reduction में कितने grammar symbols pop होते हैं?
A. 0 B. 1 C. 2 D. सभी symbols
उत्तर: A
A: RHS length शून्य है; फिर A पर goto लें।
B: ε pop होने वाला stack symbol नहीं।
C: यहाँ RHS symbols नहीं हैं।
D: Pop count केवल RHS length से मिलता है।
स्रोत और सीमा
Official 2026 course के अनुसार विषय का सीमित भाग। 2027 की पूर्णता का दावा नहीं। सभी उदाहरण तथा अभ्यास मौलिक हैं.
प्रगति सहेजने के लिए साइन इन करें। साइन इन