정규식을 사용하여 HTML / XML을 구문 분석 할 수없는 이유 : 일반인 용어의 공식 설명
정규 표현식을 요구하는 (X) HTML 또는 XML 구문 분석에 대한 질문없이 통과하는 SO에는 하루가 없습니다.
이 작업 에 대한 정규 표현식 의 비 생존 가능성을 보여주는 예제 또는 개념을 나타내는 표현 모음을 비교적 쉽게 제시 할 수는 있지만, 여전히 평신도에서는 불가능한 이유에 대한 공식적인 설명을 찾을 수 없었 습니다. 자귀.
이 사이트에서 지금까지 찾을 수있는 유일한 형식적인 설명은 아마도 매우 정확할 수도 있지만, 스스로 가르치는 프로그래머에게는 매우 암시적일 것입니다.
여기서 결점은 HTML은 Chomsky Type 2 문법 (문맥이없는 문법)이고 RegEx는 Chomsky Type 3 문법 (정규 표현식)입니다.
또는:
정규식은 일반 언어와 만 일치 할 수 있지만 HTML은 문맥없는 언어입니다.
또는:
유한 오토 마톤 (정규 표현식의 기초가되는 데이터 구조)은 현재 상태와 별개로 메모리를 가지고 있지 않으며 임의로 중첩이 깊으면 임의로 오토 마톤이 필요하며 이는 유한 오토 마톤의 개념과 충돌합니다.
또는:
일반 언어에 대한 펌핑 보조 법은 그렇게 할 수없는 이유입니다.
[공정하게 말하면 : 위의 설명의 대부분은 위키 백과 페이지에 연결되지만 답변 자체보다 이해하기 쉽지 않습니다].
그래서 내 질문은 : 누군가가 정규식 설명에 대해 평신도의 용어로 번역을 제공 할 수 있습니까? 왜 정규식을 구문 분석 (X) HTML / XML에 사용할 수 없습니까?
편집 : 첫 번째 대답을 읽은 후에 나는 분명히해야한다고 생각했습니다. 나는 번역 하려고하는 개념을 간략하게 설명 하는 "번역"을 찾고 있습니다 . 답변 끝에 독자는 대략적인 아이디어를 가져야합니다-예를 들어 "일반 언어"와 "문맥없는 문법"의 의미 ...
이것에 집중하십시오 :
유한 오토 마톤 (정규 표현식의 기초가되는 데이터 구조)은 현재 상태와 별개로 메모리를 가지고 있지 않으며 임의로 중첩이 깊으면 임의로 오토 마톤이 필요하며 이는 유한 오토 마톤의 개념과 충돌합니다.
정규 표현식 의 정의 는 문자열이 패턴과 일치하는지 여부에 대한 테스트가 유한 오토 마톤 (각 패턴마다 다른 오토 마톤)으로 수행 될 수 있다는 사실과 같습니다. 유한 오토 마톤에는 메모리, 스택, 힙, 낙서 할 무한 테이프가 없습니다. 그 안에는 유한 한 수의 내부 상태가 있으며, 각 상태는 테스트 할 문자열에서 입력 단위를 읽고이를 사용하여 다음 상태로 이동할 상태를 결정합니다. 특수한 경우로, "예, 일치"및 "일치하지 않음"이라는 두 가지 종료 상태가 있습니다.
반면에 HTML은 임의로 깊게 중첩 될 수있는 구조를 가지고 있습니다. 파일이 유효한 HTML인지 여부를 확인하려면 모든 닫는 태그가 이전 여는 태그와 일치하는지 확인해야합니다. 그것을 이해하려면 어떤 요소가 닫혀 있는지 알아야합니다. 어떤 시작 태그를 "기억"할 수단이 없다면 기회는 없습니다.
그러나 대부분의 "regex"라이브러리는 실제로 정규 표현식의 엄격한 정의 이상의 것을 허용합니다. 역 참조와 일치 할 수 있다면 일반 언어를 넘어선 것입니다. 따라서 HTML에서 정규식 라이브러리를 사용하지 않아야하는 이유는 HTML이 규칙적이지 않다는 단순한 사실보다 조금 더 복잡합니다.
HTML이 일반 언어를 나타내지 않는다는 사실은 붉은 청어입니다. 정규 표현과 정규 언어 는 비슷 하지만 비슷 하지는 않습니다. 동일한 원점을 공유하지만 학계의 "정규 언어"와 엔진의 현재 일치하는 능력 사이에는 주목할만한 거리가 있습니다. 실제로 거의 모든 현대 정규식 엔진은 비정규 기능을 지원 (.*)\1합니다. 간단한 예는 다음과 같습니다 . 역 참조를 사용하여 반복되는 문자 시퀀스를 일치 시킵니다 ( 예 123123: 또는) bonbon. 재귀 적 / 균형 구조를 일치 시키면 더 재미있어집니다.
위키 백과에 의해 견적에, 잘이를두고 래리 벽 :
'정규 표현식'[...]은 실제 정규 표현식과 거의 관련이 없습니다. 그럼에도 불구하고, 용어는 패턴 매칭 엔진의 기능과 함께 성장했기 때문에 여기서 언어 적 필요성에 맞서려고하지는 않을 것입니다. 그러나 나는 일반적으로 "정규"(또는 내가 앵글로색슨 분위기에있을 때 "정규")라고 부를 것이다.
보시다시피 "정규 표현식은 일반 언어와 만 일치 할 수 있습니다"는 일반적으로 언급 된 오류 일뿐입니다.
그렇다면 왜 그렇지 않습니까?
HTML을 정규식과 일치시키지 않는 좋은 이유는 "단순히해야한다는 것을 의미 할 수 없기 때문"입니다. 가능할 수도 있지만 작업을위한 더 나은 도구가 있습니다. 고려하면:
- 유효한 HTML은 생각보다 어렵고 복잡합니다.
- "유효한"HTML에는 여러 유형이 있습니다. 예를 들어 HTML에서 유효한 것은 XHTML에서 유효하지 않습니다.
- 인터넷에서 발견되는 대부분의 자유 형식 HTML은 유효하지 않습니다 . HTML 라이브러리는 이것들도 잘 처리하며 많은 일반적인 경우에 대해 테스트되었습니다.
데이터 전체를 구문 분석하지 않고 데이터의 일부를 일치시키는 것은 불가능한 경우가 많습니다. 예를 들어, 모든 제목을 찾고 주석 또는 문자열 리터럴 내에서 일치하게 될 수 있습니다.
<h1>.*?</h1>메인 타이틀을 찾기위한 대담한 시도 일 수 있지만 다음을 찾을 수 있습니다.<!-- <h1>not the title!</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 파일의 일회성 업데이트가 필요하고 구조가 일관된 것을 알고있을 때.
- When you have a very small snippet of HTML.
- When you aren't dealing with an HTML file, but a similar templating engine (it can be very hard to find a parser in that case).
- When you want to change parts of the HTML, but not all of it - a parser, to my knowledge, cannot answer this request: it will parse the whole document, and save a whole document, changing parts you never wanted to change.
Because HTML can have unlimited nesting of <tags><inside><tags and="<things><that><look></like></tags>"></inside></each></other> and regex can't really cope with that because it can't track a history of what it's descended into and come out of.
A simple construct that illustrates the difficulty:
<body><div id="foo">Hi there! <div id="bar">Bye!</div></div></body>
99.9% of generalized regex-based extraction routines will be unable to correctly give me everything inside the div with the ID foo, because they can't tell the closing tag for that div from the closing tag for the bar div. That is because they have no way of saying "okay, I've now descended into the second of two divs, so the next div close I see brings me back out one, and the one after that is the close tag for the first". Programmers typically respond by devising special-case regexes for the specific situation, which then break as soon as more tags are introduced inside foo and have to be unsnarled at tremendous cost in time and frustration. This is why people get mad about the whole thing.
A regular language is a language that can be matched by a finite state machine.
(Understanding Finite State machines, Push-down machines, and Turing machines is basically the curriculum of a fourth year college CS Course.)
Consider the following machine, which recognizes the string "hi".
(Start) --Read h-->(A)--Read i-->(Succeed)
\ \
\ -- read any other value-->(Fail)
-- read any other value-->(Fail)
This is a simple machine to recognize a regular language; Each expression in parenthesis is a state, and each arrow is a transition. Building a machine like this will allow you to test any input string against a regular language -- hence, a regular expression.
HTML requires you to know more than just what state you are in -- it requires a history of what you have seen before, to match tag nesting. You can accomplish this if you add a stack to the machine, but then it is no longer "regular". This is called a Push-down machine, and recognizes a grammar.
A regular expression is a machine with a finite (and typically rather small) number of discrete states.
To parse XML, C, or any other language with arbitrary nesting of language elements, you need to remember how deep you are. That is, you must be able to count braces/brackets/tags.
You cannot count with finite memory. There may be more brace levels than you have states! You might be able to parse a subset of your language that restricts the number of nesting levels, but it would be very tedious.
A grammar is a formal definition of where words can go. For example, adjectives preceed nouns in English grammar, but follow nouns en la gramática española. Context-free means that the grammer universally in all contexts. Context-sensitive means there are additional rules in certain contexts.
In C#, for example, using means something different in using System; at the top of files, than using (var sw = new StringWriter (...)). A more relevant example is the following code within code:
void Start ()
{
string myCode = @"
void Start()
{
Console.WriteLine (""x"");
}
";
}
There's another practical reason for not using regular expressions to parse XML and HTML that has nothing to do with the computer science theory at all: your regular expression will either be hideously complicated, or it will be wrong.
For example, it's all very well writing a regular expression to match
<price>10.65</price>
But if your code is to be correct, then:
It must allow whitespace after the element name in both start and end tag
If the document is in a namespace, then it should allow any namespace prefix to be used
It should probably allow and ignore any unknown attributes appearing in the start tag (depending on the semantics of the particular vocabulary)
It may need to allow whitespace before and after the decimal value (again, depending on the detailed rules of the particular XML vocabulary).
It should not match something that looks like an element, but is actually in a comment or CDATA section (this becomes especially important if there is a possibility of malicious data trying to fool your parser).
It may need to provide diagnostics if the input is invalid.
Of course some of this depends on the quality standards you are applying. We see a lot of problems on StackOverflow with people having to generate XML in a particular way (for example, with no whitespace in the tags) because it is being read by an application that requires it to be written in a particular way. If your code has any kind of longevity then it's important that it should be able to process incoming XML written in any way that the XML standard permits, and not just the one sample input document that you are testing your code on.
In a purely theoretical sense, it is impossible for regular expressions to parse XML. They are defined in a way that allows them no memory of any previous state, thus preventing the correct matching of an arbitrary tag, and they cannot penetrate to an arbitrary depth of nesting, since the nesting would need to be built into the regular expression.
Modern regex parsers, however, are built for their utility to the developer, rather than their adherence to a precise definition. As such, we have things like back-references and recursion that make use of knowledge of previous states. Using these, it is remarkably simple to create a regex that can explore, validate, or parse XML.
Consider for example,
(?:
<!\-\-[\S\s]*?\-\->
|
<([\w\-\.]+)[^>]*?
(?:
\/>
|
>
(?:
[^<]
|
(?R)
)*
<\/\1>
)
)
This will find the next properly formed XML tag or comment, and it will only find it if it's entire contents are properly formed. (This expression has been tested using Notepad++, which uses Boost C++'s regex library, which closely approximates PCRE.)
Here's how it works:
- The first chunk matches a comment. It's necessary for this to come first so that it will deal with any commented-out code that otherwise might cause hang ups.
- If that doesn't match, it will look for the beginning of a tag. Note that it uses parentheses to capture the name.
- This tag will either end in a
/>, thus completing the tag, or it will end with a>, in which case it will continue by examining the tag's contents. - It will continue parsing until it reaches a
<, at which point it will recurse back to the beginning of the expression, allowing it to deal with either a comment or a new tag. - It will continue through the loop until it arrives at either the end of the text or at a
<that it cannot parse. Failing to match will, of course, cause it to start the process over. Otherwise, the<is presumably the beginning of the closing tag for this iteration. Using the back-reference inside a closing tag<\/\1>, it will match the opening tag for the current iteration (depth). There's only one capturing group, so this match is a simple matter. This makes it independent of the names of the tags used, although you could modify the capturing group to capture only specific tags, if you need to. - At this point it will either kick out of the current recursion, up to the next level or end with a match.
This example solves problems dealing with whitespace or identifying relevant content through the use of character groups that merely negate < or >, or in the case of the comments, by using [\S\s], which will match anything, including carriage returns and new lines, even in single-line mode, continuing until it reaches a -->. Hence, it simply treats everything as valid until it reaches something meaningful.
For most purposes, a regex like this isn't particularly useful. It will validate that XML is properly formed, but that's all it will really do, and it doesn't account for properties (although this would be an easy addition). It's only this simple because it leaves out real world issues like this, as well as definitions of tag names. Fitting it for real use would make it much more of a beast. In general, a true XML parser would be far superior. This one is probably best suited for teaching how recursion works.
Long story short: use an XML parser for real work, and use this if you want to play around with regexes.
Don't parse XML/HTML with regex, use a proper XML/HTML parser and a powerful xpath query.
theory :
According to the compiling theory, XML/HTML can't be parsed using regex based on finite state machine. Due to hierarchical construction of XML/HTML you need to use a pushdown automaton and manipulate LALR grammar using tool like YACC.
realLife©®™ everyday tool in a shell :
You can use one of the following :
xmllint often installed by default with libxml2, xpath1 (check my wrapper to have newlines delimited output
xmlstarlet can edit, select, transform... Not installed by default, xpath1
xpath installed via perl's module XML::XPath, xpath1
xidel xpath3
saxon-lint my own project, wrapper over @Michael Kay's Saxon-HE Java library, xpath3
or you can use high level languages and proper libs, I think of :
python's lxml (from lxml import etree)
perl's XML::LibXML, XML::XPath, XML::Twig::XPath, HTML::TreeBuilder::XPath
ruby nokogiri, check this example
php DOMXpath, check this example
'Programming' 카테고리의 다른 글
| Android 환경 설정 : 사용자가 환경 설정 화면을 사용하지 않은 경우 기본값을로드하는 방법은 무엇입니까? (0) | 2020.08.03 |
|---|---|
| ViewModelLocator는 무엇이며 DataTemplate과 비교하여 장단점이 무엇입니까? (0) | 2020.08.03 |
| 이 코드는 릴리스 모드에서 정지하지만 디버그 모드에서는 제대로 작동합니다. (0) | 2020.08.03 |
| 테스트하는 동안 DateTime.Now를 덮어 쓰는 좋은 방법은 무엇입니까? (0) | 2020.08.03 |
| JQuery : 크기 조정이 끝나면 RESIZE 이벤트를 호출하는 방법은 무엇입니까? (0) | 2020.08.03 |