Come meglio analizzare una grammatica semplice?

Question

Ok, quindi ho fatto un po 'di domande più piccole su questo progetto, ma non ho ancora molta fiducia nel design che sto creando, quindi farò una domanda su una scala più ampia .

Sto analizzando le descrizioni dei prerequisiti per un catalogo dei corsi. Le descrizioni seguono quasi sempre una certa forma, il che mi fa pensare di poterne analizzare la maggior parte.

Dal testo, vorrei generare un grafico delle relazioni pre-requisito del corso. (La parte sarà facile, dopo aver analizzato i dati.)

Alcuni ingressi e uscite del campione:

"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. Se l'intera descrizione è solo un corso, è emesso direttamente.

2. Se i corsi sono congiunti ("e"), sono tutti in uscita nella stessa lista

3. Se il corso sono disgiunti ("o"), sono in liste separate

4. Qui, abbiamo sia "e" che "o".

Un avvertimento che rende più facile: sembra che la nidificazione di "e"/"o" ​​frasi non è mai superiore come mostrato nell'esempio 3.

Qual è il modo migliore per farlo ? Ho iniziato con PLY, ma non sono riuscito a capire come risolvere i conflitti di riduzione/riduzione. Il vantaggio di PLY è che è facile da manipolare ciò che ogni regola di parsing genera:

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

Con PyParse, è meno chiaro come modificare l'output di parseString(). Stavo considerando l'idea di @Alex Martelli di mantenere lo stato in un oggetto e di costruire l'output da quello, ma non sono sicuro di come sia meglio farlo.

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) 

Per esempio, per gestire "o" casi:

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 

Come si fa a sapere che disjunctionCourses() più piccola frasi di disgiungere? Tutto ciò che ottiene è gettoni, ma ciò che è stato analizzato fino ad ora è memorizzato in result, così come può la funzione di dire che i dati in result corrisponde a quale elementi di token? Credo che avrei potuto cercare attraverso i gettoni, poi trovare un elemento di result con gli stessi dati, ma che si sentono contorto ...

Inoltre, ci sono molte descrizioni che includono testo Varie, come:

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

Ma non è fondamentale che io analizzi quel testo.

Che cosa è un modo migliore per affrontare questo problema?

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 

cede

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

Se si riducono/riducono i conflitti è necessario specificare la precedenza di "o" e "e".Sto indovinando "e" si lega più stretto, che significa "CS 101 e CS 102 o CS 201" significa [[CS 101, CS 102] [CS 201]].

Se riesci a trovare esempi di entrambi, allora la grammatica è ambigua e sei sfortunato. Tuttavia potresti essere in grado di lasciare che questa ambiguità sia lasciata sotto-specificata, tutto a seconda di cosa farai con i risultati.

PS, sembra che la lingua sia regolare, si potrebbe prendere in considerazione un DFA.

Answer 3

Per semplici grammatiche mi piace molto Analisi di espressione Grammatiche (PEG), che ammontano a un modo strutturato disciplinato di scrivere un parser ricorsivo-discesa. In un linguaggio tipizzato dinamicamente come Python puoi fare cose utili senza avere un "generatore di parser" separato. Ciò non significa assurdità con conflitti di riduzione-riduzione o altri arcani di analisi LR.

Ho fatto una piccola ricerca e pyPEG sembra essere una bella libreria per Python.

Answer 4

Non pretendo di sapere molto sull'analisi di una grammatica, e per il tuo caso la soluzione di unutbu è tutto ciò di cui hai bisogno. Ma ho imparato un bel po 'di parsing da Eric Lippert nella sua recente serie di post sul blog.

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

Si tratta di una serie in 7 parti che passa attraverso la creazione e l'analisi di una grammatica, quindi ottimizzando la grammatica per rendere l'analisi più facile e più performante. Produce codice C# per generare tutte le combinazioni di grammatiche particolari, ma non dovrebbe essere troppo lungo per convertirlo in Python per analizzare una grammatica piuttosto semplice della tua.