Por que não é possível usar regex para analisar HTML / XML: uma explicação formal em termos gerais

Não há dia no SO que passe sem uma pergunta sobre a análise (X) de HTML ou XML com expressões regulares sendo feitas.

Embora seja relativamente fácil encontrar exemplos que demonstrem a inviabilidade de regexes para esta tarefa ou com uma coleção de expressões para representar o conceito, ainda não consegui encontrar no SO uma explicação formal de por que isso não é possível feito em layman's termos.

As únicas explicações formais que consegui encontrar até agora neste site são provavelmente extremamente precisas, mas também bastante enigmáticas para o programador autodidata:

a falha aqui é que HTML é uma gramática Chomsky Tipo 2 (gramática livre de contexto) e RegEx é uma gramática Chomsky Tipo 3 (expressão regular)

ou:

Expressões regulares só podem corresponder a linguagens regulares, mas HTML é uma linguagem livre de contexto.

ou:

Um autômato finito (que é a estrutura de dados subjacente a uma expressão regular) não tem memória separada do estado em que se encontra e, se você tiver um aninhamento profundo arbitrário, precisará de um autômato arbitrariamente grande, que colide com a noção de um autômato finito.

ou:

O lema do Pumping para linguagens regulares é a razão pela qual você não pode fazer isso.

[Para ser justo: a maior parte da explicação acima leva a páginas da wikipedia, mas não são muito mais fáceis de entender do que as próprias respostas].

Portanto, minha pergunta é: alguém poderia fornecer uma tradução em termos gerais das explicações formais fornecidas acima de por que não é possível usar regex para analisar (X) HTML / XML?

EDITAR: Depois de ler a primeira resposta achei que deveria esclarecer: estou procurando uma "tradução" que também explique resumidamente os conceitos que tenta traduzir: ao final de uma resposta, o leitor deve ter uma ideia aproximada - por exemplo - do que significam "linguagem regular" e "gramática livre de contexto" ...

Concentre-se neste:

Um autômato finito (que é a estrutura de dados subjacente a uma expressão regular) não tem memória separada do estado em que se encontra e, se você tiver um aninhamento profundo arbitrário, precisará de um autômato arbitrariamente grande, que colide com a noção de um autômato finito.

A definição de expressões regulares é equivalente ao fato de que um teste para verificar se uma string corresponde ao padrão pode ser realizado por um autômato finito (um autômato diferente para cada padrão). Um autômato finito não tem memória - nenhuma pilha, nenhum heap, nenhuma fita infinita para rabiscar. Tudo o que ele possui é um número finito de estados internos, cada um dos quais pode ler uma unidade de entrada da string sendo testada e usá-la para decidir qual estado mover para o próximo. Como casos especiais, tem dois estados de terminação: "sim, isso corresponde" e "não, isso não corresponde".

O HTML, por outro lado, tem estruturas que podem ser aninhadas de forma arbitrária. Para determinar se um arquivo é HTML válido ou não, você precisa verificar se todas as marcas de fechamento correspondem a uma marca de abertura anterior. Para entender isso, você precisa saber qual elemento está sendo fechado. Sem nenhum meio de "lembrar" as tags de abertura que você viu, sem chance.

Observe, entretanto, que a maioria das bibliotecas "regex" na verdade permite mais do que apenas a definição estrita de expressões regulares. Se eles podem combinar referências anteriores, então eles foram além de uma linguagem regular. Portanto, a razão pela qual você não deve usar uma biblioteca regex em HTML é um pouco mais complexa do que o simples fato de que o HTML não é regular.

O fato de o HTML não representar uma linguagem regular é uma pista falsa. Expressão regular e linguagens regulares parecem semelhantes , mas não são - elas compartilham a mesma origem, mas há uma distância notável entre as "linguagens regulares" acadêmicas e a atual potência correspondente dos motores. Na verdade, quase todos os mecanismos modernos de expressão regular suportam recursos não regulares - um exemplo simples é (.*)\1. que usa backreferencing para corresponder a uma sequência repetida de caracteres - por exemplo 123123, ou bonbon. A combinação de estruturas recursivas / balanceadas torna isso ainda mais divertido.

A Wikipedia coloca isso muito bem, em uma citação de Larry Wall :

