[Compiler] 13. Semantic analyzer

Semantic analyzer (의미분석)

- 프로그램의 semantics은 "meaning" 이다.

- 구문적으론 올바르지만 의미상 틀린 것

- 일치하지 않는 Type, 선언되지 않은 변수 사용, 잘못된 인수로 호출된 함수, access 위반 등 확인

 

- syntax tree에 주석 달기
  -> type 정보(attribute) 포함

- tree의 할당이 적절한지 확인

ex) integer가 맞는가?

- 프로그램의 syntactic 구조를 알면, 컴파일에 필요한 추가 정보를 계산한다.

- 언어의 의미를 지정하기 위해 사용되는 표준 방법은 없다. -> 알고리즘은 parsing 알고리즘만큼 명확하게 표현되지 않는다.

 

Attribute and binding

- Attribute

• 프로그래밍 언어 구조의 모든 속성
• Ex
  • 변수의 데이터 타입
  • 표현식의 값
  • 메모리에서 변수의 위치 등

- Binding

• attribute를 계산하고, 계산된 값을 연결하는 프로세스
• attribute마다 binding time이 다르다.
  ex) static binding, dynamic binding

- C || Pascal에서 Type checker들이 semantic analyzer에 속하는 것이다.

• data type이 정의된 모든 언어 entity의 data type attribute를 계산하고 확인한다.

 

Attribute grammar

- Context-free grammars(CFGs)는 모든 프로그래밍 언어의 syntax와 semantic을 묘사할 수 없다.

- parse tree를 따라 일부 semantic 정보를 전달하기 위한 CFG 추가

- CFG가 주어졌을 때, rule에 속성을 부착해 parsing하는 동시에 semantic analyzer를 확인하는 방법을 Syntax-directed semantics라고 한다.

- attribute grammar는 다음을 따르는 context-free grammar G = (S, N, T, P)이다.

• 각 grammar symbol은 attribute를 갖는다.
• 각 rule은 function을 갖는다.
• fuction을 통해 attribute값을 세팅하거나, semantic이 맞는지 확인한다.

- syntax-directed semantics : CFG rule들에 attribute를 부착한 것.

• attribute : a1, ..., ak 가 있다고 가정
• rule : X0 -> X1...Xn 이 있다고 가정
• Xi · ai = f_ij(X0 · a1, ..., X0 · ak, ..., Xn · a1, ..., Xn · ak)
  -> i번째 symbol에 j번째 속성 결정은 f_ij(X0 · a1, ..., Xn · ak)로 결정한다.

 

Example of attribute grammar(1)

- unsigned number

- rule

• number -> number digit | digit
• digit -> 0 | 1 | 2 | ... | 9

숫자의 기본적인 속성은 value이다.

만약 number가 "number -> digit"로 유도된다면, number는 하나의 digit을 포함한다. -> numver.val = digit.val

Grammar rule	Semantic rules
number1 -> number2 digit	number1·val = number2·val * 10 + digit.val
number -> digit	number.val = digit.val
digit -> 0	digit.val = 0
...	...

↓

Parse tree showing attribute computation

ex) 345 (left derivation)

 

Example of attribute grammar (2)

C와 같은 syntax에서 변수 선언 문법

ex) float x, y

• rule
• decl -> type var-list
• type -> int | float
• var-list -> id, var-list | id

Grammar rule	Semantic rules
decl -> type var-list	var-list.dtype = type.dtype
type -> int	type.dtype = integer
type -> float	type.dtype = real
var-list1 -> id, var-list2	id.dtype = var-list1 · dtype var-list2 · dtype = var-list1 · dtype
var-list -> id	id.dtype = var-list.dtype

 

Attribute grammars : Definition

- Synthesized attributes (합성 속성)

• bottom -> top
• child에서 parent로 올라오며 속성이 결정된다.
• 함수 형식 : S(X0) = f( A(X1), ..., A(Xn) )

- Inherited attributes (상속 속성)

• top -> bottom
• 합성속성 이외의 것들은 다 상속 속성
• 앞의 2번 예제와 같은 것들이 상속 속성
• 함수 형식 : I(Xj) = f( A(X0), ..., A(Xn)), i <= j <= n

- intrinsic attribute : leaf 노드 스스로 무언가의 속성을 가진 것

 

Attribute grammars : Example

- Syntax

• <assign> -> <var> = <expr>
• <expr> -> <var> + <var> | <var>
• <var> -> A | B | C

- actual_type

• 갖는 값
• synthesized for <var> and <expr>

- expected_type

• 기대하는 값
• inherited for <expr>

 

Attribute grammar

attribute 값은 어떻게 계산되나?

- 모든 속성이 inherited라면, tree는 top-down으로 계산된다.

- 모든 속성이 synthesized라면, tree는 bottom-up으로 계산된다.