如何最好地解析一个简单的语法？

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 开始，但我不知道如何解决减少/减少冲突。 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"

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

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

原文由 Nick Heiner 发布，翻译遵循 CC BY-SA 4.0 许可协议

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 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

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

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

原文由 Norman Ramsey 发布，翻译遵循 CC BY-SA 2.5 许可协议