'Expressões regulares' [...] são apenas marginalmente relacionadas a expressões regulares reais. No entanto, o termo cresceu com as capacidades de nossos mecanismos de correspondência de padrões, então não vou tentar lutar contra a necessidade linguística aqui. No entanto, geralmente os chamarei de "regexes" (ou "regexen", quando estou no humor anglo-saxão).

"Expressão regular só pode corresponder a linguagens regulares", como você pode ver, nada mais é do que uma falácia comumente declarada.

Então, por que não então?

Uma boa razão para não combinar HTML com expressão regular é que "só porque você pode, não significa que você deve". Embora seja possível - existem ferramentas simplesmente melhores para o trabalho . Considerando:

• HTML válido é mais difícil / mais complexo do que você pode pensar.
• Existem muitos tipos de HTML "válido" - o que é válido em HTML, por exemplo, não é válido em XHTML.
• Muito do HTML de formato livre encontrado na Internet não é válido de qualquer maneira . Bibliotecas HTML também fazem um bom trabalho ao lidar com isso e foram testadas para muitos desses casos comuns.

• Muitas vezes é impossível combinar uma parte dos dados sem analisá-los como um todo. Por exemplo, você pode estar procurando por todos os títulos e acabar correspondendo dentro de um comentário ou literal de string. <h1>.*?</h1>pode ser uma tentativa ousada de encontrar o título principal, mas pode encontrar:

  <!-- <h1>not the title!</h1> -->

  Ou ainda:

  <script>
  var s = "Certainly <h1>not the title!</h1>";
  </script>

O último ponto é o mais importante:

• Usar um analisador HTML dedicado é melhor do que qualquer regex que você possa criar. Muitas vezes, o XPath permite uma maneira melhor expressiva de localizar os dados de que você precisa, e usar um analisador HTML é muito mais fácil do que a maioria das pessoas imagina .

Um bom resumo do assunto e um comentário importante sobre quando misturar Regex e HTML podem ser encontrados no blog de Jeff Atwood: Parsing Html The Cthulhu Way .

Quando é melhor usar uma expressão regular para analisar HTML?

Na maioria dos casos, é melhor usar XPath na estrutura DOM que uma biblioteca pode fornecer. Ainda assim, contra a opinião popular, existem alguns casos em que eu recomendo fortemente o uso de uma regex e não de uma biblioteca de analisador:

Dadas algumas dessas condições:

• Quando você precisa de uma atualização única de seus arquivos HTML e sabe que a estrutura é consistente.
• Quando você tem um pequeno snippet de HTML.
• Quando você não está lidando com um arquivo HTML, mas com um mecanismo de modelagem semelhante (pode ser muito difícil encontrar um analisador neste caso).
• Quando você deseja alterar partes do HTML, mas não todo - um analisador, até onde sei, não pode responder a essa solicitação: ele analisará todo o documento e salvará um documento inteiro, alterando partes que você nunca quis alterar.

Porque HTML pode ter aninhamento ilimitado de <tags><inside><tags and="<things><that><look></like></tags>"></inside></each></other>e regex não pode realmente lidar com isso porque não pode rastrear um histórico de onde ele desceu e saiu.

Uma construção simples que ilustra a dificuldade:

<body><div id="foo">Hi there!  <div id="bar">Bye!</div></div></body>

99,9% das rotinas de extração baseadas em regex generalizadas não serão capazes de me fornecer corretamente tudo dentro do divcom o ID foo, porque eles não podem dizer a tag de fechamento para aquele div da tag de fechamento para o bardiv. Isso porque eles não têm como dizer "ok, agora desci para o segundo de dois divs, então o próximo div que vejo me traz de volta um, e o seguinte é a marca de fechamento do primeiro" . Os programadores normalmente respondem criando regexes para casos especiais para a situação específica, que então quebram assim que mais tags são introduzidas fooe precisam ser desarmadas a um custo tremendo de tempo e frustração. É por isso que as pessoas ficam bravas com a coisa toda.

Uma linguagem regular é aquela que pode ser correspondida por uma máquina de estado finito.

(Noções básicas sobre máquinas de estado finito, máquinas push-down e máquinas de Turing é basicamente o currículo de um curso de ciência da computação do quarto ano.)

