如何最佳解析简单语法？

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中展示的更大的嵌套“and”/“or”短语。

最佳方法是什么？我先尝试了 PLY，但是我没法解决 reduce/reduce 冲突。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)

例如，处理“or”情况的方法是：

    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"

但是解析那段文本并不是至关重要的。

有一个更好的方法来解决这个问题吗？

- Nick Heiner

---

你的样例输入和输出中的编号与你对它们的讨论中的编号不匹配。 - Tommy Herbert

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

- unutbu

---

哇，这比我之前尝试的其他方法简单多了。你是怎么想到的？ - Nick Heiner

@Rosarch: 我相信有改进我所写内容的方法，但关键思想是可以从左到右读取标记并通过跟踪状态来构建结果。一旦找到类似于“CS”的部门，后面的所有数字都指向“CS”，直到找到另一个部门...我先编写了测试代码，然后进行多次迭代来编写解析函数以通过测试。在第一次尝试解决这个问题时，我忽略了“and”和“or”。然后在第二次尝试中，我意识到“and”有点无关紧要，但“or”需要使用第二个列表option。希望能对您有所帮助。 - unutbu

Answer 2

对于简单的语法，我非常喜欢解析表达式语法（PEGs），它是一种有纪律、结构化的递归下降解析器编写方式。在像Python这样的动态类型语言中，您可以在不需要单独的“解析器生成器”的情况下进行有用的操作。这意味着没有无用的reduce-reduce冲突或其他LR解析的奥秘。

我做了一些搜索，pyPEG 看起来是一个不错的Python库。

- Norman Ramsey

---

pyPEG的源代码看起来简洁而且写得很好。棒极了。 - minghua

已添加了一个带有 PEG 解析器的答案。 - Jan

Answer 3

我知道这个问题已经有十年的历史，并且肯定已经得到了答复。我主要发布这个答案是为了证明我已经最终理解了PEG解析器。我在这里使用了极好的parsimonious模块。
话虽如此，您可以构建一个解析语法，构建一棵抽象语法树并访问它，以获得所需的结构。

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)

我们从底层开始，一步步地介绍如何使用类似于空格的brickets、运算符or、and和,来逐渐构建出课程和最终的term。访客类（Visitor Class）将会构建所需的结构（当然，需要去掉最后一个元组元素）。

- Jan

Answer 4

如果你遇到了reduce/reduce冲突，你需要指定"or"和"and"的优先级。我猜"and"的绑定最紧密，意味着"CS 101 and CS 102 or CS 201"的意思是[[CS 101，CS 102] [CS 201]]。

如果你能找到两者的例子，那么语法就是模棱两可的，你就没办法了。然而，你可能可以让这种歧义保持未指定状态，这完全取决于你要对结果做什么。

顺便说一句，看起来这种语言是规则的，你可以考虑使用DFA。

- user110763

Answer 5

为了完整起见，还有SLY。创建者David Beazley在PyCon 2018上做了一个很棒的演讲，非常有趣。

- CpILL

Answer 6

我不会假装自己对语法解析知道很多，就你的情况而言，unutbu的解决方案已经足够。但是，我从Eric Lippert最近的一系列博客文章中学到了许多有关语法解析的知识。

链接

这是一个由七部分组成的系列，介绍如何创建和解析语法，然后通过优化语法使解析更容易、更高效。他还编写了C#代码来生成特定语法的所有组合，但将其转换为Python以解析自己相当简单的语法应该不是什么难事。

- Josh Smeaton

---

请注意，在语言中使用语法作为字符串的生成器和使用语法作为字符串的识别器之间存在巨大的区别。前者问题非常简单；正如您所看到的，我只用了几十行代码就解决了它。后者则相当困难，特别是如果语法很复杂。 - Eric Lippert

@eric 好的，我写完这个答案后，尝试着自己做了一下，发现它相当不同，对于那些正在摸索中的人来说更加困难。 - Josh Smeaton

链接已失效。 - CpILL