How does a parser (for example, HTML) work?

2023-01-05 10:02 问答作者：

For argument's sake lets assume a HTML parser.

I'开发者_运维知识库ve read that it tokenizes everything first, and then parses it.

What does tokenize mean?

Does the parser read every character each, building up a multi dimensional array to store the structure?

For example, does it read a < and then begin to capture the element, and then once it meets a closing > (outside of an attribute) it is pushed onto a array stack somewhere?

I'm interested for the sake of knowing (I'm curious).

If I were to read through the source of something like HTML Purifier, would that give me a good idea of how HTML is parsed?

Tokenizing can be composed of a few steps, for example, if you have this html code:

<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>

the tokenizer may convert that string to a flat list of significant tokens, ~~discarding whitespaces~~ (thanks, SasQ for the correction):

["<", "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", ">"
]

there may be multiple tokenizing passes to convert a list of tokens to a list of even higher-level tokens like the following hypothetical HTML parser might do (which is still a flat list):

[("<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>"
]

then the parser converts that list of tokens to form a tree or graph that represents the source text in a manner that is more convenient to access/manipulate by the program:

("<html>", {}, [
    ("<head>", {}, [
        ("<title>", {}, ["My HTML Page"]),
    ]), 
    ("<body>", {}, [
        ("<p>", {"style": "special"}, ["This paragraph has special style"]),
        ("<p>", {}, ["This paragraph is not special"]),
    ]),
])

at this point, the parsing is complete; and it is then up to the user to interpret the tree, modify it, etc.

First of all, you should be aware that parsing HTML is particularly ugly -- HTML was in wide (and divergent) use before being standardized. This leads to all manner of ugliness, such as the standard specifying that some constructs aren't allowed, but then specifying required behavior for those constructs anyway.

Getting to your direct question: tokenization is roughly equivalent to taking English, and breaking it up into words. In English, most words are consecutive streams of letters, possibly including an apostrophe, hyphen, etc. Mostly words are surrounded by spaces, but a period, question mark, exclamation point, etc., can also signal the end of a word. Likewise for HTML (or whatever) you specify some rules about what can make up a token (word) in this language. The piece of code that breaks the input up into tokens is normally known as the lexer.

At least in a normal case, you do not break all the input up into tokens before you start parsing. Rather, the parser calls the lexer to get the next token when it needs one. When it's called, the lexer looks at enough of the input to find one token, delivers that to the parser, and no more of the input is tokenized until the next time the parser needs more input.

In a general way, you're right about how a parser works, but (at least in a typical parser) it uses a stack during the act of parsing a statement, but what it builds to represent a statement is normally a tree (and Abstract Syntax Tree, aka AST), not a multidimensional array.

Based on the complexity of parsing HTML, I'd reserve looking at a parser for it until you've read through a few others first. If you do some looking around, you should be able to find a fair number of parsers/lexers for things like mathematical expressions that are probably more suitable as an introduction (smaller, simpler, easier to understand, etc.)

Don't miss the W3C's notes on parsing HTML5.

For an interesting introduction to scanning/lexing, search the web for Efficient Generation of Table-Driven Scanners. It shows how scanning is ultimately driven by automata theory. A collection of regular expressions is transformed into a single NFA . The NFA is then transformed to a DFA to make state transitions deterministic. The paper then describes a method to transform the DFA into a transition table.

A key point: scanners use regular expression theory but likely don't use existing regular expression libraries. For better performance, state transitions are coded as giant case statements or in transition tables.

Scanners guarantee that correct words(tokens) are used. Parsers guarantee the words are used in the correct combination and order. Scanners use regular expression and automata theory. Parsers use grammar theory, especially context-free grammars.

A couple parsing resources:

http://www.cs.utk.edu/~eijkhout/594-LaTeX/handouts/parsing/parsing-tutorial.pdf
http://cryptodrm.engr.uconn.edu/c244lect/L2.pdf

HTML and XML syntax (and others based on SGML) are quite hard to parse and they don't fit well into the lexing scenario, because they're not regular. In the parsing theory, a regular grammar is the one with doesn't have any recursion, that is, self-similar, nested patterns, or parentheses-like wrappers which have to match each other. But HTML/XML/SGML-based languages does have nested patterns: tags could be nested. Syntax with nesting patterns is higher in level in the Chomsky's classification: it's context-free or even context-dependent.

But back to your question about lexer:
Each syntax consists of two kinds of symbols: non-terminal symbols (those which unwind into other syntax rules) and terminal symbols (those which are "atomic" - they are leafs of the syntax tree and don't unwind into anything else). Terminal symbols are often just the tokens. Tokens are pumped one by one from the lexer and matched to their corresponding terminal symbols.

Those terminal symbols (tokens) have often regular syntax, which is easier to recognize (and that's why it's factored out to the lexer, which is more specialized for regular grammars and could do it quicker than by using more general approach of non-regular grammars).

So, to write a lexer for HTML/XML/SGML-like language, you need to find parts of the syntax which are atomic enough and regular, to be dealt with easily by the lexer. And here the problem arises, because it's not at first obvious which parts are these. I struggled with this problem for a long time.

But Lie Ryan above have done a very good job in recognizing these parts. Bravo for him for that! The token types are following:

TagOpener: < lexeme, used for starting tags.
TagCloser: > lexeme, used for ending tags.
ClosingTagMarker: / lexeme used in closing tags.
Name: alphanumeric sequence starting with letter, used for tag names and attribute names.
Value: Text which can contain variety of different characters, spaces etc. Used for values of attributes.
Equals: = lexeme, used for separating attribute names from its values.
Quote: ' lexeme, used for enclosing attribute values.
DoubleQuote: " lexeme, used for enclosing attribute values.
PlainText: Any text not containing < character directly and not covered by the above types.

You can also have some tokens for entity references, like   or &. Probably:

EntityReference: a lexeme consisting of & followed by some alphanumeric characters and ended with ;.

Why I used separate tokens for ' and " and not one token for attribute value? Because regular syntax couldn't recognize which of these characters should end the sequence - it depends on the character which started it (ending character have to match the starting character). This "parenthesizing" is considered non-regular syntax. So I promote it into a higher level - to the Parser. It'd be his job to match these tokens (starting and ending) together (or none at all, for simple attribute values not containing spaces).

Afterthought: Unfortunately, some of these tokens may occur only inside other markup. So the use of lexical contexts is needed, which after all is another state machine controlling the state machines recognizing particular tokens. And that's why I've said that SGML-like languages don't fit well into the schema of lexical analysis.