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

python plotly axis

Question

Ok, así que he hecho un montón de preguntas más pequeñas sobre este proyecto, pero todavía no tengo mucha confianza en los diseños que se me ocurren, así que voy a hacer una pregunta en una escala más amplia.

Estoy analizando las 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.

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

Algunos ejemplos de entradas y salidas:

"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 la descripción completa es solo un curso, se envía directamente.

2. Si los cursos están unidos ("y"), todos se mostrarán en la misma lista

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

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

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

¿Cuál es la mejor manera de hacer esto? Comencé con PLY, pero no pude averiguar cómo resolver los conflictos de reducción / reducción. La ventaja de PLY es que es fácil 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 considerando construir sobre la idea de @Alex Martelli de mantener el estado en un objeto y acumular resultados a partir 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 sabe disjunctionCourses() qué frases más pequeñas para separar? Todo lo que obtiene son tokens, pero lo que se ha analizado hasta ahora se almacena en el result , entonces, ¿cómo puede la función indicar qué datos en el result corresponden a qué elementos del token ? Supongo que podría buscar a través de los tokens, luego encontrar un elemento de result con los mismos datos, pero eso se siente complicado ...

Además, hay muchas descripciones que incluyen texto misceláneo, 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 la mejor manera de abordar este problema?

Answer 1

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 necesita. Pero aprendí un poco sobre el análisis de Eric Lippert en su reciente serie de publicaciones de blog.

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

Es una serie de 7 partes que consiste en crear y analizar una gramática, luego optimizar la gramática para que el análisis sea más fácil y tenga más rendimiento. Produce el código C # para generar todas las combinaciones de gramáticas particulares, pero no debería ser demasiado difícil convertirlo en python para analizar una gramática bastante simple.

Answer 2

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

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

Answer 3

Si obtiene reducir / reducir conflictos, debe especificar la prioridad de "o" y "y". Estoy adivinando "y" se une más estrechamente, lo que significa "CS 101 y CS 102 o CS 201" significa [[CS 101, CS 102] [CS 201]].

Si puedes encontrar ejemplos de ambos, entonces la gramática es ambigua y no tienes suerte. Sin embargo, es posible que pueda dejar esta ambigüedad sin especificar, dependiendo de lo que vaya a hacer con los resultados.

PD: Parece que el lenguaje es regular, se podría considerar un DFA.

Answer 4

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

rendimientos

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)]]