재귀 함수 활용 변수 선언문 처리 1.

안녕하세요.

Geeks_Company 입니다.

최근 혼자서 하는 작업중 하나가 컴파일러 관련 부분인데요

재귀 함수를 사용하여서 문법에 맞게 파싱하는 방식에 관해서 적어 볼까 합니다.

예제 문법

==================================================

stmts = stmt stmts | stmt NULL ; 

stmt = variable_decl ';' ; 

variable_decl = 'var' id '=' value; 

id = char+ ;

value = digit+ | string+ | '"' string+ '"' ;

==================================================

위의 문법을 간략한 의사 코드로 바꾸면 이러합니다.

function stmts parse(input)

 if(token=="var") parse_variable_decl() -> stmts.stmt;

 else throw "error"; 

 if(token == ";") "accept"; 

 else "error";

 if(hasMoreToken) parse -> stmts.stmts; 

 else stmts.stmts=null;

 

 return stmts;

==================================================

그럼 이제 입력된 값을 토대로 문법 적용 되는걸 보겠습니다.

입력 : var a=123; 

stmts 

=> stmt stmts 

=> variable_decl ';' stmts 

=> 'var' id '=' value ';' stmts 

=> 'var' id '=' value ';' stmts

=> 'var' id '=' value ';' NULL

=> Accept;

입력 : var a=123; var b=test; var c="testttt";

stmts 

=> stmt stmts 

=> variable_decl ';' stmts 

=> 'var' id '=' value ';' stmts 

=> 'var' id '=' value ';' stmts

=> 'var' id '=' value ';' stmt stmts

=> 'var' id '=' value ';' variable_decl ';' stmts

=> 'var' id '=' value ';' 'var' id '=' value ';' stmts

=> 'var' id '=' value ';' 'var' id '=' value ';' stmt stmts

=> 'var' id '=' value ';' 'var' id '=' value ';' variable_decl ';'  stmts

=> 'var' id '=' value ';' 'var' id '=' value ';' 'var' id '=' value ';' stmts

=> 'var' id '=' value ';' 'var' id '=' value ';' 'var' id '=' value ';' NULL

=> Accept; 

===================================================

보시면 아시겠지만, 

일반적인 재귀 함수를 사용하여 처리 할수 있는 반복문으로 보시면 됩니다.

간략한 반복문 구조를 보여드리겠습니다.

1 2 abstract public class stmt { } 3 public class vardecl : stmt 4 { 5 public string id { get; set; } 6 public object value { get; set; } 7 } 8 public class stmts 9 { 10 public stmt mstmt { get; set; } 11 public stmts mstmts { get; set; } 12 } 13 14 15 public stmts parse() 16 { 17 stmts stmts = new stmts(); 18 19 // 변수 선언 문의 경우 값을 할당. 20 if (result[idx++].Equals("var")) 21 { 22 vardecl vardecl = new vardecl(); 23 // ...값을 vardecl에 맞게 입력 하는 부분... 24 stmts.mstmt = vardecl; 25 } 26 27 // 마지막 부분이 세미콜론 확인. 28 if (result[idx++].Equals(this.Semi)) 29 { 30 Console.WriteLine("문법에 맞게 처리되었습니다"); ; 31 } 32 else throw new System.Exception(Semi.ToString() + " required"); 33 34 // 토큰이 더 있으면 , 재귀 함수 호출로 재 파싱. 아니면 null값 넣은 후 종료. 35 if (idx < result.Count) 36 stmts.mstmts = parse(); 37 else stmts.mstmts = null; 38 39 return stmts; 40 } 


위의 빨간 35-37 줄이 반복문을 활용하여 구문을 파싱하는 핵심 부분입니다.

var a=123; 을 입력 하여 구문 분석 후 값을 저장할때 출력된 값.

var a=123; var b=test; var c="testttt"; 을 입력 하여 구문 분석 후 값을 저장할때 출력된 값.

var a=123; var b="ccc" ( 로 문법에 맞지 않게 처리 할 경우 나오는 값. System.Object는 각 Token의 저장된 값 형태 입니다.