एक साधारण व्याकरण का विश्लेषण कैसे करें?

Question

ठीक है, इसलिए मैंने इस परियोजना के बारे में छोटे प्रश्नों के एक समूह से पूछा है, लेकिन मुझे अभी भी उन डिज़ाइनों में अधिक विश्वास नहीं है जिनके साथ मैं आ रहा हूं, इसलिए मैं एक व्यापक पैमाने पर एक प्रश्न पूछने जा रहा हूं ।

मैं पाठ्यक्रम सूची के लिए पूर्व-आवश्यक विवरण पार्स कर रहा हूं। विवरण लगभग हमेशा एक निश्चित रूप का पालन करते हैं, जो मुझे लगता है कि मैं उनमें से अधिकांश को पार्स कर सकता हूं।

पाठ से, मैं पाठ्यक्रम के पूर्व-आवश्यक संबंधों का एक ग्राफ उत्पन्न करना चाहता हूं। (यह हिस्सा है, आसान हो जाएगा के बाद मैं डेटा पार्स है।)

कुछ नमूना इनपुट और आउटपुट:

"CS 2110" => ("CS", 2110) # 0 

"CS 2110 and INFO 3300" => [("CS", 2110), ("INFO", 3300)] # 1 
"CS 2110, INFO 3300" => [("CS", 2110), ("INFO", 3300)] # 1 
"CS 2110, 3300, 3140" => [("CS", 2110), ("CS", 3300), ("CS", 3140)] # 1 

"CS 2110 or INFO 3300" => [[("CS", 2110)], [("INFO", 3300)]] # 2 

"MATH 2210, 2230, 2310, or 2940" => [[("MATH", 2210), ("MATH", 2230), ("MATH", 2310)], [("MATH", 2940)]] # 3 

1. पूरी विवरण सिर्फ एक कोर्स है, तो यह उत्पादन सीधे है।

2. पाठ्यक्रम संयुक्त ("और") कर रहे हैं, वे एक ही सूची

3. पाठ्यक्रम disjoined रहे हैं ("या") के सभी उत्पादन कर रहे हैं, वे अलग-अलग सूचियों में हैं

4. यहां, हमारे पास "और" और "या" दोनों हैं।

एक चेतावनी करना अधिक आसान हो: ऐसा लगता है कि की "और"/"या" वाक्यांशों नेस्टिंग कभी नहीं से अधिक के रूप में उदाहरण में दिखाया गया है 3.

क्या यह करने के लिए सबसे अच्छा तरीका है ? मैंने पीएलवाई के साथ शुरुआत की, लेकिन मैं समझ नहीं पाया कि संघर्ष को कम/कम करने के तरीके को कैसे हल किया जाए। यह कैसे parseString() के उत्पादन में संशोधित करने के लिए कम स्पष्ट है,

def p_course(p): 
'course : DEPT_CODE COURSE_NUMBER' 
p[0] = (p[1], int(p[2])) 

PyParse साथ

: प्लाई का लाभ यह है हेरफेर करने के लिए क्या प्रत्येक पार्स नियम उत्पन्न करता है आसान है। मैं एक ऑब्जेक्ट में राज्य को रखने और उस से आउटपुट बनाने के @ एलेक्स मार्टेलि के विचार पर निर्माण पर विचार कर रहा था, लेकिन मुझे यकीन नहीं है कि यह वास्तव में कैसे किया जाता है।

def addCourse(self, str, location, tokens): 
    self.result.append((tokens[0][0], tokens[0][1])) 

def makeCourseList(self, str, location, tokens): 

    dept = tokens[0][0] 
    new_tokens = [(dept, tokens[0][1])] 
    new_tokens.extend((dept, tok) for tok in tokens[1:]) 

    self.result.append(new_tokens) 

उदाहरण के लिए, संभाल करने के लिए "या" मामलों:

def __init__(self): 
      self.result = [] 
      # ... 
    self.statement = (course_data + Optional(OR_CONJ + course_data)).setParseAction(self.disjunctionCourses) 



def disjunctionCourses(self, str, location, tokens): 
    if len(tokens) == 1: 
    return tokens 

    print "disjunction tokens: %s" % tokens 

कैसे disjunctionCourses() पता है जो छोटे वाक्यांशों अंगों को अलग-अलग करना के लिए? यह सब टोकन है, लेकिन अब तक पार्स किया गया है result में संग्रहीत किया गया है, तो फ़ंक्शन कैसे बता सकता है कि result में कौन सा डेटा token के कौन से तत्वों से मेल खाता है? मुझे लगता है मैं टोकन के माध्यम से खोज सकते हैं, तो एक ही डेटा के साथ result का एक तत्व मिल जाए, लेकिन यह है कि जटिल लग रहा है ...

इसके अलावा, कई विवरण इस तरह, विविध पाठ शामिल हैं:

"CS 2110 or permission of instructor" 
"INFO 3140 or equivalent experience" 
"PYSCH 2210 and sophomore standing" 

लेकिन यह महत्वपूर्ण नहीं है कि मैं उस पाठ को पार्स करता हूं।