Considere a seguinte máquina, que reconhece a string "hi".

(Start) --Read h-->(A)--Read i-->(Succeed)
  \                  \
   \                  -- read any other value-->(Fail) 
    -- read any other value-->(Fail)

Esta é uma máquina simples para reconhecer uma linguagem regular; Cada expressão entre parênteses é um estado e cada seta é uma transição. Construir uma máquina como essa permitirá que você teste qualquer string de entrada em relação a uma linguagem regular - portanto, uma expressão regular.

HTML requer que você saiba mais do que apenas em que estado você está - requer um histórico do que você viu antes, para corresponder ao aninhamento de tags. Você pode fazer isso se adicionar uma pilha à máquina, mas ela não será mais "normal". Isso é chamado de máquina pushdown e reconhece uma gramática.

Uma expressão regular é uma máquina com um número finito (e tipicamente pequeno) de estados discretos.

Para analisar XML, C ou qualquer outra linguagem com aninhamento arbitrário de elementos de linguagem, você precisa se lembrar de quão profundo você é. Ou seja, você deve ser capaz de contar colchetes / colchetes / tags.

Você não pode contar com memória finita. Pode haver mais níveis de suporte do que estados! Você pode analisar um subconjunto de sua linguagem que restringe o número de níveis de aninhamento, mas seria muito tedioso.

Uma gramática é uma definição formal de para onde as palavras podem ir. Por exemplo, adjetivos precedem substantivos in English grammar, mas seguem substantivos en la gramática española. Livre de contexto significa que a gramática universalmente em todos os contextos. Sensível ao contexto significa que existem regras adicionais em determinados contextos.

Em C #, por exemplo, usingsignifica algo diferente no using System;início dos arquivos, do que using (var sw = new StringWriter (...)). Um exemplo mais relevante é o seguinte código dentro do código:

void Start ()
{
    string myCode = @"
    void Start()
    {
       Console.WriteLine (""x"");
    }
    ";
}

Há outra razão prática para não usar expressões regulares para analisar XML e HTML que não tem nada a ver com a teoria da ciência da computação: sua expressão regular será terrivelmente complicada ou errada.

Por exemplo, é muito bom escrever uma expressão regular para corresponder

<price>10.65</price>

Mas se seu código deve estar correto, então:

• Ele deve permitir um espaço em branco após o nome do elemento na tag de início e fim

• Se o documento estiver em um namespace, ele deve permitir que qualquer prefixo de namespace seja usado

• Provavelmente, deve permitir e ignorar quaisquer atributos desconhecidos que apareçam na tag inicial (dependendo da semântica do vocabulário específico)

• Pode ser necessário permitir espaços em branco antes e depois do valor decimal (novamente, dependendo das regras detalhadas do vocabulário XML específico).

• Não deve corresponder a algo que se pareça com um elemento, mas na verdade está em um comentário ou seção CDATA (isso se torna especialmente importante se houver a possibilidade de dados maliciosos tentando enganar seu analisador).

• Pode ser necessário fornecer diagnósticos se a entrada for inválida.

É claro que parte disso depende dos padrões de qualidade que você está aplicando. Vemos muitos problemas no StackOverflow com pessoas tendo que gerar XML de uma maneira particular (por exemplo, sem espaços em branco nas tags) porque ele está sendo lido por um aplicativo que requer que seja escrito de uma maneira particular. Se o seu código tiver qualquer tipo de longevidade, é importante que ele seja capaz de processar XML de entrada escrito de qualquer maneira que o padrão XML permita, e não apenas o documento de entrada de amostra no qual você está testando seu código.

Em um sentido puramente teórico, é impossível para expressões regulares analisar XML. Eles são definidos de uma forma que não lhes permite memória de qualquer estado anterior, evitando assim o casamento correto de uma tag arbitrária, e eles não podem penetrar em uma profundidade arbitrária de aninhamento, uma vez que o aninhamento precisaria ser embutido na expressão regular.

Os analisadores regex modernos, entretanto, são construídos para sua utilidade para o desenvolvedor, ao invés de sua aderência a uma definição precisa. Como tal, temos coisas como referências anteriores e recursão que fazem uso do conhecimento de estados anteriores. Usando isso, é extremamente simples criar um regex que pode explorar, validar ou analisar XML.

