[Compiler] 1. Lexical Analyzer :: 소개와 용어 정리
Compiler의 첫 번째 단계는 Lexical Analysis로 가장 먼저 Lexical Analyzer를 실행합니다.
Lexical Analyzer는 어떤 일을 할까요?
Lexical Analyzer는 Input 문자열들을 스캔하면서 의미가 있는 단위로 문자열을 묶습니다. (그래서 Scanner라고도 불립니다). 그리고 일련의 Token들을 생성해 내고 Syntax Analyzer에게 보냅니다. 이 과정을 진행하면서 Token들에 대한 정보들을 Symbol Table에 저장합니다.
Lexical Analyzer의 동작 방식을 알아보기 전에 앞으로 쓸 용어들에 대해 알아봅시다.
Lexical Analyzer에서 쓰는 용어들: Token, Lexeme, Pattern
Token
A token is a pair consisting of a token name and an optional attribute value. The token name is an abstract symbol representing a kind of lexical unit, e.g., a particular keyword, or sequence of input characters denoting an identifier. The token names are the input symbols that the parser processes.
▶ Token은 token name, token value의 쌍입니다. (token value는 생략해도 됩니다).
> token name은 특정한 어휘를 대표하는 symbol입니다.
> token name 예
- sum, num, i, j, k,... 같은 (Keyword가 아닌) 일련의 문자들을 대표하는 token name은 IDENTIFIER,
- 1, 2, 3, 2.7, ... 같은 숫자들을 대표하는 token name은 NUMBER,
- *, /, +, -, %와 같은 산술 연산자들을 대표하는 token name은 ARITHMETIC OPERATOR,
- =과 같은 대입 연산자를 대표하는 token name은 ASSIGN이라고 할 수 있습니다.
> token value는 token name의 속성 값입니다.
> token value 예
- sum, num, i, j, k과 같은 것들이 IDENTIFIER의 token value,
- 1, 2, 3, 2.7과 같은 것들이 NUMBER의 token value,
- *, /, +, -, % 와 같은 것들이 ARITHMETIC OPERATOR의 token value라고 할 수 있습니다.
- token value가 ASSIGN인 경우는 '='인 것이 자명하므로 token value는 생략할 수 있겠죠?
▶ Token은 token name과 token value의 쌍이라고 했습니다.
이와 같은 쌍을 표현하기 위해 앞으로 Token은 <token name, token value>의 형태로 나타내겠습니다.
물론 token value는 생략할 수도 있으므로 Token이 <token name>의 형태일 수도 있겠죠!
▶ Token 예
<IDENTIFIER, sum>
<IDENTIFIER, num>
<IDENTIFIER, i>
<IDENTIFIER, j>
<IDENTIFIER, k>
<NUMBER, 1>
<NUMBER, 2>
<NUMBER, 2.7>
<ARITHMETIC OPERATOR, *>
<ARITHMETIC OPERATOR, />
<ARITHMETIC OPERATOR, +>
<ARITHMETIC OPERATOR, ->
<ARITHMETIC OPERATOR, %>
<ASSIGN>
Lexeme
A lexeme is a sequence of characters in the source program that matches the pattern for a token and is identified by the lexical analyzer as an instance of that token.
▶ Lexeme은 Input Stream(소스 코드)의 문자들 중에서 Token의 Pattern을 만족하는 일련의 문자들 입니다!
> 여기서 Pattern은 Token을 정의하기 위한 rule들의 집합이라고 이해하시면 됩니다.
▶ Lexeme 예
| Token Name | Lexeme |
| IDENTIFIER | a, b, c, d, num, sum, ... |
| NUMBER | -2, -1, 0, 1, 2, 3, 4, 1000, 2.7, 6.02e23, ... |
| IF | if |
| COMMA | , |
| LBRACE | { |
| RBRACE | } |
| LPAREN | ( |
| RPAREN | ) |
| LITERAL | "I am groot" |
| COMPARISON | <, >, <=, >=, ==, != |
| ARITHMETIC OPERATOR | *, /, +, -, % |
Pattern
A pattern is a description of the form that the lexemes of a token may take. In the case of a keyword as a token, the pattern is just the sequence of characters that form the keyword. For identifiers and some other tokens, the pattern is more complex structure that is matched by many strings.
▶ Pattern은 Token이 Lexeme으로 어떤 형태가 될 수 있는지에 대한 설명입니다.
음.. 말이 조금 이상한데 Pattern은 Token이 소스 코드에서 어떻게 생겼는지에 대한 설명이라고 보시면 됩니다.
예를 들어서, Token인 IF의 Pattern은 "첫 번째 문자로 i, 두 번째 문자로 f인 문자열"이라고 할 수 있겠습니다.
▶ Pattern 예
| Token Name | Pattern |
| IF | 문자 i, 문자 f 순서인 문자열 |
| COMMA | 문자 , |
| LBRACE | 문자 { |
| ARITHMETIC OPERATOR | 문자 *, 또는 문자 /, 또는 문자 +, 또는 문자 -, 또는 문자 % |
다양한 Token들 알아보기!
- Keywords: IF(if), ELSE(else), FLOAT(float), CHAR(char)
- Operators: ADD(+), COMPARISON(<,>,...)
- Identifiers: ID(모든 종류의 식별자)
- Constants: NUMBER(모든 숫자 형태의 상수: 정수, 실수, 리터럴)
- Punctuation Symbols: LBRACE({), COMMA(,)
- Whitespace: 띄어쓰기, 새 줄 문자(\n), 탭들의 비어 있지 않은 열거.
※ Lexical Analyzer는 parsing 하는데 필요 없는 것들은 버립니다. (예) whitespace, comment
출처
- Lexeme, Token, Pattern의 정의는 다음의 책에서 인용했습니다.
Compilers Principles, Techniques, & Tools, 2nd Ed. by Aho, Lam, Sethi and Ullman, Page 111 - Icons made by Smashicons from www.flaticon.com