낱말 분석

어휘 토큰화(lexical tokenization)는 "어휘 분석기(lexer)" 프로그램에 의해 정의된 범주에 속하는 (의미론적 또는 구문론적으로) 의미 있는 어휘 토큰으로 텍스트를 변환하는 과정이다. 자연어의 경우 이러한 범주에는 명사, 동사, 형용사, 구두점 등이 포함된다. 프로그래밍 언어의 경우 이러한 범주에는 식별자, 연산자, 그룹화 기호, 자료형 및 언어 키워드가 포함된다. 어휘 토큰화는 대형 언어 모델 (LLM)에서 사용되는 토큰화 유형과 관련이 있지만 두 가지 차이점이 있다. 첫째, 어휘 토큰화는 일반적으로 어휘 문법을 기반으로 하는 반면, LLM 토크나이저는 일반적으로 확률 기반이다. 둘째, LLM 토크나이저는 토큰을 숫자 값으로 변환하는 두 번째 단계를 수행한다.

 규칙 기반 프로그램 
어휘 토큰화를 수행하는 규칙 기반 프로그램을 토크나이저라고 부르며, 스캐너라고도 하지만 스캐너는 어휘 분석기의 첫 번째 단계에 대한 용어이기도 하다. 어휘 분석기는 처리 과정에서 컴파일러 프론트엔드의 첫 번째 단계를 구성한다. 분석은 일반적으로 한 번의 패스로 이루어진다. 어휘 분석기와 구문 분석기는 대부분 컴파일러에 사용되지만, 프리티프린터나 린터와 같은 다른 컴퓨터 언어 도구에도 사용될 수 있다. 어휘 분석은 두 단계로 나눌 수 있다. 첫 번째는 입력 문자열을 어휘소라고 하는 구문 단위로 분할하고 이를 토큰 클래스로 분류하는 스캐닝이며, 두 번째는 어휘소를 처리된 값으로 변환하는 평가이다.

어휘 분석기는 일반적으로 매우 단순하며, 대부분의 복잡성은 구문 분석 또는 의미 분석 단계로 미뤄지며, 어휘 분석기 생성기, 특히 Lex 또는 파생 도구에 의해 생성되는 경우가 많다. 그러나 어휘 분석기는 때때로 구문 구조 처리와 같은 일부 복잡성을 포함하여 입력을 더 쉽게 만들고 구문 분석기를 단순화할 수 있으며, 더 많은 기능을 지원하거나 성능을 위해 부분적으로 또는 전체적으로 수작업으로 작성될 수도 있다.

 "어휘소"의 의미 구별 

규칙 기반 자연어 처리에서 "어휘소"라고 불리는 것은 언어학에서 어휘소라고 불리는 것과 같지 않다. 규칙 기반 자연어 처리에서 "어휘소"라고 불리는 것은 영어와 같은 분석어에서만 언어학적 등가물과 같을 수 있지만, 굴절어와 같은 고도로 종합어에서는 그렇지 않다. 규칙 기반 자연어 처리에서 어휘소라고 불리는 것은 언어학에서 단어라고 불리는 것과 더 유사하며 (컴퓨터 아키텍처의 단어와 혼동하지 말 것), 어떤 경우에는 형태소와 더 유사할 수도 있다.

 어휘 토큰 및 어휘 토큰화 

어휘 토큰은 대형 언어 모델에서 사용되는 확률적 토큰과 대조적으로 할당되어 식별된 의미를 가진 문자열이다. 어휘 토큰은 토큰 이름과 선택적 토큰 값으로 구성된다. 토큰 이름은 규칙 기반 어휘 단위의 범주이다.

C 프로그래밍 언어의 다음 표현식을 고려해 보자:
 

이 표현식의 어휘 분석은 다음 토큰 시퀀스를 산출한다:
 

토큰 이름은 언어학에서 품사라고 불릴 수 있는 것이다.

어휘 토큰화는 식별자, 연산자, 그룹화 기호 및 자료형과 같이 "어휘 분석기" 프로그램에 의해 정의된 범주에 속하는 (의미론적 또는 구문론적으로) 의미 있는 어휘 토큰으로 원시 텍스트를 변환하는 과정이다. 결과 토큰은 다른 형태의 처리로 전달된다. 이 과정은 입력 구문 분석의 하위 작업으로 간주될 수 있다.

