¿Cuál es la mejor manera de analizar una gramática simple?

Question

Ok, entonces hice un montón de preguntas más pequeñas sobre este proyecto, pero todavía no tengo mucha confianza en los diseños que voy a desarrollar, por lo que voy a hacer una pregunta en una escala más amplia .

Estoy analizando descripciones de requisitos previos para un catálogo de cursos. Las descripciones casi siempre siguen una cierta forma, lo que me hace pensar que puedo analizar la mayoría de ellas.

Desde el texto, me gustaría generar un gráfico de las relaciones de los requisitos previos del curso. (Esa parte será fácil, después de haber analizado los datos.)

Algunas entradas y salidas de la muestra:

"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. Si toda la descripción es sólo un curso, que se emite directamente.

2. Si los cursos son unidos ("y"), que son todos de salida en la misma lista

3. Si el curso se disocian ("o"), que están en listas separadas

4. Aquí, tenemos tanto "y" y "o".

Una advertencia que hace que sea más fácil: parece que la anidación de las frases "y"/"o" ​​nunca es mayor que el del ejemplo 3.

¿Cuál es la mejor manera de hacer esto ? Empecé con PLY, pero no pude resolver cómo resolver los conflictos de reducción/reducción. La ventaja de PLY es que es fácil de manipular lo que genera cada regla de análisis:

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

Con PyParse, es menos claro cómo modificar la salida de parseString(). Estaba pensando en la idea de @Alex Martelli de mantener el estado en un objeto y aumentar el rendimiento de eso, pero no estoy seguro de cómo hacerlo mejor.

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) 

Por ejemplo, para manejar "o" casos:

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 

¿Cómo disjunctionCourses() saben qué frases más pequeño para disjoin? Todo lo que obtiene son tokens, pero lo que se ha analizado hasta ahora se almacena en result, entonces, ¿cómo puede la función indicar qué datos en result corresponden a qué elementos de token? Creo que podría buscar a través de las fichas, y luego encontrar un elemento de result con los mismos datos, pero que se sienten enrevesado ...

Además, hay muchas descripciones que incluyen texto misceláneos, como:

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

Pero no es crítico que analice ese texto.

¿Cuál es una mejor manera de abordar este 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 

produce

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

Si obtiene conflictos de reducción/reducción, debe especificar la precedencia de "o" y "y".Supongo que "y" se une más apretado, lo que significa "CS 101 y CS 102 o CS 201" significa [[CS 101, CS 102] [CS 201]].

Si puede encontrar ejemplos de ambos, entonces la gramática es ambigua y no tiene suerte. Sin embargo, es posible que deje que esta ambigüedad quede poco especificada, todo depende de lo que vaya a hacer con los resultados.

PD, Parece que el lenguaje es regular, puede considerar un DFA.

Answer 3

Para gramáticas simples me gusta mucho Analizar gramáticas de expresión (PEG), que equivalen a una forma disciplinada y estructurada de escribir un analizador sintáctico descendente recursivo. En un lenguaje de tipado dinámico como Python puede hacer cosas útiles sin tener un "generador de analizador" por separado. Eso significa que no hay tonterías con los conflictos reducir-reducir u otros arcanos de análisis LR.

Hice una pequeña búsqueda y pyPEG parece ser una buena biblioteca para Python.

Answer 4

No pretendo saber mucho sobre el análisis de una gramática, y para su caso la solución de unutbu es todo lo que necesitará. Pero aprendí bastante sobre el análisis de Eric Lippert en su reciente serie de publicaciones en el blog.

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

Es una serie de 7 porciones que pasa a través de la creación y análisis de una gramática, a continuación, la optimización de la gramática para hacer el análisis más fácil y con más prestaciones. Produce código C# para generar todas las combinaciones de gramáticas particulares, pero no debería ser demasiado exagerado convertirlo en python para analizar una gramática bastante simple.