Como a análise de HTML funciona se não estiver usando regexp?

Eu vejo perguntas todos os dias perguntando como analisar ou extrair algo de alguma string HTML e a primeira resposta / comentário é sempre "Não use RegEx para analisar HTML, para não sentir a ira!" (essa última parte às vezes é omitida).

Isso é um pouco confuso para mim, sempre pensei que, em geral, a melhor maneira de analisar qualquer string complicada é usar uma expressão regular. Então, como funciona um analisador de HTML? Não usa expressões regulares para analisar.

Um argumento específico para usar uma expressão regular é que nem sempre há uma alternativa de análise (como JavaScript, onde DOMDocument não é uma opção disponível universalmente). jQuery, por exemplo, parece funcionar bem usando um regex para converter uma string HTML em nós DOM.

Não tenho certeza se devo ou não CW isso, é uma pergunta genuína que eu quero que seja respondida e não pretendo realmente ser um tópico de discussão.

Normalmente, usando um tokeniser. O rascunho da especificação do HTML5 tem um algoritmo extenso para lidar com "HTML do mundo real".

Então, como funciona um analisador de HTML? Não usa expressões regulares para analisar?

Bem não.

Se você voltar em seu cérebro para um curso de teoria da computação, se você fez um, ou um curso de compiladores, ou algo semelhante, você deve se lembrar que existem diferentes tipos de linguagens e modelos computacionais. Não estou qualificado para entrar em todos os detalhes, mas posso revisar alguns dos pontos principais com você.

O tipo mais simples de linguagem e computação (para esses propósitos) é uma linguagem regular. Eles podem ser gerados com expressões regulares e reconhecidos com autômatos finitos. Basicamente, isso significa que as strings de "análise" nessas linguagens usam estado, mas não memória auxiliar. HTML certamente não é uma linguagem regular. Se você pensar sobre isso, a lista de tags pode ser aninhada profundamente de forma arbitrária. Por exemplo, as tabelas podem conter tabelas e cada tabela pode conter muitas tags aninhadas. Com as expressões regulares, você pode escolher um par de tags, mas certamente nada aninhado arbitrariamente.

Uma linguagem simples clássica que não é regular é a combinação correta de parênteses. Por mais que tente, você nunca será capaz de construir uma expressão regular (ou autômato finito) que sempre funcionará. Você precisa de memória para controlar a profundidade do aninhamento.

Uma máquina de estado com uma pilha de memória é a próxima força do modelo computacional. Isso é chamado de autômato push-down e reconhece linguagens geradas por gramáticas livres de contexto. Aqui, podemos reconhecer parênteses combinados corretamente - de fato, uma pilha é o modelo de memória perfeito para ela.

Bem, isso é bom o suficiente para HTML? Infelizmente não. Talvez para um XML super-duper cuidadosamente validado, na verdade, no qual todas as tags sempre se alinham perfeitamente. Em HTML no mundo real, você pode facilmente encontrar trechos como <b><i>wow!</b></i>. Isso obviamente não aninha, então, para analisá-lo corretamente, uma pilha não é poderosa o suficiente.

O próximo nível de computação são as linguagens geradas por gramáticas gerais e reconhecidas pelas máquinas de Turing. É geralmente aceito como efetivamente o modelo computacional mais forte que existe - uma máquina de estado, com memória auxiliar, cuja memória pode ser modificada em qualquer lugar. Isso é o que as linguagens de programação podem fazer. Este é o nível de complexidade em que reside o HTML.

Para resumir tudo aqui em uma frase: para analisar HTML geral, você precisa de uma linguagem de programação real, não uma expressão regular.

O HTML é analisado da mesma forma que outras linguagens: lexing e parsing. A etapa lexing divide o fluxo de caracteres individuais em tokens significativos. A etapa de análise reúne os tokens, usando estados e memória, em um documento logicamente coerente que pode ser executado.

As expressões regulares são apenas uma forma de analisador. Um analisador HTML honesto será significativamente mais complicado do que pode ser expresso em regexes, usando descida recursiva , previsão e várias outras técnicas para interpretar corretamente o texto. Se você realmente deseja se aprofundar nele, você pode verificar lex & yacc e ferramentas semelhantes.

A proibição de usar regexes para análise de HTML provavelmente deve ser escrita mais corretamente como: "Não use expressões regulares ingênuas para analisar HTML ..." (para que não sinta a ira) "... e trate os resultados com cautela." Para certos objetivos específicos, um regex pode ser perfeitamente adequado, mas você precisa ter muito cuidado para estar ciente das limitações de seu regex e ser tão cauteloso quanto apropriado para a fonte do texto que você está analisando (por exemplo, se for entrada do usuário, tenha muito cuidado).

Analisar HTML é a transformação de um texto linear em uma estrutura de árvore. As expressões regulares geralmente não podem lidar com estruturas de árvore. A expressão regular necessária em cada ponto para obter o próximo token muda o tempo todo. Você pode usar expressões regulares em um analisador, mas precisará de todo um array de expressões regulares para cada estado possível de análise.

Se você deseja ter uma solução 100%: Você precisa escrever seu próprio código personalizado que itera por meio do HTML caractere por caractere e você precisa ter uma quantidade enorme de lógica para determinar se deve parar o nó atual e iniciar o Próximo.

O motivo é que este é um HTML válido:

<ul>
<li>One
<li>Two
<li>Three
</ul>

Mas isso também é:

<ul>
<li>One</li>
<li>Two</li>
<li>Three</li>
</ul>

Se você concordar com a "solução 90%": Então, usar um analisador XML para carregar um documento está bom. Ou usando Regex (embora o xml seja mais fácil se você for o mestre do conteúdo).