इस समस्या से संपर्क करने का एक बेहतर तरीका क्या है?

Answer 1

def parse(astr): 
    astr=astr.replace(',','') 
    astr=astr.replace('and','')  
    tokens=astr.split() 
    dept=None 
    number=None 
    result=[] 
    option=[] 
    for tok in tokens: 
     if tok=='or': 
      result.append(option) 
      option=[] 
      continue 
     if tok.isalpha(): 
      dept=tok 
      number=None 
     else: 
      number=int(tok) 
     if dept and number: 
      option.append((dept,number)) 
    else: 
     if option: 
      result.append(option) 
    return result 

if __name__=='__main__': 
    tests=[ ("CS 2110" , [[("CS", 2110)]]), 
      ("CS 2110 and INFO 3300" , [[("CS", 2110), ("INFO", 3300)]]), 
      ("CS 2110, INFO 3300" , [[("CS", 2110), ("INFO", 3300)]]), 
      ("CS 2110, 3300, 3140", [[("CS", 2110), ("CS", 3300), ("CS", 3140)]]), 
      ("CS 2110 or INFO 3300", [[("CS", 2110)], [("INFO", 3300)]]), 
      ("MATH 2210, 2230, 2310, or 2940", [[("MATH", 2210), ("MATH", 2230), ("MATH", 2310)], [("MATH", 2940)]])] 

    for test,answer in tests: 
     result=parse(test) 
     if result==answer: 
      print('GOOD: {0} => {1}'.format(test,answer)) 
     else: 
      print('ERROR: {0} => {1} != {2}'.format(test,result,answer)) 
      break 

पैदावार

GOOD: CS 2110 => [[('CS', 2110)]] 
GOOD: CS 2110 and INFO 3300 => [[('CS', 2110), ('INFO', 3300)]] 
GOOD: CS 2110, INFO 3300 => [[('CS', 2110), ('INFO', 3300)]] 
GOOD: CS 2110, 3300, 3140 => [[('CS', 2110), ('CS', 3300), ('CS', 3140)]] 
GOOD: CS 2110 or INFO 3300 => [[('CS', 2110)], [('INFO', 3300)]] 
GOOD: MATH 2210, 2230, 2310, or 2940 => [[('MATH', 2210), ('MATH', 2230), ('MATH', 2310)], [('MATH', 2940)]] 

Answer 2

यदि आप "या" और "और" की प्राथमिकता निर्दिष्ट करने के लिए संघर्ष को कम/कम करते हैं।मैं अनुमान लगाता हूं "और" कसकर बांधता है, जिसका अर्थ है "सीएस 101 और सीएस 102 या सीएस 201" का अर्थ है [[सीएस 101, सीएस 102] [सीएस 201]]।

यदि आप दोनों के उदाहरण पा सकते हैं तो व्याकरण अस्पष्ट है और आप भाग्य से बाहर हैं। हालांकि आप परिणामों के साथ क्या करने जा रहे हैं, इस पर निर्भर करते हुए, आप इस अस्पष्टता को अव्यवस्थित छोड़ने में सक्षम हो सकते हैं।

पीएस, ऐसा लगता है कि भाषा नियमित है, आप एक डीएफए पर विचार कर सकते हैं।

Answer 3

सरल व्याकरण के लिए मैं वास्तव में अभिव्यक्ति व्याकरण (खूंटे), पार्स की तरह एक रिकर्सिव-डिसेंट पार्सर लिखने की एक अनुशासित, संरचित तरीके को जो राशि। पाइथन जैसे गतिशील रूप से टाइप की गई भाषा में आप एक अलग "पार्सर जनरेटर" के बिना उपयोगी चीजें कर सकते हैं। इसका मतलब है कि एलआर पार्सिंग के संघर्ष या अन्य आर्कना को कम करने के साथ कोई बकवास नहीं है।

मैंने थोड़ा खोज किया और pyPEG पाइथन के लिए एक अच्छी लाइब्रेरी प्रतीत होता है।

Answer 4

मैं व्याकरण को पार्स करने के बारे में ज्यादा जानने का नाटक नहीं करता हूं, और आपके मामले के लिए unutbu द्वारा समाधान की आवश्यकता होगी। लेकिन मैंने अपनी हालिया श्रृंखला ब्लॉग पोस्ट में एरिक लिपर्ट से पार्सिंग के बारे में काफी कुछ सीखा।

http://blogs.msdn.com/b/ericlippert/archive/2010/04/26/every-program-there-is-part-one.aspx

यह एक 7 भाग श्रृंखला है कि बनाने और पार्स करने एक व्याकरण, तो आसान है और अधिक performant को पार्स करने के लिए व्याकरण के अनुकूलन के माध्यम से चला जाता है है। वह विशेष व्याकरण के सभी संयोजन उत्पन्न करने के लिए सी # कोड उत्पन्न करता है, लेकिन इसे अपने आप के एक साधारण सरल व्याकरण को पार्स करने के लिए पाइथन में परिवर्तित करने के लिए बहुत अधिक खिंचाव नहीं होना चाहिए।