[regex] 정규식을 사용하여 HTML / XML을 구문 분석 할 수없는 이유 : 평신도 용어의 공식적인 설명

정규 표현식을 요청하는 (X) HTML 또는 XML 구문 분석에 대한 질문없이 지나가는 SO의 날은 없습니다.

이 작업에 대한 정규식의 실행 불가능 성을 보여주는 예제 또는 개념을 나타내는 표현 모음을 사용하는 것은 비교적 쉽지만 평신도에서 이것이 가능하지 않은 이유에 대한 공식적인 설명은 여전히 찾을 수 없습니다. 자귀.

내가 지금까지이 사이트에서 찾을 수있는 유일한 공식적인 설명은 아마도 매우 정확할 것입니다.

여기서 결함은 HTML이 Chomsky Type 2 문법 (문맥 자유 문법)이고 RegEx가 Chomsky Type 3 문법 (정규식)이라는 것입니다.

또는:

정규 표현식은 정규 언어와 만 일치 할 수 있지만 HTML은 컨텍스트가없는 언어입니다.

또는:

유한 오토 마톤 (정규 표현식의 기본이되는 데이터 구조)은 상태와 별도로 메모리를 갖지 않으며, 임의로 깊은 중첩이있는 경우 유한 오토 마톤의 개념과 충돌하는 임의의 큰 오토 마톤이 필요합니다.

또는:

정규 언어에 대한 펌핑 기본형은 그렇게 할 수없는 이유입니다.

[공평하게 말하면 : 위의 설명의 대부분은 위키피디아 페이지로 연결되지만 답변 자체보다 이해하기가 쉽지 않습니다.]

그래서 내 질문은 : 누군가가 (X) HTML / XML을 구문 분석하기 위해 정규식을 사용할 수없는 이유에 대한 위에 주어진 공식적인 설명에 대한 평신도의 용어로 번역을 제공 할 수 있습니까?

편집 : 첫 번째 답변을 읽은 후 명확히해야한다고 생각했습니다. 번역 하려는 개념을 간략하게 설명 하는 “번역”을 찾고 있습니다 . 답변이 끝나면 독자는 대략적인 아이디어를 가지고 있어야합니다. – “일반 언어”와 “문맥없는 문법”의 의미 …

답변

이것에 집중하십시오 :

유한 오토 마톤 (정규 표현식의 기본이되는 데이터 구조)은 상태와 별도로 메모리를 갖지 않으며, 임의로 깊은 중첩이있는 경우 유한 오토 마톤의 개념과 충돌하는 임의의 큰 오토 마톤이 필요합니다.

정규식 의 정의 는 문자열이 패턴과 일치하는지 여부에 대한 테스트가 유한 오토 마톤 (각 패턴에 대해 하나의 다른 오토 마톤)에 의해 수행 될 수 있다는 사실과 동일합니다. 유한 오토 마톤에는 메모리가 없습니다. 스택, 힙, 낙서 할 무한 테이프가 없습니다. 그것이 가진 것은 한정된 수의 내부 상태 뿐이며, 각각은 테스트중인 문자열에서 입력 단위를 읽고이를 사용하여 다음으로 이동할 상태를 결정할 수 있습니다. 특수한 경우에는 “예, 일치 함”및 “아니오, 일치하지 않음”의 두 가지 종료 상태가 있습니다.

반면 HTML은 임의로 깊이 중첩 될 수있는 구조를 가지고 있습니다. 파일이 유효한 HTML인지 확인하려면 모든 닫는 태그가 이전 여는 태그와 일치하는지 확인해야합니다. 이를 이해하려면 어떤 요소가 닫혀 있는지 알아야합니다. 당신이 본 여는 태그를 “기억”할 수단이 없으면 기회가 없습니다.

그러나 대부분의 “정규식”라이브러리는 실제로 정규식의 엄격한 정의 이상의 것을 허용합니다. 역 참조와 일치 할 수 있다면 일반 언어를 넘어선 것입니다. 따라서 HTML에서 정규식 라이브러리를 사용하지 않아야하는 이유는 HTML이 규칙적이지 않다는 단순한 사실보다 조금 더 복잡합니다.

답변

HTML이 일반 언어를 나타내지 않는다는 사실은 붉은 청어입니다. 정규 표현과 정규 언어 는 비슷하게 들리지만 그렇지는 않습니다. 동일한 기원을 공유하지만 학문적 “정규 언어”와 현재 엔진의 일치 능력 사이에는 눈에 띄는 거리가 있습니다. 사실, 거의 모든 최신 정규식 엔진은 비정규 기능을 지원 (.*)\1합니다. 간단한 예는 . 역 참조를 사용하여 반복되는 문자 시퀀스 (예 123123: 또는) 를 일치 bonbon시킵니다. 재귀 / 균형 구조의 매칭은이를 더욱 재미있게 만듭니다.

