3

我正在尝试编写一个程序，该程序将接受描述正则表达式的字符串。例如：

10(0U1)*

其中 U 是联合运算符， * 是 Kleene 星（我们还看到了隐含的串联）。

我考虑过标记字符串的原子并基于运算符和操作数构建机器。我想用类似于这样的规则对每个原子进行算法操作：http ://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html

我不确定如何以智能方式最好地解析这种类型的输入，以便我可以以编程方式构建 NFA。

我的程序的目标是接受上述输入并输出将由其 5-touple 描述的相应 NFA。非常感谢任何有关实现该目标的建议。

4

1 回答 1

2

如果您可以使用外部库，最好让现代解析器生成器（例如ANTLR ）完成所有解析工作，并为您的正则表达式提供一个抽象语法树，即使它是一种相对简单的语言。

否则，如果您需要从头开始编写它，则需要首先确定是否需要分词器（或“词法分析器”）。如果您的语言由单字符标记组成（如您的示例中所示），那么您可以安全地跳过编写标记器，而只需遍历字符串中的字符。然后你必须编写解析器，一个扫描令牌列表并构建语法树的大循环。

在任何情况下，您都应该得到这样的语法树，例如10(0U1)*：

语法树

请注意，在语法树中，所有括号和隐式优先规则都消失了，它们被树的结构所取代。

之后，您必须递归地将树转换为 NFA 图。

这是一种可能的方法的粗略草图。

为每种语法节点类型编写翻译方法。该方法将以其开始和结束 NFA 状态作为参数调用，后者是可选的。该方法将绘制自己的图形片段，适当地调用其子级的翻译方法，并返回其结束状态（可能已作为参数省略，因此调用者不知道。）

  • 创建一个开始状态并为语法树的根节点调用翻译方法，将开始状态作为其开始状态传递给它。
  • 文字语法节点（在您的示例中为 0 和 1）将从其起始状态绘制一个箭头到其结束状态，如果未提供，则创建一个新的结束状态：
    在此处输入图像描述
  • 星节点将调用其子节点的转换方法，将其自己的起始状态作为子节点的开始和结束状态（以便 NFA 能够根据需要多次“循环”该状态。）
  • 一个 concat 节点将调用第一个子节点，给它它的开始状态，但没有结束状态；然后它将调用第二个孩子，将第一个孩子的结束状态作为起始状态传递给它；依此类推，构建一个子图的单向序列，每个子图一个。

你应该明白了。

在您将 NFA 图构建为状态的链接结构后（并且可能将其显示为实际图，以用于调试或文档目的），您可以将其转换为正式的元组并输出。

于 2013-02-23T20:43:19.353 回答