[Compiler] FA : Finite Automata 와 ambiguity

본 내용은 아래의 출처에서 본것이고 허락을 맡고 포스트한다.

 

출처 : https://talkingaboutme.tistory.com/category/About%20Study/Compiler  

 

Lexical Analyis에 대해 알아보고 정규 표현을 통해 코드상의 string을 뽑는 것을 알아보았다.

 

코드상에는 string뿐만 아니라, alphabet, keword 등 많은 요소들로 구성되어 있다. 이를 정규 표현식 방법으로 적용해 코드상에서 뽑아낼 수 있는 단어는 위의 요소들 중 하나이고 각각 정규 표현의 Union에는 포함되어 있을 것.

Regulat Expression L(R) = L(keyword) | L(number) | L(identifier) | L(operator) | ....

 

예를 들어, else라는 단어를 위의 Union(합집합) 으로 찾으면 else의 e를 찾고 다음에 e를 삭제하고 l을 찾고.... 이 과정을 반복할 것이다. 그러다 특정 patter속에 else가 나타내는 의미가 정의된 부분을 찾고 이를 parse할 수 있도록 넘겨주게 될 것이다. 

 

하지만, elsewhere를 생각해보자. 여기서 모호성(ambiguity)가 발생한다. else를 찾는 과정은 같고 where를 어떻게 처리하느냐가 문제이다. 

elsewhere 라는 단어를 찾을때, 모호성이 발생
- else를 찾는 과정은 문자 하나하나 판별하여 분석, 뒤의 where가 조건문의 keyword인가, identifier인가 모호성 발생

 

다른 예시

identifier vs identifier  : tmp / tmp1
kwyword vs identifier : else / elsewhere
operator vs operator : = / ==

 

Lexical Analysis(어휘 분석)의 알고리즘에서 이런 모호성을 해결하는 규칙이 있다.

 

maximal munch / longest match : 분석을 끝까지 최대한 해보는 것, else를 찾았다고 parse하는것이 아니라 끝까지 감, elsewhere가 키워드가 아니라면 그냥 identifier로 구분

Priority Ordering : 우선순위를 두어 가장 ordering이 높은 Expression에 의미를 부여하는 것

else라는 단어를 찾고나면 분석하면서 가장 높은 ordering에 Expression 의미를 부여한다.

 

여기서는Lexical Analysis(어휘 분석) 알고리즘에서 모호성을 해결하는 게 있구나 정도만을 알자

 

위와 같은 몇가지 방법이 있지만, 컴파일러가 해당하지 않는 구문이 있다면 쉽게 인지하지 못한다. '@$23_djhf' 같은 string을 변수로 삽입하지 못하고 에러를 출력할 것이다. 

 

여기까지 Lexeme을 분리하고 처리하는 방식을 살펴보았다. 이를 처리하기 위해 구현을 하는것은 쉽지 않은 일이다.

하지만, 이것을 이해하기 위한 기본적인 전제는 모든 String이 Finite 하다는 것이다.  

어떤 patter을 사전에 정의하고 기계의 힘으로 분석하면 기기의 컴파일러는 state에 따라서 string을 추출할 수 있다. 

하나하나 case를 나눌 필요가 없다는 뜩이다. 이런 방식을 FA : Finite (state) Automata 라고 한다.

 

이 FA의 수행방식에 따라 DFA와 NFA로 나눌수 있다.

 

정리하면, FA는 특정 문구를 뽑아내기 위한 Regular Expression이 나오면, 이를 Finite State 형태로 구현하는 것이 

Finite Automata이다.