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

Question

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

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

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

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

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

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" 

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

Что является лучшим способом подойти к этой проблеме?

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

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

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