[컴파일러개론 1] 어휘분석
어휘분석
- 소스 코드를 정규 문법 (regular grammar)에 따라 토큰 (token)으로 분류하는 어휘 분석 또는 스캐닝 (scanning)이라고 한다.
(원시프로그램을 긴 문자열로 보고 차례대로 문자를 검사하여, 의미있는 최소 단위들(토큰)로 변환하는 것)
- 어휘분석 시 공백 을 제거해서 코드 크기 줄어든다.
- 토큰을 어떻게 다룰지가 핵심이 된다.
토큰은 "문법적으로 의미 있는 최소단위" 이다. 예시로 알아보자.
토큰에는 식별자, 키워드, 상수, 연산자, 문자열 로 나눌 수 있다. 식별자는 변수가 들어갈 수 있다. 키워드는 코딩 언어에서 배웠던 반복문, 조건문 어휘가 들어간다. 상수는 숫자이며 연산자는 배운 연산자들이 들어간다.
- 식별자 : x y elsex y12
-키워드: if else while for break
-상수: 2 1000 -20 -0.0010 .02
-연산자 : + * { ++ << < <= ]
-문자열: "x" "He said, \" I love CSE.\""
자바에는 StringTokenizer 클래스가 있다. 이는 문자열을 토큰으로 분리하는 것이다. 이를 사용하기 위해서는 import java.util.StringTokenizer 를 통해 임포트 해줘야한다.
* StringTokenizer in Java
import java.util.StringTokenizer;
=> Token 으로 분리
어휘분석은 토큰을 어떻게 나누는 지가 핵심이 된다
따라서 토큰을 어떻게 나눌지에 대한 방법을 알아보자
1. How to describe tokens?
프로그래밍 언어 제작자가 토큰을 어떻게 기술하는가
- 정규표현식을 사용해서 토큰을 설명한다.
정규표현식은 사람보다는 기계에게 좋은 식이다. 정규표현식이란 아래 형식으로 표현하는 것이다.
예시로 이해해보자.
abc 가 있다면 "abc"로 인식되며
abc* 이라면 c는 0번 이상 나오므로 "ab" "abc" "abcc" "abccc" 모두 가능하다.
(abc)* 이라면 abc 모두 0번 이상 나오면 되므로 "" "abc" "abcabc" "abcabcabc" 모두 가능하다
(a|엡실론)b 라면 a가 한번 나오거나 아님 아예 안나오는 것이 일단 한 번 나오고 b 가 나오므로 "ab" "b" 가 가능하다
다만 마지막 예시에는 생각해볼 요소가 있다. 1(0|1)* 이란 1다음에 0이거나1 이 0번 이상 나오는 집합을 의미한다. 여기서는
0이라는 숫자가 표현이 안된다. 따라서 인식되는 문자열은 2진수 집합 또는 0이다.
정규표현식을 위한 몇가지 표현들이 있다.
R+란 R이 한번 이상 나타나는것을 의미한다. R+ = R(R*) (R다음에 R이 0번이상 등장)
R? 란 R이 한번 있거나 아무것도 없음을 의미한다. R? = (R|엡실론) (R이 한번 있거나 아무것도 없음)
[abc] = (a|b|c) (a한번 있거나 b 한번있거나 c 한번있거나 이므로 괄호 속의 문자들 중 하나)
[a-z] = (a|b|....z)이다. 이는 이 범위 속 문자 중 하나를 의미한다.
[^ab] = 괄호 속 문자들만 제외하는 것을 의미한다.
[^a-z]= 이 범위 내 문자들만 제외하는 것을 의미한다.
( 연습 문제 )
https://regex101.com/ 정규표현식 연습하는 사이트
regex101: build, test, and debug regex
Regular expression tester with syntax highlighting, explanation, cheat sheet for PHP/PCRE, Python, GO, JavaScript, Java, C#/.NET, Rust.
regex101.com
2. How to recognize tokens?
: 토큰을 인식해 내는 방법
FSA, Finite State Automata, 유한 상태 오토마타
이제 1번과정에서 정규표현식을 배웠으니 이 정규표현식을 어떻게 코딩으로 식별해낼 것인지가 문제가 된다.
여기에는 유한 상태 오토마타가 사용된다. 정규표현식은 이 유한 상태 오토마타로 나타낼 수 있다. 정규표현식과 유한 상태 오토마타는 표현력이 동일하다!
유한 상태 오토마타란 아래 그림과 같이 나타내는 것이다.
정의를 내리자면 유한상태 오토마타는
1. 상태를 유한한 갯수까지만 가진다. 2. 상태간의 전이를 정의한다. 3. 시작 상태 한 개와 끝 상태 여러 개를 가진다.
유한 상태 오토마타는 정규 표현식과 동일한 표현력을 지니기 때문에 어휘 분석의 기초가 되는 이론적 기반이 된다.
예를 들어 이해하자.
l = [a-xA-Z] 라고 하자. 이는 a부터 z, A 부터 Z 까지 알파벳 대소문자를 의미한다.
d = [0-9] 이므로 0부터 9까지의 정수를 의미한다.
- 식별자는 유한 상태 오토마타를 통해 다음 처럼 인식할 수 있다. 처음에 S 상태로 시작한 후 처음에 l이 한번나오고 l 또는 d 가 계속나오다가 A로 멈춘다. 이는 정규표현식으로는 l(l|d)* 이다.
- 정수는 처음에 S 상태로 시작한 후 + 나 - 혹은 d 가 처음에 나오고 + 나 - 가 나왔다면 그 뒤에 d 가 한 번 더 나온 후 d가 0번 이상 계속 나오고 C로 멈춘다. 이는 정규표현식으로 ('+'|-|엡실론)d+ 이다.
실수는 처음 S 상태로 시작한후 d 가 한번이상 나온 후 .(점) 이 나온다 그후 d가 한번 이상 나오고 C까지도 실수 이고, 아님 e가 나오고 +, -, 엡실론 후에 d 가 한번이상 나오고 E에서 멈춰도 실수이다.
스트링은 S상태에서 "따옴표와 따옴표 사이에 a가 나오는데 \이거나 에스케이프문자면 따로 처리한다.(c는 에시크에프문자이나 여기 오토마타에서는 어느 문자나 가능하다) (\t 같은 경우)
정리하면 토큰 인식을 위해선 사용자가 정의한 정규표현식을 FSA(유한 상태 오토마타)로 변환해야한다. 그 후 FSA 대로 인식한다.
DFA ( Deterministic finite automata)
: FSA 의 한 종류로 간결해서 인식기 구현이 쉽다. 이는 각 상태에서 '나가는 edge'가 레이블 문자에 의해 유일하게 결정이 된다. 쉽게 말하면 각상태마다 문자 'a'가 붙은 edge 는 한 개만 나갈 수 있다는 의미이다. DFA는 엡실론이 붙은 엣지도 없다.
예시로 이해하자면, 눈으로만 봐도 DFA 가 이해하기 쉬운 것을 알 수 있다.
따라서 토큰 인식은 정규표현식을 NFA(non-DFA) 로 우선 변환시키고 , 다시 이 NFA 를 DFA 로 변환시키고 이 DFA 를 따라 인식한다.
3. How to break up text?
다음은 텍스트를 어떻게 토큰으로 분리할지에 대한 문제이다
예를 들어 elsex = 0; 이라는 텍스트가 있다고 하자.
이는 아래처럼 두 개 이상의 정규표현식이 매치될 수 있다.
| else | x | = | 0 | ; |
| elsex | = | 0 | ; |
일반적으로는(그렇게 많이 쓰진 않음) 긴 토큰을 우선으로 한다.
4. How to represent tokens?
다음은 토큰을 어떻게 표현할지에 대한 문제이다.
어휘 분석 결과 내에서 토큰들은 어떻게 표현될까?
전통적으로는 Lexeme = <토큰번호, 토큰값> 으로 나타낸다.
토큰번호는 각 토큰들을 효율적으로 처리하기 위해 정한 고유의 내부번호이다.
토큰값이란 토큰이 프로그래머가 사용한 값을 가질 때의 값을 말한다. 명칭의 토큰값은 그 자신의 스트링 값이며 상수의 토큰값은 그 자신의 상수 값이 된다.
예를 들어 if X<Y then X :=10;
이라는 텍스트가 있을때
| If | X | < | Y | then | X | := | 10 | ; |
| (29,0) | (1,X) | (18,0) | (1,Y) | (35,0) | (1,X) | (9,0) | (2,10) | (7,0) |
으로 표현한다. 교유의 내부 번호의 배정 방법은 해당 컴파일러 개발자만 알 것 이다.
(예시문제) 다음 정규표현식을 인식하는 유한상태오토마타를 상태전이도로 표현하시오 (전체 구조를 먼저 파악할 것)
1. ab
2. a|b
3. a*
4. a+
5. a+c
풀어보기 !
6. ((a+c)|x)*
풀어보기 !
정리
어휘분석이란 소스코드를 "문법적으로 의미 있는 최소단위"인 토큰으로 분리하는 것이다.
토큰과 관련된 질문들에는 4가지가 있다.
1. How to descrive tokens? : 프로그래밍 언어 제작자가 토큰 하나하나를 기술하는 방법 => 정규표현식
2. How to recognize tokens? : 토큰을 인식해 내는 방법 => FSA
3. How to break up tokens? : 여러 토큰이 인식되었을 때 결정하는 방법 => 일반적으로는 토큰의 길이
4. How to represent tokens? : 토큰이 컴퓨터에서 표현되는 방법 => 전통적으로는 Lexeme = <토큰번호, 토큰값>