Как лучше проанализировать простую грамматику?
https://stackoverflow.com/questions/2945357
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
ОК, поэтому я спросил кучу меньших вопросов об этом проекте, но у меня все еще нет особой уверенности в дизайнах, которые я придумывал, поэтому я собираюсь задать вопрос о более широком масштабе.
Я анализируя предварительные необходимые описания для каталога курса. Описания почти всегда следуют определенной форме, что заставляет меня думать, что я могу разобрать большинство из них.
Из текста я хотел бы создать график конечно необходимых отношений. (Эта часть будет легкой, после того, как я сбрал данные.)
Некоторые образцы входов и выходов:
"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
Если все описание просто курс, он выводится напрямую.
Если курсы соединены («и»), все они выводятся в одном списке
Если курс разъединен («или»), они находятся в отдельных списках
Здесь у нас есть как ", так и" и "или".
Одно предостережение, которое облегчает: кажется, что гнездование «и» / «или» фразы никогда не больше, чем показано в примере 3.
Какой лучший способ сделать это? Я начал с PLY, но я не мог выяснить, как разрешить снижение / уменьшение конфликтов. Преимущество PLY заключается в том, что легко манипулировать то, что генерирует каждый правило анализа:
def p_course(p):
'course : DEPT_CODE COURSE_NUMBER'
p[0] = (p[1], int(p[2]))
С Pyparse, менее ясно, как изменить вывод parseString(). Отказ Я рассматривал здание на идею @Alex Martelli о том, чтобы сохранить государство в объекте и наращивать вывод от этого, но я не уверен, что именно это лучше всего сделать.
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)
Например, чтобы обрабатывать «или» случаи:
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
Как делает disjunctionCourses() знать, какие меньшие фразы раздают? Все, что он получает, это токены, но то, что было расставлено, пока хранится в result, так как функция может сказать, какие данные в result соответствует каким элементам token? Я думаю, я мог бы искать по токенам, а затем найти элемент result с теми же данными, но которые чувствуют себя запутанными ...
Кроме того, есть много описаний, которые включают в себя текст MISC, например:
"CS 2110 or permission of instructor"
"INFO 3140 or equivalent experience"
"PYSCH 2210 and sophomore standing"
Но это не критично, что я анализ этот текст.
Что лучше подойти к этой проблеме?
Решение
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)]]
Другие советы
Для простых грамматических грамматиков мне очень нравится разбирающиеся грамматики выражения (PEGS), которые составляют дисциплинированный, структурированный способ написания рекурсивного анализатора. На динамически наведенном языке, похожему на Python, вы можете сделать полезные вещи, не имея отдельного «генератора парсеров». Это означает, что нет ерунды с уменьшением противоречивых конфликтов или других арканов LR Parsing.
Я немного поправил и выпивка Похоже, хорошая библиотека для Python.
Я не претендую о том, чтобы узнать много о разборе грамматики, а для вашего случая решения ЮНУТБУ - это все, что вам нужно. Но я узнал о том, что я узнал об одновременном разборе от Эрика Липперта в своей недавней серии постов в блоге.
http://blogs.msdn.com/b/ericlippert/Archive/2010/04/26/every-prograpogle-there-is-part-one.aspx.
Это серия из 7 деталей, которая проходит через создание и разборка грамматики, затем оптимизируя грамматику, чтобы сделать разборы проще и более качественным. Он производит C # код для генерирования всех комбинаций определенных грамматических грамматиков, но это не должно быть слишком много растяжения, чтобы преобразовать это в Python, чтобы разбирать довольно простой грамматику самостоятельно.
Я знаю, что этот вопрос о десятилетии старый и, безусловно, теперь ответили. Я в основном публикую этот ответ, чтобы доказать себя, что я понял PEG Фарсеры наконец. Я использую фантастическую parsimonious модуль здесь.
То, что говорится, что вы могли бы придумать обшивку грамматики, построить AST и посетить это, чтобы получить желаемую структуру:
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)
Здесь мы проводим путь снизу вверх, начиная с киресуля, как пробел, операторы or, and а также , что в конечном итоге приведет к курсу и, наконец, term. Отказ Класс для посетителей строит желаемую (ну, вроде, нужно избавиться от последнего элемента Tuple).
Если вы уменьшите / уменьшите конфликты, вам нужно указать приоритет «или» и «и». Я предполагаю, что «и« Персональный самый жесткий », что означает« CS 101 и CS 102 или CS 201 »означает [[CS 101, CS 102] [CS 201]].
Если вы можете найти примеры обоих, затем грамматика вернутся, и вы не повезете. Однако вы можете позволить этой двусмысленности оставить подчеркивание, все в зависимости от того, что вы собираетесь делать с результатами.
PS, похоже на язык регулярно, вы могли бы рассмотреть DFA.
