[컴파일러] 2.2. 토큰의 명세

정규식이란 문자의 패턴을 명시하기 위한 형식언어이다.

어휘분석기 생성기에서 사용되며 이후 정규식을 특정 토큰의 인식을 수행하는 오토마타로 변환함으로써 어휘분석기를 구성하는 방법을 진행할텐데, 정규식 개념이 필요하다.

 

스트링에 관한 용어

용어	설명		예제
접두사(prefix)	스트링의 끝으로부터 0개 이상의 기호를 제거하여 얻어지는 스트링이다		"ban", "banana", ""는 banana의 접두사이다
접미사(suffix)	스트링의 앞에서부터 0개 이상의 기호를 제거하여 얻어지는 스트링이다		"nana", "banana", ""는 banana의 접미사이다
부분스트링(substring)	스트링의 접두사나 접미사를 제거하여 얻어지는 스트링이다		"nan", banana", ""는 banana의 부분스트링이다
진(proper)	진(진 접두사, 진 접미사, 진 부분스트링)는 공백, 스트링자체가 아닌 접두사, 접미사, 부분스트링이다		"banana"는 "banana"의 진 접두사가 아니다
부분순차(subsequence)	스트링의 0개 이상의 위치를 제거함으로써 형성되는 스트링이다 (연속될 필요는 없음)		"banana"

 

 

언어 연산 정의

연산	정의와 표기
L과 M의 합집합	L∪M = {s | s는 L에 있거나 M에 있다}
L과 M의 접합	LM = {st | s는 L에 있고 t는 M에 있다}
L의 Kleene 클로저
L의 양의 클로저

 

정규식

정규식이라는 표기법이 어떤 알파벳의 기호들에 연산자를 적용하여 구성할 수 있는 모든 언어를 서술하는데 사용한다.

(책이 좀 이상한데 그냥써봄)

조건			표기
id(c언어의 변수 규칙)는 첫글자에 숫자가 올 수 없고 특수문자를 포함하지 않는 알파벳+숫자의 조합이다			letter(letter | digit)*
id(c언어의 변수 규칙)는 첫글자에 숫자가 올 수 없고 "_"(언더 스코어)특수문자를 제외한 특수문자를 포함하지 않는 알파벳+숫자의 조합이다			letter(letter | digit | _)*
정수(digits)			digit*
부동소수점(optionalFraction)			. digits | 빈 문자열
지수표기법(optionalExponent)			(E ( + | - | 빈문자열) digits | 빈문자열
number			정수 부동소수점 지수표기법

 

축약 예시

ID 표기)

letter -> [A-Za-z]

digit -> [0-9]

id -> letter(letter | digit)*

 

number 표기)

digit -> [0-9]

digits -> digit+

number -> digits(. digits)? (E[+-]? digits)?