[컴파일러] - Semantices

What do we need to know to compile this?

Beyond Syntax

• CFG는 프로그래밍 언어의 구문 구조를 정의하는 데 사용되지만, 언어의 모든 의미론적 측면(Semantic aspect)을 포착하지는 못한다.
• CFG는 토큰과 그들의 조합으로 구문을 정의하지만, 변수의 선언, 타입 일관성, 표현식의 유효성, 메서드 호출의 적절성 등과 같은 의미론적 규칙은 포함하지 않는다.
• 이러한 의미론적 규칙은 컴파일러나 인터프리터가 소스 코드를 분석하고 실행 가능한 프로그램을 생성하는 데 필수적임
• 의미론적 규칙의 예:
  1. 변수 선언 확인:
     • 프로그램에서 사용되는 모든 변수가 선언되었는지 확인
  2. 표현식 내 타입 일관성:
     • 연산자와 피연산자 간의 타입이 적절히 일치하는지 검사
  3. 할당 가능성 검사:
     • x = y와 같은 할당문에서 y의 타입이 x에 할당 가능한 타입인지 확인
  4. 메서드 호출의 파라미터 검사:
     • 메서드 호출 시 제공되는 인자의 수와 타입이 메서드 정의와 일치하는지 확인
  5. 클래스 인스턴스의 멤버 접근 검사:
     • p.q와 같은 선택자(selector)에서 q가 클래스 인스턴스 p의 메서드나 필드인지 확인
  6. 변수 초기화 검사:
     • 변수가 사용되기 전에 반드시 초기화되었는지 검증
  7. 널 참조(null reference) 검사:
     • p.q 실행 시 p가 널(null)이 아닌지 검사하여 런타임 오류를 방지

Code를 생성하기 위해 알아야 할 것들은?

1. 객체 내 필드 할당 위치:
   • 객체의 각 필드가 메모리 내에서 어디에 할당되는지 결정해야함
   • 이는 객체 내부의 데이터 레이아웃을 정의하는 것을 포함한다.
2. 객체의 크기:
   • 객체가 차지하는 메모리의 크기를 결정해야 합니다.
   • 이는 new와 같은 객체 생성 연산자에 의해 할당되는 저장 공간의 크기를 결정하는 데 필요하다.
3. 메서드 호출 시 지역 변수 저장 위치:
   • 메서드가 호출될 때, 지역 변수들이 스택이나 레지스터 등에 어떻게 저장되는지 결정해야 한다.
   • 이는 메서드의 호출 규약과 밀접하게 관련있다.
4. 객체/클래스와 연관된 메서드:
   • 특정 객체 또는 클래스에 어떤 메서드들이 연관되어 있는지 결정해야 한다.
   • 이는 클래스의 메서드 테이블이나 가상 메서드 테이블을 생성하는 것을 포함할 수 있음
5. 런타임 시 메서드 호출 결정:
   • 객체의 런타임 타입에 기반하여 어떤 메서드를 호출할지 결정하는 메커니즘을 구현해야 한다.
   • 이는 다형성을 지원하는 언어에서 특히 중요하며, 가상 메서드 테이블(virtual method table)을 사용하여 구현될 수 있다.

Types

• 프로그래밍 언어에서 type의 고전적인 역할
  • Run-time safety
  • compile-time error detection
  • Improved expressiveness (method or operator overloading, for exampl)
  • Provide information to optimizer

Semantic Analysis

• Main tasks:
  • 프로그램으로부터 type과 다른 정보를 추출
  • CFG를 넘어 language rule 확인
• key data Structures: symbol tables
  • 프로그램에서 각 identifier에 대해서 그것의 attributes(kind, type, etc.)를 기록

Semantic Information의 몇가지 종류

Semantic Checks

• 프로그램이 해당 언어의 의미론적 규칙과 제약 조건을 준수하고 있는지 확인하는 과정
  • 어떤 semantic 규칙이 check 되어야 하는지
    • 각 언어 구조(변수 선언, 표현식, 함수 호출 등)에 대해 어떤 의미론적 규칙을 검사해야 하는지를 정의
  • 표현식의 type 결정
    • 각 표현식에 대해 그 타입을 결정하고, 현재 컨텍스트에서 표현식의 사용이 적법한지 확인
    • 예를 들어, 정수 타입의 변수에 문자열을 할당하는 것은 타입 오류를 발생
  • 선언에 필요한 정보 캡처:
    • 변수, 함수, 클래스 등의 선언에 대한 중요 정보를 수집하고 저장한다. 이 정보는 프로그램의 다른 부분에서 참조될 수 있음
    • 심볼 테이블(Symbol Table)이 이 정보를 저장하는 데 사용되며, 각 식별자의 타입, 범위, 선언 위치 등의 정보를 포함한다.

A Sampling of Semantic Checks

• Name: id
  • id는 그것의 범위 안에서 선언 되어있는지
  • id의 추론된 타입은 그것의 선언된 타입인지
• Constant: v
  • 추론된 타입인지
  • 값이 명시적인지
• Binary operator: exp1 op exp2
  • exp1과 exp2는 호환가능한 types을 가지고 있는지
    • Identical, or
    • 적절한 유형으로 잘 변환됬는지
      • ex) 2.0 + 1 → 결과를 float할지 int할지는 설계자 마음
  • 추론된 type은 operator, operands의 타입이여한다.
