Lexical And Syntax Analysis

프로그래밍 언어의 동작 방식

- 컴파일 : C / C++

  수행시간이 빨라야함

 

- 순수 인터프리터 : Python, Javascript in HTML

  작은 프로그램

 

- 하이브리드 ( 컴파일 + 인터프리터 ) : Java

  효율적이지만 컴파일 언어보다는 느림

Syntax analyzer or Parser

CFG, BNF 장점

명확하고, 유지보수가 쉬움

컴파일러의 분석 방법 2가지

Lexical analysis(어휘 분석)

이름, 리터럴과 같은 소규모의 검사로, 컴파일러의 Syntax analysis 앞 쪽에 먼저 수행된다.

일종의 패턴 매칭이라고 보면 되는데

문자들을 모아서 논리적인 단위로 그룹핑을 함 : lexemes

이들을 하나의 token 으로 취급. 이 토큰이 변수인지, expression 인지 뭔지는 나중에 결정되고, 일단 구분함

주석이나 공백들은 적절히 쳐냄

프로그래머가 임의로 정의한 구조체 같은 것들도 적절한 lexeme 으로 취급함

이렇게 구분된 토큰에서 에러가 있는지 확인

 

크게 4가지 방법으로 Lexical analysis 가 이루어집니다.

 

1. Regular expression

2. State transition dialgram ( Deterministic Finite Automata, DFA )

3. if / switch based State diagram ( goto )

4. Table-driven State diagram

 

이 중에서 DFA, State diagram 방식을 가장 많이 쓰는데

 

State diagram

사실 중요하진 않은데 계속 등장하는 단어 DFA 에 대해 간단히 말하자면 FA 라는건 위 그림처럼 언어를 표현하는 방법이에요

Deterministic 의 의미는 A,B,C,D,E 정점들에 대해서 모든 arrow 가 결정적임을 말해요. Arrow 는 연산을 의미하구요!

말이 좀 어려웠는데 쉽게 말해서 이 언어에서는 isAlpha() 연산과 isdigit() 연산이 가능하다고 정의된 언어라서 모든 정점에서 isAlpha(), isdigit() 에 대한 Arrow 가 있어야해요. 반면 없어도 되는 그림을 NFA (Nondeterministic) 이라고하죠.

따라서 제가 위에서 그린 그림이 NFA냐 DFA 냐고 물으면 NFA가 사실 정확한 표현이에요. 왜냐면 C 에서 isAlpha() 일 때의 Arrow 가 없기 때문이죠

정확한 DFA 표현법

이렇게 어떤 경우에는 어떻게 해야한다. (error 로 처리되어야한다 같은) 방식이 정말 명확하게 나와있죠.

NFA 같은 경우에는 없는 arrow 의 경우에는 error 라고 봐요. 그래서 NFA 표현방식을 많이 쓰죠!

 

if-switch (goto) 방식이에요

goto 방식

지금 위에서 표현한 언어들은 변수명 같은 IDENTIFIER 에 숫자가 포함될 수 없는 구조를 갖고 있어요

이를 숫자도 표현될 수 있는 언어로 표현해보고 다음 내용으로 넘어갈게요

 

이런 State diagram 을 수학적으로 Regular language(정규언어) 로 표현 할 수있어요

흔히 알고계시는 정규표현식이 정규언어에요

Syntax analysis(구문 분석)

expression, statement, program unit 단위의 큰 규모의 검사

 

원래는 Lexical analysis 가 Syntax 검사와 하나로 묶여 있었는데 단순성, 효율성, 재사용성을 위해 분리됨

다른 이름으로는 Parsing 이라고도 불려요.

 

구문분석은 프로그램이 문법적으로 틀린 부분이 없는지 검사하기 위해 하는거에요.

 + 파스 트리를 만들어내요

 

파스 트리를 만드는 방법은 크게 두 가지로 나뉘어요

Top-down

Leftmost derivation, Preorder traversal(전위 탐색)

LL Parser

Recursive-descent parser

함수 호출 방식으로 파싱하는 방법으로

void program() {
    char c = getchar();
    program();
    expr();
}

void expr() {
    char c = getchar();
    expr();
    if (c == '+')
    	term();
}

void term() {
    char c = getchar();
    term();
    if (c == '*')
    	factor();
}

void factor() {
    char c = getchar();
    
    if (c == '(')
    	expr();
    else
	    factor();
}

Bottom-up

Rightmost derivation