![[5. Lexer (1).pdf]] # Part 1: Lexer Overview ## Lexer는 컴파일러의 어떤 부분에 위치하는가? ### 복습: 3단계 구조 - Middle-end가 추가 - IR Program → IR Program - 성능 개선 역할도 겸함 ### 복습: Front-End: 입력 언어를 이해하는 과정 - Front-end의 구조: 입력 언어로 작성된 소스 코드를 - 이해 / 검사 / 변환 - Lexer: 어휘 분석기 - Parser: 구문 분석기 - Symantic Analyzer: 의미 분석기 - IR Translator: 변환 ### 복습: 어휘 분석기 (Lexical Analyzer = Lexer) - 그냥 말 그대로... Lexical 단어의... - 문자열 → Token의 나열로 변환 - 공백, 주석 제거 - `var lexer: string -> Token list` - 그럼 여기서 토큰이란 무엇인가? ### Token == 문법적으로 의미를 갖는 최소 단위 문자열 - `type Token = string` - if → i, f / == → =, = ### Token의 분류 | 종류 | 설명 | 예시 | | --------- | ------------------------- | ----- | | ID | 함수, 변수, 타입 등의 **이름** | a, b | | NUM | 정수 값의 표현 | 0 | | PAREN | 열고 닫는 괄호 | (, ) | | IF | if문 키워드 | if | | OP | 비교, 대입 등 **연산자** operator | ==, = | | SEMICOLON | Statement의 마지막 표시 | ; | | 등등등... | | | ### Token의 재정의 ```f# type Token = | ID of string | NUM of string | PAREN of string | IF of string | OP of string | SEMICOLON of string // | .... let tokens = [ IF "if"; PAREN "("; ID "b"; OP "=="; NUM "0"; PAREN ")"; ID "a"; OP "="; SEMICOLON ";"] ``` 여기서 Token의 실제 값 == Lexeme(어휘소)로 생각하면? ```f# type Lexeme = string type Token = | ID of Lexeme | NUM of Lexeme | LPAREN | RPAREN | IF | EQ | ASSIGN | SEMI // | .... let tokens = [ IF; LPAREN; ID "b"; EQ; NUM "0"; RPAREN; ID "a"; ASSIGN; ID "b"; SEMI ] ``` 위 예시와 달라진 점 - Lexeme = 실제 문자열 값 - LPAREN, RPAREN, IF... 등은 값이 고정이라 따로 저장할 필요가 없어서 그냥 저렇게 된 거 - 왜냐?? 첫 번째 방식은 뭐 어차피 고정인데 따로 저장하니까 불필요한 메모리 + 비교 비용 증가 가능성이 있을 듯. - 그래서 tokens에서도 문자열이 아니라 **타입 자체로 표현됨** ### 주석이나 공백? - 문법적으로 의미가 있다면 token에 포함 (Python `INDENT`, `DEDENT`) - 그러나 일반적으로는 제외 ### 왜 Lexical Analysis를 할까? - 다음 단계(Parser)에서 더 간결한 입력을 받아들이기 위해 - char list보다는 token list가 나으니까! - 어휘 분석(Lexical Analysis)가 구문 분석(Parsing)보다 더 쉬운 문제 - Regular (Lexer) ⊂ Context-Free (Parser) ⊂ Context-Sensitive ⊂ Recursively Enumerable ```mermaid graph TD RE[Recursively Enumerable - 뭘까... 질문좀...] CS[Context-Sensitive - ?] CF[Context-Free - Parser] R[Regular - Lexer] RE --> CS CS --> CF CF --> R ``` ### 예제: Lexer Test Case 1 ```python # 입력 if (b == 0) a = b; ``` ```f# // 출력 [IF; LPAREN; ID "b"; EQ; NUM "0"; RPAREN; ID "a"; ASSIGN; ID "b"; SEMI] ``` ### 예제: Lexer Test Case 2 ```python # 입력 if (b == 1x23) a = b; ``` ```f# // 출력 Error occurred at line: 1, Col: 10! ``` - Col은 그냥 10번째 문자 위치임. - 숫자 1까지 갔는데 뒤에 x가 있어서 정의 안 됨 → 이런 **어휘 오류는 무조건 Lexer에서** 잡아야 함 ### 예제: Lexer Test Case 3 ```python # 입력 of (b == 0) a = b; ``` ```f# // 출력 [ID "of"; LPAREN; ID "b"; EQ; NUM "0"; RPAREN; ID "a"; ASSIGN; ID "b"; SEMI] ``` - if를 of로 쓰는 '문법 오류'가 있지만, Lexer는 잡지 않음 - **문법 오류는 무조건 Parser에서!** ### Lexer와 Token의 재정의 ```f# type Lexeme = string type Info = { FilePath: String; Line: int; Col: int } // 구조체 type Token = | ID of Lexeme * Info // 예: ID("a", 위치) // of: "이 타입은 값을 하나 더 들고 있다" // 걍 클래스에 있는 필드 추가한다는 거로 생각하면 될듯... // class LPAREN implements Token { // Info info; // } | NUM of Lexeme * Info | LPAREN of Info | RPAREN of Info | EQ of Info | ASSIGN of Info // |... module FrontEnd = var lexer: string -> Result<Token list, Info> // 자바로 따지면 걍 제네릭 // Result<A, B> = 성공이면 A, 실패면 B // Either<List<Token>, Info> ``` ### Part 1 정리 - Lexer: 문자열을 Token의 나열로 분해하는 과정 - Token: 문법적으로 의미를 갖는 최소 단위 문자열 - Lexical Analysis는 Parsing을 보다 수월하게 하도록 도와줌 → 그럼 Lexer를 어떻게 구현해야 할까? # Part 2: Regular Expression (regex) ## 어떻게 Lexer를 구현할까? ### 예: C23의 Integer [[constant]] > An integer constant **begins with a digit**, but has **no period or exponent part**. > It may have > 1. **a prefix that specifies its base** and > 2. **a suffix that specifies its type**. > An optional separating single quote character (‘) in an integer or floating constant is called **a digit separator**. Digit separators are ignored when determining the value of the constant. - 정수는 숫자로 시작 - 근데 소수점이나 지수 $e$는 없음 - 앞에 진수 표기(0x15, 0b101 이런 거)는 됨 - 뒤에 타입 표기(123U, 123L, 123UL 이런 거)는 됨 - 숫자 사이에 `'` 넣을 수 있음 = [[digit seperator]] - 당연히 값 계산할 때는 무시 ### Ad-hoc Lexer (아까 그 C23 Integer constant 처리하는 Lexer) - Left-to-Right: 왼쪽부터 읽는다는 소리임 - Lookahead 필요: 뒤 내용 봐야 한다는 소리임 - 다시 시작할 수도 있음: invalid하면 다시 해석 ```python def get_int_token(s, pos): start = pos # [1] 토큰 시작 위치 저장 # Check prefix if s[pos] == '0' and s[pos+1] in 'xX': pos += 2 chars = hex_chars # [2] 16진수 시작 (0x...) elif s[pos] == '0' and s[pos+1] in 'bB': pos += 2 chars = bin_chars # [3] 2진수 시작 (0b...) else: chars = dec_chars # [4] 기본은 10진수 # Read chars while s[pos] in chars or s[pos] == '\'': pos += 1 # [5] 숫자 계속 읽기 (digit separator 포함) # 나중에 끝 위치가 pos가 됨 # Check floats if s[pos] in '.eE': return Invalid(start) # [6] float, e면 int 아님 → rollback # Check suffix while s[pos] in 'uUlL': pos += 1 # [7] suffix (unsigned, long 등) # Return return Token(INT, s[start:pos]) # [8] 최종 토큰 생성 ``` ### Ad-hoc Lexer의 문제점 1. 복잡한 구현 1. 한 종류 token 분석하는데 이미 분기가 많음 2. 비효율 1. invalid한 순간 바로 처음으로 돌아가야 하니까... ### Lexer Design 요구사항 1. Token의 명확한 정의 2. 문자열의 Token 구분 3. 효율적으로 Token 분리 1. 각 문자열을 $O(1)$번 만큼 보는 게 목표 ## Token을 어떻게 정의할까? ### 복습: NUM Token - `NUM of Lexeme * Info` - NUM의 lexeme은 문자열 but 모든 문자열이 NUM의 lexeme은 X **→ Token 문자열을 어떻게 1) 정의하고 2) 표현해야 할까?** ### 언어 정의 방법 - Language: 특정 규칙을 만족하는 문자열의 집합 - Alphabet: 언어를 구성하는 글자들의 집합 - {0, 1}: 이진수를 만들 수 있는 alphabet - Grammar: 언어를 이루고 있는 규칙들의 집합 - 좌변 → 우변: 좌변을 우변으로 유도 - <두 글자 이상 이진수> → 1 <한 글자 이상 이진수> - 두 글자 이상인 경우 제일 앞자리에는 1만 - <이진수 문자열> → <이진수 문자열> 0 / <이진수 문자열> 1 - 문자열 뒤에 0 or 1 ### 언어 문법의 형식적 정의 문법은 4-tuple $(T, NT, S, P)$로 정의 - $T$ = terminal들의 집합 (=Alphabet) - 원소들을 소문자로 많이 나타냄 - $\epsilon \in T$ (empty string, 길이가 0인 특수한 문자) - 예 {0, 1} - $NT$ = Non-terminal들의 집합 - 아직 완성 안 된 중간 상태 - 원소들을 대문자로 많이 나타냄 - 예시: {< 이진수 문자열 >, ...} - $S$ = 문자열 생성 시작을 나타내는 특별한 기호 $(S \in NT)$ - $P$ = 문법 생성 규칙들의 집합 - 바로 위 예시들 ### 예시: C23의 Integer Constant Grammar ```f# <integer_constant> ::= <hex_constant> // Non-terminal(아직 완성 안 된 개념) 정의 | <bin_constant> | <dec_constant> | ... // 정수 = 16진수 or 2진수 or 10진수 <dec_constant> ::= <dec_constant_nosuffix> | <dec_constant_nosuffix> <int_suffix> | ... // 10진수 = 숫자 or 숫자 + suffix <int_suffix> ::= uL | ... // type 정보 suffix <dec_constant_nosuffix> ::= 1 <digit> | 2 <digit> | ... // 숫자는 1~9로 시작하고 뒤에 digit 붙는다 <digit> ::= 0 | 1 | 2 | ... // 그냥 숫자 정의 ``` - $T$ = terminal들의 집합 (=Alphabet) - 0,1,2,...,x,b,u,l 등 실제 문자 - $NT$ = Non-terminal들의 집합 - <integer_constant>, <dec_constant> 같은 거 - $S$ = 문자열 생성 시작을 나타내는 특별한 기호 $(S \in NT)$ - $P$ = 문법 생성 규칙들의 집합 - ::= 같은 거? → 이거 질문하자 ### Regular Language - 컴퓨터가 인식할 수 있는 **가장 단순한 종류의 언어** - Token이 반드시 RL? ㄴㄴ 근데 RL이면 좋음 ### Regular Grammar의 정의 Regular Grammar $(T, NT, S, P)$는 다음 두 가지 성질 중 하나를 만족하는 문법 1. Left-regular grammar (left-linear grammar) 1. $P$의 모든 규칙은 다음의 3가지 형태 중 하나 1. $A \to \epsilon$ 1. NT에서 입력 없이 끝낼 수 있음 2. $A \to a$ 1. NT에서 a 하나 읽고 끝낼 수 있음 3. $A \to Ba$ 1. NT A에서 a를 읽고 NT B로 감 (오른쪽에서 왼쪽으로? 읽는 느낌? 이것도 질문드려야겠다...) 2. Right-regular grammar (right-linear grammar) 1. $P$의 모든 규칙은 다음의 3가지 형태 중 하나 1. $A \to \epsilon$ 1. NT에서 입력 없이 끝낼 수 있음 2. $A \to a$ 1. NT에서 a 하나 읽고 끝낼 수 있음 3. $A \to aB$ 1. NT A에서 a를 읽고 NT B로 감 (왼쪽에서 오른쪽으로? 읽는 느낌?) ### 예시: C23의 Integer Constant Regular Grammar ```f# <integer_constant> ::= 1 <dec_constant> | 2 <dec_constant> | ... <dec_constant> ::= 0 <dec_constant> | 1 <dec_constant> | ... | 9 <dec_constant> | epsilon | u <unsigned_suffix> | ... ``` 너무 복잡함 → 문자열의 패턴을 나타내는 다른 방법이 없을까? ## Regular Expression (RE) - 문자열의 패턴을 나타내는 방법 - Regular grammar보다 사람이 이해하기 훨씬 쉬움 - $L(RE) =$ RE가 받아들이는 문자열의 집합 (= 언어) - RE는 **귀납적으로 정의**됨 → 차근차근 따라가기! ### RE의 정의 - Base Case - $\epsilon$: 길이가 0인 문자열 패턴 - $L(\epsilon) =$ {""} - $a$: 어떤 alphabet 'a'에 대해 'a' 한 글자만 가지고 있는 문자열 패턴 - $L(a) =$ {"a"} ### RE의 정의 - Inductive Case (Concatenation) - $R \cdot S$ : 두 RE $R$, $S$에 대해 $L(R)$과 $L(S)$의 문자열이 연결된 패턴 - $L(R \cdot S) = \{r \cdot s | r \in L(R), s \in L(S)\} (\therefore 문자열\ 연결)$ - $\cdot$ 을 생략하기도 함 - 예: $L(ab) =$ {"ab"} ### RE의 정의 - Inductive Case (Alternation) - $R | S$: 두 RE $R$, $S$에 대해, $L(R)$, $L(S)$ 둘 중 하나에 속하는 문자열 패턴 - $L(R|S) = L(R) \cup L(S)$ - 예: $L(a|b) =$ {"a", "b"} ### RE의 정의 - Inductive Case (Kleene Star) - $R^\ast$ : RE $R$에 대해, $L(R)$에 속하는 문자열의 0회 이상 반복 패턴 - $L(R^\ast) = L(\epsilon) \cup L(R) \cup L(R^2) \cup \cdots$ ($R^n$ : $R$을 $n$회 concatenate) - 예: $L(a^\ast) =$ {"", "a", "aa", "aaa", ...} ### RE의 정의 - Inductive Case (Group) - $(R)$: RE $R$에 대해, $L(R)$에 해당되는 문자열 패턴 - $L((R)) = L(R)$ - 예: $L((a)) =$ {"a"} ## RE 각 Case 간의 우선 순위 - $* > \cdot > |$ - ab|cd* 는 (ab)|(c(d*)) ### RE 예제 - $(0|1)^\ast0$ - 그럼 $0|1$ 먼저니까 {"0", "1"} - {"0", "1"}의 0회 이상 반복 패턴이니까 { "", "0", "1", "00", "01", "10", "11", "000", ... } - {"", "0", "1", "00", "01"...}에 0 concat하니까 { "0", "00", "10", "000", "010", "100", "110", ... } - 모든 이진 문자열 중 마지막 문자가 0인 문자열들의 집합 - Alphabet = {"a", "b"}, a가 짝수 번 등장하는 RE? - 즉, a 개수만 중요하고 b 개수는 상관없음 - a를 짝수 번 등장하도록 하려면? a를 항상 “쌍으로” 묶으면 되고, b는 상관없음 - $(b^*)a(b^*)a(b^*)$ 이게 "a 두 개" 만드는 한 덩어리 → 그럼 얘를 반복하면 됨 - 즉, $((b^*)a(b^*)a(b^*))^*$ → 맞는지 질문 ### RE의 Syntactic Sugar - Syntactic Sugar: 기능을 추가하진 않지만, 편의를 위해 도입된 문법 - $R^+$: RE $R$에 대해, $L(R)$에 속하는 문자열의 1회 이상 반복 패턴 - 기본적인 RE로 어떻게 표현할까요? $RR^\ast$ - $R?$ : RE $R$에 대해, $L(R)$에 속하는 문자열의 선택적 존재 패턴 - 기본적인 RE로 어떻게 표현할까요? $\epsilon | R$ - $[0 - 9]: L([0 - 9]) = \{0, 1, ..., 9\}$ ### Regular Grammar = Regular Expression - Regular grammar로 표현된 언어는 그에 해당하는 Regular expression이 있고, - Regular expression에 대해 이를 표현하는 Regular grammar가 있음. → 당연하다 ### 예시: C23의 Integer Constant Regular Expression $(0|([1-9]('?[0-9])^*))(u|U)?(ll|LL|l|L)?$ - 아까 나왔던 integer constant 처리하는 것 - 0 아니면 - ({0, 1, 2 ... 9} concat ((digit seperator의 선택적 존재 concat {0, 1, 2 ... 9})의 0회 이상 반복 패턴)) concat (u 아니면 U의 선택적 존재) concat (ll, LL, l, L의 선택적 존재) ### Token을 RE로 정의하기 ```f# type Token = | ID of Lexeme * Info // (* alphabet_ + alphanumeric_* *) // alphabet_ concat (alphanumeric_)반복 // ID 토큰: 첫 글자는 alphabet_ (문자 또는 _), // 이후는 alphanumeric_ (문자+숫자+_) 0개 이상 // → 정규식으로 쓰면: [a-zA-Z_][a-zA-Z0-9_]* | NUM of Lexeme * Info (* non-zero numeric + numeric * *) // NUM 토큰: 첫 글자는 0이 아닌 숫자, 이후 숫자 0개 이상 // → 정규식: [1-9][0-9]* | LPAREN of Info // "(" 하나 | IF of Info // "if" 키워드 //|| ... ``` ### 기호, 연산자, 예약어 - "(" - "IF" - "\==" - ... ### ID Token - 첫 글자: alphabet + underscore - $[(a-z)|[A-Z]|\_]$ - $letter = [a-z]|[A-Z]$라고 정의한다면 $(letter|\_)$ - 그 이후: alphanumeric + underscore - $(letter|[0-9]|\_)^*$ - $digit = [0-9]$라고 정의하면 $(letter|\_)(letter|digit|\_)^*$ - ID Token RE: $(letter|\_)(letter|digit|\_)^*$ ## Token을 어떻게 인식할까? ### 문제: Regular Grammar/Expression은 언어를 정의만 함 → 문자열이 언어에 속하는지 어떻게 알까? ### Finite State Machine (FSM) - 각각의 서로 다른 순간을 서로 다른 "상태"로 구분 - 아무것도 안 읽은 상태 - e를 읽은 상태 - el을 읽은 상태 - ... - 각각의 상태는 "문자"를 하나 읽을 때마다 변한 - State Machine: 상태(State)와 상태 사이의 전이(Transition)을 나타내는 장치 - Finite State Machine: 유한한 State를 갖는 State Machine ### FSM의 형식적 정의 5-tuple $(\Sigma, S, s_0, \delta, F)$ - $\Sigma$: Alphabet들의 집합 - $S$: State들의 **유한** 집합 - $s_0$: 시작을 나타내는 특별한 state $(s_0 \in S)$ - $\delta$: state들의 transition을 나타내는 함수 $(\delta: S \times \Sigma \to S)$ - "현재 상태 + 입력 문자 → 다음 상태" - $F$: 마지막 상태들의 집합 - 공집합 가능