예를 들어, 텍스트 문자열에서:
 The quick brown fox jumps over the lazy dog

이 문자열은 자연어 화자가 할 것처럼 암묵적으로 공백으로 분할되지 않는다. 원시 입력, 즉 43개의 문자는 주어진 공백 구분자 (즉, 문자열 " " 또는 정규 표현식 와 일치하는)로 명시적으로 9개의 토큰으로 분할되어야 한다.

토큰 클래스가 둘 이상의 가능한 어휘소를 나타낼 때, 어휘 분석기는 종종 원본 어휘소를 재현할 수 있는 충분한 정보를 저장하여 의미 분석에 사용될 수 있도록 한다. 구문 분석기는 일반적으로 어휘 분석기로부터 이 정보를 검색하여 추상 구문 트리에 저장한다. 이는 숫자가 유효한 식별자일 수도 있는 경우 정보 손실을 피하기 위해 필요하다.

토큰은 어휘 분석기의 특정 규칙에 따라 식별된다. 토큰을 식별하는 데 사용되는 몇 가지 방법에는 정규 표현식, 플래그라고 불리는 특정 문자 시퀀스, 구분 문자라고 불리는 특정 구분 문자, 그리고 사전에 의한 명시적 정의가 포함된다. 구두점 문자를 포함한 특수 문자는 서면 언어 및 프로그래밍 언어에서 자연스럽게 사용되기 때문에 어휘 분석기가 토큰을 식별하는 데 일반적으로 사용된다. 어휘 분석기는 일반적으로 토큰 조합에 대해 아무것도 하지 않으며, 이 작업은 구문 분석기에게 맡겨진다. 예를 들어, 일반적인 어휘 분석기는 괄호를 토큰으로 인식하지만 각 "("이 ")"와 일치하는지 확인하는 작업은 하지 않는다.

어휘 분석기가 구문 분석기에 토큰을 제공할 때 사용되는 표현은 일반적으로 열거형으로, 이는 숫자 표현의 목록이다. 예를 들어, "식별자"는 0으로, "할당 연산자"는 1로, "덧셈 연산자"는 2 등으로 표현될 수 있다.

토큰은 종종 lex와 같은 어휘 분석기 생성기가 이해하는 정규 표현식이나 수작업으로 코딩된 유한 상태 기계에 의해 정의된다. 어휘 분석기(lex와 같은 도구에 의해 자동으로 생성되거나 수작업으로 작성됨)는 문자 스트림을 읽고, 스트림에서 어휘소를 식별하고, 이를 토큰으로 분류한다. 이를 토큰화라고 한다. 어휘 분석기가 유효하지 않은 토큰을 발견하면 오류를 보고한다.

토큰화 다음에는 구문 분석이 이어진다. 거기서부터 해석된 데이터는 일반적인 사용, 해석 또는 컴파일을 위해 자료 구조로 로드될 수 있다.

 어휘 문법 
프로그래밍 언어의 사양에는 종종 어휘 구문을 정의하는 규칙 집합인 어휘 문법이 포함된다. 어휘 구문은 일반적으로 정규 언어이며, 문법 규칙은 정규 표현식으로 구성된다. 이는 토큰의 가능한 문자 시퀀스(어휘소) 집합을 정의한다. 어휘 분석기는 문자열을 인식하고, 발견된 각 종류의 문자열에 대해 어휘 프로그램은 동작을 취하는데, 가장 간단하게는 토큰을 생성한다.

