04 Static Semantics

Static Semantics란

Static Semantics(정적 의미론)란 프로그램을 실행하지 않고도 검사할 수 있는 (=컴파일 타임에 확인되는) 의미적 규칙이다.

e.g. 변수의 선언 여부 확인, 변수의 타입 검사

Attribute Grammar란 속성(Attribute, 의미적 정보)를 구문 트리의 각 노드에 부여하고, 그 속성값을 계산하는 방법이다.

CFG 언어의 어떠한 특징들은 BNF로 표현하기 어려운 경우가 있다.
Attribute Grammar는 BNF만으로 표현하기 어려운 언어의 의미론적(semantic) 규칙을 보완한다.

• Attribute
  • associated with grammar symbols
  • 의미 정보 (변수의 타입, 선언 여부 등)
• Predicate Function
  • boolean expression on attribute set and literal attribute values
    Attribute 값이 유효한지 검사
  • Predicate function value for nonterminal should be true
    각 비터미널에 대해 정의된 Predicate 함수는 해당 구문 노드의 속상 값이 올바르게 계산되었음을 보장하기 위해 항상 true여야 함
• Attribute Computation Functions
  • associated with how attribute values are compute
  • Attribute 값을 계산해서 상위/하위 노드에 전달

Synthesized/Inherited Attributes

속성(Attribute)는 Synthesized Attribute와 Inherited Attribute로 나눌 수 있다.

속성 종류	설명	방향	예시
Synthesized Attribute (합성 속성)	자식 노드 → 부모 노드 (자식 노드들의 정보 “합성”)	Bottom-up	표현식의 결과 타입 계산
Inherited Attribute (상속 속성)	부모 노드 → 자식 노드	Top-down	변수의 기대 타입 전달

• A(X): 기호 X에 연결된 모든 속성들
• S(X): X의 합성 속성들
• I(X): X의 상속 속성들

아래와 같은 BNF에 대해

<stmt>     → <decl> | <assign>  
<decl>     → type id  
<assign>   → id = <expr>  
<expr>     → id | number

아래는 Synthesized Attribute의 예시다.

<expr> → id  
{ <expr>.type = lookup(id).type; }

<expr> → number  
{ <expr>.type = "int"; }

<expr>.type이라는 Synthesized Attribute를 만들고, 이 속성은 부모 노드로 전달되어 사용된다.

아래는 Inherited Attribute의 예시이다.

<assign> → id = <expr>;  
{ <expr>.expected_type = lookup(id).type; }

위에서 좌변 타입이 우변에 전달 된 후, <expr>.actual_type이 계산되어 비교될 것이다.
따라서 우변 <expr>이 어떤 타입이 되어야 할지를 부모가 알려주는 구조이다.

아래는 Predicate Function의 사용 예시이다.

<assign> → id = <expr>;
{ if (lookup(id).type ≠ <expr>.type)
    error("타입 불일치"); }

실제 코드로 보면

int x;
x = 123;

예시

Procedure 이름 일치 검사

Rule that name on the end should match with procedure’s name

BNF

<proc_def> → procedure <proc_name>[1] <proc_body> end <proc_name>[2];

BNF로 알 수 있는 것들

• “procedure” 키워드로 시작하고,
• 첫 번째 <proc_name>[1] (절차 이름)이 나오며,
• 절차 본문 <proc_body> 가 이어지고,
• “end” 키워드 뒤에 두 번째 <proc_name>[2] (절차 이름)가 나오며,
• 마지막에 세미콜론(;)으로 끝남.

마지막에 나오는 <proc_name>[2]는 처음에 나온 <proc_name>[1]과 반드시 동일해야 함.
Predicate을 통해 <proc_name>이 동일한지 확인할 수 있다.

Predicate: <proc_name>[1].string == <proc_name>[2].string

타입 규칙이 포함된 할당문 검사

How an attribute grammar can be used to check the type rules of a simple.

• 변수: A, B, C
• 타입: int, real
• 연산: +, -
• 규칙:
  • 피연산자 타입이 같으면 그대로
  • 다르면 real로 승격됨 (자동 형변환처럼)

BNF

<assign> → <var> = <expr>
<expr> → <var> + <var>
       | <var>  
<var> → A | B | C

1. Syntax rule: <assign> → <var> = <expr>
   Semantic rule: <expr>.expected_type ← <var>.actual_type
2. Syntax rule: <expr> → <var>[2] + <var>[3]
   Semantic rule: <expr>.actual_type ←
                    if (<var>[2].actual_type = int)
                    and (<var>[3].actual_type = int) 
	                    then int else real end if
   Predicate: <expr>.actual_type == <expr>.expected_type
3. Syntax rule: <expr> → <var>
   Semantic rule: <expr>.actual_type ← <var>.actual_type
   Predicate: <expr>.actual_type == <expr>.expected_type
4. Syntax rule: <var> → A | B | C
   Semantic rule: <var>.actual_type ← look-up(<var>.string)

The look-up function looks up a given variable name in the symbol table and returns the variable’s type.