정규식을위한 파서 작성

정규식을위한 파서 작성

---

수년간의 프로그래밍 후에도 정규 표현식을 완전히 파악한 적이 없다고 말하는 것이 부끄럽습니다. 일반적으로 문제가 정규식을 요구할 때 일반적으로 (구문을 참조한 후) 적절한 것을 찾을 수 있지만 점점 더 자주 사용하는 기술입니다.

그래서 스스로를 가르치고 정규 표현식을 제대로 이해 하기 위해 무언가를 배우려고 할 때 항상하는 일을하기로 결정했습니다. 즉, 내가 충분히 배웠다고 느끼 자마자 포기할 야심 찬 무언가를 작성하십시오.

이를 위해 파이썬으로 정규식 파서를 작성하고 싶습니다. 이 경우 "충분히 학습한다"는 것은 Perl의 확장 정규식 구문을 완전히 이해할 수있는 파서를 구현하고 싶다는 의미입니다. 그러나 가장 효율적인 파서이거나 실제 세계에서 반드시 사용할 수있는 것은 아닙니다. 문자열의 패턴과 정확히 일치하거나 일치하지 않으면됩니다.

문제는 어디서부터 시작해야하나요? 나는 정규식이 어떤 식 으로든 유한 상태 자동화를 포함한다는 사실을 제외하고 정규식이 어떻게 구문 분석되고 해석되는지에 대해 거의 알지 못합니다. 이 다소 어려운 문제에 접근하는 방법에 대한 제안을 많이 주시면 감사하겠습니다.

편집 : 파이썬에서 정규식 파서 를 구현 하는 동안 예제 나 기사가 작성된 프로그래밍 언어에 대해 지나치게 소란스럽지 않다는 것을 명확히해야합니다 . Brainfuck에없는 한 충분히 이해할 수있을 것입니다. 그것의 가치를내는 동안.

---

정규식 엔진의 구현을 작성하는 것은 실제로 매우 복잡한 작업입니다.

그러나 실제로 구현하는 데 필요한 세부 사항을 충분히 이해하지 못하더라도이를 수행하는 방법에 관심이 있다면 적어도이 기사를 살펴 보는 것이 좋습니다.

정규식 일치는 간단하고 빠를 수 있지만 Java, Perl, PHP, Python, Ruby 등에서는 느립니다.

인기있는 프로그래밍 언어 중 몇 개가 일부 정규식에 대해 매우 느릴 수있는 방식으로 정규식을 구현하는지 설명하고 더 빠른 약간 다른 방법을 설명합니다. 이 기사에는 C의 일부 소스 코드를 포함하여 제안 된 구현이 작동하는 방법에 대한 세부 정보가 포함되어 있습니다. 정규 표현식을 배우기 시작했다면 약간 읽기 어려울 수 있지만 두 가지의 차이점에 대해 알아두면 가치가 있다고 생각합니다. 구혼.

---

저는 Mark Byers에게 이미 +1을주었습니다.하지만 제가 기억하는 한,이 논문은 한 알고리즘이 왜 나쁘고 다른 알고리즘이 훨씬 더 나은지 설명하는 것 이상으로 정규 표현식 매칭이 어떻게 작동하는지에 대해 많이 언급하지 않았습니다. 링크에 뭔가?

유한 오토마타를 만드는 좋은 접근 방식에 초점을 맞출 것입니다. 최소화가없는 결정 론적 오토마타로 자신을 제한한다면 이것은 그리 어렵지 않습니다.

내가 (매우 빠르게) 설명 할 것은 Modern Compiler Design 에서 취한 접근 방식 입니다.

다음과 같은 정규 표현식이 있다고 상상해보십시오.

a (b c)* d

문자는 일치시킬 리터럴 문자를 나타냅니다. *는 일반적인 0 개 이상의 반복 일치입니다. 기본 아이디어는 점선 규칙을 기반으로 상태를 파생하는 것입니다. 상태 0을 아직 일치하지 않는 상태로 간주하므로 점이 맨 앞에갑니다.

0 : .a (b c)* d

유일하게 가능한 일치는 'a'이므로 우리가 파생하는 다음 상태는 ...

1 : a.(b c)* d

이제 두 가지 가능성이 있습니다. 'b'와 일치 ( 'b c'가 하나 이상 반복되는 경우) 또는 그렇지 않으면 'd'와 일치합니다. 참고-우리는 기본적으로 여기서 digraph 검색 (깊이 우선 또는 너비 우선 또는 무엇이든)을 수행하지만 검색하면서 digraph를 발견합니다. 폭 우선 전략을 가정하면 나중에 고려할 수 있도록 사례 중 하나를 대기열에 추가해야하지만 여기서부터는이 문제를 무시하겠습니다. 어쨌든, 우리는 두 개의 새로운 상태를 발견했습니다 ...

2 : a (b.c)* d
3 : a (b c)* d.

상태 3은 종료 상태입니다 (둘 이상일 수 있음). 상태 2의 경우 'c'만 일치시킬 수 있지만 나중에 점 위치에주의해야합니다. 상태 1과 동일한 "a. (bc) * d"를 얻습니다. 따라서 새로운 상태가 필요하지 않습니다.

