[PL] Syntax Analysis : Lexical error와 Syntax error의 차이 & 정규표현식의 한계

✔️ 컴파일러의 Front-end

컴파일러의 Front-end는 Lexical Analysis, Syntax Analysis이다.

Front-end의 목적은 프로그램을 AST(컴파일러가 Backend 단계에서 다루기 좋은 구조)로 바꾸는 것이다.

Lexical Analysis에서 lexer에게 'regular expression'을 사용해 토큰을 만들어내도록 했던 것처럼, syntax analysis에서도 parser에게 명료한 syntax를 정의해줄 필요가 있다.

그렇다면 syntax analyzer에게 어떻게 올바른 syntax를 전달할 수 있을까?!

1. Lexical Error & Syntax Error

📌 Lexical Error

lexical error은 문자열이 토큰의 패턴에 맞지 않으면 발생한다.

int main() {
	int 3num = 1234; // c에서 변수이름은 digit으로 시작할 수 없는데 3으로 시작하므로, lexical error
    return 0;
}

int main() {
/* comment 			// 주석이 /\* 로 시작하지만 \*/로 끝나지 않으므로, 주석 패턴에 맞지 않아서 lexical error 발생
	cout << 'GFG!';
    return 0;
}

➡️ 예시

INT_KEYWORD = int
ID = [a-z]
ASSIGNMENT = '='
NUM = [0-9]

int a = 9
double a = 1
이 경우엔 lexical error X

INT_KEYWORD = int
ID = [a]
ASSIGNMENT = '='
NUM = [0-9]

int a = 9
double a = 1
이 경우엔 Lexer가 'double'을 알지 못함 => lexical error 발생 !

📌 Syntax Error

PROGRAM = STATEMENT/*
C, 자바 등 program은 zero or more statement이다.

STATEMENT = EXPRESSION | IF_STMT | WHILE_STMT | ...
Statement는 expression, if문, while문 등으로 구성된다.

OP = + | - | /

EXPRESSSION = (NUM | ID | DECIMAL) OP (NUM | ID | DECIMAL)

✔️ 5 + 10 Valid
✔️ 1 + 2 + 3 Valid
✔️ foo - bar

• Lexer 관점에서 항상 valid 하다. EXPRESSION = ID OP ID 이기 때문이다.
• 반면 Parser관점에선 상황에 따라 다르다.
• 만약 foo, bar이 integer type이라면 valid하다. 만약 아니라면 invalid하다.

➡️ 예시

NUM = RE~
DOT = RE~
ID = RE, '(', ')'~
PLUS = RE~

ID DOT ID

obj.var;
obj.foo();

Lexical Analysis 에서는 ID DOT ID 패턴을 갖추었기 때문에 옳다. 그렇지만 자바에서, 해당 내용은 Syntax Analysis에서 옳을까?
상황에 따라서 옳을 수도 있고, 아닐 수도 있다.
obj가 위에 먼저 정의되어 있고 var 변수가 obj 안에 있다면 valid하지만 그렇지 않다면 옳지 않다.
이러한 것을 Syntaxl analyzer가 점검한다.

import xxx;
obj.var;
obj.foo;
int main() {
..
}
이 코드라면, lexer는 obj.var;을 ID DOT ID 토큰으로 생성하고 complain 하지 않겠지만 Syntax analyzer는 complain하고 error을 발생시킨다.

2. 정규 표현식의 한계

정규 표현식은 (), (()), ((())) 등 matching parenthesis를 표현하지 못한다.

▪️ 예시
Program = statement*
statement = NUM PLUS NUM;
2+2, 1+1, 5+5;
(5+5) 는 어떻게 표현할 수 있을까?
LP.RP = ()
((5)+5) 와 같은 (())은 어떻게 Regular Expression으로 표현할 수 있을까?
(LP.RP)+ = ()()()() != (()) => 즉 불가능하다!

정규 표현식은 모든 프로그래밍의 syntax를 파악하는 데 표현력의 한계가 있다. 따라서 우리는 Context Free Grammer을 이용한다.

📌 정리

Lexical Analysis : Regular Expression을 사용하여 source code => Tokens

Syntax Anlaysis : Context Free Grammer을 사용하여 Tokens => AST