파서트리

파서 트리

   파싱을 목적으로 하는 트리

파싱

   원본을 목적에 맞게 변환하는 작업

   A포맷으로 되어 있는 원본을 B포맷으로 변환하는 작업

 

예) 수식 파서 트리(피 연산자는 음이 아닌 정수, 연산자는 사칙연산에 한한다고 하자.)

  

먼저 중위 표기에 해당하는 정규식을 만들어보자.

Numeric Expression!: <operand><mid - expression!>0

mid -expression!: <operator><operand>

operator: <+>|<->|<*>|</>

operand: <number_char>*

number_char:<0>|<1>|...|<9>

 

위 첨자가 작성이 안되어서 다음과 같이 약속한다.

참고 <a>* : a가 1번 이상 반복된다.

       <a>0 :  a가 0번 이상 반복된다.

 

수식 파서 트리를 만들기 위해서

1. 원본을 입력받는다.

2. 토큰을 생성한다.(Lexical) :잘못된 토큰이 있으면 멈춤다.

    ==> 원본에 모든 요소가 operand 혹은 operator로 구분할 수 있는지 판단하여 구분한다.

3. 문법을 체크한다.(Syntax): 문법과 다른 형태로 토큰이 나열되어 있으면 멈춘다.

   ==> 토큰 배열의 요소가 Numeric Expression! 문법에 맞는지 확인하다.

4.후위 운행한다.