정규식(Regular Expression)

• 특정한 규칙을 가진 문자열의 집합을 표현하는 데 사용하는 형식 언어
  • 아래 3개의 기본 연산들로 이루어진 symbol들의 string
• Symbol
  • • : 괄호 안에 있는 문자들이 0번 이상 나타남.
  • ? : 어떤 문자와도 매치됨.
  • • : 1번 이상 반복됨.
• Example
  • ?(ie+ei)? : ie 또는 ei를 가지고 있는 모든 단어
  • (1+01)*(0+1) : 연속적으로 두 개의 0이 나오지 않는 0과 1로 이루어진 모든 string

Pattern Matching

• Text string에서 원하는 문자 패턴을 찾아내는 것
• 패턴 기술

  • 접합(Concatenation)

    → 패턴에서 인접해 있는 두 문자가 텍스트에서 나타나면 매치

  • 논리합(Or)

    → 두 개의 문자 중 하나가 텍스트에 나타나면 매치

  • 폐포(Closure)

    → 특정한 문자가 0개 이상 나타나면 매치

Pattern matching machine(패턴 매칭 장치)?

패턴 매칭에 사용되는 장치 패턴을 말함.

Deterministic(결정적) 장치

• 각각의 상태 전이가 다음 입력 문자에 의해 완전하게 결정되는 것
• Ex) KMP 알고리즘을 위한 유한 상태 장치

Nondeterministic(비결정적) 장치

• 패턴을 매칭하기 위해 하나 이상의 방법이 있을 경우 장치가 올바른 것을 찾아 나가는 것
• Text String에서 (A*B+AC)D와 같은 정규식을 찾는 경우 사용됨.
• 유일한 시작 상태와 종료 상태를 가짐

패턴 매칭 구성 장치