Considere, por exemplo,

(?:
    <!\-\-[\S\s]*?\-\->
    |
    <([\w\-\.]+)[^>]*?
    (?:
        \/>
        |
        >
        (?:
            [^<]
            |
            (?R)
        )*
        <\/\1>
    )
)

Isso encontrará a próxima tag ou comentário XML devidamente formado e só o encontrará se todo o conteúdo estiver formado corretamente. (Esta expressão foi testada usando o Notepad ++, que usa a biblioteca regex do Boost C ++, que se aproxima muito do PCRE.)

Funciona assim:

1. O primeiro bloco corresponde a um comentário. É necessário que isso venha primeiro para que possa lidar com qualquer código comentado que, de outra forma, poderia causar travamentos.
2. Se não corresponder, ele procurará o início de uma tag. Observe que ele usa parênteses para capturar o nome.
3. Esta tag terminará com a />, completando assim a tag, ou terminará com a >, caso em que continuará examinando o conteúdo da tag.
4. Ele continuará analisando até chegar a um <, ponto em que retornará ao início da expressão, permitindo-lhe lidar com um comentário ou uma nova tag.
5. Ele continuará pelo loop até chegar ao final do texto ou a um <que ele não consegue analisar. A falha na correspondência, é claro, fará com que o processo seja reiniciado. Caso contrário, <é presumivelmente o início da tag de fechamento para esta iteração. Usando a referência anterior dentro de uma tag de fechamento <\/\1>, ela corresponderá à tag de abertura para a iteração atual (profundidade). Há apenas um grupo de captura, então essa partida é simples. Isso o torna independente dos nomes das tags usadas, embora você possa modificar o grupo de captura para capturar apenas tags específicas, se necessário.
6. Nesse ponto, ele será expulso da recursão atual para o próximo nível ou terminará com uma partida.

Este exemplo resolve problemas de lidar com espaços em branco ou de identificar conteúdo relevante por meio do uso de grupos de caracteres que apenas negam <ou >, ou no caso dos comentários, usando [\S\s], que corresponderá a qualquer coisa, incluindo retornos de carro e novas linhas, mesmo em uma linha modo, continuando até atingir a -->. Portanto, ele simplesmente trata tudo como válido até que alcance algo significativo.

Para a maioria dos propósitos, uma regex como essa não é particularmente útil. Ele validará se o XML está formado corretamente, mas isso é tudo o que realmente fará, e não leva em conta as propriedades (embora isso seja uma adição fácil). É simples assim porque deixa de fora problemas do mundo real como este, bem como definições de nomes de tag. Ajustá-lo para um uso real o tornaria muito mais uma besta. Em geral, um verdadeiro analisador XML seria muito superior. Este provavelmente é mais adequado para ensinar como funciona a recursão.

Resumindo: use um analisador XML para trabalho real e use-o se quiser brincar com regexes.

Não analise XML / HTML com regex, use um analisador XML / HTML adequado e um poderoso xpath inquerir.

teoria:

De acordo com a teoria de compilação, XML / HTML não pode ser analisado usando regex com base em máquina de estado finito . Devido à construção hierárquica de XML / HTML, você precisa usar um autômato pushdown e manipular a gramática LALR usando uma ferramenta como o YACC .

ferramenta cotidiana realLife © ® ™ em um Concha :

Você pode usar um dos seguintes:

xmllint frequentemente instalado por padrão com libxml2, xpath1 (verifique meu invólucro para ter uma saída delimitada por novas linhas

xmlstarlet pode editar, selecionar, transformar ... Não instalado por padrão, xpath1

xpath instalado através do módulo de perl XML :: XPath, xpath1

xidel xpath3

saxon-lint meu próprio projeto, empacotar a biblioteca Saxon-HE Java de @Michael Kay, xpath3

ou você pode usar linguagens de alto nível e bibliotecas adequadas, eu penso em:

Pitãode lxml( from lxml import etree)

perlé XML::LibXML, XML::XPath, XML::Twig::XPath,HTML::TreeBuilder::XPath

rubi nokogiri, verifique este exemplo

php DOMXpath, verifique este exemplo

Verifique: Usando expressões regulares com tags HTML