정규 문법의 연산 순서

정규 문법의 연산 순서

정규 문법의 연산자 우선순위와 연산 과정을 살펴보자
핵심 개념

정규식의 연산자 우선 순위는 정규식을 평가할 때 작업 순서를 명확히 하기 위해 정의됩니다.

다음은 정규 표현식 연산자와 그 우선 순위입니다

1. Kleene Star (*): 이 연산자는 우선 순위가 가장 높습니다. 바로 앞의 정규 표현식이 0개 이상 발생함을 나타냅니다.
   • "r"이 정규식인 경우 "r*"는 0개 이상의 “r” 항목과 일치합니다.
2. 연결(.): 두 번째로 높은 우선 순위는 연결 연산자입니다.
   • 두 개의 정규식 "r"과 "s"를 하나로 결합합니다.
   • 여기서 “r” 바로 뒤에 "s"가 옵니다. 즉, "r"과 "s"가 정규 표현식인 경우 "r.s"는 두 부분으로 분해될 수 있는 모든 문자열과 일치합니다.
   • 여기서 첫 번째 부분은 "r"과 일치하고 두 번째 부분은 "s"와 일치합니다.
3. 결합(+): 이 연산자는 우선 순위가 가장 낮습니다.
   • 두 정규식 중 적어도 하나와 일치하는 모든 문자열과 일치합니다.
   • “r” 및 "s"가 정규식인 경우 "r+s"는 “r” 또는 "s"와 일치하는 모든 문자열과 일치합니다.

연습 : (a+b) ^ * Abb (a+b)

**1단계: a+b **

• (a+b) 식에서 ‘+’ 연산자는 'a’와 ‘b’ 사이의 선택 또는 합집합을 나타냅니다.
  2단계: (a+b)^*
• 별표 '*'는 Kleene 별 연산을 나타내며, 이는 이전 정규식(여기서는 (a+b))이 0회 이상 발생함을 의미합니다.
  **3단계: 마지막 a+b **
• 첫 번째 단계에서와 마찬가지로 표현식의 마지막 (a+b)는 다시 'a’와 ‘b’ 사이의 선택 또는 합집합을 나타냅니다.
  4단계: abb로 연결
• 이제 시퀀스 abb는 나타나야 하는 특정 문자열 "abb"로 이해됩니다.
  **5단계: 전체 표현식 (a+b)^* abb(a+b) **
• 이 전체 정규식은 0개 이상의 ‘a’ 또는 ‘b’ 인스턴스로 시작하고 특히 'abb’가 뒤따르고 ‘a’ 또는 'b’로 끝나는 모든 문자열과 일치합니다.

예제 : 정규 표현에 의해 생성 되는 언어

• 0 + 1 :
• (0 + 1 ) 0 :
• 0^* :
• ( 0 + 1 )^* :

예제 : (a + B ) * abb

(a + b)*abb는 a와 b로 만들어지는 모든 문자열 중에서 abb로 끝나는 문자열 의 집합이다

예제 : 정규 표현인지 판단하고 생성 되는 언어 구하기

• 0*(0+1)*
  • 이 언어는 ε을 포함하여 0과 1로 만들 수 있는 모든 문자열의 집합이다.

예제 : 정규 표현으로 나타내기

• (l + _)(l + d +_ )*
  • 단, l → a |⋯| z
  • d → 0 | 1 | ⋯| 9

ident는 첫 자가 영문자 소문자 a,⋯, z, 언더바로 시작하고 두 번째 자부터는 영 문자 소문자 a, ⋯, z, 숫자 0, 1, ⋯, 9 그리고 언더바가 되며 길이는 제한이 없는 문자열이다.

부족한 점이나 잘못 된 점을 알려주시면 시정하겠습니다 :>