두 가지 중요한 일반적인 어휘 범주는 공백과 주석이다. 이들도 문법에 정의되어 어휘 분석기에 의해 처리되지만 (토큰을 생성하지 않고) 버려지거나 중요하지 않은 것으로 간주될 수 있으며, 최대 두 개의 토큰을 분리하는 역할만 한다 (예: `ifx` 대신 `if x`). 여기에는 두 가지 중요한 예외가 있다. 첫째, 들여쓰기로 블록을 구분하는 오프사이드 룰 언어에서는 초기 공백이 유의미하며, 블록 구조를 결정하고 일반적으로 어휘 분석기 수준에서 처리된다. 아래의 구문 구조를 참조하라. 둘째, 어휘 분석기의 일부 사용에서는 주석과 공백이 보존되어야 한다. 예를 들어, 프리티프린터는 주석을 출력해야 하고 일부 디버깅 도구는 프로그래머에게 원본 소스 코드를 보여주는 메시지를 제공할 수 있다. 1960년대, 특히 ALGOL에서는 라인 재구성 단계(컴파일러 프론트엔드의 초기 단계)의 일부로 공백과 주석이 제거되었지만, 이 별도의 단계는 제거되었고 이제 이들은 어휘 분석기에 의해 처리된다.

 세부 정보 
 스캐너 
첫 번째 단계인 스캐너는 일반적으로 유한 상태 기계 (FSM)를 기반으로 한다. 이 스캐너에는 처리하는 토큰(이러한 문자 시퀀스의 개별 인스턴스는 어휘소라고 함) 내에 포함될 수 있는 가능한 문자 시퀀스에 대한 정보가 인코딩되어 있다. 예를 들어, 정수 어휘소는 숫자 문자 시퀀스를 포함할 수 있다. 많은 경우, 첫 번째 비공백 문자를 사용하여 뒤따르는 토큰의 종류를 추론할 수 있으며, 이후의 입력 문자는 해당 토큰에 허용되는 문자 집합에 속하지 않는 문자에 도달할 때까지 한 번에 하나씩 처리된다(이를 최대 탐욕 또는 최장 일치 규칙이라고 함). 일부 언어에서는 어휘소 생성 규칙이 더 복잡하여 이전에 읽은 문자를 퇴각검색해야 할 수도 있다. 예를 들어, C 언어에서는 'L' 문자는 'L'로 시작하는 식별자와 와이드 문자열 리터럴을 구별하기에 충분하지 않다.

 평가자 
그러나 어휘소는 특정 종류로 알려진 문자열(예: 문자열 리터럴, 문자 시퀀스)일 뿐이다. 토큰을 구성하려면 어휘 분석기에 두 번째 단계인 평가자가 필요하며, 이 평가자는 어휘소의 문자를 검토하여 값을 생성한다. 어휘소의 유형과 값이 결합된 것이 토큰을 정확히 구성하며, 이는 구문 분석기에 제공될 수 있다. 괄호와 같은 일부 토큰은 실제로 값이 없으므로 이들에 대한 평가자 함수는 아무것도 반환하지 않을 수 있다. 유형만 필요하다. 마찬가지로, 때로는 평가자가 어휘소를 완전히 억제하여 구문 분석기로부터 숨길 수 있는데, 이는 공백과 주석에 유용하다. 식별자에 대한 평가자는 일반적으로 단순하지만(식별자를 문자 그대로 나타냄) 일부 언스트로핑을 포함할 수도 있다. 정수 리터럴에 대한 평가자는 문자열을 전달하거나(평가를 의미 분석 단계로 연기함) 자체적으로 평가를 수행할 수 있으며, 이는 다른 진법 또는 부동 소수점 숫자에 대해 복잡할 수 있다. 간단한 따옴표로 묶인 문자열 리터럴의 경우 평가자는 따옴표만 제거하면 되지만, 이스케이프된 문자열 리터럴의 평가자는 이스케이프 시퀀스를 이스케이프 해제하는 어휘 분석기를 통합한다.

예를 들어, 컴퓨터 프로그램의 소스 코드에서 다음 문자열:
 
다음 어휘 토큰 스트림으로 변환될 수 있다. 공백은 억제되고 특수 문자는 값이 없다:
 IDENTIFIER net_worth_future
 EQUALS
 OPEN_PARENTHESIS
 IDENTIFIER assets
 MINUS
 IDENTIFIER liabilities
 CLOSE_PARENTHESIS
 SEMICOLON

