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을 반환한다고 정의한 함수이다.
이 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
'ComputerScience > Principle of programing language' 카테고리의 다른 글
PL6. Syntax Analysis - top down parsing (0) | 2023.10.06 |
---|---|
PL5. Dynamic semantics : Axiomatic (0) | 2023.10.04 |
PL4. Dynamic semantics : Operational, Denotational (0) | 2023.09.27 |
PL2. Syntax (0) | 2023.09.14 |
PL1. Programming Languages? (0) | 2023.09.14 |