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

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

27 голосов
/ 31 мая 2010

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

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

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

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

"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

  1. Если все описание является просто курсом, оно выводится напрямую.

  2. Если курсы объединены («и»), все они выводятся в одном списке

  3. Если курс отделен ("или"), они находятся в отдельных списках

  4. Здесь мы имеем «и» и «или».

Одна оговорка, которая облегчает: кажется, что вложение фраз "и" / "или" никогда не бывает больше, чем показано в примере 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"

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

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

Ответы [ 5 ]

24 голосов
/ 31 мая 2010 
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)]]
7 голосов
/ 01 июня 2010

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

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

1 голос
/ 03 марта 2019

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

1 голос
/ 01 июня 2010

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

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

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

0 голосов
/ 31 мая 2010

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

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

PS, похоже, язык обычный, вы могли бы рассмотреть DFA.

...