Wikipedia는 Larry Wall 의 인용문에서 이것을 멋지게 표현했습니다 .

‘정규식'[…]은 실제 정규식과 거의 관련이 없습니다. 그럼에도 불구하고이 용어는 패턴 매칭 엔진의 기능과 함께 성장했기 때문에 여기서는 언어 적 필요성에 맞서 싸우려고하지 않을 것입니다. 그러나 일반적으로 “정규식”(또는 앵글로색슨 분위기 일 때 “정규식”)이라고 부를 것입니다.

보시다시피 “정규 표현식은 정규 언어와 만 일치 할 수 있습니다.”는 일반적으로 언급되는 오류에 지나지 않습니다.

그럼 왜 안되죠?

HTML을 정규 표현식과 일치시키지 않는 좋은 이유는 “당신이 할 수 있다는 것을 의미하지는 않는다”는 것입니다. 가능할 수도 있지만 작업을위한 더 나은 도구가 있습니다. 고려하면:

유효한 HTML은 생각보다 어렵거나 복잡합니다.
“유효한”HTML에는 여러 유형이 있습니다. 예를 들어, HTML에서 유효한 것은 XHTML에서는 유효하지 않습니다.
인터넷에있는 대부분의 자유 형식 HTML은 어쨌든 유효하지 않습니다 . HTML 라이브러리는 이러한 문제를 잘 처리하고 이러한 일반적인 경우에 대해 테스트되었습니다.
전체를 구문 분석하지 않고는 데이터의 일부를 일치시키는 것이 불가능한 경우가 많습니다. 예를 들어, 모든 제목을 찾고 주석 또는 문자열 리터럴 내에서 일치하게 될 수 있습니다. <h1>.*?</h1>주요 제목을 찾기위한 대담한 시도 일 수 있지만 다음을 찾을 수 있습니다.
```

```
또는:
```
<script>
var s = "Certainly <h1>not the title!</h1>";
</script>
```

마지막 요점이 가장 중요합니다.

전용 HTML 파서를 사용하는 것이 당신이 생각할 수있는 어떤 정규식보다 낫습니다. 종종 XPath를 사용하면 필요한 데이터를 더 잘 표현할 수 있으며 HTML 파서를 사용하는 것이 대부분의 사람들이 생각하는 것보다 훨씬 쉽습니다 .

주제에 대한 좋은 요약과 Regex와 HTML을 혼합하는 것이 적절할 수있는 경우에 대한 중요한 의견은 Jeff Atwood의 블로그 인 Parsing Html The Cthulhu Way 에서 찾을 수 있습니다 .

HTML을 구문 분석하기 위해 정규 표현식을 사용하는 것이 더 좋은 때는 언제입니까?

대부분의 경우 라이브러리가 제공 할 수있는 DOM 구조에서 XPath를 사용하는 것이 좋습니다. 그럼에도 불구하고 대중의 의견에 반하여 파서 라이브러리가 아닌 정규식을 사용하도록 강력히 권장하는 몇 가지 경우가 있습니다.

다음과 같은 몇 가지 조건이 주어집니다.

HTML 파일의 일회성 업데이트가 필요하고 구조가 일관적임을 알고있는 경우.
아주 작은 HTML 스 니펫이있을 때.
HTML 파일을 다루지 않지만 유사한 템플릿 엔진 (이 경우 파서를 찾기가 매우 어려울 수 있음)을 다룰 때.
HTML의 일부를 변경하고 싶지만 전부가 아닌 경우 -내가 아는 한 파서는이 요청에 응답 할 수 없습니다. 전체 문서를 구문 분석하고 전체 문서를 저장하여 변경하고 싶지 않은 부분을 변경합니다.

답변

HTML은 무제한 중첩을 가질 수 <tags><inside><tags and="<things><that><look></like></tags>"></inside></each></other>있고 정규식은 그것이 들어오고 나오는 것에 대한 기록을 추적 할 수 없기 때문에 실제로 대처할 수 없기 때문입니다.

난이도를 보여주는 간단한 구조 :

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

