ale*_*lex 37 html browser parsing tokenize html-parsing
为了论证,我们假设一个HTML解析器.
我已经读过它首先将所有内容标记化,然后解析它.
tokenize意味着什么？
解析器是否每个都读取每个字符,构建一个多维数组来存储结构？
例如,它是读取a <然后开始捕获元素,然后一旦它遇到关闭>(在属性之外)它被推送到某个地方的数组堆栈？
我为了知道而感兴趣(我很好奇).
如果我要阅读像HTML Purifier这样的内容,那么这会让我对HTML的解析方式有所了解吗？
Lie*_*yan 57
标记可以由几个步骤组成,例如,如果你有这个HTML代码:
<html>
<head>
<title>My HTML Page</title>
</head>
<body>
<p style="special">
This paragraph has special style
</p>
<p>
This paragraph is not special
</p>
</body>
</html>
tokenizer可以将该字符串转换为重要令牌的平面列表,丢弃空格(谢谢,SasQ进行更正):
["<", "html", ">",
"<", "head", ">",
"<", "title", ">", "My HTML Page", "</", "title", ">",
"</", "head", ">",
"<", "body", ">",
"<", "p", "style", "=", "\"", "special", "\"", ">",
"This paragraph has special style",
"</", "p", ">",
"<", "p", ">",
"This paragraph is not special",
"</", "p", ">",
"</", "body", ">",
"</", "html", ">"
]
可能有多个标记化过程将标记列表转换为更高级别标记的列表,如下面的假设HTML解析器可能做的那样(仍然是一个平面列表):
[("<html>", {}),
("<head>", {}),
("<title>", {}), "My HTML Page", "</title>",
"</head>",
("<body>", {}),
("<p>", {"style": "special"}),
"This paragraph has special style",
"</p>",
("<p>", {}),
"This paragraph is not special",
"</p>",
"</body>",
"</html>"
]
然后解析器转换该令牌列表以形成一个树或图形,以一种更方便访问/操作程序的方式表示源文本:
("<html>", {}, [
("<head>", {}, [
("<title>", {}, ["My HTML Page"]),
]),
("<body>", {}, [
("<p>", {"style": "special"}, ["This paragraph has special style"]),
("<p>", {}, ["This paragraph is not special"]),
]),
])
此时,解析完成; 然后由用户来解释树,修改它等等.
Jer*_*fin 30
首先,您应该意识到解析HTML特别难看 - 在标准化之前,HTML在广泛(和不同)中使用.这会导致各种丑陋,例如标准指定不允许某些构造,但随后指定这些构造所需的行为.
直接提出问题:标记化大致相当于采用英语,并将其分解为单词.在英语中,大多数单词是连续的字母流,可能包括撇号,连字符等.大多数单词被空格包围,但句点,问号,感叹号等也可以表示单词的结尾.同样,对于HTML(或其他),您可以指定一些关于可以构成此语言中的标记(单词)的规则.将输入分解为标记的代码段通常称为词法分析器.
至少在正常情况下,你就不是你开始解析之前,打破所有的输入为特征符.相反,解析器调用词法分析器以在需要时获取下一个标记.当它被调用时,词法分析器会查看足够多的输入以找到一个标记,将其传递给解析器,并且在下一次解析器需要更多输入之前,不会对输入进行标记化.
一般来说,你对解析器的工作方式是正确的,但是(至少在一个典型的解析器中)它在解析语句的过程中使用了一个堆栈,但是它构建的表示语句通常是一个树(和抽象语法树,又名AST),不是多维数组.
基于解析HTML的复杂性,我会保留查找解析器,直到您首先阅读其他几个.如果你做一些环顾四周,你应该能够找到相当数量的解析器/词法分析器,比如数学表达式,它们可能更适合作为介绍(更小,更简单,更容易理解等)
不要错过W3C关于解析HTML5的注释.
有关扫描/ lexing的有趣介绍,请在网页上搜索高效生成表驱动扫描仪.它显示了扫描最终是如何由自动机理论驱动的.正则表达式的集合被转换为单个NFA.然后将NFA转换为DFA以使状态转换具有确定性.然后,本文描述了将DFA转换为转换表的方法.
关键点:扫描仪使用正则表达式理论,但可能不使用现有的正则表达式库.为了获得更好的性能,状态转换被编码为巨型语句或转换表.
扫描仪保证使用正确的单词(令牌).解析器保证单词以正确的组合和顺序使用.扫描仪使用正则表达式和自动机理论.解析器使用语法理论,尤其是无上下文语法.
一对解析资源:
HTML和XML语法(以及其他基于SGML的语法)很难解析,并且它们不适合lexing场景,因为它们不是常规的.在解析理论中,常规语法是没有任何递归的语法,即自相似,嵌套模式或类似于括号的包装器,它们必须相互匹配.但是基于HTML/XML/SGML的语言确实有嵌套模式:标签可以嵌套.嵌套模式的语法在Chomsky分类中的级别更高:它是无上下文的,甚至是依赖于上下文的.
但回到你关于词法分析器的问题:
每种语法都包含两种符号:非终端符号(那些解开其他语法规则的符号)和终端符号(那些是"原子"的 - 它们是语法树的叶子并且不要放松其他任何东西).终端符号通常只是令牌.令牌从词法分析器逐个泵送并与其相应的终端符号匹配.
那些终端符号(标记)通常具有常规语法,这更容易识别(这就是为什么它被排除在词法分析器之外,对于常规语法更加专业,并且可以比使用更常规的非常规语法方法更快地完成它).
因此,要为类似HTML/XML/SGML的语言编写词法分析器,您需要找到足够原子且规则的语法部分,以便词法分析器轻松处理.这里出现了问题,因为最初并不清楚这些部分是哪些部分.我很长一段时间都在努力解决这个问题.
但上面的Lie Ryan在识别这些部件方面做得非常好.为他而战!令牌类型如下:
<lexeme,用于启动标签.>lexeme,用于结束标签./用于关闭标签的lexeme.=lexeme,用于将属性名称与其值分隔开.'lexeme,用于包含属性值."lexeme,用于包含属性值.<直接包含字符且未被上述类型覆盖的文本.您还可以为实体引用添加一些令牌,例如 或&.大概:
&后跟一些字母数字字符,以#结尾;.为什么我用不同的令牌'和"而不是属性值一个令牌？因为常规语法无法识别哪些字符应该结束序列 - 它取决于启动它的字符(结束字符必须与起始字符匹配).这种"括号"被认为是非常规语法.所以我把它提升到更高的层次 - 对Parser来说.将这些标记(开始和结束)匹配在一起(或者根本不匹配,对于不包含空格的简单属性值)是他的工作.
事后想法: 不幸的是,其中一些令牌可能只在其他标记内发生.因此需要使用词汇上下文,这毕竟是控制状态机识别特定令牌的另一个状态机.这就是为什么我说类似SGML的语言不适合词法分析的模式.