어휘 분석기는 수작업으로 작성할 수 있다. 토큰 목록이 작다면 이것은 실용적이지만, 컴파일러 컴파일러 툴체인의 일부로 자동화된 도구에 의해 생성된 어휘 분석기는 더 많은 잠재적 토큰에 대해 더 실용적이다. 이러한 도구는 일반적으로 입력 스트림에서 허용되는 토큰을 설명하는 정규 표현식을 허용한다. 각 정규 표현식은 프로그래밍 언어의 어휘 문법에서 정규 표현식과 일치하는 어휘소를 평가하는 생성 규칙과 연결된다. 이러한 도구는 컴파일 및 실행할 수 있는 소스 코드를 생성하거나 유한 상태 기계에 대한 상태 전이표를 구성할 수 있다(이는 컴파일 및 실행을 위한 템플릿 코드에 연결됨).

정규 표현식은 어휘소의 문자들이 따를 수 있는 패턴을 압축적으로 나타낸다. 예를 들어, 영어 기반 언어의 IDENTIFIER 토큰은 모든 영어 알파벳 문자 또는 밑줄로 시작하고, ASCII 영숫자 문자 및 밑줄이 몇 번이든 뒤따를 수 있다. 이는 문자열 로 압축적으로 표현될 수 있다. 이는 "a-z, A-Z 또는 _ 문자 중 하나로 시작하고, 그 뒤에 a-z, A-Z, _ 또는 0-9 문자가 0개 이상 오는 것"을 의미한다.

정규 표현식과 그들이 생성하는 유한 상태 기계는 "n개의 여는 괄호, 뒤따르는 문장, 뒤따르는 n개의 닫는 괄호"와 같은 재귀 패턴을 처리할 만큼 강력하지 않다. n에 대해 유한한 허용 값 집합이 존재하지 않는 한, 양쪽에서 n이 같은지 수를 세고 확인할 수 없다. 이러한 패턴을 일반적인 방식으로 인식하려면 완전한 구문 분석기가 필요하다. 구문 분석기는 스택에 괄호를 푸시한 다음 팝하여 스택이 끝에서 비어 있는지 확인할 수 있다(프로그램의 구조와 해석 책의 예시 참조).

 장애물 
일반적으로 어휘 토큰화는 단어 수준에서 발생한다. 그러나 "단어"가 무엇을 의미하는지 정의하기가 어려울 때가 있다. 종종 토크나이저는 간단한 휴리스틱에 의존한다. 예를 들어:
 구두점과 공백은 결과 토큰 목록에 포함될 수도 있고 포함되지 않을 수도 있다.
 연속된 알파벳 문자열은 모두 하나의 토큰의 일부이며, 숫자도 마찬가지다.
 토큰은 공백이나 줄 바꿈과 같은 공백 문자 또는 구두점 문자로 구분된다.

단어 사이의 공백을 사용하는 언어(예: 라틴 알파벳을 사용하는 대부분의 언어 및 대부분의 프로그래밍 언어)에서는 이 접근 방식이 매우 간단하다. 그러나 여기에도 축약, 하이픈으로 연결된 단어, 이모티콘, 그리고 URI와 같은 더 큰 구조(어떤 목적에는 단일 토큰으로 간주될 수 있는)와 같은 많은 예외가 있다. 고전적인 예는 "New York-based"인데, 순진한 토크나이저는 공백에서 나눌 수 있지만 더 나은 분리는 (아마도) 하이픈에서 이루어진다.

토큰화는 스크립티오 콘티누아로 작성된 언어에 특히 어렵다. 이러한 언어는 단어 경계가 없으며, 고대 그리스어, 중국어, 또는 태국어와 같다. 교착어인 한국어도 토큰화 작업을 복잡하게 만든다.

더 어려운 문제를 해결하는 몇 가지 방법에는 더 복잡한 휴리스틱 개발, 일반적인 특수 사례 테이블 조회, 또는 나중 처리 단계에서 연어를 식별하는 언어 모델에 토큰 맞추기가 포함된다.

 어휘 분석기 생성기 

