알고리즘2011. 8. 7. 14:21


하향식 파싱은  재귀 하강 파싱 방법으로 LL 계열이다.

흔히 이 파싱의 문제점은

Strong일 경우 
 '|' 으로 인해서 Body 가 여러개로 나누어질 경우 
반드시 Body 의 맨앞에는 Terminal이 와야 하며 
Tail Recursion 형태일 경우 반드시 무한 재귀호출을 탈출하기 위한
Epsilon body 가 존재하여야만 한다.

 
하지만 하향식 연산자 우선순위 기법은 이러한 재귀 하강 방식과  연산자 우선순위 구문 기법을 결합한 하나의 파싱 기법
이다.

이러한 기법은 동적인 함수형 언어에서 사용될 때 가장 효과적이다.




bp (Binding Power) 

결속력이라고 한다.

d A e B f
# A, B: 연산자

(d A e) B f
d A (e B f)
# e 는 어떤 연산자에 결속 되는가? 


파싱은 이러한 모호성을 어떻게 해결하는가가 핵심이다.

TDOP 알고리즘은 bp 와

nud (Null Denotation) : 결속 없음 , 값 (atom) 과 전위(prefix) 연산자에 쓰인다.
led (Left Denotation) :  왼쪽으로 결속, 중위 연산자 (infix) 와 후위 (suffix) 연산자에 쓰인다.

각 토큰은 위 세개의 멤버를 지니게 되지만 반드시 두개를 가질 필요는 없다. 

(실은 nud, led 두개의 메서드를 지닌 최 상위 클래스를 선언한뒤 이를 상속받아 오버라이딩 한다.
이유는 슈퍼클래스에서 nud, led 메서드는 무조건 예외를 발생시키고 실제로 메서드를 가져야할 토
큰에 대해서만 오버라이딩 하게 되면 간결하고 깔끔해진다. OOP의 힘이다)





TDOP (Top Down Operator Precedence) algorithm

먼저 Expression 의 형태이다.
  

 먼저 값을 요구하고

오른쪽 결속력이 왼쪽보다 더 커질 때까지 led 메서드를 호출하게 된다.

이러한 과정은 재귀적으로 반복될 수 있는데  nud 나 led 메서드가 내부적으로 다시 Expression을 호출 가능하기 때문이다.


다음은 Token들의 형태이다.



 이는 동적 타입 언어인 python이니까 가능한 것이고 , 실제로 강타입 언어 같은 경우는 

예를 들어 자바 같은 경우는 슈퍼클래스로 token을 선언한뒤, 세개의 메서드를 선언하고  이를 상속받아

오버라이딩 하는 형태로 작성하면 될 것이다. 

연산자 토큰에 진입하였어도 우선 결합시키지 않고 다시 expression 을 재 호출하는것을 볼 수 있다.

이는 우선 두고 보는것과 마찬가지 이다.


다음은 간단한 Tokenizer 와  파스 메서드인다.

 

파스를 하면서 바로 계산하는 형태이나,

좀 복잡한 언어 구문을 파싱할 경우 AST를 동시에 형성하는 것이 낫겠다.




이 외에
 

전위 연산자의 경우는  오른쪽으로 결합한다

ex)  -1
# '-'  -> '1'  , -심볼은 1 과 연결

 왼쪽으로 묶이지 않으므로 왼쪽 결속력이 없다. ( nud 만 존재)

한편 전위연산자의 경우는 예약어 일 수도 있다.!! 




배정 연산자(=, +=, -=, *= ....)의 경우는 l-value 때문에 추가적인 연산이 필요하다.

따라서 새로운 함수를 만들고 이를 내포시켜 작성한다.

이개념은 함수형 언어의 Lambda 개념이다.



상수의 경우 심볼테이블이 준비되어 있는 경우 

해당 심볼테이블에 저장된 실제 리터럴 토큰으로 변환한다.

왼쪽 결속력이 없다.



문장 (Statement) 의 경우 모든것이 표현식인 함수형 언어에서는 굳이 필요가 없지만

대부분 주류 언어는 Statement (if-else 문, while 문, for문, Compound 문 , return 문....) 를 가지게 되므로 

토큰에 std (Statement) 메서드를 추가함으로서 쉽게 적용 가능하다.




이 외에도

함수, 배열, 객체, 클래스 ... 등등등

응용하기 나름이다. 
Posted by 멍충한아싸

댓글을 달아 주세요