PL3. Static semantic

1. Semantic

CFG, BNF만으로는 의미론적으로 문장이 올바른지 검사할 수 없다.

예를 들어 '프로그램 내에서 어떤 변수는 참조되기 전에 선언되어야한다' 라는 규칙은 BNF로 표현할 수 없다. 

 

syntax가 문장 구성 문법을 정의한다면 semantic은 문법이 의미론 적으로도 올바른지를 검사한다.

semantic을 기술하는 대표적인 두가지 방법이 있다. 

Static Semantic, Dynamic Semantic

 

2. Static Semantic : Attribute Grammar

Static Semantic은 compile time에 체크하는 semantic이다.

Attribute Grammar는 Static Semantic의 한 종류로써 BNF에 세가지(1,2,3) Semantic Rule을 더한 것이다.

따라서 AGs는 syntax와 semantic 둘 다를 검사한다.

CFG는 G = (S, N, T, P)로 나타냈었다. 

 

1. 여기에 각 symbol마다 속성이 부여된다. A(x)

그리고 그 속성들은 (parse tree로 표현 되었을 때) 자식 노드로 부터 결정되거나 synthesized attribute

부모 노드로 부터 결정 될 수도 있고 inherited attribute

스스로 (보통 리프노드)결정될 수도 있다. intrinsic attribute

 

2. 속성을 표현하는 함수 3. 속성 간의 관계(predicate)

 

3. Example(1) of AGs

<assign> -> <var> = <expr>
         -> <var> + <var> | <var>
<var> -> a l b | c

이 BNF에 type을 체크할 수 있는 AGs를 정의해보자.

각 토큰마다 두 가지 속성을 부여할 수 있다.

- actual_type : 자식 노드로부터 유추되는 synthesized attribute

- expected_type : 부모 노드로부터 유추되는 inherited attribute

 

그럼 semantic rule과 predicate를 정의해보자.

predicate은 반드시 true 여야 한다.

lookup은 var의 변수 이름을 받아서 type을 반환한다고 정의한 함수이다.

https://destiny738.tistory.com/171

이 semantic rule을 가지고 parse tree에서 타입 검사를 수행해보자.

그리고 타입 검사 시에 semantic rule에 해당하는 predicate가 반드시 참이여야 할 것이다.

타입이 자식에서 부모로 추론되면 bottom-up 방식으로 타입 검사가 이루어질 것이다.

 

3. Example(2) of AGs

<var> -> <id>
<id> -> a | b | c

 

- semantic rule : <var> actual_type<- lookup(<var>.string)

- lookup은 var의 변수 이름을 받아서 type을 반환한다고 정의한 함수이다.

- predicate : None