Attribute Grammars

BNF/EBNF (context free) 에는 한 가지 한계가 있다. 바로 변수 간의 타입 차이로 인한 오류 표현이 불가능하다는 것이다.

만약, 다른 데이터 타입 간의 산수 연산이 불가능한 언어가 있다고 가정하자.

int a;
float b;
int c;

c = a + b; // 에러 발생

a와 b의 데이터 타입이 다르기 때문에 c = a + b; 구문에서 에러를 띄워야 한다. 하지만 BNF/EBNF에서는 문법상 틀린 것이 없기 때문에 이를 에러로 처리하지 못한다. 이를 해결하기 위해 등장한 것이 바로 attribute grammars 이다.

따라서 AGs에는 문법에 속성 (attribute) 이 추가되었다.

• Synthesized attributes
  자식 노드로부터 자신의 속성을 결정받는다.

• Intrinsic attributes
  부모 노드로부터 자신의 속성을 결정받는다.

글로는 잘 이해가 되지 않으니 실제 문법을 보며 설명하도록 하겠다.

위의 구문을 전개하면 A = B + C가 된다.

1. B 와 C 의 데이터 타입이 다르면 B + C 의 결과는 실수로 지정한다.

2. B 와 C 의 데이터 타입이 같으면 B + C 의 결과는 B 와 C의 타입으로 지정한다.

3. A = B + C 에서 A와 B + C 의 데이터 타입이 같으면 구문을 실행하고, 아니면 에러를 띄운다.

위의 과정을 AGs로 작성하면 다음과 같다.

<expr>.expected_type <- var.actual_type (A)

<expr>.actual_type
<- if (<var>[1].actual_type = int) & &(<var>[2].actual_type = int) then int else real

expr = B + C
if (B == int && C == int) : expr = int
else : expr = real
위의 1, 2번 식을 표현한 것이다.

<expr>.expected_type == <expr>.actual_type

<expr>.expected_type = A의 데이터 타입
<expr>.actual_type = B + C 의 데이터 타입

위의 과정을 좀 더 이해하기 쉽게 parse tree로 그렸으니 참고하길 바란다.