F#에 들어갔기 때문에 정규 표현 엔진을 써봤어요.

읽고"F# 알았으면 좋겠어요". F#에 관심이 생겨서 F#를 시작했어요.튜토리얼만 하면 재미없으니까 정규 표현 엔진을 만들면서 F# 기능을 배우기로 했어요.

만든 물건

매우 간단한 정규 표현식 엔진을 만들다.사용할 수 있는 메타 문자는 다음 네 개뿐입니다.

. 문자와 일치

* 0회 이상 일치

| 좌우 한 쪽과 일치

()그룹

효율을 전혀 고려하지 않다.계산은 시간을 들일 수도 있고 메모리를 대량으로 사용할 수도 있다.

첫걸음

정규 표현식의 유형을 나타낸다Pattern.처음부터 완전한 것을 만들기 어려웠기 때문에 표시.나 특정한 문자(예를 들어a)를 먼저 정의했다.

type Pattern =
    | Char of char
    | AnyChar

Pattern는 공용체를 판별하다로 정의됩니다.정규 표현식.은 AnyChar, 정규 표현식a은 Char 'a'이다.
이어서 주어진 문자열 중 Pattern 과 일치하는 부분을 골라 함수를 씁니다.임의의 위치와 일치하는 함수를 고려하는 것은 매우 어렵기 때문에 문자열의 시작 부분부터 일치하는 경우에만 한정됩니다.또한 정규 표현식과 일치하는 부분이 여러 개 있기 때문에 되돌아오는 값은 하나의 값이 아니라 값의 열이다.
또한 반환값으로 일부 문자열 자체를 반환할 필요가 없습니다.처음부터 시작하는 부분 문자열인 것을 알기 때문에 부분 문자열의 길이만 계산하면 정보로 충분하다.
따라서 일치 함수에 대한 서명은 다음과 같습니다.

// s の先頭から始まる部分文字列の中で pattern にマッチするものの長さを返す
let matchLengths (pattern: Pattern) (s: string) : seq<int> =
    ...

seq이런 눈에 거슬리는 게 나왔어. C#가 말한 거IEnumerable야.있다IEnumerable.나중에 나오니까 기대해주세요.
그럼 함수 주체를 쓰세요.

let matchLengths (pattern: Pattern) (s: string) : seq<int> =
    match pattern with
    | Char ch ->
        if s.StartsWith ch then seq [ 1 ] else Seq.empty
    | AnyChar ->
        if s <> "" then seq [ 1 ] else Seq.empty

