c++ - 正则表达式解析器

Question

我最近一直在学习基础知识，作为练习，我决定在 C++ 环境中实现 DFA。所以基本上它是正则表达式。当我从头开始构建树时，它运行良好，但我不确定如何处理正则表达式。

我的意思是如果我有一个正则表达式，例如 (test)* 我必须将它转换成 DFA。问题是，为了做到这一点，我必须解析正则表达式。这似乎是一个恶性循环(更糟糕的是因为我实际上需要一个括号感知解析器，正则表达式在这里不起作用)。

那么怎么处理呢？我完全理解我们现在有工具可以做到这一点(例如 Flex 和 Bison)，但这些工具是基于正则表达式的(好吧，至少分词器是)。那么一开始发生了什么？如何从头开始编写正则表达式解析器？任何对书籍/文章的引用表示赞赏。

Answer 1

我曾经写过我自己的 Flex 版本，它生成了一组类而不是整个程序。首先，我不得不手动解析正则表达式，但当我最终编写它时，我将正则表达式解析机制替换为程序本身生成的解析机制。

手动解析正则表达式其实很简单。首先，您必须指定要达到的结果。例如在我的例子中:

[abc]+test

被解释为:

[abc]@[abc]*@[t]@[e]@[s]@[t]

其实是等价的(@是人为添加的连接符)

然后您必须创建一组规则，例如。

'[' spotted:
    - (optionally) expect '^' character;
    - repeat:
        - expect a non-special character;
            - If it is not last character and is succeeded by '-', expect another character
    - until `]` is spotted
    - Return a character set
'(' spotted:
    - Return a block-begin
')' spotted:
    - Return a block-end
'*' spotted:
    - Return a star-operator
'+' spotted:
    - Return a plus-operator
'.' spotted:
    - Return a whole character set
Any other char spotted:
    - Return a character set consisting of this single character

这样编写的算法将为您提供一个分词器 - 例程，它将元素分解为逻辑分词。然后你必须将它们处理成一个表达式树，这可以通过实现 Reverse Polish Notation algorithm 来解决。 .

你可以查看我的解析器生成器here ，尽管它会生成一个 Delphi 代码。不幸的是，自述文件是波兰语的，但里面有一些例子。尝试例如:

Number=[0-9]+
Operator=[\+\-\*/]

和

SpkParserGenerator -i myfile.regex -mc -sg

顺便说一句，你可以自己生成一个解析器，然后简单地将它从Delphi翻译成C++，即使你不太了解Delphi，它实际上也很简单。

这是我用来为解析器生成器生成解析器的一组规则:

SetRange=\{([0-9]*,[0-9]+)|([0-9]+,[0-9]*)|([0-9]+)\}
Star=\*
Plus=\+
QMark=\?
CharRange=\[\^?((\\.)|(\#[0-9]{3})|([^\\\#\]]))+\]
AnyChar=\.
EscapedChar=\\.
AsciiChar=\#[0-9]{3}
Char=[^\[\]\{\}\.\(\)\#\*\+\?\|\\]
OpenParenthesis=\(
CloseParenthesis=\)
Alternative=\|