HTML标记器算法

Question

我正在尝试编写一个基本的html解析器，它不容忍错误，并且正在读取HTML5解析算法，但是对于一个简单的解析器来说，它的信息量太大了。我想知道是否有人对基本令牌器的逻辑有了什么想法，它将简单地将一个小的html转换成一个重要标记的列表。我更感兴趣的是逻辑而不是代码。

std::string html = "<div id='test'> Hello <span>World</span></div>";

Tokenizer t;
t.tokenize(html);

因此，对于上面的html，我想将其转换为如下所示的列表：

["<","div","id", "=", "test", ">", "Hello", "<", "span", ">", "world", "</", "span", ">", "<", "div", ">"]

对于tokenize方法，我没有任何东西，但我想知道逐字符迭代html字符是否是构建列表的最佳方法。

void Tokenizer::tokenize(std::string html){
    std::list<std::string> tokens;

    for(int i = 0; i < html.length();i++){
        char c = html[i];
        if(...){
            ...
        }
    }
}

Answer 1

我想你要找的是一个词法分析器。它的目标是获取在您的语言中定义的所有标记，在本例中是HTML。正如@IraBaxter所说，您可以使用一个在Linux或OSX中创建的词汇工具，比如Lex；但是您必须定义规则，为此需要使用正则表达式。

但是，如果你想知道这个问题的算法，你可以查阅Keith D. Cooper & Linda Torczon的书，第2章，扫描仪。本章讨论Automatas和谁可以用来创建扫描仪，在那里它使用表格驱动的扫描器来获取令牌，就像您想要的那样。让我和大家分享一下这一章的形象：

​

​

我们的想法是定义一个DFA，其中您拥有：

• 识别器中的有限状态集，包括开始状态、接受状态和错误状态。
• 阿尔法贝。
• 一个函数，它帮助确定转换是否有效，使用转换表，或者，如果不想使用表，则编写自动机。

花点时间研究一下这一章。

Answer 2

这里的其他答案都很棒，您肯定应该使用词汇分析器生成器(如flex )来完成这项工作。这种生成器的输入是标识不同令牌类型的规则列表。输入文件可能如下所示：

WHITE_SPACE    \s*
IDENTIFIER     [a-zA-Z0-9_]+
LEFT_ANGLE     <

flex使用的算法本质上是：

• 找到与文本最匹配的规则。
• 如果两个规则匹配相同的文本长度，请选择前面提供的规则列表中出现的规则。

您可以使用正则表达式轻松地编写此算法。但是，请记住，这不会像flex那样快，因为flex将正则表达式编译成非常快的DFA。