• Assignment: exp1 = exp2
  • exp1은 assignable해야한다.
  • exp1과 exp2는 호환가능한 타입을 가지고 있다.
    • Identical, or
    • exp2는 exp1로 변환되거나 exp2의 타입은 exp1의 subtype일 수 있다.
  • 추론된 타입은 exp1의 타입이다
• Cast: (exp1)exp2
  • exp1은 타입이다
  • exp2 either
    • exp1과 같은 타입을 가진다
    • exp1의 타입으로 변환될 수 있다
    • exp1의 서브클래스
  • 추론된 타입은 exp1이다
• Field reference exp.f
  • exp는 참조 타입이다.(class instance)
  • exp의 클래스는 f라는 이름의 필드를 갖고있다.
  • 추론된 타입은 선언된 f의 타입이다.
• Method call exp.m(e1, e2, …, en)
  • exp는 참조 타입이다.(class instance)
  • exp의 클래스는 m이라고 명명된 method를 갖고있다.
  • method 함수는 n개의 parameters를 갖고있다
  • 각 argument 타입과 파라미터 타입이 일치한다.
  • 추론된 타입은 method 선언에 의해 주어진다.
• Return statement (return exp; return;)
  • exp가 반환된 타입으로 선언된 타입인지 확인한다.
  • expression이 올 수 없다.

Semantic Analysis

• 의미 분석(Semantic Analysis)은 구문 분석(Syntax Analysis) 단계 이후에 수행되는 컴파일 과정의 핵심 단계 중 하나
• 파서는 AST를 만든다
• semantic information을 추출하고 constraints(제약)를 확인할 필요가 있다.
  • AST를 기반으로 프로그램의 의미론적 정보를 추출하고 언어의 규칙(예: 타입 체크, 변수의 올바른 사용 등)을 검사한다.
  • 이 과정에서 식별자의 유효성, 타입 호환성, 올바른 메서드 호출 등을 확인
• 정보는 symbol tables 안에 저장되어있다.
  • 심볼 테이블은 의미 분석 과정에서 생성되며, 이후 컴파일 단계에서도 참조된다.

Attribute Grammers

• 의미 분석을 체계적으로 접근하는 방법으로, 컴파일러 설계에서 중요한 도구 중 하나이다.
• 속성 문법은 때때로 컴파일러 구현에 직접 사용
• syntax tree에 있는 각 노드들에 속성을 추가한다.
• attributes의 예
  • 타입정보
  • Assignable(e.g., expression vs variable - lvalue vs rvalue)
  • Value
  • etc..
• Notation: X.a ← 만약 a가 노드 X의 속성일 경우

Attribute Example

• 각 노드는 .val이라는 속성을 갖고 있다고 가정하자
• (1+2) * (6/2)에 대한 AST와 attribution
• 

Inherited and Synthesized Attributes

• Production이 주어져있다. $X::=Y_1Y_2...Y_n$
  • A synthesized attribute: X의 합성된 속성 X.a 는 $Y_i$의 attributes들(bottom up)
  • An inherited attribute: $Y_i.b$는 X의 속성 X.a 및 다른 $Y_j$의 속성 $Y_j.c$를 기반으로 계산(top down) - synthesized를 제외하고 생각하면 쉽다.

Informal Example of Attribute Rule

• 간단한 산수 언어의 Attributes
• Grammar
• program::= decl stmt decl::= int id; stmt::= exp = exp; exp::= id | exp+exp | 1
• Attributes - semantic check 하는 3가지
  • env(environment, e.g., symbol table); decl에 의해 합성된다, stmt에 의해 합성된다
  • type(expression type); 합성된다
  • kind(variable [lvalue] vs value [rvalue]); 합성된다

Attributes for Declarations

• decl ::= int id;
  • decl.env - {identifier, int, var}
    • $\sigma_1 = {id \longmapsto(int, var)}$
      
      35-bfdf-44f2-b82d-76aea097ff8f/e30b4d5e-cb80-4d1d-80bd-06ff31c744e5/Untitled.png)

Attributes for Program

• Program ::= decl stmt
  • stmt.env = decl.env
  • 

Attributes for Constants

• exp ::= 1
  • exp.kind = val (1은 상수라서 val)
  • exp.type = int
  • 

Attributes for Expressions

• exp ::= id
  • id = exp.env.lookup(id)
  • exp.type = id.type
  • exp.kind = id.kind
  • 

Attributes for Addition

• exp ::= exp1 + exp2
  • exp1.env = exp.env
  • exp2.env = exp.env
  • error if exp1.type ≠ exp2.type
    • (or error if not combatable if rules are move complex)
  • exp.type = exp1.type
  • exp.kind = val
  • 

Attribute Rules for Assignment

• stmt :: = exp1 = exp2;
  • exp1.env = stmt.env
  • exp2.env = stmt.env
  • Error if exp2.type is not assignment compatibile with exp1.type
  • error if exp1.jind == val(must be var)
  • 

Example

• int x; x = x + 1;
  • symbol table: $\sigma_1 = {x \longmapsto(int, var)}$
  •