क्या यह एक अस्पष्ट व्याकरण है? मुझे इसे कैसे हल करना चाहिए?

Question

इसका प्रस्ताव देने के लिए, इस तरह की चीजों का मेरा ज्ञान दंडनीय है।

वैसे भी, मैं एलेग्राब्रिक अभिव्यक्तियों की संरचना का वर्णन करने के लिए एक संदर्भ मुक्त व्याकरण विकसित कर रहा हूं, इसलिए मैं स्वयं को सिखा सकता हूं कि सीवाईके पार्सिंग एल्गोरिदम कैसे काम करता है। मैं समझता हूं कि इस तरह की संरचना केवल इन्फिक्स बीजगणितीय अभिव्यक्तियों के साथ कैसे काम कर सकती है, लेकिन मैं समझ नहीं पा रहा हूं कि व्याकरण कैसे विकसित किया जाए जो ऑपरेटर की यूनरी और बाइनरी परिभाषाओं को संभाल सकता है।

संदर्भ के लिए, व्याकरण मैं लिखा है (जहां एस शुरुआत प्रतीक है) CNF में बताया गया है:

एस -> एक्स
A -> ओएस
एस -> पौंड
बी -> एसआर
एस -> केएस
हे -> +
हे -> -
हे -> *
हे ->/
हे ->^
कश्मीर -> -
एल -> (
आर ->) -> एस और ए -> ओएस

समस्या कैसे CYK एल्गोरिथ्म को पार्स समय है कि क्या एस के बीच तय करने से पहले पता कर सकते हैं वह यह है कि जब यह ऑपरेटर का सामना करता है? क्या ऐसा व्याकरण संदर्भ अब मुक्त है? और सबसे महत्वपूर्ण बात यह है कि प्रोग्रामिंग भाषाएं बाइनरी और यूनरी माइनस साइन दोनों के साथ भाषाओं को संभाल सकती हैं, इसलिए मुझे इसे उचित रूप से कैसे पार्स करना चाहिए?

Answer 1

यह परिमित राज्य ऑटोमेटा से संबंधित एक समस्या की तरह लगता है और मैं अपने पाठ्यक्रम से सब कुछ याद नहीं है, लेकिन मैं OCaml में एक CYK पार्सर लिखा था , तो मैं आगे जाना है और एक शॉट :)

ले आप 3- -4 की तरह एक अभिव्यक्ति पार्स करने के लिए उदाहरण के लिए, यदि आप अपने S -> K S नियम होता प्रयास कर रहे हैं जाएगा -4 और फिर अपने A -> O S नियम - -4 अवशोषित होता खपत करते हैं। यह अंततः शीर्ष-सबसे अधिक S उत्पादन नियम तक काम करेगा। आपको व्याकरण के साथ सावधान रहना चाहिए, हालांकि A आपके द्वारा सूचीबद्ध उत्पादन नियम S से नहीं पहुंचा जा सकता है और आपके पास शायद S -> S O S किसी प्रकार का नियम होना चाहिए।

जिस तरह से सीवाईके पार्सिंग एल्गोरिदम काम करता है वह बैकट्रैकिंग के माध्यम से होता है, न कि आपके प्रश्न में उल्लिखित "समय से पहले जानना" के माध्यम से। आपके सीवाईके एल्गोरिदम को -4 को S -> K S नियम के रूप में पार्स करना है और फिर यह को S -> K S नियम के साथ फिर से अवशोषित करने का प्रयास करेगा क्योंकि यह उत्पादन नियम यूनरी - की मनमाने ढंग से लंबी श्रृंखला के लिए अनुमति देता है। लेकिन एक बार आपके एल्गोरिदम को यह पता चलता है कि यह इंटरमीडिएट पार्स 3 S के साथ फंस गया है, यह महसूस करता है कि इसमें कोई उत्पादन प्रतीक नहीं है जिसका उपयोग इसे पार्स करने के लिए किया जा सकता है। एक बार यह महसूस हो जाता है कि यह अब पारदर्शी नहीं है, यह वापस जायेगा और इसके बजाय - को S -> O S नियम के रूप में पार्स करने और इसके आनंददायक तरीके से जारी रखने का प्रयास करेगा।

यह है कि आपके व्याकरण विषय से मुक्त रहता है एक संदर्भ के प्रति संवेदनशील व्याकरण का मतलब है जब से तुम उत्पादन नियमों के बाईं ओर स्थित टर्मिनल है, ताकि आप उस संबंध में अच्छा कर रहे हैं मतलब है। HTH!

Answer 2

व्याकरण संदिग्ध है, और पार्सर यह तय नहीं कर सकता कि कौन सा मामला लेना है।

आप शायद की तरह एक व्याकरण का उपयोग करना चाहिए निम्नलिखित:

S -> EXPR 
EXPR -> (EXPR) 
EXPR -> - EXPR 
EXPR -> EXPR + EXPR 
EXPR -> EXPR - EXPR 
// etc... 

Answer 3

बीजीय भाव के आधार पर व्याकरण बल्कि स्पष्ट करने के लिए मुश्किल हैं। यहाँ समस्याओं के कुछ उदाहरण जो संबोधित करने की जरूरत है:

एक + बी + सी स्वाभाविक रूप से दो पार्स पेड़ पैदा करता है। इसे हल करने के लिए, आपको + की सहयोगीता की अस्पष्टता को हल करने की आवश्यकता है। आप बाएं से दाएं पार्सिंग रणनीति को आपके लिए इस पर ध्यान देना चाहेंगे, लेकिन सावधान रहें: एक्सपोनेंटिएशन शायद दाएं से बाएं को जोड़ना चाहिए।

ए + बी * सी स्वाभाविक रूप से दो पार्स पेड़ बनाता है। इस समस्या को ठीक करने के लिए, आपको ऑपरेटर प्राथमिकता से निपटने की आवश्यकता है।

निहित गुणा (अ + ईसा पूर्व), अगर यह अनुमति दी है, बुरे सपने के सभी प्रकार, ज्यादातर tokenization पर बनाता है।

यूनरी घटाव समस्याग्रस्त है, जैसा कि आप उल्लेख करते हैं।

यदि हम इन समस्याओं को हल करना चाहते हैं, लेकिन अभी भी बीजगणित के लिए विशेष रूप से एक तेज-पार्सिंग व्याकरण है, तो एक दृष्टिकोण है कि EXPR के विभिन्न "स्तर", प्राथमिकता स्तरों के अनुसार आवश्यक प्रत्येक स्तर के बाध्यकारी के लिए एक है। उदाहरण के लिए,

TERM -> (S) 
EXPO -> TERM^EXPO 
PROD -> PROD * EXPO 
PROD -> PROD/EXPO 
PROD -> -PROD 
SUM -> SUM + PROD 
SUM -> SUM - PROD 
S -> SUM 

यह जरूरी है कि आप भी प्रकार के "प्रचार" अनुमति देते हैं: योग - ताकि चीजें समाप्त कर सकते हैं,> अवधि, आदि -> ठेस, ठेस -> ऍक्स्प, ऍक्स्प।

आशा है कि इससे मदद मिलती है!