컴파일러 설계-정규식

어휘 분석기는 사용중인 언어에 속하는 유한 한 유효한 문자열 / 토큰 / 어휘 집합 만 스캔하고 식별하면됩니다. 언어 규칙에 정의 된 패턴을 검색합니다.

정규식에는 유한 한 기호 문자열에 대한 패턴을 정의하여 유한 언어를 표현하는 기능이 있습니다. 정규식으로 정의 된 문법은 다음과 같습니다.regular grammar. 정규 문법으로 정의 된 언어는 다음과 같습니다.regular language.

정규식은 패턴을 지정하기위한 중요한 표기법입니다. 각 패턴은 문자열 세트와 일치하므로 정규 표현식은 문자열 세트의 이름 역할을합니다. 프로그래밍 언어 토큰은 일반 언어로 설명 할 수 있습니다. 정규식의 사양은 재귀 적 정의의 예입니다. 일반 언어는 이해하기 쉽고 효율적으로 구현됩니다.

정규 표현식을 따르는 대수 법칙이 많이 있으며, 정규 표현식을 동등한 형태로 조작하는 데 사용할 수 있습니다.

운영

언어에 대한 다양한 작업은 다음과 같습니다.

  • 두 언어 L과 M의 결합은 다음과 같이 작성됩니다.

    LUM = {s | s는 L 또는 s는 M}

  • 두 언어 L과 M의 연결은 다음과 같이 작성됩니다.

    LM = {st | s는 L, t는 M}

  • 언어 L의 Kleene Closure는 다음과 같이 작성됩니다.

    L * = 언어 L이 0 개 이상 발생합니다.

표기법

r과 s가 언어 L (r)과 L (s)을 나타내는 정규식이면

  • Union : (r) | (s)는 L (r) UL (s)을 나타내는 정규식입니다.

  • Concatenation : (r) (s)는 L (r) L (s)을 나타내는 정규식입니다.

  • Kleene closure : (r) *은 (L (r)) *을 나타내는 정규식입니다.

  • (r)은 L (r)을 나타내는 정규식입니다.

우선 순위 및 연관성

  • *, 연결 (.) 및 | (파이프 기호)는 연관되어 있습니다.
  • * 우선 순위가 가장 높습니다.
  • 연결 (.)은 두 번째로 높은 우선 순위를 갖습니다.
  • | (파이프 기호)는 우선 순위가 가장 낮습니다.

정규식에서 언어의 유효한 토큰 표시

x가 정규식이면 다음과 같습니다.

  • x *는 x가 0 개 이상 발생 함을 의미합니다.

    즉, {e, x, xx, xxx, xxxx,…}를 생성 할 수 있습니다.

  • x +는 하나 이상의 x 발생을 의미합니다.

    즉, {x, xx, xxx, xxxx…} 또는 xx *를 생성 할 수 있습니다.

  • 엑스? x의 최대 한 번 발생을 의미합니다.

    즉, {x} 또는 {e}를 생성 할 수 있습니다.

  • [az]는 모두 영어의 소문자 알파벳입니다.

    [AZ]는 모두 영어의 대문자 알파벳입니다.

    [0-9]는 수학에서 사용되는 모든 자연 숫자입니다.

정규식을 사용하여 기호 발생 표시

letter = [a – z] 또는 [A – Z]

숫자 = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 또는 [0-9]

기호 = [+ | -]

정규식을 사용하여 언어 토큰 표시

십진수 = (기호) ? (숫자) +

식별자 = (문자) (문자 | 숫자) *

어휘 분석기에 남은 유일한 문제는 언어의 키워드 패턴을 지정하는 데 사용되는 정규식의 유효성을 확인하는 방법입니다. 잘 받아 들여진 해결책은 검증을 위해 유한 오토마타를 사용하는 것입니다.