Cách tốt nhất để phân tích ngữ pháp đơn giản?

Question

Ok, vì vậy tôi đã hỏi một loạt các câu hỏi nhỏ hơn về dự án này, nhưng tôi vẫn không có nhiều tự tin trong các thiết kế mà tôi sắp đưa ra, vì vậy tôi sẽ đặt một câu hỏi trên quy mô rộng hơn .

Tôi đang phân tích cú pháp mô tả trước khi cần thiết cho danh mục khóa học. Các mô tả hầu như luôn luôn tuân theo một hình thức nhất định, điều đó khiến tôi nghĩ rằng tôi có thể phân tích hầu hết chúng.

Từ văn bản, tôi muốn tạo biểu đồ các mối quan hệ tiền điều kiện tiên quyết. (Phần đó sẽ được dễ dàng, sau khi tôi đã phân tích dữ liệu.)

Một số đầu vào và đầu ra mẫu:

"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. Nếu mô tả toàn bộ chỉ là một khóa học, nó là kết quả trực tiếp.

2. Nếu khóa học là dính liền ("và"), họ là tất cả đầu ra trong cùng một danh sách

3. Nếu khóa học được disjoined ("hay"), họ đang có trong danh sách riêng biệt

4. Ở đây, chúng tôi có cả "và" và "hoặc".

Một caveat mà làm cho nó dễ dàng hơn: có vẻ là làm tổ của cụm từ "và"/"hoặc" không bao giờ lớn hơn như trong ví dụ 3.

cách tốt nhất để làm điều này là gì ? Tôi bắt đầu với PLY, nhưng tôi không thể tìm ra cách giải quyết các xung đột giảm/giảm. Ưu điểm của PLY là nó dễ dàng để thao tác những gì từng quy tắc phân tích cú pháp tạo:

def p_course(p): 
'course : DEPT_CODE COURSE_NUMBER' 
p[0] = (p[1], int(p[2])) 

Với PyParse, đó là chưa rõ ràng làm thế nào để sửa đổi đầu ra của parseString(). Tôi đang xem xét xây dựng theo ý tưởng của @Alex Martelli về giữ trạng thái trong một đối tượng và xây dựng đầu ra từ đó, nhưng tôi không chắc chắn chính xác cách thực hiện tốt nhất.

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) 

Ví dụ, để xử lý "hoặc" trường hợp:

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 

Làm thế nào để biết được disjunctionCourses() nhỏ cụm từ để disjoin? Tất cả nó được là thẻ, nhưng những gì được phân tích cú pháp cho đến nay được lưu trữ trong result, vì vậy làm thế nào có thể chức năng cho biết dữ liệu trong result tương ứng với các yếu tố của token? Tôi đoán tôi có thể tìm kiếm thông qua các thẻ, sau đó tìm một phần tử của result với cùng một dữ liệu, nhưng điều đó cảm thấy phức tạp ...

Ngoài ra, có rất nhiều mô tả mà bao gồm văn bản misc, như:

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

Nhưng điều quan trọng là tôi phân tích văn bản đó.

Cách nào tốt hơn để tiếp cận vấn đề này?

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 

mang

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

Nếu bạn nhận được giảm/giảm xung đột bạn cần xác định quyền ưu tiên của "hoặc" và "và".Tôi đoán "và" liên kết chặt chẽ nhất, có nghĩa là "CS 101 và CS 102 hoặc CS 201" có nghĩa là [[CS 101, CS 102] [CS 201]].

Nếu bạn có thể tìm thấy các ví dụ về cả hai ngữ pháp thì không rõ ràng và bạn đã hết may mắn. Tuy nhiên bạn có thể để cho sự mơ hồ này được để lại dưới mức không xác định, tất cả phụ thuộc vào những gì bạn sẽ làm với kết quả.

PS, Có vẻ như ngôn ngữ là thông thường, bạn có thể xem xét DFA.

Answer 3

Đối với văn phạm đơn giản, tôi thực sự thích Phân tích biểu thức ngữ pháp (chốt), trong đó số tiền một cách có cấu trúc xử lý kỷ luật của việc viết một phân tích cú pháp đệ quy-gốc. Trong một ngôn ngữ được gõ động như Python, bạn có thể làm những việc hữu ích mà không cần phải có một trình tạo phân tích cú pháp riêng biệt. Điều đó có nghĩa là không vô nghĩa với việc giảm bớt xung đột hoặc các arcana khác của phân tích LR.

Tôi đã tìm kiếm một chút và pyPEG dường như là một thư viện tốt cho Python.

Answer 4

Tôi không giả vờ biết nhiều về phân tích ngữ pháp và đối với trường hợp của bạn, giải pháp của unutbu là tất cả những gì bạn cần. Nhưng tôi đã học được một chút công bằng về phân tích cú pháp từ Eric Lippert trong loạt bài đăng blog gần đây của anh ấy.

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

Đó là một loạt 7 phần mà đi thông qua việc tạo và phân tích ngữ pháp, sau đó tối ưu hóa ngữ pháp để làm phân tích dễ dàng hơn và performant hơn. Ông sản xuất mã C# để tạo ra tất cả các kết hợp của các ngữ pháp cụ thể, nhưng nó không nên quá nhiều của một đoạn để chuyển đổi thành python để phân tích một ngữ pháp khá đơn giản của riêng bạn.