Parser에서 재귀 함수의 역할

현재 컴파일러 관련된 어플을 제작 중이며, 컴파일러에서 재귀 함수의 사용이 제법 많은 빈도수를 찾지 함을 보게 됩니다.

그 역할에 관해서 짧게 언급을 할려고 합니다.

예1 - 

문법 1) string function1 ( int a , int b, int c ) 

 위의 문법 1 의 경우 간단히 보여드리면, 

<type> <id> '(' <params> ')' 로 상징화가 됩니다.

다시  <params> 속을 들여다 보게 되면, 

<params> := <type> <id> | <type> <id> , <params> 가 됩니다.

위의 문법을 간략히 설명 드리면, 

params 은 type 과 id로 변환이 될수도 있으며, 

type 과 id 과 콤마 그리고 params로 변환이 될수 있습니다.

class 로 간략히 변환을 하게 되면 이러 합니다.

class params {

string type;

string id;

class params;

}

 

이 Class를 이용하여 문법 1 안에 있는 <params>를 파싱하여 AST로 변환하는 과정에

사용되는 함수의 의사 코드는 이러 합니다.

(이미 모든 토큰 값들은 params's parent-child 관계로 저장이 되었다는 가정입니다)

function parser_params(params)

if(params.params != null )

 -> call parser_params(params.params)

 

else parse_type_id(params.type, params.id)

즉 위에서 함수의 파라미터인 int a , int b, int c 는 차례로 다음 child 노드(params)에 차곡 차곡 저장이 됩니다.

이럴 상황에서 재귀 함수는 마법 처럼 parsing 된 모든 값들을 차례로 저장하며 

elegant 하게 일을 처리 하게 됩니다.

구지 이것 뿐이 아니고 나중에 Source 생성시에서 Abstracted Syntax Tree에서 역시 재귀 함수의 역할이 빛을 바라게 됩니다.