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

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

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

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

Если вы получаете конфликты уменьшения/уменьшения, вам необходимо указать приоритет «или» и «и». Я предполагаю, что «и» связывает сильнее всего, что означает «CS 101 и CS 102 или CS 201» означает [[CS 101, CS 102] [CS 201]].

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

PS. Похоже, язык обычный, можно подумать о DFA.

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

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

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