개요

컴파일러의 어휘분석에 대해 알아본다. 이 글은 내공 있는 프로그래머로 길러주는 컴파일러의 이해의 내용을 기반으로 함을 미리 밝힌다. 책 내용이 괜찮으니 관심있으신 분들은 사보는것을 추천한다.(필자는 이해관계자는 아님을 밝힌다.)

목차

컴파일러 강의 다른 포스팅은 아래의 링크를 참고하자.

목차

  • 어휘분석의 개요
  • 토큰의 인식
  • 어휘분석기의 설계 및 구현

Regular Definitions

Extensions of Regular Expressions

Filename expression used by the sh

어휘분석의 개요

  • 어휘분석이란 소스프로그램을 읽어 토큰으로 분리하는 것으로 토큰 스트림을 출력
  • 어휘 분석 도구를 어휘 분석기 또는 스캐너라 칭함

  • 어휘 분석기의 기능
    • 토큰 인식
    • 전처리
    • 기호표 구성
    • 에러 처리에 대한 진단

어휘분석의 개요: 용어

  • 용어
    • 토큰(Token) : 문법적으로 의미 있는 최소 단위
    • 패턴(Pattern) : 토큰을 서술하는 규칙들
    • 렉심(Lexeme) : 패턴에 의해 매칭된 문자열
  • 일반적인 프로그래밍 언어에서 사용하는 토큰
    1. 예약어(Reserved word) — for, if, int 등의 언어에 이미 정의된 단어
    2. 연산자 기호(Operator symbol) — +, -, *, /, <, =, ++ 등의 기호
    3. 구분자(Delimiter) — ;, ,, (, ), [, ] 등 단어와 단어, 문장과 문장들을 구분
    4. 식별자(identifier) — abc, b12, sum, 등 프로그래머가 정의하는 변수
    5. 상수(constant) — 526, 3.0, 0.1234e-10, ‘string’ 등 정수형, 실수형, 문자형
      상수

어휘분석의 개요: 패턴

예제 : 토큰 스트림 구하기

예제 : 토큰, 렉심, 패턴 구하기

어휘분석의 개요: 토큰의 표현

  • 토큰의 표현
    • 효율적인 구문분석을 위해 토큰을 토큰번호와 토큰 값의 순서쌍으로 표현
    • (토큰번호, 토큰값)
    • 토큰번호 : 각각의 토큰을 구분하기 위해 부여한 정수
    • 토큰값 : 토큰들 중에 식별자나 상수는 서로 구별하기 위한 값

토큰 스트림을 순서쌍으로 표현하기

토큰의 인식, 식별자 인식

  • 토큰의 인식
    • 토큰의 구조 : 정규표현을 사용해서 표현
    • 어휘분석기는 정규표현으로 부터 이를 받아들이는 유한 오토마타를 구성함으로써 구현
  • 토큰 인식을 위한 영문자와 숫자
    • letter -> [a-Za-z]
    • digit -> [0-9]
  • identifier(식별자) 인식
    • C언어의 식별자는 첫글자가 letter이거나 밑줄로 시작하고 두번째 부터 letter, _, digit이 오며 길이는 무제한
    • 상태 전이도를 만듦

예약어 인식

정수 및 실수 상수의 인식

어휘분석기의 설계 및 구현

  • 어휘분석기의 구현 방법
    • 이론적인 방법들을 프로그래밍을 통하여 구현
    • 어휘분석기 생성기를 통해서 구문 분석기를 생성

어휘분석기의 설계 및 구현

어휘분석기의 설계 및 구현: 식별자

어휘분석기의 설계 및 구현: 상수

어휘분석기의 설계 및 구현: 연산자

어휘분석기의 설계 및 구현: 구분자

어휘분석기의 설계 및 구현: 토큰 표

어휘분석기의 설계 및 구현:전체 상태 전이도

어휘분석기 C로 구현

어휘분석기 C로 구현: 상수

어휘분석기의 설계 및 구현

요약

  • 어휘분석
    • 어휘 분석은 컴파일러의 첫 번째 단계로 소스 프로그램을 읽어들여 문법적으로 의미 있는 최소 단위인 토큰으로 분리하는 것
    • 어휘 분석을담당하는도구는 어휘분석기 또는 스캐너
  • 토큰의인식
    • 토큰 : 문법적으로 의미 있는최소단위
    • 패턴 : 각문자열을토큰에 대응시키기 위한규칙
    • 렉심 : 토큰을구성하는소스프로그램에 있는문자의 나열
  • 어휘분석기의 설계 및 구현