[컴파일러] 5. 어휘분석

3/24, 3/30

어휘분석기의 역할

• 주) 입력 문자열을 읽어 토큰의 생성
• 부) 빈공간 제거, 오류메시지와 소스 프로그램 연관
• 선형 분석(스캐닝)- 문장을 token 단위 분리
• 식별자와 키워드 인식
  • 키워드: 프로그램 언어에서 특수 의미를 가지는 문자열(예약어와 식별자 구분)
  • 심벌테이블 이용: 식별자의 실제 문자 값(렉심)과의 연결(파서에는 실제 문자열 값을 넘김)
    • lexeme(어휘소, 렉심): 하나의 토큰을 만들어내는 연속적인 입력 문자들
• 상수 처리
• 여백과 주석 제거
• 입력버퍼 처리
• 토큰 번호 부여(파서와 통신)
• 분리의 목적
  • 간단한 설계
  • 컴파일 효율 향상
  • 이식성 증가

패턴: 동일한 토큰 값을 갖는 문자열 집합

렉심(lexeme): 패턴에 적합한 문자들의 나열

 

토큰 구분 요소

• 자유 입력 형식: 구성요소가 라인의 어느 위치든 관계없이 처리
• 공백의 처리: 무시=토큰 식별 어려움
• 예약어 처리: 문자열이 키워드로 예약되지 않으면 처리 복잡

 

정규표현(regular expression)

• 정의 규칙
  • 어떤 기호는 그 집합을 나타냄
  • r과 s가 정규표현 L(r), L(s)를 나타낸다고 하면
    • |은 합집합, 그냥 붙으면 곱, *은 (L(r)))*, (r)은 L(r)을 나타내는 정규표현
  • 불필요한 괄호를 없애기 위한 규약
    • 단항 연산 * 는 가장 높은 우선순위를 가지면 좌측 연관
    • 연결은 두번째 우선순위, 좌측 연관
    • |는 가장 낮은 우선순위, 좌측연관
  • 정규집합: 정규표현으로 표현되는 언어
  • 정규표현의 대수
    • 교환/결합/배분/단위원/기타(r* = (r|epsilon)*)
  • 축약표기 연산자
    • 단항 후위 연산자+ : 하나 또는 그 이상의 갯수
    • 단항 후의 연산자?: 0개 또는 하나
    • 문자 클래스: [abc] == a|b|c, [a-z] == a|b|c|d|...|z

심볼테이블

• 소스 언어의 정보 유지
  • 렉심 저장 및 검색
• 심볼테이블을 이용한 예약어 처리
  • 예약어를 심벌테이블에 토큰값과 함께 저장

정규표현=> 전이 다이어그램(상태전이도)=> 어휘 분석기

 

문자열과 언어

• 문자열: 알파벳에서 뽑아낸 기호의 유한순서
  • |s|가 문자열 s의 길이
  • 입실론이 빈 문자열
• 언어: 고정된 알파벳으로 만들어진 문자열 집합
• 문자열 연결
  • 곱으로 표현
• 문자의 부분열: 문자열 일부

합집합(union)

연결(concatenation)

클로저(closure)

-클리네 클로저(L*)

-양의 클로저(L+)

 

 

 

전이 다이어그램

• 역할: 정규 표현을 다이어그램으로 표시하여 어휘분석기로 구현토록 함
• 구성
  • 상태: 다이어그램 각각 위치. 원으로 표현
  • 연결선: 다음에 나올 수 있는 입력문자 레이블을 표시한 화살표
  • 시작상태: start라고 이름 붙여진 다이어그램의 초기상태
  • 도달상태: 토큰 발견. 이중원으로 표시
  • 입력 retraction: *로 표시. 토큰이 아닌 부분을 읽을때 되돌리는 표시