1960년대 이후, 모든 프로그래밍 언어의 syntax는 formal grammar에 의해 지정됐다. BNF(Backus-Naur Form or Backus-Normal Form)은 ALGOL 60의 syntax를 표현했다.
program ::= statement | program statement
statement ::= assignStmt | ifStmt
assignStmt ::= id = expr;
ifStmt ::= if ( expr ) stmt
expr ::= id | int | expr + expr
id ::= a | b | c | i | j | k | n | x | y | z
int ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Productions
문법의 규칙을 production이라고 한다.
여기에 nonterminal symbol과 terminal symbol이 있다.
Nonterminal symbol이란 문법적으로 변할 수 있는 요소로 위에서 program, statement, id 등을 예로 들 수 있다.
terminal symbol은 프로그램에서 고정된 syntax를 의미한다. a, b, c나 0, 1 혹은 if와 같은 것들을 예로 들 수 있다.
대부분의 production 형태는 nonterminal symbol을 terminal symbol나열과 nonterminal symbol(없을 수도 있다.)로 바꾼다.
::= 대신 ->를 사용할 수 있다.
Lexical analyzer의 역할
parsing
프로그램의 derivation(syntatic structur)을 재구성하는 것. 컴파일러 중 parser는 토큰 스트림을 읽어 drivation을 재구성한다.
lexing
코드 스트림을 토큰 스트림으로 바꾸는 것. 컴파일러 중 lexical analyzer (scanner)는 문자를 토큰으로 바꾸는 역할을 한다. 또한 잘못된 문자나 심볼 에러를 보고하는 역할을 한다.
그 외에 다른 기능 역시 한다.
- white space와 comment를 삭제해준다.
- reading ahead
- symbol table 관리
- 상수 관리
왜 lexer와 parser로 나눴지?
- 설계의 단순성
- 컴파일러 효율성 up
- parser보다 lexical analysis가 간단함 (심지어 자동화 구현)
- 컴파일러 portability (유지 보수성)
- 언어에 따른 각기 다른 토큰
Token
BNF에서 나타낼 수 있는 최소 단위. lexical token은 의미를 가진 최소한의 단위로 더 이상 쪼개질 수 없는 문자열이다. token name과 optional token value로 이루어져 있다. 예를 들어 정수 512가 들어가면 <INT, 512>로 토큰이 만들어진다.
if (x <= y) x = 512;
input text가 위와 같을 때 token stream으로 변환하면 아래와 같다.
IF
LPAREN
ID, x
LEQ
ID, y
RPAREN
ID, x
BECOMES
INT, 512
SCOLON
Token, lexeme and pattern