현재는 yield와 Char만 있기 때문에 매우 간단하다.AnyChar의 경우 Char의 시작이 규정된 문자로 시작되면 길이 1의 문자열과 일치하기 때문에 되돌아오는 열s이다.그렇지 않으면 일치하지 않습니다[ 1 ].Seq.empty의 경우 빈 문자열이 아닌 경우 길이가 1인 문자열과 일치합니다.빈 문자열이 어떤 것도 일치하지 않습니다.(서로 다른 연산자를 판정하는 것 같다AnyChar(단, 왠지 이 함수는 REPL에서 컴파일할 수 없습니다.<> 부분은 유형이 틀렸다고 여겨집니다.REPL의 일반적인 컴파일링이 아니라 잘 컴파일했습니다.s.StartsWith ch 과부하와 관련이 있을 수 있지만 잘 모르겠습니다.)s.StartsWith해보세요.

matchLengths (Char 'a') "a"
|> Seq.toList
|> printfn "%A" // [1] が出力される

matchLengths (Char 'a') "b"
|> Seq.toList
|> printfn "%A" // [] が出力される

결과는 예기한 대로 순조롭다.matchLengths 파이프 연산자인 것 같습니다.이것은 왼쪽 값을 오른쪽 함수에 전달하는 연산자로서, 이를 사용하면 루비의 방법으로 그런 분위기에 들어가 코드를 쓸 수 있다.

Alternation

다음은 |>를 포함하는 정규 표현식을 사용합니다.|의 정의는 다음과 같다.

type Pattern =
    | Char of char
    | AnyChar
    | Alter of Pattern * Pattern

Pattern는 두 개Alter를 얻기 위해 귀속 정의이다.
일치하는 문자열Pattern의 하위 문자열Alter lhs rhs은 일치하는 문자열s의 하위 문자열과 일치하는 문자열lhs의 합집합이다.rhs에서 이 조작을 실현할 때 다음과 같다.

let rec matchLengths (pattern: Pattern) (s: string) : seq<int> =
    match pattern with
    | Char ch ->
        if s.StartsWith ch then seq [ 1 ] else Seq.empty
    | AnyChar ->
        if s <> "" then seq [ 1 ] else Seq.empty
    | Alter (lhs, rhs) ->
        seq {
            yield! matchLengths lhs s
            yield! matchLengths rhs s
        }

matchLengths는 컴퓨터식라고 불리는 것 같다.(나는 아직 컴퓨터식을 완전히 이해하지 못했다.)seq { ... }에서 seq { ... } 또는 yield 등의 문법을 사용할 수 있다.예를 들어 평가yield!할 때seq { yield 1; yield 2 }가 되돌아온다.
한편, seq [1; 2]와yield!는 비슷하지만 한 번flattten.예컨대

let s1 = seq [1; 2]
let s2 = seq [3; 4]
seq { yield! s1; yield! s2 }

되돌아오다yield.
그러므로

seq {
    yield! matchLengths lhs s
    yield! matchLengths rhs s
}

seq [1; 2; 3; 4]와 일치하는 부분 문자열과 lhs가 일치하는 부분 문자열을 연결하는 열입니다.
또한 rhs C#의 generator와 같은 값으로 계산이 지연됩니다.이걸 사용하면 무한 서열을 정의할 수 있을 것 같아.(이번 예에서는 유한한 서열만 나타났다)

Conceation 및 Repeat

나머지는 연결seq { ... }입니다.빈 문자열과 일치하는 패턴도 필요합니다.*의 정의를 Pattern,Zero,Repeat,Concat를 더한다.

type Pattern =
    | Zero
    | Char of char
    | AnyChar
    | Alter of Pattern * Pattern
    | Repeat of Pattern
    | Concat of Pattern * Pattern

matchLengths의 실현은 다음과 같다.Repeat 빈 문자열과 일치하는 상황에서 처리하는 것은 미묘하게 얄밉다.나는 이 외에도 많은 직관적인 실시 방식이 있다고 생각한다.

let rec matchLengths (pattern: Pattern) (s: string) : seq<int> =
    match pattern with
    | Zero ->
        seq [ 0 ]
    | Char ch ->
        if s.StartsWith ch then seq [ 1 ] else Seq.empty
    | AnyChar ->
        if s <> "" then seq [ 1 ] else Seq.empty
    | Alter (lhs, rhs) ->
        seq {
            yield! matchLengths lhs s
            yield! matchLengths rhs s
        }
    | Concat (head, tail) ->
        seq {
            for n1 in matchLengths head s do
                for n2 in matchLengths tail (s.Substring n1) do
                    yield n1 + n2
        }
    | Repeat inner ->
        seq {
            for n1 in matchLengths inner s do
                if n1 = 0 then
                    yield 0
                else
                    for n2 in matchLengths pattern (s.Substring n1) do
                        yield n1 + n2
            yield 0
        }

seq { ... }에서 for .. in .. do ..의 문법을 사용할 수 있다.네스트할 수도 있습니다.이 함수는 사용되지 않았지만 if로도 필터를 할 수 있을 것 같습니다.
이렇게 정규 표현식의 맵이 완성되었다.해봐.

// <(.*)> を表す Pattern
let p = Concat (Char '<', Concat (Repeat AnyChar, Char '>'))
let s = "<hello>world</hello>"
matchLengths p s
|> Seq.toList
|> printfn "%A"

실행할 때 [20; 7] 출력합니다.<hello>world</hello>는 20자, <hello>는 7자여서 정확하게 움직였다.너무 좋아요

다음 편역편?

현재 정규 표현식을 사용하기 위해서는 직접 조립해야 한다Pattern.이거 불편해요.그래서 저는 ab*|c.d처럼 익숙한 표기부터 Pattern까지 컴파일된 코드를 썼습니다. 동력이 있으면 다음에 소개하겠습니다.