구문 지시적 번역

구문 지시적 번역

- 각 생성 규칙에 해당하는 의미 수행 코드(semantic action code)를 직접 기술하여 필요한 일을 처리하는 방법

- 따라서, 문맥 자유 문법의 각 생성 규칙은 컴파일러에 속하는 변수 값 계산, 중간 코드 생성, 에러 메시지 출력, 기호표에 정보 삽입 등과 관련된 부 프로그램이나 의미 수행 코드로 구성되어 있음

- 즉, 구문 지시적 번역은 생성 규칙과 그에 해당하는 의미 규칙을 결합한 것

 

E -> E1 + E2 { E.VAL = E1.VAl + E2.VAL }

- 의미 규칙은 중괄호로 묶어서 표시하고 생성 규칙 뒤에 나타냄

- 의미 규칙에서 생성 규칙의 왼쪽 부분과 관련된 번역 E.VAL은 오른쪽 부분의 E와 관련된 번역 E.VAL과 E2.VAL을 더하여 구하는 것.. 앞에 생성 규칙에서 터미널 기호 +는 의미 규칙에 의해 수학적인 의미로 번역

 

구문 지시적 번역기의 구현

- 상당히 어려운데, 합성 속성만 가지고 구문 지시적 정의를 이용하여 쉽게 만들어보자

- 합성 속성은 입력이 구문 분석될 때 상향식으로 계산

- 감축이 발생할 때마다 감축되는 생성 규칙의 오른쪽 문법 기호에 대해 스택에 나타나는 속성을 가지고 새로운 합성 속성 값을 계산하는 것

- 상향식 구문 분석기는 구문 분석된 서브 트리에 대한 정보 저장을 위해 스택을 사용

 

구문 지시적 번역 방법과 주석 파스 트리를 이용하여 +, * 계산기 설계

S -> E$

E -> E1 + T

E -> T

T -> T1 * F

T -> F

F -> (E)

F -> digit

 

E, T, F -> E.VAL, T.VAL, F.VAL

digit -> LEXVAL

각 프로그램이 수행된 다음엔 새로운 스택의 탑이 NTOP

 

생성 규칙	의미 수행 코드
S -> E$	print VAL[TOP]
E -> E1 + T	VAL[NTOP] = VAL[TOP - 2] + VAL[TOP]
E -> T
T -> T1 * F	VAL[NTOP] = VAL[TOP-2] * VAL[TOP]
T -> F
F -> (E)	VAL[NTOP] = VAL[TOP-1]
F -> digit	VAL[NTOP] = LEXVAL

주의, +도 스택에 포함되니 TOP-2임

 

23 * 5 + 4$에 대한 구문 분석기 수행 과정

STATE는 파서 스택, VAL은 의미 스택, _는 값이 없는 토큰

상향식으로 감축

입력 기호	STATE	VAL	적용된 생성 규칙
23 * 5 + 4$
* 5 + 4$	23	23
* 5 + 4$	F	23	F -> digit
* 5 + 4$	T	23	T -> F
5 + 4$	T *	23 _
+ 4$	T * 5	23 _ 5	F -> digit
+ 4$	T * F	115	F -> digit
+ 4$	T	115	E -> T
+ 4$	E	115	E -> T
4$	E +	115 _
$	E + 4	115 _ 4
$	E + F	115 _ 4	F -> digit
$	E + T	115 _ 4	T -> F
$	E	119	E -> E + T
	E$	119 _
	S	119	S -> E$