एक रिकर्सिव व्याकरण के FIRST और FOLLOW सेट कैसे खोजें?

Question

मान लीजिए कि मेरे पास निम्नलिखित CFG है।

A -> B | Cx | EPSILON 
B -> C | yA 
C -> B | w | z 

अब अगर मैं

FIRST(C) = FIRST(B) U FIRST(w) U FIRST(z) 
     = FIRST(C) U FIRST(yA) U {w, z} 

यही है, मैं एक पाश में जा रहा हूँ पता लगाने की कोशिश। इस प्रकार मुझे लगता है कि मुझे इसे एक ऐसे रूप में परिवर्तित करना है जिसने तत्काल बाएं रिकर्सन किया है, जो मैं निम्नानुसार कर सकता हूं।

A -> B | Cx | EPSILON 
B -> C | yA 
C -> C | yA | w | z 

अब अगर मैं पहले सेट की गणना करने का प्रयास करता हूं, तो मुझे लगता है कि मैं इसे निम्नानुसार प्राप्त कर सकता हूं।

FIRST(C) = FIRST(C) U FIRST(yA) U FIRST(w) U FIRST(z) 
     = { y, w, z } // I ignore FIRST(C) 
FIRST(B) = FIRST(C) U FIRST(yA) 
     = { y, w, z } 
FIRST(A) = FIRST(B) U FIRST(Cx) U FIRST(EPSILON) 
     = { y, w, z, EPSILON } 

क्या मैं वहां सही हूं?

लेकिन यहां तक ​​कि अगर मैं वहां हूं, तो भी मैं इस समस्या से निम्नलिखित सेटों की गणना करने का प्रयास करता हूं, फिर भी एक समस्या में भाग लेता हूं।

FOLLOW(A) = { $ } U FOLLOW(B) U FOLLOW(C) 

मुझे तीसरे नियम से दूसरे नियम और अनुसरण (सी) से अनुसरण करें (बी) प्राप्त करें। लेकिन अब फोल्लो (बी) की गणना करने के लिए, मुझे निम्नलिखित (ए) (प्रथम व्याकरण नियम से) की आवश्यकता है, इसलिए मैं एक लूप में फंस गया हूं।

कोई मदद? अग्रिम धन्यवाद!

Answer 1

चूंकि FIRST और FOLLOW (सामान्यतः) रिकर्सिव हैं, इसलिए उनके बारे में सोचने के लिए समीकरणों की प्रणालियों को हल करना उपयोगी होता है; समाधान को एक सरल वृद्धिशील एल्गोरिदम का उपयोग करके हासिल किया जा सकता है जिसमें चक्र के दौरान कोई सेट नहीं बदला जाता है जब तक कि सभी दाएं हाथों को बार-बार लागू नहीं किया जाता है।

A → B | Cx | ε 
B → C | yA 
C → B | w | z 

हम सीधे समीकरण प्राप्त कर सकते हैं::

FOLLOW(A) = FOLLOW(B) ∪ {$} 
FOLLOW(B) = FOLLOW(A) ∪ FOLLOW(C) 
FOLLOW(C) = FOLLOW(B) ∪ {x} 

सभी {} सेट का पालन तो हम शुरू में सेट है, और आगे बढ़ना

तो चलो देखते हुए व्याकरण के लिए अनुसरण संबंध लेते हैं ।

पहले दौर:

FOLLOW(A) = {} ∪ {$} = {$} 
FOLLOW(B) = {$} ∪ {} = {$} 
FOLLOW(C) = {$} U {x} = {$,x} 

दूसरा दौर:

FOLLOW(A) = {$} ∪ {$} = {$} 
FOLLOW(B) = {$} ∪ {$,x} = {$,x} 
FOLLOW(C) = {$,x} U {x} = {$,x} 

तीसरा दौर:

FOLLOW(A) = {$,x} ∪ {$} = {$,x} 
FOLLOW(B) = {$} ∪ {$,x} = {$,x} 
FOLLOW(C) = {$,x} U {x} = {$,x} 

चौथा दौर:

FOLLOW(A) = {$,x} ∪ {$} = {$,x} 
FOLLOW(B) = {$,x} ∪ {$,x} = {$,x} 
FOLLOW(C) = {$,x} U {x} = {$,x} 

यहां हम रुकते हैं क्योंकि अंतिम दौर में कोई बदलाव नहीं किए गए थे।

यह एल्गोरिदम समाप्त होना चाहिए क्योंकि प्रतीकों की एक सीमित संख्या है, और प्रत्येक दौर केवल चरणों में प्रतीकों को जोड़ सकता है। यह सबसे कुशल तकनीक नहीं है, हालांकि यह आम तौर पर अभ्यास में काफी अच्छा है।