일반화 된 정규식 기반 추출 루틴의 99.9 %는 div의 닫는 태그에서 해당 div의 닫는 태그를 알 수 없기 때문에 divID가있는 내부의 모든 것을 올바르게 제공 foo할 수 없습니다 bar. 왜냐하면 그들은 “좋아, 나는 이제 두 div 중 두 번째 div로 내려 갔기 때문에 내가 본 다음 div 닫기는 나를 다시 가져오고 그 다음 div는 첫 번째 div에 대한 닫기 태그입니다”라고 말할 방법이 없기 때문입니다. . 프로그래머는 일반적으로 특정 상황에 대해 특수한 경우의 정규식을 고안하여 대응합니다. 그런 다음 내부에 더 많은 태그가 도입 되 자마자 중단되고 foo엄청난 비용과 시간과 좌절감으로 풀려야합니다. 이것이 사람들이 모든 것에 대해 화를내는 이유입니다.

답변

정규 언어는 유한 상태 머신과 일치시킬 수있는 언어입니다.

(유한 상태 머신, 푸시 다운 머신 및 튜링 머신을 이해하는 것은 기본적으로 대학 4 년차 CS 과정의 커리큘럼입니다.)

문자열 “hi”를 인식하는 다음 기계를 고려하십시오.

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

이것은 일반 언어를 인식하는 간단한 기계입니다. 괄호 안의 각 표현식은 상태이고 각 화살표는 전환입니다. 이와 같은 기계를 구축하면 입력 문자열을 정규 언어 (따라서 정규 표현식)에 대해 테스트 할 수 있습니다.

HTML을 사용하려면 현재 상태 이상의 것을 알아야합니다. 태그 중첩과 일치하려면 이전에 본 내용의 기록이 필요합니다. 머신에 스택을 추가하면이 작업을 수행 할 수 있지만 더 이상 “일반”이 아닙니다. 이것을 푸시 다운 기계라고하며 문법을 인식합니다.

답변

정규식은 한정된 (일반적으로 다소 작은) 수의 이산 상태를 가진 기계입니다.

임의의 언어 요소 중첩을 사용하여 XML, C 또는 기타 언어를 구문 분석하려면 얼마나 깊이 있는지 기억해야합니다. 즉, 중괄호 / 대괄호 / 태그를 셀 수 있어야합니다.

유한 한 기억으로는 셀 수 없습니다. 상태보다 중괄호 수준이 더 많을 수 있습니다! 중첩 수준 수를 제한하는 언어의 하위 집합을 구문 분석 할 수 있지만 매우 지루할 것입니다.

답변

문법은 단어가 어디로 갈 수 있는지에 대한 공식적인 정의입니다. 예를 들어, 형용사는 명사 앞에오고 명사 in English grammar뒤에옵니다 en la gramática española. 문맥이 없다는 것은 문법이 모든 문맥에서 보편적으로 사용된다는 것을 의미합니다. 상황에 맞는 것은 특정 상황에 추가 규칙이 있음을 의미합니다.

C #에서, 예를 들어, using에서 뭔가 다른 의미 using System;보다는 파일의 상단에를 using (var sw = new StringWriter (...)). 더 관련성이 높은 예는 코드 내의 다음 코드입니다.

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

답변

컴퓨터 과학 이론과 전혀 관련이없는 XML 및 HTML을 구문 분석하는 데 정규식을 사용하지 않는 또 다른 실용적인 이유가 있습니다. 정규식이 끔찍하게 복잡하거나 잘못 될 것입니다.

예를 들어, 모두 일치하는 정규 표현식을 작성하는 것이 좋습니다.

<price>10.65</price>

그러나 코드가 정확하다면 :

시작 및 끝 태그 모두에서 요소 이름 뒤에 공백을 허용해야합니다.
문서가 네임 스페이스에있는 경우 모든 네임 스페이스 접두사를 사용할 수 있어야합니다.
시작 태그에 나타나는 알 수없는 속성을 허용하고 무시해야합니다 (특정 어휘의 의미에 따라 다름).
10 진수 값 앞뒤에 공백을 허용해야 할 수도 있습니다 (다시 말하지만 특정 XML 어휘의 세부 규칙에 따라 다름).
요소처럼 보이지만 실제로는 주석 또는 CDATA 섹션에있는 것과 일치해서는 안됩니다 (악성 데이터가 파서를 속이려고 할 가능성이있는 경우 특히 중요합니다).
입력이 유효하지 않은 경우 진단을 제공해야 할 수 있습니다.

물론이 중 일부는 적용하는 품질 표준에 따라 다릅니다. 특정 방식으로 작성해야하는 응용 프로그램에서 XML을 읽고 있기 때문에 특정 방식 (예 : 태그에 공백 없음)으로 XML을 생성해야하는 사람들과 함께 StackOverflow에서 많은 문제가 발생합니다. 코드의 수명이 긴 경우 코드를 테스트하는 하나의 샘플 입력 문서가 아니라 XML 표준이 허용하는 방식으로 작성된 들어오는 XML을 처리 할 수 있어야합니다.