एलएल (1) संदिग्ध नहीं हो सकता

Question

यह कैसे दिखाया जा सकता है कि कोई एलएल (1) व्याकरण संदिग्ध नहीं हो सकता है?

मुझे पता है कि संदिग्ध व्याकरण क्या है लेकिन उपर्युक्त प्रमेय/लेम्मा साबित नहीं कर सका।

Answer 1

मुझे लगता है कि यह एलएल (1) की परिभाषा का लगभग प्रत्यक्ष परिणाम है। विरोधाभास द्वारा प्रमाण का प्रयास करें; मान लें कि आपके पास एक एलएल (1) व्याकरण है जो संदिग्ध है और कुछ ऐसा दिखता है जिसे आप सच और सत्य नहीं दिखा सकते हैं। शुरुआती बिंदु के रूप में "आप इनपुट को संसाधित करते समय हमेशा क्या जानते हैं?"

जैसा कि यह एक होमवर्क समस्या की तरह लगता है और मैंने वास्तव में ऊपर से बाहर स्केच किए गए समस्या को समाप्त नहीं किया है, मैं वहां रुक जाऊंगा।

Answer 2

साबित करें कि कोई संदिग्ध व्याकरण एलएल (1) व्याकरण नहीं हो सकता है। संकेतों के लिए, http://www.cse.ohio-state.edu/~rountev/756/pdf/SyntaxAnalysis.pdf देखें, 18-20 स्लाइड्स। http://seclab.cs.sunysb.edu/sekar/cse304/Parse.pdf, पीजी भी देखें। 11 और इससे पहले।

Answer 3

यहां सबूत पर मेरा पहला ड्राफ्ट है। इसे कुछ अच्छी ट्यूनिंग की आवश्यकता हो सकती है, लेकिन मुझे लगता है कि यह सभी मामलों को शामिल करता है। मुझे लगता है कि कई समाधान संभव हैं। यह एक प्रत्यक्ष सबूत है।

(साइड नोट:। यह एक दया अतः जैसे लेटेक्स में के रूप में गणित का समर्थन नहीं करता, है)

सबूत

Let टी और एन टर्मिनल और गैर टर्मिनल प्रतीकों में से सेट हो ।

कि एक व्याकरण डालूँगा है निम्नलिखित पकड़ चलो

MaybeEmpty(s) = true <=> s ->* empty 
First(s) = X containing all x for which there exists Y such that s ->* xY 
Follow(A) = X containing all x for which there exists Y,Z such that S ->* YAxZ 

नोट (1) निम्नलिखित प्रस्तुतियों एक की प्रत्येक जोड़ी के लिए रखती है अगर -> B और A -> सी:

1. (not MaybeEmpty(B)) or (not MaybeEmpty(C)) 
2. (First(B) intersect First(C)) = empty 
3. MaybeEmpty(C) => (First(B) intersect Follow(A)) = empty 

एलएल (1) के साथ एक भाषा पर विचार करें, A -> B और A -> C के साथ। यह कहना है कि टर्मिनल टीजेड की कुछ स्ट्रिंग है जो विशिष्ट पार्स पेड़ों द्वारा एकाधिक व्युत्पन्नों को स्वीकार करती है।

मान लीजिए कि बाएं व्युत्पन्न S ->* TAY ->* TZ तक पहुंचता है। अगला चरण या तो TAY -> TBY, या TAY -> TCY हो सकता है। इस प्रकार भाषा अस्पष्ट है यदि BY ->* Z और CY ->* Z दोनों। (ध्यान दें कि जब एक एक मनमाना गैर टर्मिनल, अगर इस तरह के किसी भी मामले से मौजूद है, भाषा गैर अस्पष्ट है।)

केस 1: = खाली जेड

डालूँगा के नियम 1 से (1) व्याकरण , बी और सी में से अधिकांश में खाली (गैर अस्पष्ट मामला) प्राप्त हो सकता है।

केस 2: जेड गैर खाली, और न तो बी और न ही सी निकाले जाते हैं खाली

डालूँगा के नियम 2 (1) व्याकरण, बी और सी के सबसे एक पर आगे व्युत्पत्ति की अनुमति सकता है क्योंकि जेड के अग्रणी टर्मिनल First(B) और First(C) (गैर-अस्पष्ट मामला) दोनों में नहीं हो सकता है।

केस 3: जेड गैर खाली, और या तो MaybeEmpty(B) या MaybeEmpty(C)

नोट डालूँगा के नियम 1 से (1) व्याकरण, बी और सी दोनों खाली प्राप्त नहीं सकता। मान लीजिए कि MaybeEmpty(C) सत्य है।

यह दो उप-मामलों देता है।

केस 3 ए: CY -> Y; और केस 3 बी: CY ->* DY, जहां डी खाली नहीं है।

3a में हमें BY ->* Z और CY -> Y ->* Z के बीच चयन करना होगा, लेकिन ध्यान दें कि First(Y) subset-of Follow(A)। चूंकि Follow(A)First(B) को अंतर नहीं करता है, केवल एक व्युत्पन्न आगे बढ़ सकता है (अस्पष्ट)।

3 बी में हमें BY ->* Z और CY ->* DY ->* Z के बीच चयन करना होगा, लेकिन ध्यान दें कि First(D) subset-of First(C)। चूंकि First(C)First(B) को अंतर नहीं करता है, केवल एक व्युत्पन्न आगे बढ़ सकता है (अस्पष्ट)।

इस प्रकार हर मामले में व्युत्पन्न केवल उपलब्ध प्रस्तुतियों में से एक द्वारा विस्तारित किया जा सकता है। इसलिए व्याकरण संदिग्ध नहीं है।