토큰을 인식 하게 되었으므로 이제는 

문법을 인식하는 문법을 (마치 부트스트랩 같은.. 부팅을 위한 코드는 부팅영역 안에 있는것과 같은)

작성하고 이를 파싱하여 인식함은 물론이고

이를 원하는 형태의 결과물로 바꿔 얻어내야 한다.

어쨋든 문법을 작성하게 되면

이를 콘트롤 하기 쉬운 형태여야 하니

이를 2차원 배열로 생각한다.

형태는 다음과 같다.

A -> B 'b' ;

 A  B  'b'


0번 인덱스는 헤드 (논터미널) 이고 1번부터가 몸통이다.

하나의 논 터미널에 여러개의 생성규칙이 배정되는 경우 (Union 연산자에 의해)

는 다음과 같이 한다.

A -> A 'a' B | B ;

 A  A  'a'  B
 A  B    

즉 Union으로 묶여 있더라도 논터미널이 같아도 서로 다른 룰으로 생각하는 것이다.


그리고 각 토큰들은 스트링의 형태로 되어 있지만 

이 스트링 자체로 비교하고 각종 파서 제네레이터를 만들어 내기에는 굉장히 부담이 되는 알고리즘들이 많으므로

심볼 테이블을 유지하고 그 심볼 테이블의 인덱스 값을 ID 로 하여 유일한 식별자로 인지하게 한다.

다만 0 의 경우에는 특수한 값으로 써야 할 경우가 많으므로 인덱스는 1부터 시작하게 한다.

또 심볼테이블을 유지해야 하는 것은 

논터미널 말고도 터미널도 있으므로 심볼 테이블은 두개를 유지하며

터미널의 경우에는 음수의 값을 배정한다. (하지만 인덱스에 접근이 필요할 때는 양수로 바꾼다)




이렇게 두개의 심볼테이블을 만들고  문법 파일을 파싱을 하면서 심볼테이블이 식별 가능하게 id를 부여하며 넣으며

동시에 문법 파일이 문법에(문법 작성 룰) 맞게 작성되었는가 확인하면서 

문법 자체를 2차원 배열에다가 매핑을 시켜야 한다.

뭔가 전부 동시에 해야될것 같고  복잡해 보이지만  

이 또한 sl2p 프로그램 같은 것으로 LL 파서를 작성하면 아주 쉽게 된다.



문법을 인식하는 문법은 다음과 같다.

// gram은 epsilon 값도 지닌다. 
gram -> 'NON' 'PRO' body 'END' gram | ;

// body 는 Union에 의해 여러개가 올수 있다.
body -> sub body_ ;

body_ -> 'UNI' sub body_ | ;

// sub body 는 논터미널이나 터미널이 몇개든지 올 수 있다. 심지어 epsilon도 가능해야 한다.
sub -> 'NON' sub | 'TER' sub | ;


이를 sl2p 에 적용 시키고 나온 결과물을 약간 변형을 시킨다.



gram 에 보면 처음 논터미널인 것을 스캐너 function을 호출하여 얻어내게 된다.

이 시점에서 심볼테이블에 할당을 해보고 기존에 있다면 인덱스를 없다면 새로운 인덱스를 얻어내게 된다.


body 가 호출 되는 시점에서  rule 배열에 넣어야 할 것을 알고 있다. 

이 시점에서는 body가 몇개나 나올지 모르기 때문에 gram 에서 논터미널의 값을 상속받아 0번 인덱스 (헤드) 에 넣게 된다.

이는 body_ 도 마찬가지 이다.

어차피 LL 조건을 만족시키려 쪼갠 것이기 때문에 body 가 오면 그냥 헤드를 넣는다.


sub에서는  터미널이냐 논 터미널이냐에 따라서 심볼테이블에 할당후 인덱스를 얻어내고 바로 rule 배열에 집어 넣는다.


따지고 보면 굉장히 단순한 일들을 한다.

gram 에서 논터미널의 값을 알아낸다.

body 에서 gram에서 넘겨받은 헤드를 rule배열의 0번에 넣는다.

sub 에서는 rule 에 계속 넣는다.

이 일들을 계속 반복하게 되면 위 그림과 같이 심볼테이블들과 rule 배열을 얻게 된다.

하나하나는 단순한 역할이지만 이것이 연계되면 복잡해 보이는 일을 하게 되는 것이다.

단순히 텍스트를 한번 선형으로 스캔하는 것만으로도 말이다. 


밑은 rule 과 심볼테이블에 관련된 함수이다.

전부 전역 변수이다.... ㅡㅡ ;; 


밑은 rule 과 관련된 함수와 전역변수들이다.

밑은 심볼테이블과 관련된 함수와 전역변수들이다.
Posted by 멍충한아싸

댓글을 달아 주세요

  1. 요즘 아주 공부가 재미있나 보다능. ㅊㅋㅊㅋ

    2011.01.11 19:43 [ ADDR : EDIT/ DEL : REPLY ]