Как лучше всего разобрать простую грамматику?

Хорошо, поэтому я задал кучу меньших вопросов об этом проекте, но у меня все еще нет уверенности в дизайнах, которые я придумываю, поэтому я собираюсь задать вопрос по более широкому масштаб.

Я разбираю предварительные описания каталога курсов. Описания почти всегда следуют определенной форме, что заставляет меня думать, что я могу разобрать большинство из них.

Из текста, я хотел бы создать график, конечно, необходимых отношений. (Эта часть будет простой, после анализа данных.)

Некоторые входы и выходы выборки:

"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 с теми же данными, но это кажется запутанным...

Кроме того, существует много описаний, которые включают в себя текст, например:

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

Но не критично, что я разбираю этот текст.

Какой лучший способ подойти к этой проблеме?

Ответ 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

дает

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

Ответ 2

Для простых грамматик мне действительно нравятся грамматики синтаксического анализа (PEG), которые представляют собой дисциплинированный, структурированный способ написания синтаксического анализатора с рекурсивным спуском. В динамически типизированном языке, таком как Python, вы можете делать полезные вещи, не имея отдельного "генератора анализатора". Это означает, что нет чепухи с конфликтами уменьшения-уменьшения или другими тайнами анализа LR.

Я немного поискал, и pyPEG, похоже, хорошая библиотека для Python.

Ответ 3

Я знаю, что этому вопросу уже около десяти лет, и на него, безусловно, уже дан ответ. В основном я публикую этот ответ, чтобы доказать, что наконец-то понял парсеры 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. Класс посетителя строит желаемую (ну, вроде, нужно избавиться от последнего элемента кортежа) структуру.

Ответ 4

Если вы получаете конфликты уменьшения/уменьшения, вам нужно указать приоритет "или" и "и". Im guessing "и" binds tightest, что означает "CS 101 и CS 102 или CS 201" означает [[CS 101, CS 102] [CS 201]].

Если вы можете найти примеры обоих, то грамматика является двусмысленной, и вам не повезло. Однако вы можете позволить этой двусмысленности оставить underspecified, все в зависимости от того, что вы собираетесь делать с результатами.

PS, Похоже, что язык является регулярным, вы можете рассмотреть DFA.

Ответ 5

Я не притворяюсь, что много разбираюсь в разборе грамматики, и для вашего случая решение unutbu - это все, что вам нужно. Но я немного узнал о разборе Эрика Липперта в его недавней серии сообщений в блогах.

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

Это серия из 7 частей, которая проходит через создание и анализ грамматики, а затем оптимизирует грамматику, чтобы сделать синтаксический анализ более простым и результативным. Он создает код С# для генерации всех комбинаций конкретных грамматик, но он не должен быть слишком большим, чтобы преобразовать его в python для синтаксического анализа довольно простой грамматики.