| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 · 형식언어 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍 · 증명보조기) · 메타 프로그래밍 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
1. 개요
Lexical analysis / Lexing주어진 입력을 사전에 정해진 규칙에 맞게 문법적으로 의미를 가지는 최소 단위인 토큰으로 분리하고 각 토큰의 종류에 맞게 적절한 분류를 수행하는 과정.
2. 명칭
이론언어학과 이론 컴퓨터 과학에서 동시에 다루어지는 주제인 만큼 여러 명칭이 공존하고 있다. 특히 컴퓨터공학 쪽에선 스캐닝(scanning), NLP 측에선 토큰화(tokenization) 등의 용어도 렉싱(lexing)만큼 자주 쓰이는 편. 정리하면 다음과 같다.| 의미 | 용어 | |
| 어휘 분석 | 영어 | lexical analysis, lexing, lexical tokenization, tokenization, tokenizing[u], scanning |
| 한국어 | 어휘 분석, 낱말 분석[u], 렉싱, 토큰화, 스캐닝 | |
| 어휘 분석의 단위 | 영어 | lexical token, token, word[u] |
| 한국어 | 어휘[u], 토큰 | |
| 어휘의 종류 | 영어 | token type, token name, lexical category[u] |
| 한국어 | 토큰 분류[u], 토큰 타입 | |
| 문장 내 실제 어휘 | 영어 | lexeme, span[d] |
| 한국어 | 어휘소[u], 렉심 | |
| 어휘 분석을 수행하는 기계 또는 프로그램 | 영어 | lexical analyzer, lexer, tokenizer, scanner, segmenter[u] |
| 한국어 | 어휘 분석기, 렉서, 토크나이저, 스캐너 | |
| 어휘 분석을 수행하는 기계 또는 프로그램을 생성하는 기계 또는 프로그램 | 영어 | lexical analyzer generator[u], lexer generator |
| 한국어 | 어휘 분석기 생성기[u], 렉서 제너레이터 | |
언어학의 lexicalization과 lexicon, lemmatization 및 기타 형태론이나 NLP 과정들과는 다르다. 렉싱의 핵심은 형태소를 형태소를 추론하는 것이 아닌 단지 주어진 문장의 segmentation이기 때문.
위에서도 언급했지만 lex- 형태의 용어는 주로 언어학 연구에서 파생된 것들이 대부분으로, 조금 더 엄밀한 명칭인 동시에 타 표현들에 비해 lexer, lexing 등의 줄임말 표현이 있기에 실무에서도 자주 쓰이는 편. 또한 타 용어들에 비해 프로그래밍 언어의 컴파일러로써의 성격도 강하다. token- 형태의 용어는 주로 NLP 분야, 즉 입력이 자연어일 경우인 맥락일 가능성이 높지만 후술할 token을 대체할 단어가 없기에 덩달아 자주 쓰인다. scan- 형태는 흔히
scanf, java.util.Scanner 등으로 연상되듯 주로 손으로 짠(handwritten) 렉서를 의미하며 완성된 프로그래밍 언어보단 문장의 일부분을 파싱하는 용도로 쓰인다. 렉서 제너레이터가 scanner generator등의 형태로 쓰이지 않는 것도 이러한 뉘앙스 때문.토큰과 토큰 타입, 렉심은 화자와 맥락에 따라 혼용되면서도 사전적으로는 다른 의미이다. 렉심의 경우 인식된 개별 토큰과 추상적으로 대응되는 입력의 일부분을 가리키지만, span은 입력 문자열의 시작과 끝 인덱스를 의미하는 조금 더 구현 친화적인 용어.
본 문서에서는 컴퓨터공학 및 컴파일러 설계적 관점을 우선하며, 용어 또한 실질적으로 현실에서 자주 쓰이는 영어 음차 용어들(렉서, 파서, 토큰, 렉심, 제너레이터 등)의 사용을 우선한다.
3. 토큰과 렉심
토큰은 문장의 최소 구성단위로, 프로그래밍 언어에서는 대체로 키워드(keyword), 식별자(identifier), 상수(constant), 문자열(string), 연산자(operator), 구분자(punctuation), 공백(whitespace) 등등이 있다. 일례로 다음의 C 언어 코드를 보자.#!syntax cpp
int mins = 24 * 60;24, 60 등은 상수이고 int는 키워드일 것이다. 마찬가지로 위 코드를 개별 토큰으로 전부 분리해 보자.| 토큰 타입 | {{{#!wiki style="margin: -15px -10px" | 키워드 | }}} | {{{#!wiki style="margin: -15px -10px" | <tablewidth=100%><tablebordercolor=#c5c2cb,#585260> 공백 | }}} | {{{#!wiki style="margin: -15px -10px" | <tablewidth=100%><tablebordercolor=#aa573c> 식별자 | }}} | {{{#!wiki style="margin: -15px -10px" | <tablewidth=100%><tablebordercolor=#c5c2cb,#585260> 공백 | }}} | {{{#!wiki style="margin: -15px -10px" | <tablewidth=100%><tablebordercolor=#2a9292> 연산자 | }}} | {{{#!wiki style="margin: -15px -10px" | <tablewidth=100%><tablebordercolor=#c5c2cb,#585260> 공백 | }}} | {{{#!wiki style="margin: -15px -10px" | <tablewidth=100%><tablebordercolor=#be4678> 상수 | }}} | {{{#!wiki style="margin: -15px -10px" | <tablewidth=100%><tablebordercolor=#c5c2cb,#585260> 공백 | }}} | {{{#!wiki style="margin: -15px -10px" | <tablewidth=100%><tablebordercolor=#2a9292> 연산자 | }}} | {{{#!wiki style="margin: -15px -10px" | <tablewidth=100%><tablebordercolor=#c5c2cb,#585260> 공백 | }}} | {{{#!wiki style="margin: -15px -10px" | <tablewidth=100%><tablebordercolor=#be4678> 상수 | }}} | {{{#!wiki style="margin: -15px -10px" | <tablewidth=100%><tablebordercolor=#955ae7> 구분자 | }}} | |||||||
| 렉심 | <rowcolor=#fff><nopad> i | <nopad> n | <nopad> t | <nopad> | <nopad> m | <nopad> i | <nopad> n | <nopad> s | <nopad> | <nopad> = | <nopad> | <nopad> 2 | <nopad> 4 | <nopad> | <nopad> * | <nopad> | <nopad> 6 | <nopad> 0 | <nopad> ; | ||||||||||||||||||||||||
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | ||||||||||||||||||||||||
이 때 키워드, 공백, 식별자 등의 유형을 토큰 타입이라고 하며,
mins, 60 등의 구체적인 값을 렉심이라고 한다. 하나의 토큰 타입은 주어진 형식 언어의 정의에 따라 0개 이상의 렉심을 가질 수 있는데, 예를 들어 24, 60 등은 서로 다른 렉심이지만 둘다 같은 토큰 타입(상수)에 해당한다.근본적으로 개별 토큰은 토큰 타입과 렉심으로 구성된다.
[math({\rm Token} = ({\rm TokenType},{\rm Lexeme}))]
실제로 렉서를 설계할 때는 최적화 및 에러 보고 등을 위해 소스에서 해당 렉심의 위치를 인덱스(pos)나 인덱스 범위(span) 형태로 기록하기도 하며, evaluation 단계에서 각 렉심에 대응되는 실제 값 정보[12]를 추가하기도 한다.
예를 들어 토큰 타입이
BOOL인 토큰이라면 가능한 렉심 값은 true 또는 false 둘 중 하나가 될 것이다. 이 값이 둘 중 무엇이냐에 따라 코드의 실행 결과가 달라지기에 각 토큰에 어떤 렉심인지 기록해둬야 할 것이다. 반면에 해당 토큰 타입에 해당하는 렉심이 단 하나뿐인 경우는 최적화 등을 위해 렉심 부분을 생략하기도 한다. 즉, 렉심은 빼고 개별 토큰에 토큰 타입 정보만 남기는 것. 주로 키워드, 구분자 등과 같이 고정적인 문자열인 경우에 토큰 타입만 사용한다.이제 위 예시를
(첫 문자 인덱스, 토큰 타입, [렉심])의 형태로 순서대로 나타내면 다음과 같을 것이다.(0, KEYWORD_INT), (3, WS), (4, IDENT, "mins"), (8, WS), (9, OP_EQ), (10, WS), (11, LIT_NUM, "24"), (13, WS), (14, OP_AST), (15, WS), (16, LIT_NUM, "60"), (18, PUNCT_SEMI) |
이와 같이 입력 소스를 개별 토큰들의 배열로 만든 것을 토큰 스트림(token stream)이라고 한다.
3.1. 주요 토큰타입
컴퓨터 언어 및 프로그래밍 언어에서 흔히 쓰이는 토큰타입들의 예시와 체계. 몇몇 토큰타입은 다른 토큰타입의 부분집합으로 서술하는데, 결정적 유한 상태 기계를 만드려면 각 토큰의 토큰타입은 반드시 하나씩일 수밖에 없기 때문에 불필요해 보이지만, 이런 분석은 추후 렉싱이 끝나고 구문 분석, 포맷팅, 신택스 하이라이팅, 린팅 등 다양한 정적 분석 작업에서 유용한 정보로 활용될 수 있다. 이를테면 키워드 토큰만 초록색으로 색칠해 보여주도록 하는 식.- 화이트스페이스 - 대부분 토큰 스트림 후처리 과정에서 제거된다. 때로는 파서로 넘겨져서 CST로 남을 때도 있는 편.
- 주석 - 경우에 따라 주석을 완전히 별도의 토큰 타입으로 빼내기도 한다. doc comment 기능 때문에 CST에서 AST로의 변환 시 주석 정보만은 남겨야 하는 경우 등.
- 공백, 탭
- 개행 - 세미콜론으로 문장이 구분되는 언어라면 상관없지만, 개행으로도 문장이 구분되어야 하는 언어라면 여기서 렉서 설계가 복잡해진다.
- 식별자 - 바인딩과 관련된 대부분의 동작을 담당하는 렉서에서 가장 중요한 타입 중 하나. 주로 키워드 역시 식별자의 부분집합이기 때문에 DFA를 거치면 같은 목적지에 도달하게 된다. 이를 구분해내는 방법은 렉서 제너레이터의 입력으로 제시된 각 패턴 정의의 결정성을 비교하는 것. 물론 Perl과 같이 식별자별로 독특한 규칙이 있어 키워드와 겹치지 않는 사례도 있다.
- 키워드 - 키워드가 식별자와 같은 생성 규칙을 가지는 언어가 많지만, 가끔 그렇지 않거나 예외적인 형태의 키워드가 있는 경우가 있다. 또한 JavaScript처럼 과거엔 식별자로 허용되었으나 최신 버전에선 키워드로 용도가 바뀐 경우, 호환성을 위해 렉서 단에서 둘을 구분하지 않게 설계해야 할 수도 있다.
async키워드를 변수명으로도, 키워드로도 쓸 수 있는 이유. - 이스케이프 식별자 - 식별자와 키워드의 생성 규칙이 겹치는 경우, 예약된 키워드와 같은 식별자를 쓰는 것은 피하되 직렬화 등 어쩔 수 없는 요인에 의해 런타임 환경에서만은 키워드와 겹치는 식별자를 사용해야 하는 경우, 언어별로 지원하는 식별자 우회 방법. C#의
@if, Rust의r#true, Kotlin이나 Swift의`class`등이 예시. - 리터럴
- Null -
null,None,nil등. - 불리언 -
true/True,false/False등. - 숫자
- 정수 - 많은 언어에서 편의성을 위해 십진법이 아닌 숫자 리터럴을 지원하는데,
0xf3(16진법),075(8진법),0b1101(2진법) 등이 있다._등의 구분자로 긴 숫자 입력을 편하게 해주는 언어도 있다. - 음수 - 주로 음수가
-(빼기 연산자)와 숫자 토큰으로 구분되는지, 아예 렉서 단위에서 처리하는지가 갈린다. 어떻게 구현하느냐에 따라 Haskell처럼1+-1이0인지 연산자 우선순위 오류가 나는지가 갈릴 수 있다. - 부동소수점 - 소수점이 들어간 숫자 뿐만 아니라
1e-5등과 같은 표기법을 허용하는 언어들도 많기 때문에 복잡하다. 특히 소수점 처리를 숫자 +.연산자(속성 참조 연산자)로 따로따로 렉싱하지 않도록 주의해야 하는 편. - 문자열 -
""또는''로 감싸인 문자열. 대부분의 경우 문자열은 엔터 기호를 포함하지 않고, 따라서 여러 줄을 가로지르는 문자열을 한 토큰으로 인식하려면 후술할 여러 줄 문자열 토큰을 별도로 정의한다. - 연산자
- 대수 연산자 -
+,-,*[13],/,%,^[비트부정][거듭제곱],**[거듭제곱] - 논리 연산자 -
!,&&,|| - 비교 연산자 -
==,===,!=,<,<=,>,>= - 복합 할당 연산자 -
=,+=,-=,*=,/= - 비트 연산자 -
^[비트부정],&,|,<<,<<<,>> - 구분자
- 괄호 -
(),{},[],<>(템플릿, 제네릭) - 기타 -
;,:,.등 - EOF - 이 토큰이 나오면 토큰 스트림이 끝난다. 물론 렉서에 따라 구현하지 않는 경우도 있다.
- 에러 토큰 - 어떤 생성문법 패턴에도 일치하지 않는 토큰. 즉시 에러를 뱉고 렉싱을 중단하는 방법도 있지만 incremental parsing 등의 특수한 상황에서는 실시간 편집으로 인해 발생한 몇몇 에러는 무시하고 진행해야 할 필요가 있다.
- 기타
- 전처리기 토큰 - C, C++ 등의 언어에만 존재.
- 정규표현식 토큰 - Perl, JavaScript 등의 언어에만 존재.
4. 종류
4.1. 정규 렉서
정규 문법을 통해 기술할 수 있는 토큰들만 허용하는 렉서. 후술할 문맥 자유 렉서에 비해 제한적이고, 시간 복잡도는 [math(\mathcal O(n))]으로 매우 빠르다. 특히 대부분의 렉서 제너레이터가 정규 렉서를 지원하므로 제너레이터의 최적화를 사용하면 손으로 짠 거의 대부분의 렉서보다 성능이 좋게 나온다. 따라서 렉서 단에서 뭔가 복잡한 로직이 필요하거나 복잡한 문법 때문에 어쩔 수 없이 문맥 자유 렉서를 짜야 하는 경우가 아니라면 대부분의 프로그래밍 언어는 정규 렉서를 사용한다.4.1.1. 정규 문법의 NFA 변환
흔히 렉서 제너레이터를 사용할 때 정규 표현식을 사용하지만, 엄밀히 말해 정규 표현식은 정규 언어의 확장(superset)으로, 백트래킹 등의 구현이 들어가면 당연히 [math(\mathcal O(n))] 시간 안에 결정가능하지 않다. 정규 렉서가 인식할 수 있는 언어는 정규 언어(regular language)로, 형식 언어의 일종이다. 이런 형식 언어를 형식 문법(formal grammar)으로 나타냈을 때 아래의 형태를 가지는 것을 정규 문법(regular grammar)이라고 하고, 이는 정규 언어를 유도(derive)함이 증명되어 있다.[math(\begin{array}lA\to t\;|\;\epsilon\\A\to tB\;\;{\rm or}\;\;Bt\end{array}\quad t\in\Sigma\;A,B\in V_{NT})]
이때 [math(A\to tB)] 형태의 문법을 우정규(right-regular) 문법, 우선형(right-linear) 문법이라 하고 [math(A\to Bt)] 형태의 문법을 좌정규(left-regular), 좌선형(left-linear) 문법이라고 한다. 모든 좌선형 문법은 우선형 문법과 동치 관계에 있음이 증명되어 있으므로 이후로는 우선형 문법을 기준으로 서술한다.
이를 실제로 나열해 보면 굉장히 긴 생성 규칙의 집합이 되는데, 이를 행렬(구현에서는 점프 테이블)로 나타내면 좋을 것이다. 다음과 같은 전이 함수를 갖는 비결정적 유한 상태 기계(NFA)를 생각해 보자.
[math({\rm NFA_G}=(Q,\Sigma,\delta,q_0\in Q,F)\quad\delta:Q\times(\Sigma\cup\{\epsilon\})\mapsto\mathcal P(Q))]
상태 집합 [math(Q)]가 반드시 논터미널 기호 집합인 [math(V_{NT})]와 같을 것 같지만 꼭 그렇지는 않다. 터미널 기호나 공문자열로 끝나는 생성 규칙의 경우 별도의 추가 상태를 정의해야 하기 때문. 일반적으로 다음 규칙에 따라 정규 문법을 NFA로 변환할 수 있다.
- [math(q_0=S)]로 한다. 즉, 시작 기호가 곧 시작(entry) 상태가 된다.
- [math(Q)]에 [math(V_{NT})]를 전부 넣는다. 즉, 모든 논터미널 기호를 별도의 상태로 만든다.
- [math(F)]는 공집합으로 둔다.
- [math(\forall p\in P_G)]에 대해
- [math(p:A\to tB)] 꼴이라면, [math(A)]에서 [math(t)]를 만났을 시 [math(B)]로 가는 전이를 추가한다. 다시 말해, [math(B\in\delta(A,t))]가 되도록 한다.
- [math(p:A\to t)] 꼴이라면, 새 상태 [math(A')]을 [math(Q)]와 [math(F)]에 추가하고 [math(A'\in\delta(A,t))]가 되도록 한다.
- [math(p:A\to\epsilon)] 꼴이라면, [math(A)]를 [math(F)]에 추가한다.
이렇게 구해진 NFA는 주어진 정규 문법과 정확히 대응한다. 유한 길이의 문자열을 시작부터 읽어들였을 때, 최종 상태 [math(q_f)]가 [math(F)]의 원소라면 허용되는 토큰, 그렇지 않고 다른 상태라면 오류 토큰인 것.
4.2. 문맥 자유 렉서
5. 렉서 제너레이터
렉서를 손으로 작성하는 경우도 있지만, 대부분의 경우는 렉서 코드를 생성하는 렉서 제너레이터를 사용한다. 사용 이유는 파서 제너레이터와 비슷한데, 렉서를 손으로 작성하는 것에 비해 개발 시간이 현저히 빠르고, 그만큼 언어 스펙 수정에 대응하기도 편하며, 대부분의 경우 모든 path에 대한 경우를 컴파일 타임에 체크하므로 에러가 없고 무결하며, 무엇보다 손으로 작성된 대부분의 렉서보다 최적화가 쉬워 성능이 훨씬 빠르기 때문이다.5.1. 목록
- lex: UNIX 생태계에서 YACC, bison과 함께 가장 성공적인 렉서 제너레이터 중 하나. 무려 1975년부터 당시 벨 연구소에 재직 중이던 마이크 레스크(Mike Lesk)와 에릭 슈미트(Eric Schmidt)에 의해 개발되기 시작했다. 정규 패턴과 수행할 코드를 정의한
.l파일을 입력하면 역시 벨 연구소의 발명품 중 하나인 C 언어로 렉서 코드를 출력하는, 당시로써는 획기적인 방식. # 이후 벨 연구소의 최대 발명품 중 하나인 UNIX에 탑재되어 사실상 표준처럼 쓰이기 시작했다. 이때의 유닉스 툴들이 대개 그렇듯이 원래는 상업용 제품이었으나 많은 오픈소스 버전들이 등장하기 시작했고, 그 중 현재 lex를 대체하고 있는 오픈소스 버전이 후술할 flex다. - flex: 상술한 lex의 오픈소스 버전으로, 레거시 lex의 상업 라이선스가 걸려 있던 소스에 기반하지 않고 처음부터 제작된 버전이다. 현재 대부분의 리눅스 배포판에는 flex가 쓰이고 있다.
- re2c: 폴리글랏 렉서 제너레이터.
- logos: 프로시저 매크로 형태의 Rust용 렉서 제너레이터.