将简化正则表达式转换为语法T

Question

我正在研究将正则表达式转换为dfa的算法实现。第一步是将输入正则表达式转换为语法树。例如，ab（a | b）abc将转换为下面的树。在

              .
             / \
            .   c
           / \
          .   b
         / \
        .   a
       / \
      /   \
     /     \
    .       |
   / \     / \
  *   *   a   b
 /     \
a       b

另外，我处理的正则表达式相当简单，唯一的特殊字符是“\”（转义符）、“|”（或运算符）、“（”“）”（括组的括号）和“*”（kleene star）。现在我遇到的问题是，对于如何（在Python中）从输入生成（作为数据结构）这个树，我感到困惑。我知道如何手工操作，但通过一段代码来做这件事让我陷入了困境。在

为了进一步扩展这个问题，我是从左到右还是从右到左来解析表达式？递归有必要吗？假设我使用treelib来创建树，我如何着手解决这个问题。与其说我要求的代码太多，不如说是我应该从哪里开始的解释或伪代码片段。我应该自己做这件事还是有一个图书馆可以让这件事更容易？如有任何答案能帮助我进一步了解如何进行这项手术，将不胜感激。在

Answer 1

对于Python，有几种词法分析和解析工具，例如ply（基本上是lex和yacc的Python实现）。在

使用其中一个而不是自己写。在

Answer 2

签出Dijkstra's Shunting Yard Algorithm。它可以用来将算术表达式转换为语法树。只需做一些更改，它就可以用于正则表达式。在