IIRC, Modern Compiler Design의 접근 방식은 점 처리를 단순화하기 위해 연산자를 칠 때 규칙을 변환하는 것입니다. 상태 1은 다음으로 변환됩니다.

1 : a.b c (b c)* d
    a.d

즉, 다음 옵션은 첫 번째 반복과 일치하거나 반복을 건너 뛰는 것입니다. 이것의 다음 상태는 상태 2와 3과 같습니다.이 접근 방식의 장점은 미래의 경기에만 관심이 있기 때문에 과거의 모든 경기 ( '.'앞의 모든 것)를 버릴 수 있다는 것입니다. 이것은 일반적으로 더 작은 상태 모델을 제공합니다 (하지만 반드시 최소한의 모델은 아님).

편집 이미 일치 된 세부 정보를 삭제하는 경우 상태 설명은이 시점부터 발생할 수있는 문자열 집합의 표현입니다.

추상 대수 측면에서 이것은 일종의 집합 종결입니다. 대수는 기본적으로 하나 이상의 연산자로 구성된 집합입니다. 우리의 세트는 상태 설명이고 연산자는 우리의 전환 (문자 일치)입니다. 닫힌 집합은 집합의 모든 구성원에 연산자를 적용하면 항상 집합에있는 다른 구성원이 생성되는 집합입니다. 세트의 폐쇄는 폐쇄 된 가장 큰 세트입니다. 따라서 기본적으로 명백한 시작 상태에서 시작하여 전환 연산자 집합에 비해 닫혀있는 최소 상태 집합, 즉 도달 가능한 상태의 최소 집합을 구성합니다.

여기서 최소는 폐쇄 프로세스를 의미합니다. 일반적으로 최소라고하는 더 작은 동등한 자동 장치가있을 수 있습니다.

이 기본 아이디어를 염두에두고 "두 세트의 문자열을 나타내는 두 개의 상태 머신이있는 경우 어떻게 합집합을 나타내는 세 번째를 파생하는지"(또는 교차 또는 세트 차이 ...)라고 말하는 것이 그리 어렵지 않습니다. 점선 규칙 대신 상태 표현은 각 입력 자동 장치의 현재 상태 (또는 현재 상태 집합)와 추가 세부 정보를 표시합니다.

정규 문법이 복잡해지면 최소화 할 수 있습니다. 여기서 기본적인 아이디어는 비교적 간단합니다. 모든 상태를 하나의 등가 클래스 또는 "블록"으로 그룹화합니다. 그런 다음 특정 전환 유형과 관련하여 블록을 분할해야하는지 (상태가 실제로 동일하지 않음) 여부를 반복적으로 테스트합니다. 특정 블록의 모든 상태가 동일한 문자의 일치를 허용 할 수 있고 그렇게함으로써 동일한 다음 블록에 도달하면 동등합니다.

Hopcrofts 알고리즘은 이러한 기본 아이디어를 처리하는 효율적인 방법입니다.

최소화에 대한 특히 흥미로운 점은 모든 결정 론적 유한 오토 마톤이 정확히 하나의 최소 형태를 갖는다는 것입니다. 또한 Hopcrofts 알고리즘은 시작된 더 큰 사례의 표현에 관계없이 최소한의 형태와 동일한 표현을 생성합니다. 즉, 이것은 해시를 유도하거나 임의적이지만 일관된 순서에 사용할 수있는 "표준"표현입니다. 이것이 의미하는 바는 최소한의 오토마타를 컨테이너의 키로 사용할 수 있다는 것입니다.

위의 내용은 아마도 약간 엉성한 WRT 정의 일 수 있으므로 직접 사용하기 전에 용어를 직접 찾아보아야합니다.하지만 운이 좋으면 기본 아이디어에 대해 공정하게 빠르게 소개 할 수 있습니다.

BTW- 나머지 Dick Grunes 사이트 살펴보기 -그는 구문 분석 기술에 대한 무료 PDF 책을 가지고 있습니다. Modern Compiler Design의 첫 번째 버전은 꽤 좋은 IMO이지만 보시다시피 두 번째 버전이 임박했습니다.

---

이 논문 은 흥미로운 접근 방식을 취합니다. 구현은 Haskell에서 제공되지만 Python 에서 적어도 한 번은 다시 구현 되었습니다 .

---

Brian Kernighan의 Beautiful Code 에 "정규 표현식 매처"라고 하는 흥미로운 장이 있습니다. 여기에서 그는 리터럴 문자와 .^$*기호를 일치시킬 수있는 간단한 매처에 대해 설명합니다 .

---

정규식 엔진을 작성하면 이해가 향상된다는 데 동의하지만 ANTLR을 살펴 보셨습니까 ??. 모든 종류의 언어에 대해 자동으로 파서를 생성합니다. 따라서 문법 예제에 나열된 언어 문법 중 하나를 사용하여 생성되는 AST 및 구문 분석기를 통해 실행 해 볼 수 있습니다. 정말 복잡한 코드를 생성하지만 파서가 어떻게 작동하는지 잘 이해할 것입니다.

참고 URL : https://stackoverflow.com/questions/3639574/writing-a-parser-for-regular-expressions