संदिग्ध व्याकरण

Question

मैं निम्नलिखित व्याकरण को देख रहा हूं और मुझे विश्वास है कि यह लाइन 3 पर अस्पष्ट है, लेकिन यकीन नहीं है।

<SL> → <S> 
<SL> → <SL> <S> 
<S> → i <B> <S> e <S> 
<S> → i <B> <S> 
<S> → x 
<S> → y 
<B> → 5 
<B> → 13 

मैं इस स्ट्रिंग xi13yi5xeyx मेरा मानना ​​है कि दो अलग अलग पार्स पेड़ उत्पन्न करता पाया है, लेकिन मुझे यकीन है कि अगर im गलत यह कर नहीं हूँ।

क्या कोई मेरे निष्कर्षों को सत्यापित कर सकता है?

Answer 1

हाँ आपका व्याकरण एक संदिग्ध व्याकरण है!
_{आप लेकिन उल्लेख नहीं किया है मुझे लगता है कि <SL> अपने व्याकरण के नियमों का उपयोग हम i5i5yey मरोड़ के रूप में followes के लिए एक से अधिक पार्स पेड़ (दो) आकर्षित कर सकते हैं शुरू व्यवहार्य}

है:

 <SL>        <SL> 
     |         | 
     <S>        <S> 
    //|\ \       /| \ 
    // | \ \      /| \ 
// | \ \      / | \ 
// | \ \      i <B> <S>  
/| | | \       |//|\ \  
i <B> <S> e <S>      5// | \ \ 
// | \  |      // | \ \ 
// | \ y      // | \ \ 
5 i <B> <S>       /| | | \ 
     | |       i <B> <S> e <S> 
     5 y        | |  | 
              5 y  y 

संरचना दोनों पार्स पेड़ के दो अलग हैं व्याकरण एक संदिग्ध व्याकरण है!

आप चित्र से ऊपर पेड़ स्ट्रिंग xi13yi5xeyx, (मैं तुम्हें लिए एक व्यायाम के रूप में इस जा रहा हूँ)

महत्वपूर्ण भाषा इस व्याकरण से उत्पन्न है not ambiguous language है उत्पन्न करने के लिए कर सकते हैं .और इसके संभावित एक लिखने के लिए इस व्याकरण के लिए बराबर स्पष्ट व्याकरण जो हमेशा व्याकरण की भाषा में प्रत्येक स्ट्रिंग के लिए अद्वितीय पेड़ उत्पन्न करता है।

HINT: स्पष्ट व्याकरण लिखने के लिए।

व्याकरण सी भाषा में if loop के लिए व्याकरण के समान है (if loop के लिए अलग-अलग वाक्यविन्यास वाले विभिन्न भाषा को नोटिस करें)। और यह लगभग सभी कंपाइलर डिजाइन पुस्तक में हल हो गया।
Resolving the General Dangling Else/If-Else Ambiguity

संदर्भ: बुक संकलनकर्ता सिद्धांतों, तकनीक, और Aho-उलमान अनुभाग द्वारा उपकरण 4.5 संघर्ष शिफ्ट के दौरान और कम पार्सिंग।