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

Ответ 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 для синтаксического анализа довольно простой грамматики.