Wie analysiere ich am besten eine einfache Grammatik?

Question

Ok, ich habe eine Reihe kleinerer Fragen zu diesem Projekt gestellt, aber ich habe immer noch nicht viel Vertrauen in die Designs, die ich mir ausgedacht habe, also werde ich eine breitere Frage stellen .

Ich analysiere die erforderlichen Beschreibungen für einen Kurskatalog. Die Beschreibungen folgen fast immer einer bestimmten Form, was mich denken lässt, dass ich die meisten von ihnen analysieren kann.

Aus dem Text möchte ich eine Grafik der natürlich erforderlichen Beziehungen generieren. (Dieser Teil wird einfach sein, nachdem ich die Daten analysiert haben.)

Einige Beispiel Ein- und Ausgänge:

"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. Wenn die gesamte Beschreibung nur ein Kurs ist, ist es direkt ausgegeben.

2. Wenn die Kurse verbunden sind ("und"), sie alle Ausgaben in derselben Liste sind

3. Wenn der Kurs disjoined werden ("oder"), sie sind in separaten Listen

4. Hier haben wir beide "und" und "oder".

Eine Einschränkung, die es einfacher macht: es scheint, dass die Verschachtelung „und“/„oder“ Sätze nie größer als wie in Beispiel 3 gezeigt

Was ist der beste Weg, dies zu tun ? Ich habe mit PLY begonnen, aber ich konnte nicht herausfinden, wie man die Konflikte reduzieren/reduzieren kann. Der Vorteil von PLY ist, dass es leicht zu manipulieren, was jeder Parse-Regel generiert:

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

Mit PyParse, es ist weniger klar, wie die Ausgabe von parseString() zu ändern. Ich überlegte, ob ich auf der Idee von Alexander Martelli aufbauen sollte, den Zustand in einem Objekt zu halten und die Ergebnisse daraus zu entwickeln, aber ich bin mir nicht sicher, wie das am besten funktioniert.

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) 

Zum Beispiel behandeln "oder" Fälle:

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 

Wie disjunctionCourses(), die nicht wissen, kleinere Sätze abzutrennen? Alles, was es bekommt, ist Tokens, aber was bisher geparst wurde, ist in result gespeichert. Wie kann die Funktion also mitteilen, welche Daten in result welchen Elementen von token entsprechen? Ich glaube, ich durch die Token suchen könnte, dann ein Element der result mit den gleichen Daten finden, aber das Gefühl, gewundenen ...

Auch gibt es viele Beschreibungen, die misc Text enthalten, wie:

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

Aber es ist nicht kritisch, dass ich diesen Text analysiere.

Was ist ein besserer Weg, dieses Problem anzugehen?

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 

ergibt

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

Wenn Sie Konflikte reduzieren/reduzieren, müssen Sie den Vorrang von "oder" und "und" angeben.Im rätseln "und" bindet am engsten, was bedeutet "CS 101 und CS 102 oder CS 201" bedeutet [[CS 101, CS 102] [CS 201]].

Wenn Sie Beispiele für beide finden können, dann ist die Grammatik zweideutig und Sie haben kein Glück. Sie können diese Mehrdeutigkeit jedoch unterspezifizieren lassen, je nachdem, was Sie mit den Ergebnissen machen wollen.

PS, Sieht aus wie die Sprache ist regulär, könnten Sie ein DFA betrachten.

Answer 3

Für einfache Grammatiken Ich mag Packrat Parser (PEGs), die Menge zu einem disziplinierten, strukturiert einen rekursiven Abstieg Parser zu schreiben. In einer dynamisch typisierten Sprache wie Python können Sie nützliche Dinge tun, ohne einen separaten "Parser-Generator" zu haben. Das bedeutet keinen Unsinn mit reduce-reduce Konflikten oder anderen Arcana of LR Parsing.

Ich habe ein wenig gesucht und pyPEG scheint eine nette Bibliothek für Python zu sein.

Answer 4

Ich gebe nicht vor, viel über das Parsen einer Grammatik zu wissen, und für Ihren Fall ist die Lösung von unutbu alles, was Sie brauchen. Aber ich habe ein wenig über Parsing von Eric Lippert in seinen letzten Blog-Posts gelernt.

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

Es ist eine 7-teilige Serie, die dann die Optimierung der Grammatik durch die Erstellung und Analyse eines Grammatik geht einfacher und performanter zu machen Parsen. Er erzeugt C# -Code, um alle Kombinationen bestimmter Grammatiken zu erzeugen, aber es sollte nicht zu weit sein, dies in Python zu konvertieren, um eine ziemlich einfache Grammatik zu parsen.