어휘분석의 개요

어휘분석 - 소스프로그램을 읽어 토큰이라는 문법적으로 의미 있는 최소의 단위로 분리하는 것으로 토큰 스트림을 출력

어휘분석기 기능

• 토큰을 인식
• 전처리 과정(코멘트, white space, tab 등을 처리)
• 기호표 구성
• 에러 처리에 대한 진단

어휘분석 용어

토큰 - 문법적으로 의미 있는 최소 단위

패턴 - 토큰을 서술하는 규칙들

렉심 - 패턴에 의해 매칭된 문자열

일반적인 프로그래밍 언어에서 사용하는 토큰

• 예약어 : for, if, int 등 언어에 이미 정의된 단어
• 연산자 기호 : +, -, / 등의 기호
• 구분자 : ;, , (,), [,] 등 단어와 단어, 문장과 문장들ㅇ르 구분
• 식별자 - 프로그래머가 정의하는 변수
• 상수 - 정수형, 실수형, 문자형 상수

패턴

패턴: 정규 표현 등으로 서술

C 언어의 식별자 : 첫 번째 기호가 영문자 혹은 언더바(_)로 시작하고 두 번째 기호 부터는 영문자나 숫자, 언더바가 오는 것

토큰, 렉심, 패턴 구하기

어휘분석기의 설계 및 구현

어휘분석기의 구현 방법

1. 이론적인 방법들을 프로그래밍을 통하여 구현
2. 어휘분석기 생성기 렉스를 통해 구문 분석기를 생성하는 방법

프로그래밍 기법

주어진 문법에 사용하는 토큰과 패턴을 찾아 이를 정규 표현으로 나타낸다. 이 정규표현을 받아들이는 NFA를 구현하고 이를 DFA로 변환한 뒤 마지막으로 DFA를 상태수가 최소화된 DFA로 변환하는 것이 어휘분석기임

전체 상태 전이도

주어진 문법에 대한 상태 전이도