34

好的，所以我已经问了一些关于这个项目的小问题，但是我仍然对我提出的设计没有太大的信心，所以我要问一个更广泛的问题。

我正在解析课程目录的先决条件描述。描述几乎总是遵循某种形式，这让我觉得我可以解析其中的大部分。

从文本中，我想生成一个课程先决条件关系图。（在我解析数据之后，这部分会很容易。）

一些示例输入和输出：

"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. 在这里，我们有“and”和“or”。

一个使它更容易的警告：似乎“and”/“or”短语的嵌套永远不会大于示例 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"

但我解析该文本并不重要。

解决这个问题的更好方法是什么？

4

6 回答 6

26 
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)]]
于 2010-05-31T18:50:35.000 回答
7

对于简单的语法，我真的很喜欢 Parsing Expression Grammars (PEGs)，它相当于一种编写递归下降解析器的有纪律的、结构化的方式。在像 Python 这样的动态类型语言中，您可以在没有单独的“解析器生成器”的情况下做有用的事情。这意味着没有减少-减少冲突或其他 LR 解析奥秘的废话。

我做了一些搜索，pyPEG似乎是一个不错的 Python 库。

于 2010-05-31T20:59:33.440 回答
4

我知道这个问题大约有十年的历史了，现在肯定已经得到了回答。我主要发布这个答案来证明自己我 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. 访问者类构建了所需的（嗯，有点，需要摆脱最后一个元组元素）结构。

于 2019-03-03T07:01:30.370 回答
1

如果您遇到减少/减少冲突，您需要指定“或”和“和”的优先级。我猜“和”绑定最紧密，意思是“CS 101 和 CS 102 或 CS 201”表示 [[CS 101, CS 102] [CS 201]]。

如果你能找到两者的例子，那么语法就是模棱两可的，你就不走运了。但是，您可能可以不指定这种歧义，这完全取决于您要对结果做什么。

PS，看起来语言是正规的，你可以考虑一个DFA。

于 2010-05-31T18:46:51.770 回答
1

我不会假装对解析语法了解很多，对于您的情况，unutbu 的解决方案就是您所需要的。但我从 Eric Lippert 最近的一系列博客文章中学到了一些关于解析的知识。

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

这是一个 7 部分的系列，通过创建和解析语法，然后优化语法以使解析更容易和更高效。他生成 C# 代码来生成特定语法的所有组合，但将其转换为 python 以解析您自己的相当简单的语法应该不会太费力。

于 2010-05-31T21:28:14.040 回答
0

只是以完整性的名义存在SLY。创作者 David Beazley在 PyCon 2018 上进行了精彩的演讲，这很有趣。

于 2021-11-24T23:40:50.027 回答