어휘 분석기는 구문 분석기 생성기와 유사하게 어휘 분석기 생성기에 의해 생성되는 경우가 많으며, 이러한 도구는 종종 함께 제공된다. 가장 잘 알려진 것은 lex와 Yacc 구문 분석기 생성기, 또는 그들의 많은 재구현인 flex (종종 GNU bison과 함께 사용됨)이다. 이러한 생성기는 도메인 특화 언어의 한 형태이며, 어휘 사양(일반적으로 일부 마크업이 있는 정규 표현식)을 입력으로 받아 어휘 분석기를 출력한다.

이러한 도구는 매우 빠른 개발을 가능하게 하며, 이는 초기 개발에 매우 중요하다. 이는 작동하는 어휘 분석기를 얻기 위해서뿐만 아니라 언어 사양이 자주 변경될 수 있기 때문이다. 또한, 수작업으로 프로그래밍하기 어려운 사전 및 사후 조건과 같은 고급 기능을 제공하는 경우가 많다. 그러나 자동으로 생성된 어휘 분석기는 유연성이 부족하여 일부 수동 수정이 필요하거나 완전히 수동으로 작성된 어휘 분석기가 필요할 수 있다.

어휘 분석기 성능은 중요한 문제이며, 최적화할 가치가 있다. 특히 어휘 분석기가 매우 자주 실행되는 안정적인 언어(예: C 또는 HTML)에서는 더욱 그렇다. lex/flex로 생성된 어휘 분석기는 합리적으로 빠르지만, 더 잘 조정된 생성기를 사용하면 2~3배의 성능 향상이 가능하다. 수동으로 작성된 어휘 분석기가 때때로 사용되지만, 현대의 어휘 분석기 생성기는 대부분의 수동으로 코딩된 것보다 빠른 어휘 분석기를 생성한다. lex/flex 계열의 생성기는 테이블 기반 접근 방식을 사용하는데, 이는 직접 코딩된 접근 방식보다 훨씬 덜 효율적이다. 후자의 접근 방식에서는 생성기가 goto 문을 통해 다음 상태로 직접 이동하는 엔진을 생성한다. re2c와 같은 도구는 flex가 생성한 엔진보다 2~3배 빠른 엔진을 생성하는 것으로 입증되었다. 일반적으로 이러한 후자 도구가 생성한 엔진보다 더 나은 성능을 내는 분석기를 수동으로 작성하는 것은 어렵다.

 구문 구조 
어휘 분석은 주로 문자 입력 스트림을 토큰으로 분할하며, 단순히 문자를 조각으로 그룹화하고 분류한다. 그러나 어휘 분석은 훨씬 더 복잡할 수 있다. 가장 간단하게는 어휘 분석기가 토큰을 생략하거나 추가 토큰을 삽입할 수 있다. 토큰, 특히 공백과 주석을 생략하는 것은 컴파일러가 필요하지 않을 때 매우 일반적이다. 덜 일반적으로, 추가 토큰이 삽입될 수 있다. 이것은 주로 토큰을 문으로, 또는 문을 블록으로 그룹화하여 구문 분석기를 단순화하기 위해 수행된다.

 줄 연속 
줄 연속은 줄 바꿈이 일반적으로 문 종결자인 일부 언어의 기능이다. 대부분의 경우, 백슬래시(바로 새줄 문자가 뒤따름)로 줄을 끝내면 줄이 계속된다. 즉, 다음 줄이 이전 줄에 합쳐진다. 이는 일반적으로 어휘 분석기에서 수행된다. 즉, 백슬래시와 줄 바꿈은 버려지며, 줄 바꿈은 토큰화되지 않는다. Bash, 다른 셸 스크립트 및 파이썬이 그 예이다.

 세미콜론 삽입 
많은 언어에서 세미콜론은 문장 종결자로 사용된다. 대부분의 경우 이는 필수적이지만, 일부 언어에서는 많은 맥락에서 세미콜론이 선택 사항이다. 이는 주로 어휘 분석기 수준에서 수행되는데, 어휘 분석기는 입력 문자 스트림에 세미콜론이 없더라도 토큰 스트림에 세미콜론을 출력하며, 이를 세미콜론 삽입 또는 자동 세미콜론 삽입이라고 한다. 이러한 경우, 세미콜론은 언어의 공식 구문 문법의 일부이지만, 어휘 분석기에 의해 삽입될 수 있으므로 입력 텍스트에서는 발견되지 않을 수 있다. 선택적 세미콜론 또는 기타 종결자나 구분자는 때때로 후행 쉼표 또는 세미콜론의 경우와 같이 구문 분석기 수준에서도 처리된다.

