어휘분석기(Lexer)
- 문자를 토큰으로 변환한다.
->int a; 를 Type(int) Variable(a); 이런식으로 변환.
- 기종마다 다른 문자열을 사용하며, 줄바꿈문자 관례도 다르다.
- 컴파일에서 성능 향상부분을 제외하면 총 시간의 75%가 어휘분석 과정이다.
- 설계가 간단하다.
파서(Parser)
- 토큰을 추상 구문트리(파스트리)로 변환한다.
- 식별자의 선언 여부, 타입검사, 묵시적 타입변환을 명시적으로 변환한다.
- 컴파일 중 상수 계산식을 실행한다.
- 성능향상을 위해 코드를 재배치하고, 불필요한 코드를 삭제한다.
- S가 시작기호라고 하면, S`->S$(eof)로 변환한다.
First집합
- 어떤 토큰 A가 무엇으로 이어질 수 잇는가? -> First(A)
ex] S-> C | D, C-> aC | b, D -> cD | d 일때,
S->C->aC, S->C->b, S->D->cD, s->D->d 이므로
FIRST(S) = {a,b,c,d}
FIRST(C) = {a, b}
FIRST(D) = {c, d}
추상 구문구조(Abstract Syntax)
- 필요한 부분을 표현해 남겨둠.
ex] BNF에서는 Assignment -> Identifier = Expression;
추상 구문구조에서는 Assignment -> Variable target; Expression source;
- 표현이 간결해지므로, 추상구문트리에서도 보기 간결하다.
결정 유한상태 오토마타 (Deterministic Finite Automata, DFA)
- $ : End of file/String
- 파서와 렉서는 한 글자/토큰 씩 가져온다.
- 한 글자 집합의 읽기를 종료할 때, 그 다음글자 까지 인식하게 된다.
-> '100 + a'라는 글자를 읽을 때, 100이 끝났다는 사실을 알기 위해서는 +까지 인식해야 한다.
-> 이를 해결하기 위해 엿보기 함수, 되돌림 함수를 만들어 이용하거나, 시작 상태에서 입력문자를 처리하지 않는다.
- 입력 끝 표시자 '$'는 토큰마다 나타나지 않고, 전체 프로그램의 끝에서만 나타난다.
- 토큰이 아닌 입력 (여백, 주석)은 시작상태로 돌려보낸다.
- 오토마타는 결정적이여야한다. (모호하면 안된다는 뜻)