La meilleure façon d'analyser une grammaire simple?
https://stackoverflow.com/questions/2945357
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Ok, donc j'ai demandé un tas de petites questions sur ce projet, mais je ne comprends toujours pas beaucoup de confiance dans la conception que je suis à venir avec, donc je vais poser une question sur une plus large échelle.
Je suis une description de pré analyse pas-requis pour un catalogue de cours. Les descriptions suivent presque toujours une certaine forme, ce qui me fait penser que je peux analyser la plupart d'entre eux.
D'après le texte, je voudrais générer un graphique des relations pré-requis cours. (Cette partie sera facile, après avoir analysé les données.)
Certaines entrées et sorties de l'échantillon:
"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
-
Si la description entière est juste un cours, il est sortie directement.
-
Si les cours sont accolées ( "et"), ils sont toutes les sorties dans la même liste
-
Si le cours sont disjoints ( "ou"), ils sont dans des listes séparées
-
Ici, nous avons à la fois "et" et "ou".
Une mise en garde qui le rend plus facile. Il semble que l'imbrication des phrases « et » / « ou » ne dépasse jamais comme indiqué dans l'exemple 3
Quelle est la meilleure façon de le faire? J'ai commencé avec PLI, mais je ne pouvais pas comprendre comment résoudre le réduire / réduire les conflits. L'avantage de PLI est qu'il est facile de manipuler ce que chaque règle d'analyse syntaxique génère:
def p_course(p):
'course : DEPT_CODE COURSE_NUMBER'
p[0] = (p[1], int(p[2]))
Avec PyParse, il est moins facile de modifier la sortie de parseString(). Je considérais la construction sur l'idée de Martelli de garder @ Alex état dans un objet et la construction de la sortie, mais je ne sais pas exactement comment cela est mieux fait.
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)
Par exemple, à la poignée "ou" cas:
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
Comment savoir de disjunctionCourses() qui plus petites phrases disjoindre? Tout ce qu'il obtient est des jetons, mais ce qui est jusqu'à présent été analysé est stocké dans result, comment tell fonction peut que les données dans correspond de result à laquelle les éléments de token? Je suppose que je pourrais chercher à travers les jetons, puis trouver un élément de result avec les mêmes données, mais cette sensation alambiquée ...
En outre, il y a beaucoup de descriptions qui incluent de textes divers, comme:
"CS 2110 or permission of instructor"
"INFO 3140 or equivalent experience"
"PYSCH 2210 and sophomore standing"
Mais il est essentiel que je parse que le texte.
Qu'est-ce qu'une meilleure façon d'aborder ce problème?
La solution
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)]]
Autres conseils
Pour des régles simples que je vraiment comme Parsing Expression (Grammars PEG), montant à une manière disciplinée, structurée d'écrire un analyseur récursif-descente. Dans un langage typé dynamiquement comme Python, vous pouvez faire des choses utiles sans avoir un « générateur d'analyseur syntaxique » séparé. Cela signifie pas un non-sens avec réduire les conflits, réduire ou d'autres Arcanes de l'analyse syntaxique LR.
Je l'ai fait un peu de recherche et pyPEG semble être une bibliothèque agréable pour Python.
Je ne prétends pas en savoir beaucoup sur l'analyse d'une grammaire, et pour votre cas, la solution par unutbu est tout ce que vous aurez besoin. Mais j'ai appris un peu de juste sur l'analyse syntaxique de Eric Lippert dans ses séries récentes de messages de blog.
http://blogs.msdn.com/b/ericlippert/archive/2010/04/26/every-program-there-is-part-one.aspx
Il est une série de 7 partie qui passe par la création et l'analyse d'une grammaire, l'optimisation puis la grammaire pour rendre l'analyse plus facile et plus performant. Il produit du code C # pour générer toutes les combinaisons de grammaires particulières, mais il ne devrait pas être trop d'un tronçon de convertir en python pour analyser une grammaire assez simple de votre propre.
Je sais que cette question est d'environ dix ans et a certainement répondu maintenant. Je signale surtout cette réponse me prouver que je l'ai compris parseurs PEG enfin. J'utilise le fantastique Module parsimonious ici.
Cela étant dit, vous pouvez venir avec une grammaire d'analyse syntaxique, construire une ast et visiter celui-ci pour obtenir la structure souhaitée:
from parsimonious.nodes import NodeVisitor
from parsimonious.grammar import Grammar
from itertools import groupby
grammar = Grammar(
r"""
term = course (operator course)*
course = coursename? ws coursenumber
coursename = ~"[A-Z]+"
coursenumber = ~"\d+"
operator = ws (and / or / comma) ws
and = "and"
or = (comma ws)? "or"
comma = ","
ws = ~"\s*"
"""
)
class CourseVisitor(NodeVisitor):
def __init__(self):
self.current = None
self.courses = []
self.listnum = 1
def generic_visit(self, node, children):
pass
def visit_coursename(self, node, children):
if node.text:
self.current = node.text
def visit_coursenumber(self, node, children):
course = (self.current, int(node.text), self.listnum)
self.courses.append(course)
def visit_or(self, node, children):
self.listnum += 1
courses = ["CS 2110", "CS 2110 and INFO 3300",
"CS 2110, INFO 3300", "CS 2110, 3300, 3140",
"CS 2110 or INFO 3300", "MATH 2210, 2230, 2310, or 2940"]
for course in courses:
tree = grammar.parse(course)
cv = CourseVisitor()
cv.visit(tree)
courses = [list(v) for _, v in groupby(cv.courses, lambda x: x[2])]
print(courses)
Ici, nous marchons chemin de bas en haut, en commençant par des espaces, comme des briquettes les opérateurs or, and et , qui finira par conduire à la formation et enfin la term. La classe de visiteur construit la (bien, en quelque sorte, on a besoin de se débarrasser du dernier élément de tuple) structure.
Si vous réduire / réduire les conflits, vous devez spécifier la priorité de « ou » et « et ». Im deviner "et" se fixe, ce qui signifie "plus serré CS 101 et CS 102 ou CS 201" signifie [[CS 101, CS 102] [CS 201]].
Si vous pouvez trouver des exemples à la fois alors la grammaire est ambigous et vous êtes hors de la chance. Cependant, vous pourriez être en mesure de laisser cette ambiguïté laisser underspecified, tout dépend de ce que vous allez faire avec les résultats.
PS, la langue On dirait est régulière, vous pourriez envisager un DFA.