세미콜론 삽입은 BCPL과 그 먼 후손인 Go의 기능이지만, B나 C에는 없다. 세미콜론 삽입은 자바스크립트에 존재하지만, 규칙이 다소 복잡하고 많은 비판을 받았다. 버그를 피하기 위해 일부는 항상 세미콜론을 사용할 것을 권장하는 반면, 다른 일부는 잠재적으로 모호한 문장의 시작 부분에 방어적 세미콜론이라고 불리는 초기 세미콜론을 사용한다.

세미콜론 삽입(세미콜론으로 종결되는 문장이 있는 언어에서)과 줄 연속(줄 바꿈으로 종결되는 문장이 있는 언어에서)은 상호 보완적인 것으로 볼 수 있다. 세미콜론 삽입은 줄 바꿈이 일반적으로 토큰을 생성하지 않더라도 토큰을 추가하는 반면, 줄 연속은 줄 바꿈이 일반적으로 토큰을 생성하더라도 토큰 생성을 방지한다.

 오프사이드 룰 

오프사이드 룰 (들여쓰기로 결정되는 블록)은 파이썬처럼 어휘 분석기에서 구현될 수 있다. 들여쓰기를 늘리면 어휘 분석기가 INDENT 토큰을 생성하고, 들여쓰기를 줄이면 어휘 분석기가 하나 이상의 DEDENT 토큰을 생성한다. 이 토큰은 블록에 중괄호를 사용하는 언어의 여는 중괄호 { 및 닫는 중괄호 }에 해당하며, 구문 문법이 중괄호 또는 들여쓰기 사용 여부에 의존하지 않음을 의미한다. 이를 위해서는 어휘 분석기가 상태, 즉 들여쓰기 수준 스택을 유지해야 하므로 들여쓰기가 변경될 때 변경 사항을 감지할 수 있으며, 따라서 어휘 문법은 문맥 자유가 아니다. INDENT–DEDENT는 이전 들여쓰기 수준의 문맥 정보에 의존한다.

 문맥 의존 어휘 분석 
일반적으로 어휘 문법은 문맥 자유이거나 거의 문맥 자유이므로 뒤로 보거나 앞으로 볼 필요가 없으며 퇴각검색도 필요 없어 간단하고 깔끔하며 효율적인 구현이 가능하다. 또한 어휘 분석기에서 구문 분석기로의 간단한 단방향 통신이 가능하며, 어휘 분석기로 다시 정보가 흐를 필요가 없다.

그러나 예외는 있다. 간단한 예로는 한 토큰을 뒤로 봐야 하는 Go의 세미콜론 삽입, 하나의 토큰을 버퍼에 저장한 후 내보내야 하는 파이썬의 연속적인 문자열 리터럴 연결(다음 토큰이 다른 문자열 리터럴인지 확인하기 위해)이 있으며, 들여쓰기 수준을 유지해야 하는 파이썬의 오프사이드 룰이 있다. 이러한 예들은 모두 어휘적 문맥만 필요하며, 어휘 분석기를 다소 복잡하게 만들지만, 구문 분석기와 이후 단계에는 보이지 않는다.

더 복잡한 예는 C 언어의 렉서 핵인데, typedef 이름과 변수 이름은 어휘적으로 동일하지만 다른 토큰 클래스를 구성하므로 문자 시퀀스의 토큰 클래스를 의미 분석 단계가 되어서야 결정할 수 있다. 따라서 이 핵에서 어휘 분석기는 의미 분석기(예: 심볼 테이블)를 호출하여 시퀀스가 typedef 이름을 필요로 하는지 확인한다. 이 경우 구문 분석기에서뿐만 아니라 의미 분석기에서 어휘 분석기로 정보가 다시 흘러야 하므로 설계가 복잡해진다.

 같이 보기 
 어휘화

 각주 

 참고 문헌 
 

분류:프로그래밍 언어 구현
분류:컴파일러 구성
분류:구문 분석